Error correction structures and methods

Details Error correction structures and methods Error correction structures and methods

2001-02-20

2004-05-11

Decady, Albert (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S781000

Reexamination Certificate

active

06735737

ABSTRACT:

BACKGROUND OF THE INVENTION
The invention relates to electronic devices, and, more particularly, to error correction structures and methods.
Digital communication and storage systems typically include error correction coding in order to overcome errors arising from the transmission or storage medium. Forward error-correction coding (FEC) systems add redundancy to the transmitted signal so that the receiver can detect and correct errors using only the received signal. This eliminates the need for the receiver to send requests for retransmission to the transmitter.
FIGS. 1-2
are high level views of a FEC system. In particular,
FIG. 1
shows a block of information symbols, I, transformed into a codeword C which is a larger block that contains both the original information and redundant symbols. After transmission over a channel, the received block of symbols can be represented as C+E where E is a block of error symbols. The decoder generates I′ from C+E, and I′ will equal I if the number of errors symbols in E is within the correction capabilities of the code.
FIG. 2
shows a more detailed description of the coding. A block of bk information bits is divided into k groups of b bits and each group of b bits represents a symbol, producing a block of k information symbols for coding. The encoder operates on the block of k information symbols to produce a codeword block of n symbols containing the original information in some form as well as redundancy. The code can be designed so that the redundancy is used for error detection only, error correction only, or a combination of some error detection and some error correction. The codeword block of n symbols is then translated into a block of bn bits and transmitted over the channel. The receiver front-end produces a block of bn bits that might be corrupted, depending upon the amount of channel distortion. The block of bn bits is translated into a block of n symbols and processed with the decoder. As long as the transmission errors lead to at most t=(n−k)/2 erroneous symbols, a hard-decision decoder can reliably recover the input k information symbols (and thus the input bk bits). The price paid for the added redundancy is the increase in the number of symbols to transmit by a factor of n/k. Of course, this means an information decrease by a factor of k
for a constant transmission rate.
One of the more popular error correction code types is BCH codes which are cyclic block codes that utilize Galois fields beyond the simplest GF(2) (the usual binary {0,1}) to prescribe code generator polynomials. Indeed, a BCH code uses a minimal degree generator polynomial with roots being a sequence of powers of a primitive element of a Galois field which may be an extension field of the symbol field (codeword components field). This leads to computations involving multiplications of Galois field elements for the usual decoding steps of syndrome calculation, association with error pattern (determine error-locator polynomial and error locations and values), and error correction. Reed-Solomon codes are a subclass of BCH codes with both symbols and generator polynomial roots in the same field GF(p
m
). The commonly used field GF(2
m
) allows the elements to be represented as m-bit words.
The nonzero elements of a Galois field form a cyclic multiplicative subgroup and can be expressed as powers of a primitive element &agr;. That is, the elements of GF(p
m
) are {0, 1, &agr;, &agr;
2
, . . . , &agr;
q
} where the maximum q=p
m
−2 and &agr;
q+1
=1. Thus the roots of a generator polynomial G(x) for a BCH code could be {&agr;, &agr;
2
, . . . , &agr;
2t
} for a code which can correct t errors per codeword. The generator polynomial thus would be the least common multiple of the polynomials &phgr;
j
(x) for j=1, 2, . . . , 2t where &phgr;
j
(x) is a minimal polynomial for &agr;
j
. The special case of the symbol field being the same as the root field (Reed-Solomon codes) implies &phgr;
j
(x) is simply x−&agr;
j
.
Systematic BCH encoding, as with cyclic codes in general, forms codewords by concatenating the k information symbols with n−k parity symbols which are computed according to x
n−k
I(x) modG(x). The additional n−k parity symbols contain the redundant information that is used by the receiver to choose the most likely transmitted k information symbols. In particular, with receiver soft decision the n−k parity symbols can be used to correct t error symbols and detect s erased symbols provided 2t+s is at most equal to n−k. Note that values such as n=204 and k=188 with the field GF(2
8
) in a Reed-Solomon code is a commonly used (shortened) code for high speed modems. Such a (204, 188) code can correct 8 error symbols per 204-symbol codeword. Similarly, the (200, 192) code can correct 4 errors per 200-symbol codeword.
FIG. 3
is a flow chart for a commonly-used method of errors-only decoding BCH coded information and which proceeds as follows. Take n−k=2t so that at most t errors can be corrected in a codeword of n symbols. The received polynomial R(x)=C(x)+E(x) where C(x) is the codeword polynomial and E(x) is the error polynomial. E(x)=&Sgr;
j
e
j
x
j
with a non-zero e
j
the error occurring in the jth position (symbol) of C(x). The decoder is to find the error positions and values to reconstruct E(x) and then recover C(x) as R(x)−E(x). The method first evaluates R(x)=r
0
x
n−1
+r
1
x
n−2
+ . . . +r
n−1
at the 2t roots of the code generator polynomial (G(x)=&pgr;
j
(x−&agr;
j
) for Reed-Solomon) and denotes these 2t evaluations as the syndromes S
0
, S
1
, S
2
, . . . , S
2t−1
. That is, with the roots of G(x) being &agr;
j
for j=0, 1, 2, . . . , 2t−1 (which are denoted &bgr;
0
, &bgr;
1
, &bgr;
2
, . . . , &bgr;
2t−1
, respectively) the syndromes are (with * denoting Galois field multiplication):
S
0
=r
0
*&bgr;
0
n−1
+r
1
*&bgr;
0
n−2
+r
2
*&bgr;
0
n−3
+ . . . +r
n−2
*&bgr;
0
+r
n−1
S
1
=r
0
*&bgr;
1
n−1
+r
1
*&bgr;
1
n−2
+r
2
*&bgr;
1
n−3
+ . . . +r
n−2
*&bgr;
1
+r
n−1
 
S
2t−1
=r
0
*&bgr;
2t−1
n−1
+r
1
*&bgr;
2t−1
n−2
+r
2
*&bgr;
2t−1
n−3
+ . . . +r
n−2
*&bgr;
2t−1
+r
n−1
Because C(x) is a product of G(x), C(x) vanishes at each of the 2t roots of G(x), and the syndrome S
j
equals E(&bgr;
j
). Thus the 2t syndrome equations are nonlinear relations between the 2t syndromes, the at most t error locations, and the at most t error values; that is, 2t nonlinear equations for at most 2t unknowns.
Next, linearize these nonlinear syndrome equations by introduction of the error locator polynomial, &Lgr;(x)=&pgr;
m
(1+X
m
x)=1+&Sgr;
m
&Lgr;
m
x
m
, where X
m
is the mth error location. The error locator polynomial has degree equal to the (not-yet-known) number of errors. That is, X
m
=&agr;
j
for the mth j for which e
j
is nonzero, and the roots of &Lgr;(x) are the inverses of the error locations.
Multiplying the defining equation for &Lgr;(x) by the error values and powers of the error locations and summing leads to n−k−e linear equations for the e unknowns &Lgr;
j
with coefficients of these linear equations being an array of the syndromes S
0
to S
2e−2
and the inhomogeneous terms being the sequence of syndromes S
e
to S
2e−1
. The number of errors, e, is unknown, so the linear equations cannot be simply solved. Rather, the method of
FIG. 3
uses the iterative and inductive Berlekamp-Massey method to find the &Lgr;
j
.
Once the locator polynomial is known, find its roots (the inverses of the error locations) using the Chien search. The Chien search systematically evaluates the locator polynomial &Lgr;(x) at all no

Affiliated with

Also associated with

Rating

Error correction structures and methods does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Error correction structures and methods, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Error correction structures and methods will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3259514