JP4379329B2 - CRC generator polynomial selection method, CRC encoding method, and CRC encoding circuit - Google Patents

Description

The present invention relates to an encoding method and apparatus for encoding data.
In particular, according to the present invention, when digital data is recorded / reproduced to / from a magnetic tape recording device, an optical disk device, or the like, or transmitted by a wireless transmission system or the like, an error caused in a transmission path is obtained by encoding. The present invention relates to a method for selecting a generator polynomial used to generate a CRC code to be detected, and a CRC code and a CRC encoding circuit that perform CRC encoding using the selected generator polynomial.

When information (data) is transmitted via a transmission path by an information recording device or a communication device, an error may occur in the transmitted information.
There is a CRC (Cyclic Redundancy Check) as a technique widely used as a method for detecting whether an error has occurred in information.

In order to perform CRC, information to be transmitted needs to be CRC encoded in advance.
CRC coding will be described with reference to FIG.
In FIG. 1, a transmission device 1 and a reception device 3 are connected via a transmission line 2.
The CRC is used for detection of error correction by error correction decoding by performing error correction coding such as Reed-Solomon code on the CRC code in which the CRC parity is added to the information word (data) in the transmission device 1. It is done.
In the transmission apparatus 1, an input information sequence in which a plurality of information words (data) to be CRC-encoded to be transmitted is continuous is input to the CRC encoder 11 and subjected to CRC encoding. Details of the CRC encoder 11 will be described later with reference to FIG. The CRC-encoded information is then input to the error correction encoder 12, where it is subjected to error correction encoding such as a Reed-Solomon code. The error-corrected encoded information is then input to the transmission path encoder 13, subjected to transmission path encoding processing corresponding to the transmission path 2, and sent to the transmission path 2.
The signal passing through the transmission path 2 is detected by the code detector 31 of the receiving device 3, and the detected information is input to the transmission path decoder 32. The error correction decoder 33 performs error correction, such as a Reed-Solomon code, on the detected information series decoded by the transmission path decoder 32 in accordance with the processing of the error correction encoder 12. The error corrected information is then input to the CRC detector 34. The CRC detector 34 performs CRC processing on the error-corrected detection sequence, determines whether the error correction is correctly performed (whether there is an error in the detection sequence), and outputs the result as a coincidence signal. .
Details of the CRC detector 34 will be described later with reference to FIG.

The coincidence signal output from the CRC detector 34 is used, for example, for improving reliability by making a retransmission request in the controller of the drive of the information recording apparatus.
As other uses of the CRC code, for example, it is used as a part of a post processor in a code detector, or used for header information and a transmission packet in packet communication. It is also used as an erasure flag for error correction.

Error detection principle by CRC code The error detection principle by CRC code will be described.
When an r-bit parity is added to an information word (digital data) consisting of k bits to form a code word of code length n (n = k + r) bits, the information word is expressed by a polynomial (k−1) -order (order multiplied by the x ^r information to the polynomial M (x) of). For example, when the information word is “1010101” in binary, the information polynomial M (x) is expressed as x ⁶ + x ⁴ + x ² +1.
The results are multiplied by x ^r the information polynomial M (x) M (x) · x r, the remainder polynomial R (x) (the order of when divided by r the following generator polynomial (generator polynomial) G (x) is ( The (n-1) th order code polynomial W (x) is configured as shown in the following expression 2 by using the (r-1) th order) and the quotient polynomial Q (x) according to the following expression 1.

[Equation 1]
M (x) · x ^r = Q (x) · G (x) + R (x)
... (1)

[Equation 2]
W (x) = M (x) · x ^r −R (x)
... (2)

  From the relationship of Equations 1 and 2, the code polynomial is W (x) = Q (x) G (x). Therefore, the sign polynomial W (x) is divisible by the generator polynomial G (x).

Under the above viewpoint, for example, when the receiving device 3 receives the transmission of the code polynomial W (x) to the receiving device 3 via the transmission path 2, the CRC of the receiving device 3 is received. The detector 34 checks whether the reception polynomial Y (x) is divisible by the generator polynomial G (x).
If the reception polynomial Y (x) is divisible by the generator polynomial G (x), the reception polynomial Y (x) matches the code polynomial W (x), and no error has occurred in the information word in the transmission path 2. If the reception polynomial Y (x) is not divisible by the generator polynomial G (x), the reception polynomial Y (x) is not the code polynomial W (x). Can be judged (can be estimated).

  Since the CRC code is a cyclic code, if the generator polynomial G (x) is determined, the circuit configuration thereof is, for example, the circuit configuration of the CRC encoder 11 of the transmission apparatus 1 in FIG. It is possible to make a device relatively easily using the sum.

Example of CRC Encoder As a generator polynomial G (x) widely used in CRC, G (x) = x ¹⁶ + x ¹² + x ⁵ +1 based on the CRC-CCITT standard, which is 16-bit CRC, or CRC− Based on the ANSI standard, G (x) = x ¹⁶ + x ¹⁵ + x ² +1.

Hereinafter, as an example, for example, a CRC encoder (CRC encoding circuit) in the transmission apparatus 1 in FIG. 1 when the generator polynomial G (x) = x ³ + x + 1 when the number of parity bits (order) r = 3 is set. ) A configuration example of 11 will be described with reference to FIG.
FIG. 2 is a diagram illustrating a configuration example of the CRC encoder 11 that generates the code polynomial W (x) from the information polynomial M (x).
The CRC encoder 11 includes a CRC parity generator 110, a first selector 111, a second selector 112, and a bit number counter 113.
The CRC parity generator 110 generates an r-bit CRC parity for the k-bit information bit sequence and outputs the CRC parity to the first selector 111. A method of generating parity in the CRC parity generator 110 will be described with reference to FIGS.
The second selector 112 outputs the input information bit sequence based on the state control signal S 1 from the bit number counter 113 during a period in which the k-bit information bit sequence is input to the “0” input terminal. In addition, when the input of the information bit sequence to the “0” input terminal is completed, the second selector 112 is generated by the CRC parity generator 110 that is input to the “1” input terminal via the first selector 111. Output r-bit parity. As described above, the second selector 112 of the CRC encoder 11 receives “k-bit information bit sequence”, followed by “r-bit parity bits generated by the CRC parity generator 110 based on the information bit sequence”. Is output. As described above, the code bit sequence output from the second selector 112 is a code bit sequence having a code length n = k + r, which includes “k-bit information bit sequence” and “r-bit parity bit”.

The CRC parity generator 110 and the first selector 111 will be described.
FIG. 3 shows a circuit example of the CRC parity generator 110 when the generator polynomial G (x) is G (x) = x ³ + x + 1.
The CRC parity generator 110 in FIG. 3 includes a first shift register R00, a first exclusive OR (EXOR) circuit EXOR1, a second shift register R01, a third shift register R02, and a second exclusive OR circuit EXOR2. Are connected in a cyclic manner, and the output of the second exclusive OR circuit EXOR2 is input to the first exclusive OR circuit EXOR1.

FIG. 4 shows an example of a circuit diagram of the CRC parity generator 110 when the generator polynomial G (x) = x ⁴ + x ³ + x ² + x + 1.
The CRC parity generator 110 of FIG. 4 includes a first shift register R00, a first exclusive OR (EXOR) circuit EXOR1, a second shift register R01, a second exclusive OR circuit EXOR2, a third shift register R02, 3 exclusive OR circuit EXOR3, 4th shift register R03, and 4th exclusive OR circuit EXOR4 are connected cyclically, and the output of 4th exclusive OR circuit EXOR4 is 1st, 2 and 3 exclusive. The signals are input to the logical sum circuits EXOR1, EXOR2, and EXOR3.

As illustrated in FIGS. 3 and 4, the CRC parity generator 110 is configured based on a generator polynomial G (x). In other words, as can be understood from the illustrations of FIG. 3 and FIG. 4, when the generator polynomial G (x) is determined, the CRC parity generator 110 cyclically connects the shift register and the exclusive OR circuit to the final stage. An exclusive OR circuit, for example, a circuit that applies the output of the second exclusive OR circuit EXOR2 in FIG. 3 or the fourth exclusive OR circuit EXOR4 in FIG. 4 to the exclusive OR circuit in the preceding stage can be configured.
The operation of the CRC parity generator 110 illustrated in FIG. 3 will be described below. The operation of the CRC parity generator 110 illustrated in FIG. 4 is basically the same as the operation of the CRC parity generator 110 illustrated in FIG.

In FIG. 3, the information bit sequence represented by the information polynomial M (x) is sent to the second exclusive OR circuit EXOR2 above the third shift register R02 every time, for example, every clock for operating the shift register. In addition, the bit sequence M (x) · x ^r, which is obtained by multiplying the information polynomial M (x) by x ^r in advance, is input to the information parity sequence in order from the higher order term of the information bit sequence bit by bit. Will be input to the device 110.
Here, the initial values of the first to third shift registers R00, R01, R02 are zero.
The values held in the first to third shift registers R00, R01, R02 at the time when the zero-order term of the information bit sequence is completely input to the CRC parity generator 110 are the respective orders of the remainder polynomial R (x). Gives the coefficient of. That is, the remainder polynomial R (x) is R (x) = (retained content of R02) × x ² + (retained content of R01) × x + (retained content of R00).
Therefore, when the zero-order term of this information bit sequence has been input to the CRC parity generator 110, the enable signal E0 output from the control circuit (not shown in FIG. 2) is disabled (inactive state), and the CRC The values held in the first to third shift registers R00, R01, R02 of the parity generator 110 are held and output to the first selector 111.

