When data is transmitted from an information recording device to an information reproducing device or when data is transmitted from a transmitting device to a receiving device, an error may occur in the data on a transmission line or the like. There is a CRC (Cyclic Redundancy Check) as a method for detecting whether an error has occurred in the data. In order to perform a CRC, data to be transmitted needs to be CRC-coded in advance in a device on a transmitting side.
FIG. 1 is a block diagram showing an example of configuration of a transmitting and receiving system.
The transmitting and receiving system of FIG. 1 is formed by connecting a transmitting device 1 and a receiving device 3 to each other via a transmission line 2. The transmitting device 1 is composed of a CRC coder 11, an error correction coder 12, and a transmission line coder 13. The receiving device 3 is composed of a code detector 21, a transmission line decoder 22, an error correction decoder 23, and a CRC detector 24. Transmission data as an object of transmission is input as an information word as an object of a CRC coding process to the CRC coder 11 in the transmitting device 1.
The information word as an object of the CRC coding process is input to the CRC coder 11 in the form of a bit string assuming values 1 and 0. Thus, an information word as an object of the CRC coding process will hereinafter be referred to also as an information bit series as appropriate. In addition, a codeword (CRC code) represented as a bit string assuming values 1 and 0 which codeword is obtained by subjecting an information bit series to the CRC coding process will hereinafter be referred to as a code bit series.
The CRC coder 11 performs the CRC coding process by adding a CRC parity to the input information word. The CRC coder 11 outputs a CRC code obtained by performing the CRC coding process to the error correction coder 12.
The error correction coder 12 subjects the CRC code supplied from the CRC coder 11 to an error correction coding process such as a Reed-Solomon coding process or the like, and outputs data resulting from the error correction coding process to the transmission line coder 13.
The transmission line coder 13 subjects the data supplied from the error correction coder 12 to a coding process (modulating process and the like) according to the transmission line 2, and transmits resulting data to the receiving device 3 via the transmission line 2. A signal representing the data transmitted from the transmission line coder 13 is input to the code detector 21 in the receiving device 3 via the transmission line 2.
The code detector 21 detects the data on the basis of the input signal, and outputs the detected data to the transmission line decoder 22.
The transmission line decoder 22 subjects the data supplied from the code detector 21 to a decoding process (demodulating process and the like) according to the transmission line 2, and outputs resulting data to the error correction decoder 23.
The error correction decoder 23 subjects the data supplied from the transmission line decoder 22 to an error correcting process, and outputs data resulting from the error correcting process as received data. The received data output from the error correction decoder 23 is supplied to a device in a succeeding stage as a received bit series made of a bit string assuming values 1 and 0, and is supplied to the CRC detector 24.
The CRC detector 24 subjects the received bit series supplied from the error correction decoder 23 to a CRC process to determine whether error correction has been made correctly, that is, whether there is an error in the received bit series. The CRC detector 24 outputs a coincidence signal indicating a result of the determination to the device in the succeeding stage.
When the device present in the stage succeeding the receiving device 3 is a recording device, and the recording device is provided with a drive for making the received data recorded on a recording medium, the coincidence signal output from the CRC detector 24 is used in a controller of the drive to improve reliability, or for example to determine whether to make a data retransmission request to the transmitting device 1. As other uses of the CRC code, the CRC code is used as a part of a postprocessor in the code detector 21, and is used for header information and transmission packets in packet communication.
Principles of error detection by the CRC code will be described in the following.
When a parity of r bits is added to an information word of k bits to form a codeword having a code length of n (n=k+r) bits, a value M(x)·xr obtained by multiplying a (k−1)th order information polynomial M(x) representing the information word as a polynomial by xr is expressed by Equation (1) below, where R(x) and Q(x) are respectively an (r−1)th order remainder polynomial and a quotient polynomial obtained when the value M(x)·xr is divided by an rth order generator polynomial G(x). In addition, when the codeword obtained by the CRC coding process is set as an (n−1)th order code polynomial W(x), the code polynomial W(x) is expressed by Equation (2) below.
[Equation 1]M(x)·xr=Q(x)·G(x)+R(x)  (1)[Equation 2]W(x)=M(x)·xr−R(x)  (2)
From Equations (1) and (2), the code polynomial W(x) is expressed by Equation (3) below. This code polynomial W(x) is divisible by the generator polynomial G(x).
[Equation 3]W(x)=Q(x)·G(x)  (3)
From the above, when the received data supplied from the error correction decoder 23 to the CRC detector 24 is set as a reception polynomial Y(x), the CRC detector 24 in the receiving device 3 receiving the codeword expressed by the code polynomial W(x) which codeword is transmitted from the transmitting device 1 in FIG. 1 checks whether the reception polynomial Y(x) is divisible by the generator polynomial G(x).
When a result of the check shows that the reception polynomial Y(x) is divisible by the generator polynomial G(x), the reception polynomial Y(x) coincides with the code polynomial W(x), and therefore the CRC detector 24 determines that no error has occurred. When the reception polynomial Y(x) is not divisible by the generator polynomial G(x), on the other hand, the reception polynomial Y(x) does not coincide with the code polynomial W(x), and therefore the CRC detector 24 determines that an error has occurred on the transmission line 2.
Because the CRC code is a cyclic code, the CRC code can be easily implemented in a device using a shift register and an exclusive OR operation circuit when the generator polynomial G(x) is determined. As the generator polynomial G(x), a CRC-CCITT (G(x)=x16+x12+x5+1) and a CRC-ANSI (G(x)=x16+x15+x2+1) as 16-bit CRCs are widely known.
Description will be made in the following of configurations of the CRC coder 11 in the transmitting device 1 and the CRC detector 24 in the receiving device 3 when the generator polynomial G(x)=x3+x+1 (r=3).
FIG. 2 is a diagram showing an example of configuration of the CRC coder 11.
As shown in FIG. 2, the CRC coder 11 is composed of a CRC parity generator 31, a selector 32, a selector 33, and a bit number counter 34. The CRC coder 11 having such a configuration generates a code bit series expressed by a code polynomial W(x) from an information bit series expressed by an information polynomial M(x).
The CRC parity generator 31 generates a CRC parity of r bits to be added to the information bit series of k bits, and outputs the generated CRC parity to the selector 32. A configuration of the CRC parity generator 31 will be described later with reference to FIG. 3.
The selector 32 selects one of outputs R00out, R01out, and R02out input from the CRC parity generator 31 to input terminals 00, 01, and 10 according to a select signal S0 output from a control circuit not shown in the figure, and outputs the output to a “1” input terminal of the selector 33 in order.
While the information bit series of k bits is input to a “0” input terminal of the selector 33, the selector 33 selects the information bit series and outputs the information bit series as it is according to a select signal S1 output from the bit number counter 34. In addition, in timing of an end of input of the information bit series, the selector 33 selects and outputs the CRC parity as the output of the selector 32 which output is input to the “1” input terminal.
Thus, a code bit series of code length n=k+r, which code bit series is composed of the information bit series of k bits and the CRC parity of r bits generated on the basis of the information bit series of k bits, is output from the selector 33.
FIG. 3 is a circuit diagram showing an example of configuration of the CRC parity generator 31 in FIG. 2. As described above, the generator polynomial G(x) is x3+x+1.
As shown in FIG. 3, the CRC parity generator 31 is formed by cyclically connecting a shift register R00, an EXOR1 as a first exclusive OR operation circuit, a shift register R01, a shift register R02, and an EXOR2 as a second exclusive OR operation circuit. An output of the EXOR2 is input to the shift register R00, and is input to the EXOR1.
The information bit series expressed by the information polynomial M(x) is input to the EXOR2 bit by bit in order from the bit of a high-order term at each time (in each timing defined by a clock signal for operating the shift registers, for example). An information bit series M(x)·xr in the form of the information polynomial M(x) multiplied by xr in advance is input to the CRC parity generator 31. An initial value of the shift registers R00, R01, and R02 is zero.
When the input of the bit of a zeroth-order term of the information bit series to the CRC parity generator 31 is finished, an enable signal E0 output from the control circuit not shown in the figure is disabled (inactive state), and the values of the shift registers R00, R01, and R02 are retained. The values of the shift registers R00, R01, and R02 at a point in time when the input of the bit of the zeroth-order term of the information bit series to the CRC parity generator 31 is finished are coefficients of respective orders of a remainder polynomial R(x). That is, the remainder polynomial R(x) is expressed as R(x)=(Value of R02)×x2+(Value of R01)×x+(Value of R00).
The values of the shift registers R00, R01, and R02 are output to the selector 32 as outputs R00out, R01out, and R02out, respectively. The output R00out is input to the input terminal 00 of the selector 32. The output R01out is input to the input terminal 01 of the selector 32. The output R02out is input to the input terminal 00 of the selector 32.
FIG. 4 is a diagram showing an example of configuration of the CRC detector 24 in the receiving device 3.
As shown in FIG. 4, the CRC detector 24 is composed of a CRC parity checker 41 and a comparator 42. The CRC detector 24 having such a configuration checks whether there is an error in a received bit series expressed by a reception polynomial Y(x) which received bit series is supplied from the error correction decoder 23.
The CRC parity checker 41 divides the reception polynomial Y(x) by the generator polynomial G(x), and outputs R10out, R11out, and R12out representing the coefficients of the remainder polynomial R(x) to the comparator 42.
The comparator 42 determines whether a result of dividing the reception polynomial Y(x) by the generator polynomial G(x) has a remainder on the basis of the outputs R10out, R11out, and R12out from the CRC parity checker 41.
When the comparator 42 determines that the result of dividing the reception polynomial Y(x) by the generator polynomial G(x) does not have a remainder and that the reception polynomial Y(x) is divisible by the generator polynomial G(x) because the values of the outputs R10out, R11out, and R12out are all zero, the comparator 42 determines that no error has occurred in the data because the reception polynomial Y(x) coincides with the code polynomial W(x), and outputs a coincidence signal indicating that the reception polynomial Y(x) coincides with the code polynomial W(x). In addition, when the comparator 42 determines that the result of dividing the reception polynomial Y(x) by the generator polynomial G(x) has a remainder and that the reception polynomial Y(x) is not divisible by the generator polynomial G(x), the comparator 42 determines that an error has occurred in the data because the reception polynomial Y(x) does not coincide with the code polynomial W(x), and outputs a coincidence signal indicating that the reception polynomial Y(x) does not coincide with the code polynomial W(x).
FIG. 5 is a circuit diagram showing an example of configuration of the CRC parity checker 41 in FIG. 4.
The configuration of the CRC parity checker 41 corresponds to the configuration of the CRC parity generator 31 shown in FIG. 3. As shown in FIG. 5, the CRC parity checker 41 is formed by cyclically connecting an EXOR11 as a first exclusive OR operation circuit, a shift register R10, an EXOR12 as a second exclusive OR operation circuit, a shift register R11, and a shift register R12. The output of the shift register R12 is input as the output R12out to the comparator 42, and is input to the EXOR11 and the EXOR12.
The received bit series expressed by the reception polynomial Y(x) is input to the EXOR11 bit by bit in order from the bit of a high-order term at each time. An initial value of the shift registers R10, R11, and R12 is zero.
The values of the shift registers R10, R11, and R12 at a point in time when the input of the bit of the zeroth-order term of the received bit series to the CRC parity checker 41 is finished are coefficients of respective orders of a remainder polynomial R(x). That is, the remainder polynomial R(x) is expressed as R(x)=(Value of R12)×x2+(Value of R11)×x+(Value of R10).
The values of the shift registers R10, R11, and R12 are output to the comparator 42 as outputs R10out, R11out, and R12out, respectively.
The performance of the CRC implemented by the devices having the configurations as described above is generally greatly affected by the order of the generator polynomial G(x), undetected error probability Pud, and minimum Hamming distance dmin.
For example, a random error detecting capability can detect all of (dmin-1) errors or less. However, a large number of other errors can also be detected. In addition, a burst error detecting capability can detect all errors whose length is equal to or less than the order of the generator polynomial G(x). However, many of burst errors whose length is greater than the order of the generator polynomial can also be detected.
The undetected error probability Pud refers to a probability of a received bit series being changed to a different code bit series from a transmitted code bit series (code bit series obtained by adding a CRC parity to another information bit series than an information bit series given as data as an object of transmission) due to an error occurring on the transmission line, and the device on the receiving side determining that there is no error even when there is actually an error in the received bit series.
The undetected error probability Pud is expressed as in Equations (4) and (5) below by a parity number r, code length n, weight distribution A determined when the generator polynomial G(x) and the code length n are determined or the weight distribution B of dual code, and channel bit error probability (transition probability) ε on a binary symmetric channel (Non-Patent Document 1).
                    [                  Equation          ⁢                                          ⁢          4                ]                                                                      P          ud                =                              ∑                          i              =              0                        n                    ⁢                                          ⁢                                    A              i                        ⁢                                                            ɛ                  i                                ⁡                                  (                                      1                    -                    ɛ                                    )                                                            n                -                i                                                                        (        4        )                                [                  Equation          ⁢                                                            ⁢                                                          ⁢          5                ]                                                                      P          ud                =                                            2                              -                r                                      ⁢                                          ∑                                  i                  =                  0                                n                            ⁢                                                                    B                    i                                    ⁡                                      (                                          1                      -                                              2                        ⁢                                                                                                  ⁢                        ɛ                                                              )                                                  i                                              -                                    (                              1                -                ɛ                            )                        n                                              (        5        )            
