Accelerated Reed-Solomon error correction

Details Accelerated Reed-Solomon error correction Accelerated Reed-Solomon error correction

1999-11-24

2003-03-25

Tu, Christine T. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S781000

Reexamination Certificate

active

06539515

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the field of communication and data storage systems, and in particular to the decoding of communications that contain block-based error correction codes.
2. Description of Related Art
One of the parameters used to specify the quality of a digital communication system is the “Bit Error Ratio”, or BER. The BER specifies the probability that an erroneous bit is produced at the output of the receiving system. Specifications for storage devices (tapes, disk, CD, DVD, barcode), mobile communications (cellular telephone, microwave links), satellite communications, digital television, and the like, often require BERs in the order of 10
−9
or less. One technique for providing a low probability of error is to transmit the information using a high powered transmitter to achieve a high signal to noise ratio (SNR). This is often impractical or costly, particularly for mobile systems that use batteries to supply the transmit power, and broadcast systems that must conform to interference standards, such as published by the FCC.
An alternative method of achieving a high BER without relying on a high SNR is to encode the information with an error correcting code, so that when an error occurs during a transmission, it can be corrected by the receiver, and therefore will no longer be an “error”. Error correcting techniques are commonly available for automatically correcting multiple errors within a transmission.
A commonly used error correcting technique is a Reed-Solomon error correcting code. Using Reed-Solomon (R-S) terminology, fixed-length (n) codewords are transmitted, each codeword comprising k information symbols and n−k appended error correcting parity symbols. Each symbol comprises s bits. A R-S decoder can correct up to (n−k)/2 symbols that contain errors in a codeword. Because each of these correctable symbols may contain multiple bit-errors, the R-S encoding technique is particularly well suited for burst errors that affect multiple contiguous bits. A common R-S encoding scheme uses a codeword of 255 eight-bit symbols, 223 of which are information symbols, and the remaining 32 symbols are error correcting parity symbols. This encoding scheme will correct up to 16 erroneous symbols in every 255 codeword, thereby providing a substantial improvement in Bit Error Rate.
The R-S encoding scheme will also detect “erasures”, which are errors at known locations, and require less information to correct. The number of errors plus twice the number of erasures that an R-S decoder can correct is (n−k)/2. For ease of reference, the term “error” is used hereinafter to refer to either an error of unknown location or an erasure of known location.
FIG. 1
illustrates an example block diagram of a prior art R-S decoder
100
. The decoder
100
receives each codeword r(x)
101
, and produces a corrected codeword c(x)
151
. A syndrome calculator
110
processes the codeword
101
to produce corresponding syndrome polynomials Si(x)
111
. Each codeword has n−k syndromes that depend only on errors, and not on the transmitted codeword. From these syndromes
111
, an error locator polynomial &Lgr;(x)
121
is produced. Euclid's algorithm
120
is illustrated for providing the error locator polynomial
121
, and an error magnitude polynomial &OHgr;(x)
122
, although other techniques, such as the Berlekamp-Massey algorithm can be used as well. Each R-S code has a parameter a that is the primitive element of a Galois Field (GF) that is chosen for the R-S code. The error locator polynomial is structured such that if an error occurs at position p, a
−p
will be a root of the error polynomial (p is indexed from 0 to n−1).
An iterative approach is conventionally applied to test each value of a
−p
for each position p in the codeword, to determine if a
−p
is a root, X
k
−1
, of the error locator polynomial
121
. A commonly used algorithm for this iterative test is the Chien error locator
130
. The Chien locator
130
also provides a related error differential term, X
k
−1
&Lgr;′(X
k
−1
)
132
, that facilitates a determination of the magnitude
141
of the error, typically via the Forney error determination algorithm, as illustrated at block
140
. The error determinator
140
evaluates the error magnitude polynomial
122
corresponding to the located error symbol. For each error that the error locator
130
locates, an error corrector
150
determines the corrected codeword c(x)
151
, based on the location
131
and magnitude
141
of this error. If an error is not detected for a given symbol, the symbol in the corrected codeword c(x)
151
at this evaluated position is equal to the symbol in the received codeword r(x)
101
.
FIG. 2
illustrates an example block diagram of a prior art Chien error locator
130
. The error locator
130
includes a plurality of polynomial term evaluators
220
. Each evaluator
220
includes a register
221
and a coefficient multiplier
225
. The set of registers
221
receive the coefficients &lgr; of the error locator polynomial &Lgr;(x)
121
, and the set of coefficient multipliers
225
multiply the coefficients &lgr; by corresponding powers of a
222
and store the resultant product terms into the registers
221
. With regard to the output polynomial value
231
, the adders
230
a
,
230
b
, and
230
c
form a single adder that combines the product terms of each coefficient multiplier
225
. That is, initially the adders provide the sum of the coefficients &lgr;, corresponding to an evaluation of the error locator polynomial &Lgr;(x)
121
at a
0
(i.e. value=&lgr;
n−1
(a
0
)
n−1
+&lgr;
n−2
(a
0
)
n−2
+ . . . +&lgr;
2
(a
0
)
2
+&lgr;
1
(a
0
)
1
+(a
0
)
0
&lgr;
0
). If this value
231
is zero, a
0
is a root, indicating that an error is present at position 0. In like manner, after multiplying the powers of a
222
with the corresponding coefficients &lgr; of the error locator polynomial &Lgr;(x)
121
, the polynomial value
231
is the evaluation of the error locator polynomial &Lgr;(x)
121
at a
−1
(i.e. value=&lgr;
n−1
(a
−1
)
n−1
+&lgr;
n−2
+ . . . +&lgr;
2
(a
−1
)
2
+&lgr;
1
(a
−1
)
1
+(a
−1
)
0
&lgr;
0
). If this value
231
is zero, a
−1
is a root, indicating that an error is present at position
1
. At the next cycle, the contents of the registers
221
are again multiplied by powers of a
222
. This results in a squaring of each power of a
222
, and the polynomial value
231
corresponds to the evaluation of the error locator polynomial at a
−2
(i.e. value=&lgr;
n−1
(a
−2
)
n−1
+&lgr;
n−2
(a
−2
)
n−2
+ . . . +&lgr;
2
(a
−2
)
2
+&lgr;
1
(a
−2
)
1
+&lgr;
0
(a
−2
)
0
). If this value
231
is zero, a
−2
is a root, indicating that an error is present at position
2
. The next cycles correspond to an evaluation of the polynomial at a
−3
, then a
−4
, then a
−5
, and so on. The iterative process continues until all n symbol positions (0 to n−1) are evaluated. As noted above, the conventional Chien locator
130
also provides a derivative term X
k
−1
&Lgr;′(X
k
−1
)
132
that facilitates the determination of the error magnitude
141
in the error determinator
140
corresponding to a located root X
k
−1
of the locator polynomial &Lgr;(x). The derivative term
132
is illustrated in
FIG. 2
as a partial sum of the even polynomial terms; alternatively, the odd terms can be used.
To reduce the time required to evaluate all n symbols of an error correcting codeword, redundant parallel embodiments of the iterative components can be considered. That is, in principle, if two copies of the error locator
130
and error determinator
140
are provided, the odd powers of a could be evaluated by one set of locator/determinators, a

Affiliated with

Also associated with

Rating

Accelerated Reed-Solomon error correction does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Accelerated Reed-Solomon error correction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Accelerated Reed-Solomon error correction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3086256