2, for example, the output from the CRC parity generator 110 whose circuit configuration is illustrated in FIG. 3 to the three input terminals 00, 01, and 10 of the first selector 111 are the shift registers R00, Outputs R00 _out , R01 _out , R02 _out of R01, R02, and the first selector 111 has three input terminals 00, 01, 10 according to a first select signal S0 output from a control circuit (not shown in FIG. 2). , One of the outputs R00 _out , R01 _out , and R02 _out from the CRC parity generator 110 are sequentially selected and output to the “1” input terminal of the second selector 112.
The second selector 112 operates in accordance with the second select signal S1 output from the bit number counter 113 controlled by a control circuit (not shown in FIG. 2), in other words, according to the bit count value of the bit number counter 113. During a period in which the k-bit information bit sequence is input to the “0” input terminal of the selector 112, the information bit sequence input to the “0” input terminal is selected and the information bit sequence is output as it is. On the other hand, when the information bit sequence is completely input to the CRC parity generator 110 and all the parities are generated, the output of the first selector 111 input to the “1” input terminal of the second selector 112, that is, The parity generated by the CRC parity generator 110 is selected and output.

In this way, for example, as described above, the code bit sequence output from the second selector 112 in the CRC encoder 11 in FIG. 2 is “k-bit information bit sequence” and “r-bit parity bit”. And a code bit sequence of code length n = k + r.
For example, in the transmission apparatus 1 of FIG. 1, as described above, the code bit sequence CRC-encoded by the CRC encoder 11 is input to the error correction encoder 12, for example, an error correction code such as a Reed-Solomon code. The error-corrected and encoded information is input to the transmission line encoder 13, subjected to transmission line encoding processing corresponding to the transmission line 2, and sent to the transmission line 2.
The signal passing through the transmission path 2 is detected by the code detector 31 of the receiving device 3, and the detected information is input to the transmission path decoder 32. The error correction decoder 33 performs error correction on the detected information sequence that has been transmission path decoded by the transmission path decoder 32. The error-corrected information is determined by the CRC detector 34 as to whether or not there is an error in the detection sequence.

FIG. 5 is a diagram illustrating a configuration example of the CRC detector 34 that checks whether there is an error in the reception polynomial Y (x).
The CRC detector 34 includes a CRC parity checker 341 and a comparator 342.
As described above, the CRC parity checker 341 checks whether the reception polynomial Y (x) is divisible by the generator polynomial G (x), and if the reception polynomial Y (x) is divisible by the generator polynomial G (x), The reception polynomial Y (x) matches the code polynomial W (x), and it is determined that no error has occurred in the information word in the transmission path 2, and the reception polynomial Y (x) is divisible by the generator polynomial G (x). Otherwise, the reception polynomial Y (x) is not the code polynomial W (x), so it is determined that an error has occurred in the information word in the transmission path 2.
The CRC parity checker 341 is a circuit that divides the reception polynomial Y (x) by the generator polynomial G (x), and the comparator 342 is a circuit that checks whether there is a remainder in the result of the division by the CRC parity checker 341. It is.

A configuration example of the CRC parity checker 341 is shown in FIG.
The CRC detector 34 corresponds to the CRC detector 34 of FIG. 1, and the configuration of the CRC parity checker 341 illustrated in FIG. 6 corresponds to the CRC parity generator 110 illustrated in FIG. When the CRC parity generator 110 has the circuit configuration of FIG. 4, the CRC parity checker 341 also has a circuit configuration conforming thereto. Hereinafter, the CRC parity checker 341 corresponding to the CRC parity generator 110 illustrated in FIG. 3 will be described.
The CRC parity checker 341 illustrated in FIG. 6 includes a first exclusive OR circuit EXOR11, a first shift register R10, a second exclusive OR circuit EXOR12, a second shift register R11, and a third shift register R12. The circuits are connected in a cyclic manner, and the output of the third shift register R12 is input to the second exclusive OR circuit EXOR12.
In the CRC parity checker 341 of FIG. 6, the received bit sequence represented by the receiving polynomial Y (x) is increased by 1 bit at each time to the first exclusive OR circuit EXOR11 at the right end of the first shift register R10. Enter the following items in order. The values of the first to third shift registers R10, R11, R12 at the time when the zero-order term of the received bit sequence has been input to the CRC parity checker 341 give the coefficient of the remainder polynomial R (x). That is, R (X) = (R12 value) × x ² + (R11 value) × x + (R10 value).
Here, the initial values of the first to third shift registers R10, R11, R12 are zero.

In FIG. 5, outputs R10 _out , R11 _out , and R12 _out from the CRC parity checker 341 to the comparator 342 are outputs of the registers R10, R11, and R12 of the CRC parity checker 341 in FIG.
The comparator 342 compares (checks) whether all the values of R10 _out , R11 _out , and R12 _out are zero, that is, the remainder is zero, and determines whether all the values of R10 _out , R11 _out , and R12 _out are zero. A 1-bit coincidence signal is output. That is, when all the values of R10 _out , R11 _out , and R12 _out are zero, the reception polynomial Y (x) matches the code polynomial W (x), and an error occurs in the information word in the transmission path 2 The comparator 342 determined not to output, for example, a match signal of logic “1”, and if not, for example, a match signal of logic “0” is output.

The error detection capability of CRC is generally evaluated by a random error detection capability, a burst error detection capability, and a code undetected error probability P _ud, which are determined by a generator polynomial G (x) and a code length n.

Here, the undetected error probability P _{ud of} the code means that the received word is different from the transmitted code word due to an error occurring on the transmission path (for an information bit different from a given information bit). This is the probability of changing to a codeword calculated by adding CRC parity. By changing to another codeword, the remainder becomes zero even when CRC is performed. In other words, it may be determined that there is no error even though there is an error in the received word.
For example, as disclosed in Non-Patent Document 1, the undetected error probability P _ud of the code is obtained by determining the degree (parity number) r, the code length n, the generator polynomial G (x), and the code length n. The distribution A or the dual code weight distribution B is expressed by the channel bit error probability (transition probability) ε in a binary symmetric channel (Binary Symmetric Channel) as follows.

With regard to the random error detection capability, all (d _min −1) or less errors can be detected. However, many other errors can be detected.
As for the burst error detection capability, all errors whose length is less than or equal to the order of the generator polynomial G (x) can be detected. However, many burst errors whose length is larger than the order of the generator polynomial can be detected.

In Non-Patent Documents 2 to 8, various reports on generator polynomials that minimize the undetected error probability of codes have been made, and various ones have been proposed according to the order of the generator polynomial (number of parity) and code length. Yes.
Non-Patent Documents 2 and 3 propose a generator polynomial that minimizes the undetected error probability of a code for each code length in a 16-bit CRC.
Further, in Non-Patent Documents 5 and 8, the undetected error probability P _ud of a code exhibits a characteristic that when the code length n changes, it increases extremely with the code length at which the minimum hamming distance d _min of the code changes as a boundary. Has been confirmed.

FIG. 7 is a graph showing an example of the minimum (limit) undetected error probability characteristic in the case of 8-bit CRC. In FIG. 7, the horizontal axis indicates the code length n (bit), and the vertical axis indicates the undetected error probability P _ud of the code. This is called n-P _ud characteristic.

Patent Document 1 discloses an invention relating to a method for selecting a CRC generator polynomial.
In Patent Document 1, when the order of a generator polynomial is given, the generator polynomial is selected based on a distance spectrum calculated for all generator polynomials of that order. This distance spectrum is a table showing the number of code words at each Hamming distance. Thus, a generator polynomial having the maximum / minimum Hamming distance is selected, and a generator polynomial that minimizes the undetected error probability of the code is selected.

JK Wolf, RD Blakeney, “An exact evaluation of the probability of undetected error for certain shortened binary CRC codes,” Military Communications Conference, 1988. MILCOM 88, Conference record. '21st Century Military Communications-What's Possible?'. 1988 IEEE, vol. 1, pp. 287-292, Oct. 1988. T. Baicheva, S. Dodunekov, P. Kazakov, “Undetected error probability performance of cyclic redundancy-check codes of 16-bitredundancy,” IEE Proc.-Commun., Vol. 147, no. 5, pp. 253-256, Oct. 2000. P. Kazakov, “Fast Calculation of the Number of Minimum-Weight Words of CRC Codes,” IEEE Trans. Inform. Theory, vol. 47, no. 3, pp. 1190-1195, Mar. 2001. P. Koopman, “Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks,” The International Conference on Dependable System and Networks, DSN-2004. G. Castagnoli, J. Ganz, P. Graber, “Optimum Cyclic Redundancy-Check Codes with 16-Bit Redundancy,” IEEE Trans. Commun., Vol. 38, no. 1, pp. 111-114, Jan. 1990. G. Funk, “Determination of Best Shortened Codes,” IEEE Trans. Commun., Vol. 44, no. 1, pp. 1-6, Jan. 1996. D. Chun, J. K. Wolf, “Special Hardware for Computing the Probability of Undetected Error for Certain CRC Codes and Test Results,” IEEE Trans. Commun., Vol. 42, no. 10, pp. 2769-2772, Oct. 1994. G. Castagnoli, S. Brauer, M. Herrmann, “Optimum of Cyclic Redundancy-Check Codes with 24 and 32 Parity Bits,” IEEE Trans. Commun., Vol. 41, no. 6, pp. 883-892, Jun. 1993. J. M. Stein, “METHOD FOR SELECTING CYCLIC REDUNDANCY CHECK POLYNOMIALS FOR LINEAR CODED SYSTEMS”, US Patent 6,085,349, Qualcomm Incorporated, Filed Aug. 27, 1997.