Non-Patent Documents 2 to 8 propose various generator polynomials that minimize the undetected error probability according to the order of the generator polynomial (parity number) and the code length.
For example, Non-Patent Documents 2 and 3 propose a generator polynomial such as minimizes the undetected error probability of code at each code length in a 16-bit CRC.
In addition, Non-Patent Documents 5 and 8 show that there is a characteristic such that when the code length n is changed, the undetected error probability Pud changes to an extreme with a code length where the minimum Hamming distance dmin changes as a boundary. This characteristic is shown in FIG. 6. FIG. 6 shows minimum (limit) undetected error probability in a 16-bit CRC.
An axis of abscissas of FIG. 6 indicates the code length n (bits), and an axis of ordinates indicates the undetected error probability Pud. A dotted line in FIG. 6 represents undetected error probability when a G(x)=x16+x12+x5+1 adopted by the CRC-CCITT standard is used for data of each code length, and a solid line represents theoretical limit undetected error probability in a 16-bit CRC.
Patent Document 1 discloses an invention relating to a method of selecting a CRC generator polynomial. In this invention, when an order of the generator polynomial is given, a generator polynomial is selected on the basis of a distance spectrum calculated for all generator polynomials of the order. The distance spectrum is a table showing the number of codewords at each Hamming distance. A generator polynomial having a maximum and minimum Hamming distance and minimizing the undetected error probability is thereby selected.
Patent Document 2 discloses a method of selecting a generator polynomial that has as low an undetected error probability as possible and as large a minimum Hamming distance as possible at a given code length and a given CRC parity length and which is usable in as wide a code length range as possible.
USPTO Backgrounds
USPTO Backgrounds