WO2003105392A1

WO2003105392A1 - Methods for use with timeslot identifiers in a timeslot-based protocol and apparatus

Info

Publication number: WO2003105392A1
Application number: PCT/EP2003/005073
Authority: WO
Inventors: Florian Bogenberger; Mathias Rausch
Original assignee: Motorola Inc
Priority date: 2002-06-06
Filing date: 2003-05-12
Publication date: 2003-12-18
Also published as: AU2003240643A1; GB0212978D0; GB2389492A

Abstract

A system (100) transmitter (200) receiver (300) and methods for use with timeslot identifiers in a timeslot-based protocol. A message identifier (ID-t) which marks the (mini) slot number is encoded with a cyclic redundancy value (CRC) into a message's error detection code in a way that can be easily inverted by the message receiver without loss of a CRC's hamming distance, which leads to the benefits of reduction of the control information in the transmitted data (reduction of overhead); and saving of bandwidth in serial data transmission.

Description

METHODS FOR USE WITH TIMESLOT INDENTIFIERS IN A TIMESLOT-BASED PROTOCOL AND

APPARATUS

Field of the Invention

This invention relates to sequential data transmission protocols, and particularly (though not exclusively) to such protocols in automotive applications.

10

Background of the Invention

In the field of this invention it is known that serial 15 communication protocols transmit data in frames. It is known, in order to verify that the frame was transmitted in the correct slot, that every frame has an identifier (ID) . However, in protocols with time triggered media access the identification information is redundant 20 (correct reception being ensured by use of a specific time slot) .

TTP/C is a known time triggered protocol but it does not use a minislotting scheme. Moreover TTP/C (in 25 versions 0.5 and earlier) does not support reconstruction of the ID used in the transmitter, nor can it distinguish transmission errors from a different ID in the receiver and transmitter.

30 Minislotting is a known scheme utilizing minislots

(unutilized slot cycles, shorter than a slot in which data is sent, each minislot being longer than the system propagation delay) , each node being assigned a unique number of minislots that must elapse, with silence on channel, before it may transmit.

The known 'byteflight' protocol uses minislotting as a bus access method, but transmits the ID on the communication medium and therefore has a higher overhead which results in reduced communication bandwidth.

Therefore, these approaches have the disadvantages that ^λbyteflight' needs additional bandwidth to transmit the IDs, and ^λTTP' is not able to reconstruct IDs in case of an error .

A need therefore exists for a scheme allowing reconstruction of frame IDs in a time triggered protocol wherein the abovementioned disadvantages may be alleviated.

Statement of Invention

In accordance with a first aspect of the present invention there is provided a communication system for use of timeslot identifiers in a timeslot-based protocol as claimed in claim 1.

In accordance with a second aspect of the present invention there is provided a transmitter for use in a communication system using timeslot identifiers in a timeslot-based protocol as claimed in claim 6.

In accordance with a third aspect of the present invention there is provided a receiver for use in a communication system using timeslot identifiers in a timeslot-based protocol as claimed in claim 11.

In accordance with a fourth aspect of the present invention there is provided a method for use in a communication system using timeslot identifiers in a timeslot-based protocol as claimed in claim 16.

In accordance with a fifth aspect of the present invention there is provided a method for a transmitter for use in a communication system for using timeslot identifiers in a timeslot-based protocol as claimed in claim 21.

In accordance with a sixth aspect of the present invention there is provided a method for a receiver for use in a communication system using timeslot identifiers in a timeslot-based protocol as claimed in claim 26.

Brief Description of the Drawings

One scheme for reconstruction of frame IDs in a minislotting protocol incorporating the present invention will now be described, by way of example only, with reference to the accompanying drawings, in which: FIG. 1 shows a block schematic diagram of an automotive communication system using a frame-based sequential data transmission protocol employing a microslotting scheme in which the present invention is used;

FIG. 2 shows a block schematic diagram showing steps performed in the communication system of FIG. 1.

Description of Preferred Embodiment

Stated briefly, the present invention, at least in a preferred embodiment, encodes a message identifier which marks the slot number into a message's error detection code in a way that can be easily inverted by the message receiver without loss of a CRC's hamming distance, which leads to the benefit of increasing the transmission bandwidth for serial protocols using time slots and message identifiers.