As described above, CRC error detection capability (code undetected error probability, random error detection capability, burst error detection capability) is determined by the generator polynomial and the code length.
There is no generator polynomial in which the undetected error probability of the code is minimum (limit value) in all code lengths, or a generator polynomial in which the minimum hamming distance of the code is maximum, and the undetected error probability of the code depends on the code length. The generator polynomials that minimize the minimum or minimum hamming distance of the code are different.
That is, the widely used CCITT standard and ANSI standard, and the generator polynomials shown in Non-Patent Documents 4 to 8 have code lengths that minimize the undetected error probability of the code and maximize the minimum hamming distance of the code. The range is limited.

  Many of the above-mentioned documents are designed so that the undetected error probability of the code is minimized (limit value) when the code length is long (several thousand bits or more) in data communication or the like. In cases where the code length is shorter, such as when CRC is used or when CRC is used for recording data on a recording medium such as an optical disk, there should be something that shows better performance, but it has not been proposed .

Non-Patent Documents 2 and 3 propose a generator polynomial with the lowest undetected error probability for each code length. In this case, when using a different code length, a different generator polynomial is used each time. Had to use.
For example, in Patent Document 1, a generator polynomial having a maximum code minimum hamming distance is selected for each code length, but this has the problem of increasing the circuit scale.

In actual systems, various code lengths and parity lengths are used, but so far, the optimum CRC code for all code lengths and parity lengths has not been clarified and is currently known. A CRC code alone is not always sufficient to obtain the minimum undetected error probability P _ud in an actual system.

From the above, there is a demand for a generator polynomial in which the undetected error probability of a code is as low as possible for a given code length and parity length, the minimum hamming distance of the code is as large as possible, and can be used in the widest possible code length range. .
Furthermore, for example, when the CRC encoder used in the transmission apparatus 1 of FIG. 1 and the CRC detector used in the reception apparatus 3 are implemented as circuits, a CRC encoding scheme that can simplify the circuit as much as possible is desired.

The object of the present invention is to select a generator polynomial that has the lowest possible undetected error probability for a given code length and parity length, that has the smallest possible hamming distance of the code, and that can be used in the widest possible code length range. The present invention provides a method for selecting a CRC generator polynomial.
A further object of the present invention is to extract a generator polynomial selected by the CRC generator polynomial selection method and make it applicable to a CRC encoder, a CRC detector, and the like.
An object of the present invention is to specifically configure and provide a CRC encoder, a CRC detector, and the like.

According to the present invention, there is provided a method for selecting a CRC and / or a generator polynomial used for CRC check of a CRC code result, which has k-bit information words, and an r-bit parity is added to the information words. a first step of obtaining a maximum and minimum Hamming distance (Max.d _min) was the maximum value of the minimum Hamming distance (d _min) of each code length of the code of the code length (n) (n), maximum and minimum hamming The code length (n) whose distance (Max.d _min ) changes is obtained, and the range of the code length n (n _min (r, Max.d _min ) ≦ n ≦ n _max (r, Max.d _min )) is obtained. In the second step to be obtained and the range of the code length (n) (n _min (r, Max. D _min ) ≦ n ≦ n _max (r, Max. D _min )), the minimum Hamming distance (d _min) is equal to the maximum and minimum Hamming distance (Max.d _min) A third step of finding condition (d _min = Max.d _min) generator polynomial satisfying (G (x)) by total search, from among the generator polynomial found by all search (G (x)), the number of terms A method for selecting a CRC generator polynomial is provided, including (w) and a fourth step of selecting the smallest undetected error probability (P _ud ) of the code.

Preferably, in the third and fourth steps, the period (p) is not less than the maximum code length (n _max (r, Max.d _min )) (p ≧ n _max (r, Max.d _min )), A generator polynomial G that satisfies the condition (d _min = Max.d _min ) where the minimum Hamming distance (d _min ) is equal to the maximum / minimum Hamming distance (Max.d _min ) for the code of (n _max , n _max −r) A step of finding (x) by a full search, a step of selecting a generator polynomial (G (x)) having the smallest number of terms (w) from the generator polynomials (G (x)) found by the full search, Finding a generator polynomial (G (x)) that minimizes the undetected error probability (P _ud ) of the code for the selected generator polynomial (G (x)).

Preferably, in the step of searching and selecting the generator polynomial G (x), the maximum / minimum Hamming distance (Max.d _min ) is Max. For d _min = 2, in the generator polynomial G (x) whose period (p) has the maximum period 2 ^r −1 (which is a primitive polynomial), the number of terms w of the generator polynomial and the undetected error of the code A generator polynomial G (x) with the smallest probability P _ud is selected.

One of the following generator polynomials G (x) is selected according to the CRC generator polynomial selection method.
1. When r = 3 and n = 4, the generator polynomial G (x) = x ³ + x ² + x + 1.
2. When r = 6 and n = 7, the generator polynomial G (x) = x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x + 1.
3. When r = 6 and n = 8, the generator polynomial G (x) = x ⁶ + x ⁴ + x ² + x + 1 (reciprocal polynomial: x ⁶ + x ⁵ + x ⁴ + x ² +1).
4). When r = 6 and n = 8, the generator polynomial G (x) = x ⁶ + x ⁴ + x ³ + x + 1 (reciprocal polynomial: x ⁶ + x ⁵ + x ³ + x ² +1).
5. When r = 6 and n = 8, the generator polynomial G (x) = x ⁶ + x ⁵ + x ³ + x + 1.
6). When r = 8 and n = 9, the generator polynomial G (x) = x ⁸ + x ⁷ + x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x + 1.
7). When r = 10 and n = 11, the generator polynomial G (x) = x ¹⁰ + x ⁹ + x ⁸ + x ⁷ + x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x + 1
8). When r = 10 and n = 12, the generator polynomial G (x) = x ¹⁰ + x ⁸ + x ⁶ + x ⁴ + x ³ + x ² + x + 1 (reciprocal polynomial: x ¹⁰ + x ⁹ + x ⁸ + x ⁷ + x ⁶ + x ⁴ + x ² +1) Is,
9. When r = 12, n = 13, the generator polynomial G (x) = x ¹² + x ¹¹ + x ¹⁰ + x ⁹ + x ⁸ + x ⁷ + x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x + 1
10. When r = 12, n = 14, the generator polynomial G (x) = x ¹² + x ¹⁰ + x ⁸ + x ⁶ + x ⁴ + x ³ + x ² + x + 1 (reciprocal polynomial: x ¹² + x ¹¹ + x ¹⁰ + x ⁹ + x ⁸ + x ⁶ + x ⁴ + X ² +1),
11. When r = 14 and n = 15, the generator polynomial G (x) = x ¹⁴ + x ¹³ + x ¹² + x ¹¹ + x ¹⁰ + x ⁹ + x ⁸ + x ⁷ + x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x + 1
12 When r = 14 and n = 16, the generator polynomial G (x) = x ¹⁴ + x ¹² + x ¹⁰ + x ⁹ + x ⁷ + x ⁵ + x ⁴ + x ³ + x + 1 (reciprocal polynomial: x ¹⁴ + x ¹³ + x ¹¹ + x ¹⁰ + x ⁹ + x ⁷ + X ⁵ + x ⁴ + x ² +1),
13. When r = 14 and n = 17, the generator polynomial G (x) = x ¹⁴ + x ¹¹ + x ⁸ + x ⁶ + x ⁵ + x ³ + x ² + x + 1 (reciprocal polynomial: x ¹⁴ + x ¹³ + x ¹² + x ¹¹ + x ⁹ + x ⁸ + x ⁶ + X ³ +1),
14 When r = 16 and n = 17, the generator polynomial G (x) = x ¹⁶ + x ¹⁵ + x ¹⁴ + x ¹³ + x ¹² + x ¹¹ + x ¹⁰ + x ⁹ + x ⁸ + x ⁷ + x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x + 1 ,
15. When r = 16 and n = 18, the generator polynomial G (x) = x ¹⁶ + x ¹⁴ + x ¹² + x ¹⁰ + x ⁸ + x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x + 1 (reciprocal polynomial: x ¹⁶ + x ¹⁵ + x ¹⁴ + x ¹³ + X ¹² + x ¹¹ + x ¹⁰ + x ⁸ + x ⁶ + x ⁴ + x ² +1)
16. When r = 16 and n = 22, the generator polynomial G (x) = x ¹⁶ + x ¹³ + x ⁸ + x ⁷ + x ⁶ + x ⁴ + x ² + x + 1 (reciprocal polynomial: x ¹⁶ + x ¹⁵ + x ¹⁴ + x ¹² + x ¹⁰ + x ⁹ + x ⁸ + X ³ +1).

