GB2389492A

GB2389492A - A transmitter which combines a time slot identifier with a CRC value, and a receiver which extracts the identifier

Info

Publication number: GB2389492A
Application number: GB0212978A
Authority: GB
Inventors: Florian Bogenberger; Mathias Rausch
Original assignee: Motorola Inc
Current assignee: Motorola Solutions Inc
Priority date: 2002-06-06
Filing date: 2002-06-06
Publication date: 2003-12-10
Also published as: WO2003105392A1; GB0212978D0; AU2003240643A1

Abstract

In prior art systems each frame of a transmitted message contains a timeslot identifier, which indicates in which slot (or after which minislot) the frame should be transmitted. The identifier is used by a receiver. In the present invention, for each frame of data, a cyclic redundancy check (CRC) value is calculated and encoded with a timeslot identifier, ID-t, to produce a check value. Preferably the identifier and the CRC value are combined in an exclusive-OR operation. For each frame received, a receiver calculates a CRC value and applies it to the check value in order to extract an identifier value, ID-c. The receiver compares the extracted identifier, ID-c, with an identifier value, ID-r, obtained by counting slots (or minislots). A match implies that the CRC information encoded in the check value must have matched the CRC value calculated at the receiver. This invention requires less overhead than previous systems which transmit CRC and identifier values separately.

Description

SYSTEM, TRANSMITTER, RECEIVER, AND METHODS FOR USE WITH

. .. TIMESLOT IDENTIFIERS IN A TIME=_Ci H^=D ExD:O__ 5 Field of the Invention

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

1C 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 0 (correct reception being ensured by use of a specific time slot).

iTTP/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 25 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 30 invention there is provided a transmitter for use in a

3 - communication system using timeslot identifiers in a timeslot-based protocol as claimed in claim 6.

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

In accordance with a fourth aspect of the present 0 invention there is provided 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 15 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 2l.

20 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 Ins in a minislotting protocol incorporating the present invention 30 will now be described, by way of example only, with reference to the accompanying drawings, in which:

- 4 FIG. 1 shows a block schematic diagram of an automotive communication system using a frame-based sequential data transmission protocol employing a 5 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 15 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 20 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 25 (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 30 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 5 (Cyclic Redundancy Check value e.g. of 24 kits? 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 'byteú1ight' 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 15 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' VO.S appends a type of ID (called "MEDE 20 position" in 'TTP') 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 25 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 30 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. l, an automotive communication system lOO incorporating the present invention has a number of transmitters 200 and receivers 300 (which in practice may be provided in transceiver units providing 0 both transmitter- gnu receiver functions) and a bus 400 to which the transmitters and receivers are coupled for communication therebetween. In the automotive communication system lOO the bus 400 and the connections thereto will typically be provided in the form of 5 electrical wires or optical Libres, 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.

20 The communication system lOO 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 25 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 30 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 5 generator 220 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 0 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 nonhero, etc.). A frame generator 240 is provided for -

producing a frame containing the data and Check Code for 15 transmission after (minislot) ID-t. -

The communication system lOO utilizes a frame-based sequential data transmission protocol employing a (mini)slotting scheme as known per se and not requiring 20 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 25 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 30 CRC mismatch or toggled bits in the Check Code). A (mini)slot counter 240 counts the number (ID-r) of the

- 8 (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 5 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: 1C A t the tram ski t t er 2 o O Assuming the transmitter will want to transmit in (after) (mini)slot 4, the transmitter ID (Idiot), is 4' as shown 15 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 20 (e.g., as a l0-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 25 be able to reconstruct at least l-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 30 (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.

5 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 0 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 15 combination function (f1), 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 20 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 GlO, to produce an indication of transmission/reception integrity of the received frame 25 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. 30 Error Scenari of

- 10 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 5 transmitter.

l) Corrupted data bits (not in the Check Code) Except in very rare cases, corrupted data bits (not in 0 the Check Code) lead to a CRC mismatch. In addiLil, iL is likely that either ID-ce cannot be decoded correctly or IDc 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 20 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 25 indicate a frame transmission error (if the difference between ID-c and ID-r is larger than l). 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 5 (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 lo in this case ID-ce earl 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 15 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 JO 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

1 - 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 5 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 10 error case 4.

6) Combination of Corrupted Bits and Timing Error It should be noted that this is not a single fault 15 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 20 the sake of completeness this scenario is described here.