The known 'byteflight' protocol, as well as the known ^λ FlexRay' protocol currently under development, uses a (mini) slotting scheme to transmit data in the format of frames . Each frame contains an identifier of 12 bits which is used by the transmitter to detect in which slot (time windows where the frame is transmitted) or after which minislot (short time windows where no frame is transmitted) the frame is to be transmitted (e.g., ID=3 means that the frame will be transmitted in the 3rd slot or after the 3rd minislot) . The receiver uses this ID to calculate the address of the message buffer to store the received frame as well as detecting mismatches between ID and the (mini) slot (timing error recognition) . A CRC (Cyclic Redundancy Check value, e.g., of 24 bits) is used to check for transmission errors due to bit corruption. 'FlexRay' has a dynamic part using minislotting and a static part using normal slots, whereas byteflight' only has a dynamic part using minislotting.

Problems occur with these known protocols as follows: a) Transmitting the ID occupies transmission bandwidth, especially because ^λbyteflight' (and 'FlexRay') have relatively short frames with 0-12 data bytes, 4 bits length field, 1 MUX bit, reserved bits (and in

^ΛFlexRay': 0-246 data bytes, 7 bits length field, no MUX bit, 2 reserved bits, sync bit, a header CRC of 11 bits, and a data update bit) . b) TTP/C V0.5 appends a type of ID (called "MEDL position" in ^XTTP' ) to the data to calculate the CRC to avoid explicit transmission of this value. This allows checking of whether the same ID is used in the transmitter and receiver, but it does not allow the receiver to easily reconstruct the ID used in the transmitter in case of a mismatch (inverting the CRC calculation is impossible due to the nature of CRC) . Moreover distortions as well as ID mismatches lead to CRC mismatches, so the receiver cannot distinguish between both these types of faults even though of very different severity (distortions are

"normal" while ID mismatches are a severe fault) . It may also be noted that TTP/C V0.6 supports an additional frame format that does contain the ID explicitly (probably due to the problem mentioned , above) .

Referring now to FIG. 1, an automotive communication system 100 incorporating the present invention has a number of transmitters 200 and receivers 300 (which in practice may be provided in transceiver units providing both transmitter and receiver functions) and a bus 400 to which the transmitters and receivers are coupled for communication therebetween. In the automotive communication system 100 the bus 400 and the connections thereto will typically be provided in the form of electrical wires or optical fibres, but (as will be explained in greater detail below) the invention is also applicable to other types of communication systems such as wireless communication systems.

The communication system 100 utilises a frame-based sequential data transmission protocol employing a (mini) slotting scheme as known per se and not requiring description in further detail. The transmitter 200 includes CRC calculator 210 for receiving data to be transmitted in a frame and for calculating therefrom a cyclic redundancy check value CRC. The transmitter 200 also includes an encoder 220 for receiving and encoding (with redundancy) a transmission (minislot) value ID-t (it will be understood that as long as the CRC is longer than the ID a redundant encoding is possible - the maximal reachable Hamming distance depends on the length difference; for example, at a basic level parity bits may be used for the redundant encoding, although more efficient alternative methods exist and will be apparent to a person of ordinary skill in the art) . A function generator 230 is provided for receiving the CRC value and the encoded transmission (mini) slot value ID-t and for producing a Check Code in the form of an invertable functional combination (f) of the CRC value and the encoded ID-t value (for example, the combination function may be Exclusive-OR or any other invertable binary function, which can be even more complicated for multi- bit operations - e.g., addition, multiplication with nonzero, etc.) . A frame generator 240 is provided for producing a frame containing the data and Check Code for transmission after (minislot) ID-t.

The communication system 100 utilises a frame-based sequential data transmission protocol employing a (mini) slotting scheme as known per se and not requiring description in further detail.

The receiver 300 includes CRC calculator 310 for calculating a cyclic redundancy check value from data received in a frame. The receiver 300 also includes a reverse function generator 320 for recovering, from a

Check Code in the received frame, the encoded ID value. A decoder 330 is provided for decoding the ID value (ID-c) from the recovered encoded value (a decoding error in the decoder 330 is indicative of a transmission error such as CRC mismatch or toggled bits in the Check Code) . A

(mini) slot counter 240 counts the number (ID-r) of the (mini) slot after which the frame information was received. A comparator 250 compares the counted (mini) slot value ID-r with the decoded ID value ID-c. The result of the comparison and a CRC matching the transmitted data determines whether the transmission was OK or was subject to error.

Referring now also to FIG. 2, the methods used in the transmitter 200 and the receiver 300 are as follows:

At the transmi tter 200