One of the following generator polynomials G (x) is selected according to the CRC generator polynomial selection method.
1. When r = 4 and 6 ≦ n ≦ 7, the generator polynomial G (x) = x ⁴ + x ² + x + 1 (reciprocal polynomial: x ⁴ + x ³ + x ² +1).
2. When r = 6 and 9 ≦ n ≦ 31, the generator polynomial G (x) = x ⁶ + x ² + x + 1 (reciprocal polynomial: x ⁶ + x ⁵ + x ⁴ +1).
3. When r = 8 and 10 ≦ n ≦ 12, the generator polynomial G (x) = x ⁸ + x ⁵ + x ⁴ + x ³ + x + 1 (reciprocal polynomial: x ⁸ + x ⁷ + x ⁵ + x ⁴ + x ³ +1).
4). When r = 8 and 10 ≦ n ≦ 12, the generator polynomial G (x) = x ⁸ + x ⁶ + x ³ + x ² + x + 1 (reciprocal polynomial: x ⁸ + x ⁷ + x ⁶ + x ⁵ + x ² +1).
5. When r = 8 and 18 ≦ n ≦ 127, the generator polynomial G (x) = x ⁸ + x ⁴ + x + 1 (reciprocal polynomial: x ⁸ + x ⁷ + x ⁴ +1).
6). When r = 8 and n ≧ 128, the generator polynomial G (x) = x ⁸ + x ⁵ + x ³ + x ² +1 (reciprocal polynomial: x ⁸ + x ⁶ + x ⁵ + x ³ +1).
7). When r = 10 and 23 ≦ n ≦ 31, the generator polynomial G (x) = x ¹⁰ + x ⁹ + x ³ + x + 1 (reciprocal polynomial: x ¹⁰ + x ⁹ + x ⁷ + x + 1).
8). When r = 10 and 32 ≦ n ≦ 511, the generator polynomial G (x) = x ¹⁰ + x ⁵ + x ² +1 (reciprocal polynomial: x ¹⁰ + x ⁸ + x ⁵ +1).
9. When r = 10 and n ≧ 512, the generator polynomial G (x) = x ¹⁰ + x ³ +1 (reciprocal polynomial: x ¹⁰ + x ⁷ +1).
10. When r = 12, 24 ≦ n ≦ 39, the generator polynomial G (x) = x ¹² + x ¹¹ + x ⁷ + x ³ + x + 1 (reciprocal polynomial: x ¹² + x ¹¹ + x ⁹ + x ⁵ + x + 1).
11. When r = 12, 40 ≦ n ≦ 65, the generator polynomial G (x) = x ¹² + x ¹⁰ + x ⁷ + x ⁶ + x ⁵ + x ² +1.
12 When r = 12, 66 ≦ n ≦ 2047, the generator polynomial G (x) = x ¹² + x ⁷ + x ² +1 (reciprocal polynomial: x ¹² + x ¹⁰ + x ⁵ +1).
13. When r = 12, n ≧ 2048, the generator polynomial G (x) = x ¹² + x ⁷ + x ⁶ + x ⁴ +1 (reciprocal polynomial: x ¹² + x ⁸ + x ⁶ + x ⁵ +1).
14 When r = 14 and 28 ≦ n ≦ 71, the generator polynomial G (x) = x ¹⁴ + x ¹⁰ + x ⁹ + x ⁶ + x ² +1 (reciprocal polynomial: x ¹⁴ + x ¹² + x ⁸ + x ⁵ + x ⁴ +1).
15. When r = 14 and 72 ≦ n ≦ 127, the generator polynomial G (x) = x ¹⁴ + x ¹¹ + x ⁵ + x ³ +1 (reciprocal polynomial: x ¹⁴ + x ¹¹ + x ⁹ + x ³ +1).
16. When r = 14 and 128 ≦ n ≦ 8191, the generator polynomial G (x) = x ¹⁴ + x ⁵ + x ² +1 (reciprocal polynomial: x ¹⁴ + x ¹² + x ⁹ +1).
17. When r = 14 and n ≧ 8192, the generator polynomial G (x) = x ¹⁴ + x ⁶ + x ⁴ + x + 1 (reciprocal polynomial: x ¹⁴ + x ¹³ + x ¹⁰ + x ⁸ +1).
18. When r = 16 and 19 ≦ n ≦ 21, the generator polynomial G (x) = x ¹⁶ + x ¹³ + x ¹² + x ⁹ + x ⁷ + x ⁶ + x ⁵ + x ⁴ + x ² +1 (reciprocal polynomial: x ¹⁶ + x ¹⁴ + x ¹² + x ¹¹ + X ¹⁰ + x ⁹ + x ⁷ + x ⁴ + x ³ +1)
19. When r = 16 and 19 ≦ n ≦ 21, the generator polynomial G (x) = x ¹⁶ + x ¹³ + x ¹² + x ⁹ + x ⁷ + x ⁵ + x ⁴ + x ³ + x ² +1 (reciprocal polynomial: x ¹⁶ + x ¹⁴ + x ¹³ + x ¹² + X ¹¹ + x ⁹ + x ⁷ + x ⁴ + x ³ +1)
20. When r = 16 and 23 ≦ n ≦ 31, the generator polynomial G (x) = x ¹⁶ + x ¹³ + x ¹¹ + x ⁵ + x ³ + x ² + x + 1 (reciprocal polynomial: x ¹⁶ + x ¹⁵ + x ¹⁴ + x ¹³ + x ¹¹ + x ⁵ + x ³ +1),
21. When r = 16, 36 ≦ n ≦ 151, the generator polynomial G (x) = x ¹⁶ + x ¹⁵ + x ¹³ + x ⁸ + x ⁵ + x ³ + x + 1 (reciprocal polynomial: x ¹⁶ + x ¹⁵ + x ¹³ + x ¹¹ + x ⁸ + x ³ + x + 1) Is,
22. When r = 16 and 152 ≦ n ≦ 257, the generator polynomial G (x) = x ¹⁶ + x ¹⁵ + x ⁸ + x + 1.
23. When r = ¹⁶ , 258 ≦ n ≦ 32767, the generator polynomial G (x) = x ¹⁶ + x ¹³ + x ² +1 (reciprocal polynomial: x ¹⁶ + x ¹⁴ + x ³ +1).
24. When r = 16 and n ≧ 32768, the generator polynomial G (x) = x ¹⁶ + x ⁹ + x ⁷ + x ⁴ +1 (reciprocal polynomial: x ¹⁶ + x ¹² + x ⁹ + x ⁷ +1).

  According to the present invention, there is provided a CRC encoding method for performing CRC encoding using the selected generator polynomial G (x).

  According to the present invention, the selected generator polynomial G (x) is cyclically connected to a shift register and an exclusive OR circuit provided according to the coefficient of the generator polynomial G (x), and A CRC encoding circuit having a circuit configuration for inputting the output of the exclusive OR circuit at the final stage to the exclusive OR circuit provided according to the coefficient of the generator polynomial G (x) is provided.

According to the present invention, there is provided a CRC encoding method for encoding a CRC code having a code length n using a generator polynomial G (x) having a degree (parity number) r and a period p, wherein the code length n and the order r The minimum Hamming distance maximum value Max. d _min , the minimum hamming distance of the code Max. When the range of code length n where d _min is constant is defined as n _min ≦ n ≦ n _max (where n _min is the minimum code length and n _max is the maximum code length), period p ≧ maximum code length n _max , or period p = 2 ^r −1 and n _min ≦ n ≦ n _max , the minimum hamming distance d _min of the code is d _min = Max. Among generator polynomials G (x) satisfying _dmin , the generator polynomial G (x) has the smallest number of terms in the generator polynomial G (x) and the smallest undetected error probability of the code in the two-dimensional symmetric channel. CRC encoding method is provided.

  By using the CRC coding method generated by using the generator polynomial according to the present invention, the undetected error of the code at a desired parity bit and code length as compared with the case of using a generator polynomial widely used conventionally. The probability can be kept low, and the minimum hamming distance of the code takes the maximum value, so that the random error detection capability can be maximized.

Further, the generator polynomial G (x) has a minimum hamming distance d _min of the code d _min = Max. In the code length range of n _min (r, Max.d _min ) ≦ n ≦ n _max (r, Max.d _min ). Since d _min is satisfied and the undetected error probability P _ud of the code satisfies P _ud ≈ (limit value), even if the code length n changes, a single generator polynomial can be used as long as it is within this code length range Is possible.

Furthermore, in the code length range of n _min (r, Max.d _min ) ≦ n ≦ n _max (r, Max.d _min ), the generator polynomial G in which the minimum hamming distance (d _min ) of the code always takes the maximum value. In (x), the one with the minimum number of terms w is used, so that the circuit scale when mounted on the circuit can be reduced.

Further, if the code length n and the undetected error probability P _{ud of the} code are determined, the number of parity (order r) necessary to satisfy the code length n can be known. Therefore, the generator polynomial G selected for the parity number r and the code length n. By using (x), a desired undetected error probability can be realized.

CRC Code Selection Method As illustrated in FIG. 7, the inventor of the present invention rapidly deteriorates the characteristic of the undetected error probability P _ud of the code at the boundary of the code length n where the minimum hamming distance d _min of the code changes. Focused on that. The n-P _ud characteristic of FIG. 7 shows the limits for various generator polynomials G (x) at each code length.
In the illustration of FIG. 7 for 8-bit CRC, the undetected error probability P _ud of the code changes abruptly at boundaries such as code lengths n = 10 to 12, 13 to 17, 18 to 127, 128 to 255, and the like.

