Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-09-17
2001-10-16
Ton, David (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S785000
Reexamination Certificate
active
06304994
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 and a decoding method.
2. Description of the Related Art
An RS decoder is mainly used for correcting errors generated during transmission in a digital communications system using a high definition television (HDTV), a digital versatile disc (DVD), or a compact disc (CD), and has excellent error correcting performance. However, the RS decoder has a very complicated structure. In general, an RS code is expressed as RS(N,I). One packet is comprised of N symbols. Among these symbols, I symbols show a message. The remaining 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 described in the document [
1
]: “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.
The conventional polynomial expansion of two parts, a first polynomial expander 106 expands an initial error locator polynomial using the root &agr;
−k
of the initial error locator polynomial on erasure information previously stored in an &agr;
−k
generator
102
. A second polynomial expander
108
expands a modified syndrome polynomial using the syndrome polynomial calculated by a first polynomial calculator
104
. The coefficients of the syndrome polynomial becomes each calculated syndrome value. Also, an erasure means an error in which the location is known from received data. An error means an error, the location and magnitude of which are known.
In the parallel expansion method provided in the document [
1
], when the number of errors capable of being corrected is t, since the first polynomial expander
106
must calculate 2t+1 coefficients because the initial error locator polynomial has 2t degrees, 2t+1 registers of m-bit(8-bit) must exist as shown in FIG.
2
. Also, 2t+1 multipliers and 2t+1 adders are necessary for expanding the initial error locator polynomial.
Since the second polynomial expander
108
for generating the modified syndrome polynomial must calculate 2t coefficients because the modified syndrome polynomial has 2t−1 degrees, 2t registers, 2t multipliers, and 2t adders for calculating and storing the 2t coefficients are necessary as shown in
FIG. 3. A
previously calculated syndrome is provided to each register as an initial value. The operation of the iterative equation shown in Equation 7 is performed with respect to the syndrome input according to a clock signal (CLK). Accordingly, the respective coefficients of the modified syndrome polynomial are obtained after a clock time of 2t.
Therefore, in the RS decoder employing a conventional parallel expansion method, the number of multipliers required for calculating the polynomial is the sum of the multipliers used during calculating the modified syndrome polynomial and the initial error locator polynomial, i.e., 2t+2t+1(=4t+1).
Since the operation used in the RS decoder is performed on the Galois Field, the multiplier is not a general decimal multiplier but a Galois field multiplier. Accordingly, the structure of the Galois field multiplier becomes more complicated. Since the Galois Field multiplier requires largest number of gates in realizing an integrated circuit of the RS decoder, the complexity remarkably increases as the number (t) of errors capable of being corrected increases in order to calculate the polynomial by the parallel expansion method.
SUMMARY OF THE INVENTION
To solve the above problems, it is an objective of the present invention to provide an RS decoder using a minimum number of multipliers regardless of the number of errors capable of being corrected in calculating a polynomial using a modified Euclidean algorithm.
It is another objective of the present invention to provide an RS decoding method using serial expansion in calculating a polynomial using a modified Euclidean algorithm.
Accordingly, to achieve the first objective, there is provided a Reed-Solomon (RS) decoder including a modified Euclidean algorithm processor for searching the location and size of an error based on syndrome values, comprising a polynomial calculator for calculating syndrome values from received data and constructing a syndrome polynomial, a generator for generating a root for an initial error locator polynomial from erasure information of the received data and a control signal showing a new root for the initial error locator polynomial whenever new erasure information is input, a first polynomial expander having a serial expansion architecture, for expanding the initial error locator polynomial using the root and control signal for the initial error locator polynomial and providing the result to the processor, and a second polynomial expander having a serial expansion architecture, for expanding a modified syndrome polynomial using the syndrome value, and the root and control signal for the initial error locator polynomial and providing the result to the processor.
To achieve the second objective, there is provided an RS decoding method using a modified Euclidean algorithm, comprising the steps of (a) calculating skis syndrome values from received data, (b) generating a root for an initial error locator polynomial from the erasure information of the received data and a control signal showing a new root for the initial error locator polynomial with respect to new erasure information, (c) expanding an initial error locator polynomial using the root for the initial error locator polynomial and the control signal, (d) expanding a modified syndrome polynomial using the syndrome value, the root for the initial error locator polynomial, and the control signal, and (e) calculating the location and size of the error included in the received data using the modified Euclidean algorithm using the expanded initial error locator polynomial and the modified syndrome polynomial.
REFERENCES:
patent: 4649541 (1987-03-01), Lahmeyer
patent: 4868828 (1989-09-01), Shao et al.
patent: 5130990 (1992-07-01), Hsu et al.
patent: 5951677 (1999-09-01), Wolf et al.
Truong et al., “Simplified Procedure for Correcting both Errors and Erasures of Reed-Solomon Code Using Euclidean Algorithm”, Nov. 1988 IEE proceedings pp. 318-324.*
Shao et al., “A Systolic VLSI Design of a Pipeline Reed-Solomon Decoder”, Oct. 1983 pp. 99-113.*
Oh et al., “An Efficient Reed-Solomon Decoder VLSI with Erasure Correction”, May 1997 IEEE pp. 193-201.*
Kwon et al., “An Area-Efficient VLSI Architechture of a Reed-Solomon Decorder/Encoder for Digital VCRs”, Jun. 1997 IEEE pp. 1019-1027.*
H.M. Shao, I.S Reed, “On the VLSI Design of a Pipeline Reed-Solomon Decoder Using Systolic Arrays” vol. 37, No. 10, Oct. 1988.
Youshi Xu, “A Modified Euclidean Algorithm and the VLSI Implementation” publication date May 13, 1996.
Oh Ji-sung
Oh Kyu-taeg
Samsung Electronics Co,. Ltd.
Sughrue Mion Zinn Macpeak & Seas, PLLC
Ton David
LandOfFree
Reed Solomon decoder and decoding method utilizing a control... 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 and decoding method utilizing a control..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reed Solomon decoder and decoding method utilizing a control... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2600540