Assuming the transmitter will want to transmit in (after) (mini) slot 4, the transmitter ID (ID-t), is 4, as shown at step 510. Rather than transmitting ID-t over the communication medium as in the ^λbyteflight' protocol, ID-t is encoded (at step 520) and combined with the CRC which is calculated (at step 530) over all transmitted frame data (so excluding ID-t) . The encoding of ID-t (e.g., as a 10-bit number) has a result with the same number of bits as the CRC, e.g., for Byteflight/FlexRay at least 15 bits (CRC length) can be used (so 5 bits are available to store redundant information) . The encoded ID-t should have a Hamming distance (h) of at least 3 to be able to reconstruct at least 1-bit corrupts. A lower Hamming distance may alternatively be used, but this would not allow distinguishing between bit corruption and timing error. The combination function (f) , shown at step 540, which produces the Check Code must be invertable (e.g., an exclusive-OR) . The Check Code is transmitted together with the other frame data, in the same way that CRC is transmitted in known systems. Part of the information transmitted on the communication medium is shown at step 550.

At the receiver 300

ID-c is reconstructed from the transmitted frame data. ID-r is obtained from a (mini) slot counter (not shown) in the receiver, e.g., if a receiver detects the start of a frame after the 4th minislot the reconstructed ID-r will be 4, as shown at step 560. ID-c is constructed from the Check Code as follows. First the receiver calculates the CRC over the frame data (excluding the Check Code) , as shown at step 570. Then it performs the inverted combination function (f¹) , i.e., a de-combination function, using the Check Code and the calculated CRC, as shown at step 580. Next the receiver decodes the encoded identifier ID (called ID-ce) from the received Check Code, as shown at step 590, to recover ID-c, as shown at step 600. If there is no error the result (called ID-ce) will be the encoded ID-t (see below for consideration of error scenarios) . Then ID-r and ID-c are compared, as shown at step 610, to produce an indication of transmission/reception integrity of the received frame - if they are identical the CRC matched and there was no timing error, so the frame transmission was correct. ID-r can be used to determine appropriate message receive filtering.

Error Scenarios The following error scenarios cover a complete set of possible scenarios caused by bit corruption during the transmission or caused by timing drifts between receiver and transmitter or by the use of an incorrect ID-t in the transmitter.

1) Corrupted data bits (not in the Check Code)

Except in very rare cases, corrupted data bits (not in the Check Code) lead to a CRC mismatch. In addition, it is likely that either ID-ce cannot be decoded correctly or ID-c will not match ID-r. All three cases indicate a frame transmission error. The Hamming distance of the CRC is not reduced in this case.

2) Corrupted bits in the Check Code

In the case of corrupted bits in the Check Code , the calculated CRC will be identical in receiver and transmitter, but ID-ce will not match the encoded ID-t. This can be recognized either because ID-ce cannot be decoded correctly (in all cases where fewer than h - the Hamming distance - bits are corrupted) or ID-c does not match ID-r (if h bits or more are corrupted) . Both cases indicate a frame transmission error (if the difference between ID-c and ID-r is larger than 1) . The Hamming distance of the CRC is not reduced in this case. Usually the difference between ID-c and ID-r will be larger than 1. 3) Timing Difference of one (Mini) slot between Receiver and Transmitter

This error causes the receiver to count one fewer or more (mini) slots than the transmitter, which is a significant error. In this case the calculated CRC matches and ID-ce will match the encoded ID-t, so ID-ce can be decoded correctly. However ID-c will not match ID-r; in this case there will be a difference of 1. It should be noted that in this case ID-ce can always be decoded correctly (in contrast to error case 2) and the difference between ID-c and ID-r is 1, which is very unlikely for error case 2. So the probability is very high that this case can be distinguished from error case 2. In any case, as ID-c and ID-r do not match this is recognized as error - the correct decoding of ID-ce and the difference between ID-c and 'ID-r being 1 allows this error to be classified as timing error and can usually be distinguished from error case 2. Even when error case 2 leads to the conditions described in this scenario, it will be recognized as error (although not classified correctly) .

4) Timing Difference of more than one (Mini) slot between Receiver and Transmitter

This error condition is similar to error case 3 except that the difference between ID-c and ID-r is bigger than 1. Consequently this error cannot be distinguished from error case 2; however it is recognized as error.

5) Use of incorrect ID-t in the Transmitter If the transmitter uses an ID-t not matching the (mini) slot of transmission, this has the same effect as the transmitter using the correct ID-t but there is a timing difference between receiver and transmitter - therefore this error case can be considered as error case 3 or error case 4 discussed above. The receiver recognizes this condition as error, but cannot distinguish between this condition and error case 3 or error case 4.

