Reed-solomon decoder

Details Reed-solomon decoder Reed-solomon decoder

1999-09-22

2002-11-26

Decady, Albert (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S785000

Reexamination Certificate

active

06487691

ABSTRACT:

BACKGROUND
RS encoding and decoding can be defined as constituting a polynomial using the element in the Galois field GF(2
m
). The following codeword polynomial W(x) is calculated for (n, k) RS encoding where n denotes the number of code blocks and k denotes the number of information blocks (a test block is n−k=2t, where t is the maximum correctable number of symbols).
W
(
x
)=
M
(
x
)
x
n−k
−R
(
x
)
where
M(x): a polynomial using information symbols as coefficients;
R(x): a polynomial using parity symbols as coefficients;
R(x)=M(x)x
n−k
mod G(x); and
G(x): generator polynomial,
G(x)=(x−a
d
)(x−a
d−1
) . . . (x−a
d+2t−1
).
In the above equation, a is defined by GF(2
m
) and is a solution of the m-order irreducible polynomial, i.e., a solution that satisfies a
8
+a
4
+a
3
+a
2
+1=0 when m=8. The polynomial W(x) can be divided by G(x) without yielding a remainder. The codeword polynomial W(x) can be a systematic codeword, compared with a method that calls for the direct multiplication of M(x) by G(x).
Generally, an LFSR (Linear Feedback Shift Register) is used for calculating the remainder of the M(x)x
n−k
by G(x). If one LFSR is used for the encoding one block, the LFSR has 2t constant multipliers and uses them (n−2t) times. Thus, 2(n−2t)t constant multiplications must be performed for the encoding.
The RS decoding is an operation used for estimating the original W(x) by using a received polynomial
Y
(
x
)=
W
(
x
)+
E
(
x
).
E(x) is a polynomial using an error symbol as a coefficient. Y(x) can also be expressed as follows, where Y
i
is a received codeword,
 
Y
(
x
)=
Y
n−1
x
n−1
+Y
n−2
x
n−2
+ . . . Y
1
x+Y
0
.
The decoding methods are mainly
(i) a method for using Y(x) to perform decoding in a time domain;
(ii) a method for using for a polynomial a remainder obtained by dividing Y(x) by G(x) (remainder-based decoding); and
(iii) a method for performing a DFT (Discrete Fourier Transformation) for Y(x) to calculate 2t continuous spectra (syndromes) in a frequency domain (syndrome-based decoding).
According to the second and the third methods, information that depends only on an error (i.e. syndromes) is calculated by using the received information, and the location of the error is extracted. Thus, the number of terms is not O(n), but instead is reduced to O(t). Therefore, since generally t<n, a required circuit in the succeeding stages is small. The third method (iii) is generally used, and is further sorted into algebraic decoding and transform decoding. The prior art will now be described by using the two decoding methods that are most closely related to the present invention.
(a) Algebraic Decoding
Specifically, this method includes the following five steps that must be performed for decoding:
(i) calculating a syndrome by performing a DFT for a received codeword;
(ii) obtaining an error-locator polynomial and an error-evaluator polynomial by using the calculated syndrome;
(iii) calculating the solution for the error-locator polynomial in order to estimate the location of the error;
(iv) estimating an error value from the error-locator and the error-evaluator polynomial by using the Forney algorithm; and
(v) correcting the error by using the received codeword and the error value.
In the calculation of the syndrome at step (i), the DFT calculation for GF(2
m
) need be performed. The DFT calculation is performed by substituting into Y(x) the elements
1
, a, a
2
, a
3
. . . and a
2t−1
of GF(2
m
). That is, the syndrome is obtained by
S
0
=Y(1)
S
1
=Y(a)
S
2
=Y(a
2
)
S
3
=Y(a
3
)
.
.
.
S
2t−1
=Y(a
2t−1
).
Since W(a
i
)=0,
S
i
=Y(a
i
)=W(a
i
)+E(a
i
)=E(a
i
)(i=0, . . . , 2t−1).
The occurrence of an error in Y(x) can be determined by examining the syndromes to determine whether they are all 0. Since generally 2t arithmetic circuits are used n times to calculate the syndromes, 2nt constant multiplications are required.
Error correction using the syndromes is performed by estimating the number of errors using S
i
. This is the calculation performed with E(x) that provides the calculated syndrome and that has a Hamming weight of t or less (i.e., that includes non zero terms equal to or less than t), and is the NP complete problem in general. However, the calculation method in the polynomial order is well known for RS code. At step (ii) the coefficient for the following error-locator polynomial is calculated by using the fact that the syndromes can be expressed as a linear combination of error values, and that symmetry exists relative to the exchange of orders of error locations.
Expression 1
Λ
⁢
(
x
)
=
∏
k
=
0
t
-
1
⁢
(
1
+
a
i
k
⁢
x
)
Coefficients &Lgr;
t
. . . and &Lgr;
l
for &Lgr;(x) are obtained by the following expression, wherein L
0
is defined as 1.
Expression 2
[
S
0
S
1
…
S
t
-
1
S
1
S
2
…
S
t
⋮
⋮
 
⋮
S
t
-
1
S
t
-
2
…
S
2
⁢
t
-
2
]
⁡
[
Λ
t
Λ
t
-
1
⋮
Λ
1
]
=
[
S
t
S
t
+
1
⋮
S
2
⁢
t
-
1
]
The Peterson method, the Berlekamp-Massey (BM) method and the Euclid method are proposed for performing this calculation in the polynomial order. According to these methods, O(t
3
), O(t
2
) and O(t
2
) multiplications are respectively performed to calculate the coefficients of the error-locator polynomial. Since these calculations are not directly related to the subject of the present invention, however, no further explanation shall be given for them. For the details, see the referenced document 1, “Theory And Practice Of Error Control Codes,” R. E. Blahut, Addison-Wesley 1984, or referenced document 2, “Coding Theory,” Hideki Imai, Institute of Electronic Information Communication, 1990.
When the coefficients &Lgr;
t
. . . and &Lgr;
l
of the error-locator polynomial are obtained, at step (iii) an error location i is obtained by performing the calculations for the polynomial. Generally, a
−i
(i=0, 1, . . . , n−1) are sequentially substituted into the error-locator polynomial, and the relation &Lgr;(a
−i
)=0 is checked by using a sequential circuit (Chien Search). Since &Lgr;(x) is the t-order polynomial, t constant multiplications must be repeated n times (a total of nt constant multiplications).
At step (iv), the Forney algorithm is used to calculate the error value by employing the following error-evaluator polynomial
&OHgr;(
x
)=
S
(
x
)&Lgr;(
x
) mod
x
2t−1
,
where S(x) is the following polynomial having syndromes as coefficients:
Expression 3
S
⁢
(
x
)
=
∑
i
=
0
2
⁢
t
-
1
⁢
S
i
⁢
x
i
The obtained error value E
i
is
E
i
=&OHgr;(
a
−i
)/(&Lgr;′(
a
−i
)
a
−i
),
where &Lgr;′(x) represents the derivative of &Lgr;(x).
Finally, at step (v) the error is corrected. That is,
W
(
x
)=
Y
(
x
)+
E
(
x
)
Most of these calculations are performed as sequential steps using a sequential circuit, as previously mentioned. Specifically, steps (i) to (v) are sequentially performed, and at each step many processes are sequentially performed, including iterative calculations. The implementation of the RS decoder does not precipitate any problem in applications that has a relatively low data transfer rate. However, with a memory ECC application for which high through-put and low latency are required, a problem may arise concerning the processing speed.
The RS decoder requires only the linear calculation performed up to the acquisition of syndromes (step (i)), but for the following process to estimate the error location and error value, it requires multiple non-linear circuits. It is difficult to provide a small, fast circuit for the nonlinear calculation in the Galois field (a circuit for two-input multiplication, reciprocal calculation, etc.) using the basic logical functio

Affiliated with

Also associated with

Rating

Reed-solomon decoder does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2949510