FIG. 1 shows a conventional transmission chain. In a first step 12, the message to be transmitted 10 (original message) is used to calculate a cyclic redundancy check (CRC) block. The CRC technique is commonly used for detecting transmission errors by adding redundancy. The redundancy block is attached to the original message (by concatenating the binary sequences of the message and the redundancy block). Hereinafter, the message obtained by adding the redundancy block or by another preliminary transformation is designated <<transformed message>> in order to differentiate it from the original message. In the context of this document, the original message can be an informational message or any other message that can be represented in binary form.
The CRC block is a binary sequence of defined length which is obtained by a hash of the original message. A CRC block of length n calculated on an original message of any given length permits the detection of all error bursts with a length that does not exceed n and a fraction of 1-2−n of the error bursts having a greater length. The CRC block is calculated by polynomial modulo 2 division. For this purpose, a polynomial of the message, hereinafter denoted M(x), is associated with the original message. The CRC block corresponds to the remainder R(x) of the polynomial modulo 2 division of M(x)·xn+1 by the generator polynomial of degree n+1, denoted G(x). The quotient of the division can be ignored. The degree of the remainder R(x) cannot be greater than the degree of G(x) minus one, i.e. n. Where necessary, 0-valued bits are added to the remainder R(x) to create a CRC block of fixed length. In order to calculate the CRC block, one can use in particular a linear feedback shift register. The data packet formed by the original message, onto which has been attached the CRC block, is sometimes referred to as “code word”.
The data packet composed of the original message and the CRC block is then trellis coded in step 14. This trellis coding can consist of a channel coding, for example a convolutional coding, or be implicit in the modulation, for example in the case of a continuous phase modulation.
The symbol sequence obtained by the coding is then used to modulate (in the modulation step 16) a signal for the purposes of the transmission by the transmission channel 18.
At the receiver side, the transmitted signal is demodulated (in the demodulation step 20) in a coherent manner (i.e. by using the known carrier phase) or in a non-coherent manner (i.e. without using the known carrier phase) and decoded (in the decoding step 22) by a decoding trellis algorithm, such as, for example with the help of the Viterbi algorithm, or even the SOVA algorithm (Soft Output Viterbi Algorithm), or even the BCJR algorithm (named after its inventors Bahl, Cocke, Jelinek and Raviv), or even a simplified BCJR algorithm.
In order to detect and/or correct the transmission errors, the receiver verifies the CRC of the message transmitted in step 24 before releasing the verified/corrected message (step 26) or an error message in the case where the correction would not be possible. Different methods are known for verifying the CRC. One of these methods consists in calculating the CRC on the received sequence of information bits and comparing it with the CRC of the transmitted message. A method that can be more easily implemented in hardware uses the property that the CRC of a binary sequence consisting of a message followed by its CRC is zero, and can be expressed as follows:CRC([data, CRC(data)])=0where CRC(.) designates the result of the calculation of CRC and [.,.] the concatenation of two binary sequences. Hence, with this method the CRC of the transmitted message is calculated (i.e. on the set of the information bits and the redundancy bits obtained from the decoding). If the result is 0 then the message is considered to have been correctly transmitted. Other methods exist that enable the position of an error bit to be detected. A method of this type is described, particularly in the article by B. McDaniel, An algorithm for error correcting cyclic redundancy checks, C/C++ Users Journal, p. 6, 2003. Developments of this method enable several error bits to be corrected (cf. e.g. S. Babaie, A. K. Zadeh, S. H. Es-hagi, N. J. Nvimipour, Double bits error correction using CRC method, International Conference on Semantics, Knowledge and Grid, no 5, pp. 254-257, 2009 and C. Shi-yi and L. Yu-bai, Error correcting cycle redundancy checks based on confidence declaration, ITS Telecommunications Proceedings, no 6, pp. 511-514, 2006).
FIG. 2 shows a conventional transmission chain that differs from that of FIG. 1 in that the stuffing bits or stuffed bits that represent neither information nor redundancy are inserted in the transformed message (step 13). These stuffing bits are typically used to limit the number of consecutive bits of the same value and to introduce supplementary transitions. The supplementary transitions serve in particular to reduce the synchronization problems at the level of the receiver or to avoid the occurrence of binary sequences with a specific meaning (such as control sequences, for example). The HDLC protocol (acronym for High-level Data Link Control) uses stuffing bits to avoid the appearance of the flag for the time frame end (which in the case of HDLC corresponds to the binary sequence 01111110). According to the HDLC protocol, a 0 bit is inserted behind a sequence of five consecutive bits of value 1, thereby ensuring that the flag for the time frame end does not appear in the middle of a message. This is illustrated in FIG. 3. The stuffing bits can have the value 0 and/or 1, depending on the protocol specifications in question. In the case of HDLC or AIS (acronym for Automatic Identification System), the stuffing bits are always bits of value 0. It should also be noted that the concept of inserting stuffing bits must not be confused with the concept of padding that consists in the insertion of bits to arrive at a binary sequence of a predetermined length. To recover the original message, the stuffing bits are removed (step 23) after decoding, but before the CRC check, as the CRC block ignores stuffing bits possibly contained in the transformed message. In addition, the CRC block can itself contain stuffing bits that can prevent checking.
All known methods of CRC verification or correction of the message based on the CRC block assume that the stuffing bits were removed from the received message before they could be applied, which in practical terms greatly reduces their interest.