6) Combination of Corrupted Bits and Timing Error

It should be noted that this is not a single fault scenario but a double fault scenario (timing error and corrupted bits) . Typically, the requirement for dependable systems is to recognize (and tolerate) single faults only. There is typically no requirement to recognize all double fault scenarios. Nevertheless, for the sake of completeness this scenario is described here.

A superposition of cases 1, 2, 3 or 4 will result in a CRC mismatch leading to errors when decoding ID-ce, or at least leading to a mismatch of ID-c and ID-r. Only in the very unlikely case that a CRC mismatch compensates exactly with bit corruption errors in the Check Code, so that ID-ce can be decoded and ID-c matches ID-r, will this error not be recognized. In this case the Hamming distance of the CRC may be reduced. However, it should be noted that similar double fault scenarios can be constructed for ^ΛTTP', 'byteflight' and 'FlexRay' - none of these protocols can recognize all these double fault scenarios. With h>3 the probability for not recognizing such a double fault with this invention is similar to the probability for double fault non-recognition in *TTP' , 'byteflight' and 'FlexRay' .

It_. will be appreciated that the transmitter and receiver described above will typically be implemented in the form of respective integrated circuits (not shown) , or in the form of a single transmitter/receiver integrated circuit for performing both transmit and receive functions .

It will be appreciated that the methods described above for transmission and reception in a communication system may be carried out in software running on a processor

(not shown) , and that the software may be provided as a computer program element carried on any suitable data carrier (also not shown) such as a magnetic or optical computer disc, a ROM, PROM or a Flash memory.

It will be understood that the scheme for use of frame ids in a (mini) slotting protocol described above provides the following advantages :

• reduction of the control information in the transmitted data (reduction of overhead) ; and

• saving of bandwidth in serial data transmission.

Claims

1. A communication system for use of timeslot identifiers in a timeslot-based protocol, the system comprising: transmitter means for transmitting data in a timeslot via a communication medium, the data including check information being a combination of cyclic redundancy information associated with said data and identification information representative of the timeslot associated with the data; and receiver means for receiving data transmitted by the transmitter means, the receiver means including: means for calculating cyclic redundancy information from the received data; means for recovering cyclic redundancy information from check information in the received data; means for performing a comparison of the calculated cyclic redundancy information with the recovered cyclic redundancy information, and for producing an indication of the integrity of the received data in dependence on the result of the comparison.

2. The communication system of claim 1 wherein the identification information is representative of a minislot associated with the data.

3. The communication system of claim 1 or 2 wherein the cyclic reduncancy information has a greater number of bits than the identification information, and the identification information has a Hamming distance of at least 3.

4. The communication system of claim 1, 2 or 3 wherein: the transmitter means comprises combining means for producing the check information as a first predetermined function combining the cyclic redundancy information and the identification information; and in the receiver means the means for recovering cyclic redundancy information comprises de-combining means for producing a second predetermined function of the check information, the second predetermined function being an inverse of the first predetermined function.

5. The communication system of any one of claims 1-4 wherein the system is an automotive system.

6. A transmitter for use in a communication system using timeslot identifiers in a timeslot-based protocol, the transmitter comprising: transmitter means for transmitting data in a timeslot via a communication medium, the data including check information being a combination of cyclic redundancy information associated with said data and identification information representative of the timeslot associated with the data.

7. The transmitter of claim 6 wherein the identification information is representative of a (mini) slot associated with the data.

8. The transmitter of claim 6 or 7 wherein the cyclic reduncancy information has a greater number of bits than the identification information, and the identification information has a Hamming distance of at least 3.

9. The transmitter of claim 6, 7 or 8 wherein: the transmitter means comprises combining means for producing the check information as a first predetermined function combining the cyclic redundancy information and the identification information.

10. The transmitter of any one of claims 6-9 wherein the system is an automotive system.

11. A receiver for use in a communication system using timeslot identifiers in a timeslot-based protocol, the receiver comprising: transmitter means for transmitting data in a timeslot via a communication medium, the data including check information being a combination of cyclic redundancy information associated with said data and identification information representative of the timeslot associated with the data; and receiver means for receiving data transmitted by a transmitter means, the data including check information being a combination of cyclic redundancy information associated with said data and identification information representative of the timeslot associated with the data, and the receiver means including : means for calculating cyclic redundancy information from the received data; means for recovering cyclic redundancy information from check information in the received data; means for performing a comparison of the calculated cyclic redundancy information with the recovered cyclic redundancy information, and for producing an indication of the integrity of the received data in dependence on the result of the comparison.