Further, the code length n at which the minimum hamming distance d _min of the code changes depends on the generator polynomial.
Further, the minimum hamming distance d _min of the code at the code length n varies depending on the generator polynomial.

FIG. 8 is a flowchart showing an example of the processing contents of the CRC code selection method of the present invention.
The CRC code selection method of the present invention by the inventor of the present invention will be described below with reference to FIG. 8 based on the above recognition.

Step 1: Max. Find d _min .
The larger the minimum hamming distance d _min of the code, the higher the random error detection capability and the lower the undetected error probability of the code. The maximum value of d _min (this is called the maximum / minimum hamming distance or the minimum hamming distance / maximum value and is expressed as Max.d _min ).

Step 2: Max. The code length n with which d _min changes is obtained.
Next, the maximum / minimum Hamming distance Max. The code length n with which d _min changes is obtained, and Max. The range of the code length n where d _min is constant is expressed as n _min (r, Max. d _min ) ≦ n ≦ n _max (r, Max. d _min ). n _min (r, Max.d _min ) is the minimum range n _min of the code length n, and r and Max. d _min . Similarly, the maximum range n _max of the code length n is r and Max. It shows that it is defined by d _min .

The case of 8-bit CRC is illustrated in FIG.
However, when the code length n exceeds the period p of the generator polynomial G (x), the minimum hamming distance d _min of the code is always 2 when n ≧ 256 in the example of FIG.
The period p of the generator polynomial G (x) is maximum when the generator polynomial G (x) is a primitive polynomial, and the maximum period is represented by (2 ^r −1). That is, Max. The range of the code length n at d _min = 2 is always 2 ^r ≦ n ≦ ∞ regardless of the generator polynomial G (x). That is, n _min (r, 2) = 2 ^r and n _max (r, 2) = ∞.

Step 3: In the case of n _min ≦ n ≦ n _max , d _min = Max. G (x) satisfying d _min is found by all searches.
Next, since a generator polynomial that can be used in the widest possible range of code lengths n is desirable, in the case of n _min (r, Max.d _min ) ≦ n ≦ n _max (r, Max.d _min ), d _min = Max. A generator polynomial G (x) satisfying d _min is found by full search.

Step 4: From G (x) found by all searches, the one having the smallest number of terms w and undetected error probability P _{ud of the} code is selected.
Further, from the generator polynomial G (x) found by all searches, the one having the minimum number of terms w and the undetected error probability P _{ud of the} code is selected.

  A specific example of the search and selection method in steps 3 and 4 will be described with reference to FIG.

Step 41: satisfy p ≧ n _max , and for the sign of (n _max , n _max −r), d _min = Max. G (x) satisfying d _min is found by all searches.
_{First, n min (r, Max.d min} ) ≦ n ≦ n max (r, Max.d min) always in, d _min = Max. To meet d _{min is, p ≧ n max (r,} Max.d min) for the period p meet, _{and, (n max, n max -r} ) for the sign of d _min = Max. Since d _min needs to be satisfied, a generator polynomial G (x) satisfying this condition is found by full search.

Step 42: A generator polynomial G (x) having the smallest number of terms w is selected from G (x) found by all searches.
Next, the generator polynomial G (x) having the smallest number of terms w is selected from the generator polynomials G (x) found by the full search. Further, when the number of terms of G (x) is w, the codeword generated by G (x) always has a codeword whose Hamming distance d _H is w. Therefore, the minimum hamming distance d _{min of the} code generated by G (x) is the maximum / minimum hamming distance Max. If d _min , be sure w ≧ Max. d _min . Using this fact, w <Max. d _min can be omitted.

Step 43: _Find G (x) where P _ud is minimized.
Next, the undetected error probability of the code in n _min (r, Max.d _min ) ≦ n ≦ n _max (r, Max.d _min ) of the CRC code encoded using this generator polynomial G (x) P _ud is obtained by Equation 4, and a generator polynomial G (x) that minimizes P _ud is found.

However, the code length n increases, and Max. In the case of d _min = 2, as described above, the range of the code length n is 2 ^r ≦ n ≦ ∞, that is, n _min (r, 2) = 2 ^r and n _max (r, 2) = ∞. Therefore, the generator polynomial G (x) cannot be searched by the procedure shown in step 41.

In addition, when 2 ^r ≦ n, all generator polynomials G (x) are d _min = Max. d _min = 2 is satisfied. Therefore, when d _min = 2, using the property that the undetected error probability P _{ud of the} code is lower as the period p is larger, Max. For d _min = 2, the number of polynomial terms w and the undetected error probability P _{ud of the} code are the smallest among the generator polynomials G (x) whose period p has the maximum period 2 ^r −1 (which is a primitive polynomial). A generator polynomial G (x) is selected. In other words, this is Max. This coincides with the generator polynomial G (x) obtained by d _min = 3. This is because n _max (r, 3) = 2 ^r −1.

An example of the generator polynomial G (x) found by the above method and the comparative example and a comparative example will be described.
Table 1-A to Table 1-C show the generation polynomial G (x) in each code length of parity bit number (order) r = 3,4,6,8,10,12,14,16 in the present invention. Examples of generator polynomials that are generally used are shown as examples and comparative examples.

The first column of Table 1-A to Table 1-C represents the number of parity bits r, and the second column and the third column respectively represent the maximum / minimum Hamming distance Max. range of code length n satisfying d _min and its maximum and minimum Hamming distances Max. d _min .
The generator polynomial G (x) is expressed in hexadecimal. For example, “F” in hexadecimal notation becomes “1111” in binary notation. Further, if "12D" in the hexadecimal notation, expressed expressed in binary, because it is "100101101", the generator polynomial ^{G (x) = x 8 +} x 5 + x 3 + x 2 +1.
A polynomial obtained by reversing the higher and lower order coefficients is called a reciprocal polynomial, and exhibits the same characteristics.

The data in the 4th to 7th columns of Tables 1-A to 1-C are the minimum hamming distance d _min of the code generated using the generator polynomial in the embodiment of the present invention, the generator polynomial G (x), the number of terms w, and represents the undetected error probability P _ud code.
The minimum Hamming distance d _min , the generator polynomial G (x), the number of terms w, and the code of the codes generated using the generator polynomial in the comparative example in the data in the 8th to 11th columns of Table 1-A to Table 1-C Represents the undetected error probability P _ud of.
In Tables 1-A to 1-C, the “-” symbol is a part for which the generator polynomial selected by performing the above search has already been proposed in other literature, and the part is shown in Table 2 for reference. Show.

The generator polynomial G (x) shown as an embodiment of the present invention is n _min (r, Max.d
_min ) ≦ n ≦ n _max (r, Max.d _min ), d _min = Max. d _min
Furthermore, the number w of terms is the smallest among the generator polynomials G (x), and the generator undetected error probability P _ud is the lowest among the generator polynomials G (x).

Further, FIGS. 10 and 11 show characteristics (n−P _ud characteristics) between the code length n and the undetected error probability P _ud of the code in 16-bit CRC and 8-bit CRC, respectively.
In this example, the generator polynomial G (x), the number of terms w, Max. d _{min represents a} constant code length range n _min ≤ n ≤ n _max. If "new" is shown at the end, the present invention, what is enclosed in "[]" has already been proposed in other literature The number represents the document number.

  Examples of the generator polynomial G (x) obtained as described above are organized and listed below.

