Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-11-01
2003-10-28
Chung, Phung M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S762000, C714S759000, C714S758000
Reexamination Certificate
active
06640327
ABSTRACT:
FIELD OF THE INVENTION
This present invention relates to digital data error detection and correction, and more particularly to a method and apparatus for performing error detection and correction using cyclic codes.
BACKGROUND OF THE INVENTION
Cyclic codes are commonly used for digital signal error detection and error correction. Digital communication systems often employ cyclic code error correction to increase the reliability of information transmission. Digital magnetic and optical storage systems use cyclic code error correction to provide reliable storage and retrieval of data.
To create a cyclic codeword, a cyclic redundancy check (CRC) is calculated for a group of information bits. The CRC is then appended to the information bits to form a codeword, which is transmitted (or stored). A system receiving the codeword can use the CRC to detect (and correct a limited set of) errors that may have been introduced into the codeword during transmission (or storage and retrieval). The CRC thus allows corrupted codewords to be detected, and the original information bits to be recovered from a corrupted codeword in many common error situations.
Within the class of cyclic codes, BCH codes (named for Bose, Chaudhuri, and Hocquenghem, who discovered the basic properties of BCH codes) are used extensively. BCH codes are identified by their total length, n, and their information length, k, using the conventional notation BCH(n,k). For example, a BCH(
15
,
7
) code has an overall length of fifteen bits, seven of which are information bits. The remaining eight bits are CRC bits.
BCH error correction requires the calculation of one or more syndromes, both at the transmitter and at the receiver. Syndrome calculation is performed by dividing the codeword by a generator polynomial using modulo two arithmetic. The division requires one codeword shift and one codeword exclusive-or (XOR) operation for each information bit present. When the error correction technique further employs Fire code error trapping for burst error correction, additional shift and XOR operations may be required, depending upon the error location and pattern. The maximum number of additional shift and XOR operations required can be as large as the total number of bits in the codeword, minus one. The following example illustrates the steps performed in BCH burst error correction using the BCH(
15
,
7
) code.
The generator polynomial for the BCH(
15
,
7
) code is x
8
+x
7
+x
6
+x
4
+1, or 111010001. The variable x is used as a place holder. The transmit codeword CRC is calculated by first multiplying the information bits by x raised to the CRC length (in this case x
8
), which effectively appends a series of zeros equal in length to the CRC length, and second dividing this result by the generating polynomial. Assuming the information bits are, for example, 1001101, then the transmit codeword CRC is calculated as follows.
Multiplication by x
8
:
1001101
=
x
6
+
x
3
+
x
2
+
1
(
x
6
+
x
3
+
x
2
+
1
)
*
x
8
=
x
14
+
x
11
+
x
10
+
x
8
x
14
+
x
11
+
x
10
+
x
8
=
100110100000000
Division by generator polynomial:
The transmit codeword is calculated by multiplying the information bits by x raised to the CRC length and adding the CRC. In this example, the transmit codeword is:
The BCH(
15
,
7
) code can correct any burst error up 4 bits long. Assuming the transmit codeword is subjected to the burst error pattern 000110100000000, then the receive codeword will be:
The receiver corrects the receive codeword by first calculating the receive codeword's syndrome, and then, in case of burst error trapping, calculating additional syndromes until the error is trapped or all possible error locations have been tested. The receive codeword's syndrome is calculated by dividing it by the generator polynomial, as shown below for the BCH(
15
,
7
) example.
When the receiver performs burst error correction, the syndrome is iteratively multiplied by x and divided by the generator polynomial until the error is trapped in the syndrome. The error is trapped when the most significant bits (msb's) of the syndrome are all zero. The least significant bits (lsb's) then contain the error pattern, and the position of the error is given by the number of iterative divisions required to trap the error. The least significant bit field length is equal to the maximum burst error length which the code can correct. The most significant bits are the remaining bits. The total number of iterative divisions which may be required is equal to the codeword length minus one, then the iterative syndromes recycle starting with the initial syndrome.
For the BCH(
15
,
7
) example, the number of msb's is four, the number of lsb's is four, and the total number of iterative divisions required is fourteen. The following shows how the BCH(
15
,
7
) error would be trapped.
The error location is equal to the codeword length minus the iteration number modded with the codeword length.
error_location=(codeword_length−iteration_number)mod codeword_length
For the BCH(
15
,
7
) example above, this is equal to bit
8
.
8=(15−7)mod 15
The receive codeword is corrected by multiplying the error pattern by x raised to the error location and adding it to the receive codeword.
The corrected information is then extracted from the corrected codeword.
These bit-aligned operations are inefficient for both hardware and software implementations. Hardware requires one clock cycle per shift/XOR operation. For the case of burst correction BCH(
15
,
7
), this is a total of 21 clock cycles. In many systems, the system clock is the same frequency as the bit rate, and thus only fifteen clock cycles would be available to perform the error correction for the BCH(
15
,
7
) case. Software requires one iteration loop pass per shift/XOR operation, and thus would require 21 iterations for the BCH(
15
,
7
) case. Also, software algorithms are faster if they are byte aligned rather than bit aligned. Byte alignment removes the need for shifting altogether. Thus, for both hardware and software, a faster, non-bit aligned algorithm is desirable.
In U.S. Pat. No. 3,859,630, issued Jan. 7, 1975, to Bennett, a parallel cyclic code error correction apparatus is disclosed. The apparatus of the '630 patent accomplishes parallel cyclic encoding and decoding using read-only memory (ROM) banks instead of serial shift/XOR operations. The encoder and decoder each have a ROM bank that stores a CRC value for each possible information bit sequence. In addition, the decoder has a second ROM bank that stores an error bit pattern for each possible “error pattern” that can be formed by comparing a received CRC with a CRC based on the received information bits. The main drawback of this fully-parallel system is that the size of the ROM banks is impracticable for even moderately-sized cyclic coding schemes. For instance, a BCH(
127
,
120
) code would require approximately 1.33×10
36
ROM CRC entries in a '630 patent implementation.
SUMMARY OF THE INVENTION
The embodiments disclosed herein provide for fast cyclic code syndrome calculation and fast burst error trapping. These embodiments utilize a set of permuted generator polynomials, each representing shifted and exclusive-ored (XORed) versions of the cyclic code generator polynomial according to a specific input bit pattern. The permuted generator polynomial may be provided by look-up table, hardware, or a software equivalent of this hardware.
In one aspect of the invention, a method for calculating a syndrome is disclosed. Considering a generator polynomial G of length g+1, capable of correcting a t-bit burst error, and an associated n-bit cyclic error correction codeword C, containing a k-bit information field, such that g=n−k, the method comprises the following. A shift distance m, greater than one but less than or equal to k, is pre-selected, and an iteration counter j is initialized to zero. A length-m address A
j
is formed by stripping the m most significant bits (m
Chung Phung M.
Marger Johnson & McCollom
Sharp Laboratories of America Inc.
LandOfFree
Fast BCH error detection and correction using generator... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast BCH error detection and correction using generator..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast BCH error detection and correction using generator... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3170810