Reed-Solomon decoder having a new polynomial arrangement...

Details Reed-Solomon decoder having a new polynomial arrangement... Reed-Solomon decoder having a new polynomial arrangement...

1998-10-14

2001-07-03

Decady, Albert (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

Reexamination Certificate

active

06256763

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an error correction decoding field, and more particularly, to a Reed-Solomon (RS) decoder having a new polynomial arrangement architecture for realizing a modified Euclidean algorithm and a decoding method therefor.
2. Description of the Related Art
A RS decoder is generally used for correcting errors generated during transmission in a digital communication system using a high definition television (HDTV), a digital versatile disc (DVD), or a compact disc (CD). Although, the RS decoder has excellent error correcting capability, it has a very complicated architecture. In general, an RS code is expressed as RS(N,I). One packet of information is constructed of N symbols. Among these symbols, I symbols show a message and the rest N-I symbols show a parity. Each symbol is comprised of m bits.
FIG. 1
is a block diagram of a conventional RS decoder using a modified Euclidean algorithm, which is disclosed in “On the VLSI Design of a Pipeline Reed-Solomon Decoder Using Systolic Arrays”, H. M. Shao and I. S. Reed, IEEE Trans. Comput, vol. 37, October 1988, pp. 1273-1280.
In
FIG. 1
, the root &agr;
−i
of an initial error locator polynomial calculated by input erasure location information is input to first and second polynomial expanders
106
and
108
. An erasure indicates an error, the location of which is known from the received data.
The initial error locator polynomial &Ggr;(x) expanded by the first polynomial expander
106
can be represented by Equation 1. A modified syndrome polynomial T(x) which is a key equation expanded by the second polynomial expander
108
can be represented by Equation 2.
Γ
⁡
(
x
)
=
∏
α
-
i
∈
Γ
⁢
(
x
-
α
-
i
)
[
EQUATION
⁢
 
⁢
1
]
wherein, Π represents a multiplication. The root of the initial error locator polynomial &Ggr;(x) shows the location where an error is generated. Namely, if &agr;
−i
is the root, the error is generated in the (i+1)th code word among received code words. In the (i+1)th code word, the code index corresponds to i.
T
(
x
)=
S
(
x
)&Ggr;(
x
) mod
x
2t
  [EQUATION 2]
wherein, T(x), S(x), and t respectively represent a modified syndrome polynomial, a syndrome polynomial, and the number of being capable of correcting errors.
When the calculation of the initial error locator polynomial and the modified syndrome polynomial is completed, an error evaluator polynomial &ohgr;(x) and an error locator polynomial &sgr;(x) are extracted by a modified Euclidean algorithm calculator
110
using the modified Euclidean algorithm.
When the iterative equations represented in Equations 4 through 7 are iterated 2t times, the desired error evaluator polynomial &ohgr;(x) and error locator polynomial &sgr;(x) are obtained as a result by the modified Euclidean algorithm calculator
110
. These are called the modified Euclidean algorithm, which is provided in the above document by H. M. Shao and I. S. Reed.
&mgr;
0
(
x
)=&Ggr;(
x
),
R
0
(
x
)=
x
2t
,&lgr;
0
(
x
)=0,
Q
0
(
x
)=
T
(
x
)  [EQUATION 3]
R
i
(
x
)=[&sgr;
i−1
b
i−1
R
i−1
(
x
)+{overscore (&sgr;
i−1
+L )}
a
i−1
Q
i−1
(
x
)]−
x
|l
i−1
|
[&sgr;
i−1
a
i−1
Q
i−1
(
x
)+&sgr;
i−1
b
i−1
R
i−1
(
x
)]  [EQUATION 4]
&lgr;
i
(
x
)=[&sgr;
i−1
b
i−1
&lgr;
i−1
(
x
)+{overscore (&sgr;
i−1
+L )}
a
i−1
&mgr;
i−1
(
x
)]−
x
|l
i−1
|
[&sgr;
i−1
a
i−1
&mgr;
i−1
(
x
)+&sgr;
i−1
b
i−1
&lgr;
i−1
(
x
)]  [EQUATION 5]
Q
i
(
x
)=&sgr;
i−1
Q
i−1
(
x
)+{overscore (&sgr;
i−1
+L )}
R
i−1
(
x
)  [EQUATION 6]
&mgr;
i
(
x
)=&sgr;
i−1
&mgr;
i−1
(
x
)+{overscore (&sgr;
i−1
+L )}&lgr;
i−1
(
x
)  [EQUATION 7]
wherein a
i−1
and b
i−1
are respectively the coefficients of the highest degree terms of R
i−1(x)
and Q
i−1(x)
.
l
i−1
=deg(R
i−1
(x))−deg(Q
i−1
(x))  [EQUATION 8]
σ
i
-
1
=
{
1
if
⁢
 
⁢
I
i
-
1
≥
0
0
if
⁢
 
⁢
I
i
-
1
<
0
[
EQUATION
⁢
 
⁢
9
]
Namely, as shown in Equations 8 and 9, when the degree of R
i−1(x)
is equal to or larger than that of Q
i−1(x), &sgr;
i−1
has a value of “1”. If not, &sgr;
i−1
has a value of “0”.
When the condition shown in the following Equation 10 is satisfied, the above iterative equations (Equations 4 through 7) are terminated.
deg(&lgr;
i
(x))>deg(R
i
(x))  [EQUATION 10]
When the above iterative equations (Equations 4 through 7) are completed, the error locator polynomial &sgr;(x) and the error evaluator polynomial &ohgr;(x) are obtained as shown in the equations 11 and 12.
&sgr;(
X
)=&lgr;
i
(
x
)  [EQUATION 11]
&ohgr;(
x
)=
R
i
(
x
)  [EQUATION 12]
The initial values of the four polynomials R
i
(x), Q
i
(x), &lgr;
i
(x), and &mgr;
i
(x) are represented in the above Equation 3. The error locator polynomial &sgr;(x) and the error evaluator polynomial &ohgr;(x) can be obtained without repeating the iterative equations (Equations 4 through 7) 2t times, under the condition that the degree of &lgr;
i
(x) is larger than that of R
i
(x). &lgr;
i
(x) becomes the error locator polynomial and R
i
(x) becomes the error estimator polynomial.
A conventional polynomial arrangement architecture for realizing the modified Euclidean algorithm is represented in FIG.
2
. In the polynomial arrangement shown in
FIG. 2
, the polynomials R(x) and Q(x), the degrees of which decrease as an iterative operation process proceeds, are arranged in registers
132
and
134
loaded in the modified Euclidean algorithm calculator
110
from the right side. The polynomials &lgr;(x) and &mgr;(x), the degrees of which increase as an iterative operation process proceeds, are arranged in registers
136
and
138
from the left side. In this case, the degrees of the respective polynomials must be stored in an additional memory (not shown) for generating a control signal required for iterative calculations.
The conventional polynomial arrangement architecture for realizing the modified Euclidean algorithm has problems in that the degrees of the respective polynomials must always be stored in the additional memory, and as many as log
2
2
t subtracters are required since the degrees must be compared as shown in Equation 8 for generating the control signal required for performing the above Equation 9. Further, the degrees must be buffered when the polynomials are buffered since the degrees of the polynomials will be used in subsequent iterative operations.
SUMMARY OF THE INVENTION
To solve the above problems, it is an objective of the present invention to provide an RS decoder of a simple architecture in which an additional degree comparing circuit is not necessary by changing the polynomial arrangement architecture when calculating a modified Euclidean algorithm.
It is another objective of the present invention to provide an RS decoding method for performing the modified Euclidean algorithm by changing the polynomial arrangement architecture.
It is still another objective of the present invention to provide a method for arranging the coefficients of the respective polynomials for performing the modified Euclidean algorithm from the left side.
Accordingly, to achieve the first objective, there is provided a Reed-Solomon (RS) decoder for correcting on error of a received symbol using a modified Euclidean algorithm, comprising a calculator for iteratively calculating four polynomials R(x), Q(x), &lgr;(x), and &mgr;(x) for the modified Euclidean algorith

Affiliated with

Also associated with

Rating

Reed-Solomon decoder having a new polynomial arrangement... 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 having a new polynomial arrangement..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reed-Solomon decoder having a new polynomial arrangement... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2558955