(1) When the order r = 3 and the code length n = 4, the generator polynomial G (x) = x ³ + x ² + x + 1.
(2) When the order r = 4 and the code length n is 6 ≦ n ≦ 7, the generator polynomial G (x) = x ⁴ + x ² + x + 1 (reciprocal polynomial: x ⁴ + x ³ + x ² +1).
(3) When the order r = 6 and the code length n = 7, the generator polynomial G (x) = x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x + 1.
(4) When the order r = 6 and the code length n = 8, the generator polynomial G (x) = x ⁶ + x ⁴ + x ² + x + 1 (reciprocal polynomial: x ⁶ + x ⁵ + x ⁴ + x ² +1).
(5) When the order r = 6 and the code length n = 8, the generator polynomial G (x) = x ⁶ + x ⁴ + x ³ + x + 1 (reciprocal polynomial: x ⁶ + x ⁵ + x ³ + x ² +1).
(6) When the order r = 6 and the code length n = 8, the generator polynomial G (x) = x ⁶ + x ⁵ + x ³ + x + 1.
(7) When the order r = 6 and the code length n is 9 ≦ n ≦ 31, the generator polynomial G (x) = x ⁶ + x ² + x + 1 (reciprocal polynomial: x ⁶ + x ⁵ + x ⁴ +1).
(8) When the order r = 8 and the code length n = 9, the generator polynomial G (x) = x ⁸ + x ⁷ + x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x + 1.
(9) When the order r = 8 and the code length n is 10 ≦ n ≦ 12,
The generator polynomial G (x) = x ⁸ + x ⁵ + x ⁴ + x ³ + x + 1 (reciprocal polynomial: x ⁸ + x ⁷ + x ⁵ + x ⁴ + x ³ +1).
(10) When the order r = 8 and the code length n is 10 ≦ n ≦ 12,
Generator polynomial ^{G (x) = x 8 +} x 6 + x 3 + x 2 + x + 1: a (reciprocal polynomial ^{x 8 + x 7 + x 6} + x 5 + x 2 +1).
(11) When the order r = 8 and the code length n is 18 ≦ n ≦ 127, the generator polynomial G (x) = x ⁸ + x ⁴ + x + 1 (reciprocal polynomial: x ⁸ + x ⁷ + x ⁴ +1).
(12) When the order r = 8 and the code length n is n ≧ 128, the generator polynomial G (x) = x ⁸ + x ⁵ + x ³ + x ² +1 (reciprocal polynomial: x ⁸ + x ⁶ + x ⁵ + x ³ +1) .
(13) When the order r = 10 and the code length n = n = 11, the generator polynomial G (x) = x ¹⁰ + x ⁹ + x ⁸ + x ⁷ + x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x + 1.
(14) When the order r = 10 and the code length n is n = 12, the generator polynomial G (x) = x ¹⁰ + x ⁸ + x ⁶ + x ⁴ + x ³ + x ² + x + 1 (reciprocal polynomial: x ¹⁰ + x ⁹ + x ⁸ + x ⁷ + X ⁶ + x ⁴ + x ² +1).
(15) When the order r = 10 and the code length n is 23 ≦ n ≦ 31, the generator polynomial G (x) = x ¹⁰ + x ⁹ + x ³ + x + 1 (reciprocal polynomial: x ¹⁰ + x ⁹ + x ⁷ + x + 1).
(16) When the order r = 10 and the code length n is 32 ≦ n ≦ 511, the generator polynomial G (x) = x ¹⁰ + x ⁵ + x ² +1 (reciprocal polynomial: x ¹⁰ + x ⁸ + x ⁵ +1).
(17) When the order r = 10 and the code length n is n ≧ 512, the generator polynomial G (x) = x ¹⁰ + x ³ +1 (reciprocal polynomial: x ¹⁰ + x ⁷ +1).
(18) When the order r = 12 and the code length n is n = 13, the generator polynomial G (x) = x ¹² + x ¹¹ + x ¹⁰ + x ⁹ + x ⁸ + x ⁷ + x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x + 1 .
(19) degree r = 12, when the code length n is n = 14, generator polynomial ^{G (x) = x 12 +} x 10 + x 8 + x 6 + x 4 + x 3 + x 2 + x + 1 ( reciprocal ^{polynomial: x 12 + x 11 + x} 10 + X ⁹ + x ⁸ + x ⁶ + x ⁴ + x ² +1).
(20) When the order r = 12, and the code length n is 24 ≦ n ≦ 39, the generator polynomial G (x) = x ¹² + x ¹¹ + x ⁷ + x ³ + x + 1 (reciprocal polynomial: x ¹² + x ¹¹ + x ⁹ + x ⁵ + x + 1) It is.
(21) When the order r = 12, and the code length n is 40 ≦ n ≦ 65, the generator polynomial G (x) = x ¹² + x ¹⁰ + x ⁷ + x ⁶ + x ⁵ + x ² +1.
(22) When the order r = 12, and the code length n is 66 ≦ n ≦ 2047, the generator polynomial G (x) = x ¹² + x ⁷ + x ² +1 (reciprocal polynomial: x ¹² + x ¹⁰ + x ⁵ +1).
(23) When the order r = 12, and the code length n is n ≧ 2048, the generator polynomial G (x) = x ¹² + x ⁷ + x ⁶ + x ⁴ +1 (reciprocal polynomial: x ¹² + x ⁸ + x ⁶ + x ⁵ +1) .
(24) When the order r = 14 and the code length n is n = 15, the generator polynomial G (x) = x ¹⁴ + x ¹³ + x ¹² + x ¹¹ + x ¹⁰ + x ⁹ + x ⁸ + x ⁷ + x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x + 1.
(25) When the order r = 14 and the code length n is n = 16, the generator polynomial G (x) = x ¹⁴ + x ¹² + x ¹⁰ + x ⁹ + x ⁷ + x ⁵ + x ⁴ + x ³ + x + 1 (reciprocal polynomial: x ¹⁴ + x ¹³ + X ¹¹ + x ¹⁰ + x ⁹ + x ⁷ + x ⁵ + x ⁴ + x ² +1).
(26) When the order r = 14 and the code length n is n = 17, the generator polynomial G (x) = x ¹⁴ + x ¹¹ + x ⁸ + x ⁶ + x ⁵ + x ³ + x ² + x + 1 (reciprocal polynomial: x ¹⁴ + x ¹³ + x ^{12 + x 11 + x 9 + x} 8 + x 6 + x 3 +1) is.
(27) When the order r = 14 and the code length n is 28 ≦ n ≦ 71, the generator polynomial G (x) = x ¹⁴ + x ¹⁰ + x ⁹ + x ⁶ + x ² +1 (reciprocal polynomial: x ¹⁴ + x ¹² + x ⁸ + x ⁵ + X ⁴ +1).
(28) When the order r = 14 and the code length n is 72 ≦ n ≦ 127, the generator polynomial G (x) = x ¹⁴ + x ¹¹ + x ⁵ + x ³ +1 (reciprocal polynomial: x ¹⁴ + x ¹¹ + x ⁹ + x ³ +1) It is.
(29) the order r = 14, when the code length n is 128 ≦ n ≦ 8191, generator polynomial ^{G (x) = x 14 +} x 5 + x 2 +1: a (reciprocal polynomial ^{x 14 + x 12 + x 9} +1).
(30) When the order r = 14 and the code length n is n ≧ 8192, the generator polynomial G (x) = x ¹⁴ + x ⁶ + x ⁴ + x + 1 (reciprocal polynomial: x ¹⁴ + x ¹³ + x ¹⁰ + x ⁸ +1).
(31) When the order r = 16 and the code length n is n = 17, the generator polynomial G (x) = x ¹⁶ + x ¹⁵ + x ¹⁴ + x ¹³ + x ¹² + x ¹¹ + x ¹⁰ + x ⁹ + x ⁸ + x ⁷ + x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x + 1.
(32) When the order r = 16 and the code length n is n = 18, the generator polynomial G (x) = x ¹⁶ + x ¹⁴ + x ¹² + x ¹⁰ + x ⁸ + x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x + 1 (reciprocal polynomial: ^{x 16 + x 15 + x 14} + x 13 + x 12 + x 11 + x 10 + x 8 + x 6 + x 4 + x 2 +1) is.
(33) When the order r = 16 and the code length n is 19 ≦ n ≦ 21, the generator polynomial G (x) = x ¹⁶ + x ¹³ + x ¹² + x ⁹ + x ⁷ + x ⁶ + x ⁵ + x ⁴ + x ² +1 (reciprocal polynomial: ^{x 16 + x 14 + x 12} + x 11 + x 10 + x 9 + x 7 + x 4 + x 3 +1) is.
(34) When the order r = 16 and the code length n is 19 ≦ n ≦ 21, the generator polynomial G (x) = x ¹⁶ + x ¹³ + x ¹² + x ⁹ + x ⁷ + x ⁵ + x ⁴ + x ³ + x ² +1 (reciprocal polynomial: ^{x 16 + x 14 + x 13} + x 12 + x 11 + x 9 + x 7 + x 4 + x 3 +1) is.
(35) When the order r = 16 and the code length n is n = 22, the generator polynomial G (x) = x ¹⁶ + x ¹³ + x ⁸ + x ⁷ + x ⁶ + x ⁴ + x ² + x + 1 (reciprocal polynomial: x ¹⁶ + x ¹⁵ + x ¹⁴ a ^{+ x 12 + x 10 + x} 9 + x 8 + x 3 +1).
(36) When the order r = 16 and the code length n is 23 ≦ n ≦ 31, the generator polynomial G (x) = x ¹⁶ + x ¹³ + x ¹¹ + x ⁵ + x ³ + x ² + x + 1 (reciprocal polynomial: x ¹⁶ + x ¹⁵ + x ¹⁴ + X ¹³ + x ¹¹ + x ⁵ + x ³ +1).
(37) When the order r = 16 and the code length n is 36 ≦ n ≦ 151, the generator polynomial G (x) = x ¹⁶ + x ¹⁵ + x ¹³ + x ⁸ + x ⁵ + x ³ + x + 1 (reciprocal polynomial: x ¹⁶ + x ¹⁵ + x ^{13 + x 11 + x 8 + x} 3 + x + 1) it is.
(38) When the order r = 16 and the code length n is 152 ≦ n ≦ 257, the generator polynomial G (x) = x ¹⁶ + x ¹⁵ + x ⁸ + x + 1.
(39) the order r = 16, when the code length n is 258 ≦ n ≦ 32767, generator polynomial ^{G (x) = x 16 +} x 13 + x 2 +1: a (reciprocal polynomial ^{x 16 + x 14 + x 3} +1).
(40) When the order r = 16 and the code length n is n ≧ 32768, the generator polynomial G (x) = x ¹⁶ + x ⁹ + x ⁷ + x ⁴ +1 (reciprocal polynomial: x ¹⁶ + x ¹² + x ⁹ + x ⁷ +1) .

As described above, according to the embodiment of the present invention, the generator polynomial G (x) conforming to various conditions can be obtained.
Note that the generator polynomials G (x) listed above can be organized into two parts when the code length n is n _min = n _max and when n _min ≠ n _max .