12. The receiver of claim 11 wherein the identification information is representative of a minislot associated with the data.

13. The receiver of claim 11 or 12 wherein the cyclic reduncancy information has a greater number of bits than the identification information, and the identification information has a Hamming distance of at least 3.

14. The receiver of claim 11, 12 or 13 wherein: the transmitter means comprises combining means for producing the check information as a first predetermined function combining the cyclic redundancy information and the identification information; and in the receiver means the means for recovering cyclic redundancy information comprises de- combining means for producing a second predetermined function of the check information, the second predetermined function being an inverse of a first predetermined function combining the cyclic redundancy information and the identification information in the check information.

15. The receiver of any one of claims 11-14 wherein the system is an automotive system.

16. A method for use in a communication system using timeslot identifiers in a timeslot-based protocol, the method comprising: providing transmitter means transmitting data in a timeslot via a communication medium, the data including check information being a combination of cyclic redundancy information associated with said data and identification information representative of the timeslot associated with the data; and providing receiver means receiving data transmitted by the transmitter means, the receiver means including: means calculating cyclic redundancy information from the received data; means recovering cyclic redundancy information from check information in the received data; means performing a comparison of the calculated cyclic redundancy information with the recovered cyclic redundancy information, and producing an indication of the integrity of the received data in dependence on the result of the comparison.

17. The method of claim 16 wherein the identification information is representative of a minislot associated with the data.

18. The method of claim 16 or 17 wherein the cyclic reduncancy information has a greater number of bits than the identification information, and the identification information has a Hamming distance of at least 3.

19. The method of claim 16, 17 or 18 wherein: the transmitter means comprises combining means producing the check information as a first predetermined function combining the cyclic redundancy information and the identification information; and in the receiver means the means recovering cyclic redundancy information comprises de-combining means producing a second predetermined function of the check information, the second predetermined function being an inverse of the first predetermined function.

20. The method of any one of claims 16-19 wherein the system is an automotive system.

21. A method for a transmitter for use in a communication system for using timeslot identifiers in a timeslot-based protocol, the method comprising: providing transmitter means transmitting data in a timeslot via a communication medium, the data including check information being a combination of cyclic redundancy information associated with said data and identification information representative of the timeslot associated with the data.

22. The method of claim 21 wherein the identification information is representative of a minislot associated with the data.

23. The method of claim 21 or 22 wherein the cyclic reduncancy information has a greater number of bits than the identification information, and the identification information has a Hamming distance of at least 3.

24. The method of claim 21, 22 or 23 wherein: the transmitter means comprises combining means producing the check information as a first predetermined function combining the cyclic redundancy information and the identification information.

25. The method of any one of claims 21-24 wherein the system is an automotive system.

26. A method for a receiver for use in a communication system using timeslot identifiers in a timeslot-based protocol, the method comprising: transmitter means for transmitting data in a timeslot via a communication medium, the data including check information being a combination of cyclic redundancy information associated with said data and identification information representative of the timeslot associated with the data; and providing receiver means receiving data transmitted by the transmitter means, the data including check information being a combination of cyclic redundancy information associated with said data and identification information representative of the timeslot associated with the data, and the receiver means including : means calculating cyclic redundancy information from the received data; means recovering cyclic redundancy information from check information in the received data; and means performing a comparison of the calculated cyclic redundancy information with the recovered cyclic redundancy information, and producing an indication of the integrity of the received data in dependence on the result of the comparison.

27. The method of claim 26 wherein the identification information is representative of a minislot associated with the data.

28. The method of claim 26 or 27 wherein the cyclic reduncancy information has a greater number of bits than the identification information, and the identification information has a Hamming distance of at least 3.

29. The method of claim 26, 27 or 28 wherein: in the receiver means the means recovering cyclic redundancy information comprises de-combining means for producing a second predetermined function of the check information, the second predetermined function being an inverse of a first predetermined function combining the cyclic redundancy information and the identification information in the check information.

30. The method of any one of claims 26-29 wherein the system is an automotive system.

31. An integrated circuit comprising the transmitter of any one of claims 6-10 or the receiver of any one of claims 11-15.

32. A computer program element comprising computer program means for performing the method of any one of claims 16-30.