A superposition of cases l, 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 25 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 30 noted that similar double fault scenarios can be constructed for 'TTP', 'byteflight' and iFlexRay' - none

- 13 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', 5 'byteflight' and ' F1 entry' 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 0 form of a single Crarlsmitter/recelver 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 15 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 25 transmitted data (reduction of overhead); and saving of bandwidth in serial data transmission.

Claims

Claims

1. A communication system for use of timeslot identifiers in a timeslotbased protocol, the system 5 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 0 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; 20 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 25 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 redundancy information has a greater number of bits than the identification information, and the identification information has a Hamming distance of at 5 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 1C predetermined function combining the cyclic redundancy information and the identification information; and in the receiver means the means for recovering cyclic redundancy information comprises decombining 15 means for producing a second predetermined function of the check information, the second predetermined function being an inverse of the first predetermined function. 20 5. The communication system of any one of claims 1-4 wherein the system is an automotive system.

- 16 6. A transmitter for use in a communication system using timeslot identifiers in a timeslot-based protocol, the transmitter comprising: 5 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 10 representative of the timeslot associated with the data.

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

8. The transmitter of claim 6 or 7 wherein the cyclic redundancy information has a greater number of bits than the identification information, and the identification 20 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 25 predetermined function combining the cyclic redundancy information and the identification information. 10. The transmitter of any one of claims 6-9 wherein the 30 system is an automotive system.

- 17 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 5 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 10 receiver means for receiving daca 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 15 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 20 information from check information in the received data; means for performing a comparison of the calculated cyclic redundancy information with i the recovered cyclic redundancy information, 25 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 30 information is representative of a minislot associated with the data.

13. The receiver of claim 11 or 12 wherein the cyclic redundancy information has a greater number of bits than the identification information, and the identification 5 information has a Hamming distance of at least 3 14. The receiver of claim ll, 12 or 13 wherein: the transmitter means comprises combining means for producing the check information as a first JO 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-

15 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 20 information in the check information.

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

1 9 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 5 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 10 providing receiver means receiving data transmitted by the transmitter means, the receiver means including: means calculating cyclic redundancy information from the received data; 5 means recovering cyclic redundancy information from check information in the received data; means performing a comparison of the calculated cyclic redundancy information with 20 the recovered cyclic redundancy information, and producing an indication of the integrity of the received data in dependence on the result of the comparison.

25 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 30 redundancy information has a greater number of bits than

- 20 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: 5 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 10 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 15 function. 20. The method of any one of claims 16-19 wherein the system is an automotive system.

- 21 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 5 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 JO 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 redundancy 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 25 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 5 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 0 providing receiver means receiving data transmitted by the transmitter means, the data including check information belug a combination of cyclic redundancy information associated with said data and identification information representative 15 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 20 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, 25 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 30 information is representative of a minislot associated with the data.

28. The method of claim 26 or 27 wherein the cyclic redundancy information has a greater number of bits than the identification information, and the identification 5 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 10 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 15 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-lo or the receiver of any one of claims 11-15.

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

33. A communication system, for use of timeslot 40 identifiers in a timeslot-based protocol, substantially as hereinbefore described with reference to the accompanying drawings.

34. A transmitter, for use in a communication system using timeslot identifiers in a timeslot-based protocol, substantially as hereinbefore described with reference to the accompanying drawings.

35. A receiver, for use in a communication system using 20 timeslot identifiers in a timeslot-based protocol, substantially as hereinbefore described with reference to the accompanying drawings.

36. A method, for use in a communication system using 25 timeslot identifiers in a timeslot-based protocol, substantially as hereinbefore described with reference to the accompanying drawings.

37. A method, for a transmitter for use in a 30 communication system for using timeslot identifiers in a

- 25 timeslot-based protocol, substantially as hereinbefore described with reference to the accompanying drawings.

38. A method, for a receiver for use in a communication 5 system for using timeslot identifiers in a timeslot-based protocol, substantially as hereinbefore described with reference to the accompanying drawings.