CRC Encoding Method and CRC Encoding Circuit The generator polynomial G (x) described above can be applied to, for example, the CRC parity generator 110 shown in FIG. 2 or the CRC parity checker 341 shown in FIG.
For example, the CRC parity generator 110 shown in FIG. 2 includes a shift register and an exclusive OR circuit provided according to the order of the generator polynomial G (x) as shown in FIG. 3 or FIG. Connect cyclically. The exclusive OR circuit is provided according to the coefficient of the generator polynomial G (x), and the output of the exclusive OR circuit at the final stage, for example, the second exclusive OR circuit EXOR2 of FIG. The circuit configuration is input to the exclusive OR circuit.
Thus, when the generator polynomial G (x) is obtained as described above, the CRC encoding circuit can be easily configured using the shift register and the exclusive OR circuit.
The same applies to the CRC parity checker 341.

As can be understood from Tables 1-A to 1-C and the examples of FIGS. 10 and 11, the generator polynomial of the comparative example widely used so far has a limit value (Bound) in a certain code length range. In the other portions, the minimum hamming distance (d _min ) / undetected error probability (P _ud ) characteristics of the code are greatly deteriorated compared to the limit value.
In comparison, in the embodiment based on the selection method according to the present invention, characteristics close to the limit value can be obtained for all code lengths n.

  As described above, by using the CRC encoding method generated by using the generator polynomial according to the preferred embodiment of the present invention, a desired parity bit can be obtained as compared with the case of using a generator polynomial widely used conventionally. In the code length, the undetected error probability of the code can be kept low, and the random error detection capability can be maximized by taking the maximum value of the minimum hamming distance of the code.

Furthermore, the generator polynomial G (x) is d _min = Max. In the code length range of n _min (r, Max.d _min ) ≦ n ≦ n _max (r, Max.d _min ). Since d _min and P _ud ≈limit value (Bound) are satisfied, even if the code length n changes, it is possible to cope with a single generator polynomial as long as it is within this code length range.

Furthermore, in the code length range of n _min (r, Max.d _min ) ≦ n ≦ n _max (r, Max.d _min ), the generator polynomial G in which the minimum hamming distance (d _min ) of the code always takes the maximum value. In (x), the one with the minimum number of terms w is used, so that the circuit scale when mounted on the circuit can be reduced.

Further, if the code length n and the undetected error probability P _{ud of the} code are determined, the number of parity (order r) necessary to satisfy the code length n can be known. Therefore, the generator polynomial G selected for the parity number r and the code length n. By using (x), a desired undetected error probability can be realized.

FIG. 1 is a diagram showing an example of the configuration of a transmission apparatus and a reception apparatus as an example to which the CRC encoding method and the CRC encoding apparatus of the present invention are applied. FIG. 2 is a diagram illustrating a configuration example of a CRC encoder in the transmission apparatus of FIG. FIG. 3 is a diagram showing a first configuration example of a CRC parity generator in the CRC encoder illustrated in FIG. FIG. 4 is a diagram showing a second configuration example of the CRC parity generator in the CRC encoder illustrated in FIG. FIG. 5 is a diagram showing a configuration example of a CRC detector in the receiving apparatus of FIG. FIG. 6 is a diagram showing a configuration example of a CRC parity checker constituting the CRC detector illustrated in FIG. FIG. 7 shows the minimum hamming distance maximum value Max. It is a graph which shows the n- _Pud characteristic which shows the change of the code undetected error probability _Pud (vertical axis) in the code length n (horizontal axis) where _dmin changes. FIG. 8 is a flowchart showing an example of the processing contents of the CRC code selection method of the present invention. FIG. 9 is a flowchart showing a partial detailed process in the flowchart illustrated in FIG. FIG. 10 is a graph showing n-P _ud characteristics for an example of the present invention and a comparative example in 16-bit CRC. FIG. 11 is a graph showing n-P _ud characteristics for an example of the present invention and a comparative example in 8-bit CRC.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 ... Transmitting device 11 ... CRC encoder
110: CRC parity generator, 111: First selector
DESCRIPTION OF SYMBOLS 112 ... 2nd selector, 113 ... Bit number counter 12 ... Error correction encoder, 13 ... Transmission path encoder 2 ... Transmission path 3 ... Reception apparatus 31 ... Code detector, 32 ... Transmission path decoder, 33 ... Error correction decoding 34 ... CRC detector
341 ... CRC parity checker, 342 ... comparator

Claims (9)

A method of selecting a generator polynomial used to CRC check a CRC code and / or CRC code result, comprising:
Maximum / minimum which is the maximum value of the minimum hamming distance (d _min ) in each code length (n) of a code having a code length (n) having k-bit information words to which r-bit parity is added. A first step for obtaining a Hamming distance (Max.d _min );
The code length (n) in which the maximum / minimum Hamming distance (Max.d _min ) of the code changes is obtained, and the range of the code length n (n _min (r, Max.d _min ) ≦ n ≦ n _max (r, Max) .D _min )) second step,
In the range of the code length (n) (n _min (r, Max. D _min ) ≦ n ≦ n _max (r, Max. D _min )), the minimum hamming distance (d _min ) of the code is always the maximum / minimum. A third step of finding a generator polynomial (G (x)) satisfying a condition (d _min = Max.d _min ) equal to the Hamming distance (Max.d _min ) by full search;
A CRC generating polynomial comprising: a fourth step of selecting the number of terms (w) and the minimum undetected error probability (P _ud ) of the code from the generating polynomial (G (x)) found by the full search How to choose. The third and fourth steps include
The period (p) is not less than the maximum code length (n _max (r, Max. D _min )) (p ≧ n _max (r, Max. D _min )) and (n _max , n _max −r) a step of finding a full search for the minimum Hamming distance (d _min) is the generator polynomial G satisfying the maximum and minimum Hamming distance (Max.d _min) equal conditions _{(d min = Max.d min) (} x) for code,
Selecting a generator polynomial (G (x)) having the smallest number of terms (w) from generator polynomials (G (x)) found by the full search;
For the selected generator polynomial (G (x)), finding a generator polynomial (G (x)) that minimizes the undetected error probability (P _ud ) of the code;
Having
The CRC generator polynomial selection method according to claim 1. In the step of searching and selecting the generator polynomial G (x), the maximum / minimum Hamming distance (Max.d _min ) is Max. For d _min = 2, in the generator polynomial G (x) whose period (p) has the maximum period 2 ^r −1 (which is a primitive polynomial), the number of terms w of the generator polynomial and the undetected error of the code The method for selecting a CRC generator polynomial according to claim 2, wherein a generator polynomial G (x) having a minimum probability P _ud is selected. In any one of claims 1 to 3, a n _min ≠ n _max,
CRC generator polynomial selection method. A method for selecting a CRC generator polynomial, wherein one of the following generator polynomials G (x) is selected by the method for selecting a CRC generator polynomial according to claim 1.
1. When r = 3 and n = 4, the generator polynomial G (x) = x ³ + x ² + x + 1.
2. When r = 6 and n = 7, the generator polynomial G (x) = x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x + 1.
3. When r = 6 and n = 8, the generator polynomial G (x) = x ⁶ + x ⁴ + x ² + x + 1 (reciprocal polynomial: x ⁶ + x ⁵ + x ⁴ + x ² +1).
4). When r = 6 and n = 8, the generator polynomial G (x) = x ⁶ + x ⁴ + x ³ + x + 1 (reciprocal polynomial: x ⁶ + x ⁵ + x ³ + x ² +1).
5. When r = 6 and n = 8, the generator polynomial G (x) = x ⁶ + x ⁵ + x ³ + x + 1.
6). When r = 8 and n = 9, the generator polynomial G (x) = x ⁸ + x ⁷ + x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x + 1.
7). When r = 10 and n = 11, the generator polynomial G (x) = x ¹⁰ + x ⁹ + x ⁸ + x ⁷ + x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x + 1
8). When r = 10 and n = 12, the generator polynomial G (x) = x ¹⁰ + x ⁸ + x ⁶ + x ⁴ + x ³ + x ² + x + 1 (reciprocal polynomial: x ¹⁰ + x ⁹ + x ⁸ + x ⁷ + x ⁶ + x ⁴ + x ² +1) Is,
9. When r = 12, n = 13, the generator polynomial G (x) = x ¹² + x ¹¹ + x ¹⁰ + x ⁹ + x ⁸ + x ⁷ + x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x + 1
10. When r = 12, n = 14, the generator polynomial G (x) = x ¹² + x ¹⁰ + x ⁸ + x ⁶ + x ⁴ + x ³ + x ² + x + 1 (reciprocal polynomial: x ¹² + x ¹¹ + x ¹⁰ + x ⁹ + x ⁸ + x ⁶ + x ⁴ + X ² +1),
11. When r = 14 and n = 15, the generator polynomial G (x) = x ¹⁴ + x ¹³ + x ¹² + x ¹¹ + x ¹⁰ + x ⁹ + x ⁸ + x ⁷ + x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x + 1
12 When r = 14 and n = 16, the generator polynomial G (x) = x ¹⁴ + x ¹² + x ¹⁰ + x ⁹ + x ⁷ + x ⁵ + x ⁴ + x ³ + x + 1 (reciprocal polynomial: x ¹⁴ + x ¹³ + x ¹¹ + x ¹⁰ + x ⁹ + x ⁷ + X ⁵ + x ⁴ + x ² +1),
13. When r = 14 and n = 17, the generator polynomial G (x) = x ¹⁴ + x ¹¹ + x ⁸ + x ⁶ + x ⁵ + x ³ + x ² + x + 1 (reciprocal polynomial: x ¹⁴ + x ¹³ + x ¹² + x ¹¹ + x ⁹ + x ⁸ + x ⁶ + X ³ +1),
14 When r = 16 and n = 17, the generator polynomial G (x) = x ¹⁶ + x ¹⁵ + x ¹⁴ + x ¹³ + x ¹² + x ¹¹ + x ¹⁰ + x ⁹ + x ⁸ + x ⁷ + x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x + 1 ,
15. When r = 16 and n = 18, the generator polynomial G (x) = x ¹⁶ + x ¹⁴ + x ¹² + x ¹⁰ + x ⁸ + x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x + 1 (reciprocal polynomial: x ¹⁶ + x ¹⁵ + x ¹⁴ + x ¹³ + X ¹² + x ¹¹ + x ¹⁰ + x ⁸ + x ⁶ + x ⁴ + x ² +1)
16. When r = 16 and n = 22, the generator polynomial G (x) = x ¹⁶ + x ¹³ + x ⁸ + x ⁷ + x ⁶ + x ⁴ + x ² + x + 1 (reciprocal polynomial: x ¹⁶ + x ¹⁵ + x ¹⁴ + x ¹² + x ¹⁰ + x ⁹ + x ⁸ + X ³ +1). The method for selecting a CRC generator polynomial according to claim 4, wherein one of the following generator polynomials G (x) is selected.
1. When r = 4 and 6 ≦ n ≦ 7, the generator polynomial G (x) = x ⁴ + x ² + x + 1 (reciprocal polynomial: x ⁴ + x ³ + x ² +1).
2. When r = 6 and 9 ≦ n ≦ 31, the generator polynomial G (x) = x ⁶ + x ² + x + 1 (reciprocal polynomial: x ⁶ + x ⁵ + x ⁴ +1).
3. When r = 8 and 10 ≦ n ≦ 12, the generator polynomial G (x) = x ⁸ + x ⁵ + x ⁴ + x ³ + x + 1 (reciprocal polynomial: x ⁸ + x ⁷ + x ⁵ + x ⁴ + x ³ +1).
4). When r = 8 and 10 ≦ n ≦ 12, the generator polynomial G (x) = x ⁸ + x ⁶ + x ³ + x ² + x + 1 (reciprocal polynomial: x ⁸ + x ⁷ + x ⁶ + x ⁵ + x ² +1).
5. When r = 8 and 18 ≦ n ≦ 127, the generator polynomial G (x) = x ⁸ + x ⁴ + x + 1 (reciprocal polynomial: x ⁸ + x ⁷ + x ⁴ +1).
6). When r = 8 and n ≧ 128, the generator polynomial G (x) = x ⁸ + x ⁵ + x ³ + x ² +1 (reciprocal polynomial: x ⁸ + x ⁶ + x ⁵ + x ³ +1).
7). When r = 10 and 23 ≦ n ≦ 31, the generator polynomial G (x) = x ¹⁰ + x ⁹ + x ³ + x + 1 (reciprocal polynomial: x ¹⁰ + x ⁹ + x ⁷ + x + 1).
8). When r = 10 and 32 ≦ n ≦ 511, the generator polynomial G (x) = x ¹⁰ + x ⁵ + x ² +1 (reciprocal polynomial: x ¹⁰ + x ⁸ + x ⁵ +1).
9. When r = 10 and n ≧ 512, the generator polynomial G (x) = x ¹⁰ + x ³ +1 (reciprocal polynomial: x ¹⁰ + x ⁷ +1).
10. When r = 12, 24 ≦ n ≦ 39, the generator polynomial G (x) = x ¹² + x ¹¹ + x ⁷ + x ³ + x + 1 (reciprocal polynomial: x ¹² + x ¹¹ + x ⁹ + x ⁵ + x + 1).
11. When r = 12, 40 ≦ n ≦ 65, the generator polynomial G (x) = x ¹² + x ¹⁰ + x ⁷ + x ⁶ + x ⁵ + x ² +1.
12 When r = 12, 66 ≦ n ≦ 2047, the generator polynomial G (x) = x ¹² + x ⁷ + x ² +1 (reciprocal polynomial: x ¹² + x ¹⁰ + x ⁵ +1).
13. When r = 12, n ≧ 2048, the generator polynomial G (x) = x ¹² + x ⁷ + x ⁶ + x ⁴ +1 (reciprocal polynomial: x ¹² + x ⁸ + x ⁶ + x ⁵ +1).
14 When r = 14 and 28 ≦ n ≦ 71, the generator polynomial G (x) = x ¹⁴ + x ¹⁰ + x ⁹ + x ⁶ + x ² +1 (reciprocal polynomial: x ¹⁴ + x ¹² + x ⁸ + x ⁵ + x ⁴ +1).
15. When r = 14 and 72 ≦ n ≦ 127, the generator polynomial G (x) = x ¹⁴ + x ¹¹ + x ⁵ + x ³ +1 (reciprocal polynomial: x ¹⁴ + x ¹¹ + x ⁹ + x ³ +1).
16. When r = 14 and 128 ≦ n ≦ 8191, the generator polynomial G (x) = x ¹⁴ + x ⁵ + x ² +1 (reciprocal polynomial: x ¹⁴ + x ¹² + x ⁹ +1).
17. When r = 14 and n ≧ 8192, the generator polynomial G (x) = x ¹⁴ + x ⁶ + x ⁴ + x + 1 (reciprocal polynomial: x ¹⁴ + x ¹³ + x ¹⁰ + x ⁸ +1).
18. When r = 16 and 19 ≦ n ≦ 21, the generator polynomial G (x) = x ¹⁶ + x ¹³ + x ¹² + x ⁹ + x ⁷ + x ⁶ + x ⁵ + x ⁴ + x ² +1 (reciprocal polynomial: x ¹⁶ + x ¹⁴ + x ¹² + x ¹¹ + X ¹⁰ + x ⁹ + x ⁷ + x ⁴ + x ³ +1)
19. When r = 16 and 19 ≦ n ≦ 21, the generator polynomial G (x) = x ¹⁶ + x ¹³ + x ¹² + x ⁹ + x ⁷ + x ⁵ + x ⁴ + x ³ + x ² +1 (reciprocal polynomial: x ¹⁶ + x ¹⁴ + x ¹³ + x ¹² + X ¹¹ + x ⁹ + x ⁷ + x ⁴ + x ³ +1)
20. When r = 16 and 23 ≦ n ≦ 31, the generator polynomial G (x) = x ¹⁶ + x ¹³ + x ¹¹ + x ⁵ + x ³ + x ² + x + 1 (reciprocal polynomial: x ¹⁶ + x ¹⁵ + x ¹⁴ + x ¹³ + x ¹¹ + x ⁵ + x ³ +1),
21. When r = 16, 36 ≦ n ≦ 151, the generator polynomial G (x) = x ¹⁶ + x ¹⁵ + x ¹³ + x ⁸ + x ⁵ + x ³ + x + 1 (reciprocal polynomial: x ¹⁶ + x ¹⁵ + x ¹³ + x ¹¹ + x ⁸ + x ³ + x + 1) Is,
22. When r = 16 and 152 ≦ n ≦ 257, the generator polynomial G (x) = x ¹⁶ + x ¹⁵ + x ⁸ + x + 1.
23. When r = ¹⁶ , 258 ≦ n ≦ 32767, the generator polynomial G (x) = x ¹⁶ + x ¹³ + x ² +1 (reciprocal polynomial: x ¹⁶ + x ¹⁴ + x ³ +1).
24. When r = 16 and n ≧ 32768, the generator polynomial G (x) = x ¹⁶ + x ⁹ + x ⁷ + x ⁴ +1 (reciprocal polynomial: x ¹⁶ + x ¹² + x ⁹ + x ⁷ +1).   A CRC encoding method for performing CRC encoding using the generator polynomial G (x) selected according to any one of claims 1 to 6. The generator polynomial G (x) selected according to any one of claims 1 to 6 is cyclically connected to a shift register and an exclusive OR circuit provided according to the coefficient of the generator polynomial G (x); The circuit configuration is such that the output of the exclusive OR circuit at the final stage is input to the exclusive OR circuit provided according to the coefficient of the generator polynomial G (x).
CRC encoding circuit. A CRC encoding method for encoding a CRC code having a code length n using a generator polynomial G (x) of degree (parity number) r and period p,
The minimum Hamming distance maximum value Max. Of the CRC code defined by the code length n and the order r. d _min , the minimum hamming distance of the code Max. When the range of code length n where d _min is constant is defined as n _min ≦ n ≦ n _max (where n _min is the minimum code length and n _max is the maximum code length), period p ≧ maximum code length n _max or period p = 2 ^r −1 and n _min ≦ n ≦ n _max
The minimum hamming distance d _{min of the} code is d _min = Max. Among generator polynomials G (x) satisfying _dmin , the generator polynomial G (x) has the smallest number of terms in the generator polynomial G (x) and the smallest undetected error probability of the code in the two-dimensional symmetric channel. ),
CRC encoding method.

Images