US 6,304,994 B1Grant
Reed Solomon decoder and decoding method utilizing a control signal indicating a new root for an initial error locator polynomial with respect to new erasure information
Issue Date:2001-10-16
•16 Claims
•4 Drawing Sheets
Abstract
A Reed-Solomon (RS) decoder and a decoding method therefor are provided. The RS decoder includes 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. According to the present invention, it is possible to simplify the circuit structure of the RS decoder by minimizing the number of multipliers required for calculating the polynomial.
Metadata
Assignee
- Samsung Electronics Co., Ltd.
Inventors
- Ji-sung Oh
- Kyu-taeg Oh
Application Information
Application Number:US 09/154,828
Filing Date:1998-09-17
Priority Date:1997-09-25
Art Unit:7
Classifications
IPC:
H03M 1300
Field of Search:
714704714784714785712228
Patent Drawings (4 sheets)
Description
Background of the Invention
[0002] 1. Field of the Invention
[0003] The present invention relates to an error correction decoding field, and more particularly, to a Reed-Solomon (RS) decoder and a decoding method.
[0004] 2. Description of the Related Art
[0005] 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.
[0006] 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.
[0007] The conventional polynomial expansion of two parts, a first polynomial expander 106 expands an initial error locator polynomial using the root α−kof the initial error locator polynomial on erasure information previously stored in an α−kgenerator 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.
[0008] 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.
[0009] 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.
[0010] 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).
[0011] 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
[0012] 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.
[0013] 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.
[0014] 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.
[0015] 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.
Brief Description of the Drawings
[0016] The above objectives and advantages of the present invention will become more apparent by describing in detail preferred embodiments thereof with reference to the attached drawings in which:
[0017] FIG. 1 is a block diagram of a conventional RS decoder;
[0018] FIG. 2 is a circuit diagram of a first polynomial expander shown in FIG. 1 having a conventional parallel expansion architecture;
[0019] FIG. 3 is a circuit diagram of a second polynomial expander shown in FIG. 1 having conventional parallel expansion architecture;
[0020] FIG. 4 is a block diagram according to an embodiment of an RS decoder of the present invention;
[0021] FIG. 5 is a circuit diagram of a first polynomial expander shown in FIG. 4 having a serial expansion architecture provided by the present invention; and
[0022] FIG. 6 is a circuit diagram of a second polynomial expander shown in FIG. 4 having the serial expansion architecture provided by the present invention.
Description of the Preferred Embodiments
[0023] In FIG. 4, which shows a block diagram of the RS decoder according to the present invention, when an α−kgenerator 202 generates the root α−kof an initial error locator polynomial from input erasure locator information and a control signal (CON) showing that α−kis a root with respect to new erasure information, a first polynomial expander 206 expands an initial error locator polynomial (┌(x)) by a serial expansion method using α−kand the control signal (CON) output from the α−kgenerator 202.
[0024] A first polynomial calculator 204 calculates syndrome values of data received using a syndrome polynomial (S(x)). The syndrome which is essential to the decoding of a packet code is defined in Equation 1.
[0025] Sk=S(αk)=γ(αk), k=0, 1, . . . , 2t−1 [EQUATION 1]
[0026] wherein, when an error is not generated, “0” is obtained by substituting α−kfor the syndrome polynomial (S(x)) and substituting α−kfor a parity polynomial (r(x)).
[0027] When v errors are generated as shown in FIG. 2, the syndrome values can be calculated using only an error polynomial by Equation 3.
[0028] e(x)=e0xj+e1xj+ . . . +euxj [EQUATION 2]
[0029] SK=S(αk)=γ(αk)=c(αk)+e(αk)=e(αk) [EQUATION 3]
[0030] In general, the most widely used method among methods for searching the location and size of an error using the calculated syndrome values is using the modified Euclidean algorithm. Since the modified Euclidean algorithm applied to a modified Euclidean algorithm processor 210 of the present invention is provided in the document [1], a detailed description thereof will be omitted. In order to perform decoding using the modified Euclidean algorithm, the calculated syndrome values must be expressed as the coefficients of the polynomial. Equation 4 is a syndrome polynomial of 2t−1 degrees, having the syndrome values as coefficients.
[0031] S(X)=S0+S1X+S22+ . . . +S2t−1X2t−1 [EQUATION 4]
[0032] A second polynomial expander 208 solves a key equation represented by Equation 5 using the syndrome polynomial (S(x)) calculated by the first polynomial calculator 204, α−koutput from the α−kgenerator 202, and the control signal (CON) and expands a modified syndrome polynomial (T(x)).
[0033] T(x)=S(x)×┌(x) mod x2t [EQUATION 5]
[0034] wherein, S(x) and ┌(x) respectively represent a syndrome polynomial and an initial error locator polynomial. At this time, the initial error locator polynomial ┌(x) is expanded by the first polynomial expander 206 using α−kand the control signal (CON) generated by the a generator 202. Since ┌(x) is represented by Equation 6 with respect to α−kcalculated by the input erasure locator information, the modified syndrome polynomial is obtained by repeating the operation such as Equation 7 in every input erasure locator information.
[0035] ┌(x)=π(x−α−k) [EQUATION 6]
[0036] wherein, π represents a multiplication. The root of the initial error locator polynomial ┌(x) shows the location where an error is generated. Namely, if α−kis the root, it means that the error is generated in the (k+1)th code word among received code words. In the (k+1)th code word, a code index corresponds to k.
[0037] iterative equation: S(x)(x−α−k)=xS(x)−α−kS(x) [EQUATION 7]
[0038] Second and third polynomial calculators 212 and 214 calculate an error evaluator polynomial ω(x) and an error locator polynomial σ(x) and apply them to a divider 216. The divider 216 calculates the error size by Equation 8 with respect to α−k.
[0039] An AND gate 218 makes only the output of the divider 216 corresponding to the root of the error locator polynomial (σ(x)) calculated by the third polynomial calculator 214 selected. An adder 222 is comprised of an exclusive-OR gate for performing an exclusive-OR operation on the received data delayed by a delay 220 and the size of the error output from the AND gate 218. The data decoded is output from the adder 222. At this time, (c(x)) represents a modified data polynomial.
[0040] In calculating the polynomial of the RS decoder using the modified Euclidean algorithm provided by the present invention, the circuit diagram of the first polynomial expander 206 realized using the serial expansion method is shown in FIG. 5. The circuit diagram of the second polynomial expander 208 is shown in FIG. 6.
[0041] When the number of errors capable of being corrected is t, the first polynomial expander 206 for obtaining the initial error locator polynomial includes a shift register 232 for storing 2t+1 coefficients, single multiplier 234, an adder 238, and a logic circuit (an AND gate 236) as shown in FIG. 5. The second polynomial expander 208 for obtaining the modified syndrome polynomial includes a shift register 242 for storing 2t coefficients, a multiplier 244, an adder 248, and an AND gate 246 as shown in FIG. 6.
[0042] The initial value of the shift register 232 of the first polynomial expander shown in FIG. 5 initializes the least significant coefficient λ0as “1” and sets the reset coefficients as “0”. The adder 238 and the multiplier 234 are operators in the Galois Field. The multiplier 234 has an architecture of a one step pipeline so that a high speed operation can be performed. The adder 238 includes an exclusive-OR gate. The AND gate 236 is used since the least significant degree operation of the initial error locator polynomial is different from an upper degree operation.
[0043] Namely, since when a new α−kvalue is input, one iterative calculation is completed and the next iterative calculation resumes, in the serial expansion method, when α−kwith respect to new error information is input, a calculation such as Equation 10 must first be performed instead of the calculation of Equation 9. The operation such as Equation 9 is iteratively performed before α−kwith respect to the next new erasure information is input.
[0044] Ŝ ;i=Siα−k+Si−1i=1, 2, . . . , 2t [EQUATION 9]
[0045] Ŝ ;i=Siα−ki=0 [EQUATION 10]
[0046] wherein, the control signal (CON) showing that a new α−kvalue is input is generated by the α−kgenerator 202 shown in FIG. 4 for storing the α−kvalues and outputting them one by one. The initial error locator generator 202 generates the control signal (CON) of logic “low” during one clock cycle where α−kis maintained for a certain time, the α−kvalue with respect to the next erasure information is sent, and it is shown that the α−kvalue is new ask. The first polynomial expander 206 starts the serial expansion on new α−kusing the control signal (CON) of the logic “low”.
[0047] Namely, the multiplier 234 multiplies the coefficient stored in the shift register 232 with the input α−k. The adder 238 adds the output of the multiplier 234 to the previous coefficient output through the AND gate 236 as shown in Equation 9 when the control signal (CON) is at logic “high” and passes the output of the multiplier 234 as shown in the Equation 10 when the control signal (CON) is at logic “low” since α−kis a root with respect to new erasure information. The output of the multiplier 234 is fed back to the shift register 232.
[0048] When all the α−kvalues stored in the α−kgenerator 202 shown in FIG. 4 are expanded, the initial error locator polynomial α−k┌(x) is obtained. The α−kgenerator 202 fills remaining information with “0” when the number of the stored α−kvalues is less than 2t. Therefore, when “0” is input to the first polynomial expander 206, the values of the storing elements of the shift register 232 are not changed.
[0049] The basic concept of a process of making a modified syndrome polynomial from the syndrome polynomial calculated from the first polynomial calculator 204 shown in FIG. 4 by the detailed circuit of the second polynomial expander shown in FIG. 6 is the same as that of a process of calculating the initial error locator polynomial described in FIG. 5. Namely, when the initial values of the respective storing elements of the shift register 242 as shown in FIG. 6 are filled with the syndrome values calculated by the first polynomial calculator 204, the coefficients of the modified syndrome polynomial can be obtained.
[0050] When the serial expansion method is used in the first and second polynomial expanders 206 and 208, the multiplier can be reduced to one in each expander regardless of the number of being capable of correcting errors. Meanwhile, 2t clock time is required in order to complete the multiplication on specific α−k.
[0051] Therefore, a processing time required in the first and second polynomial expanders 106 and 108 using the conventional parallel expansion method is only 2t clock time. Meanwhile, a latency which is a calculation delay time increases in the first and second polynomial expanders 206 and 208 of the present invention. Namely, the calculation delay time in the first polynomial expander 206 is 2t*(2t+1). The calculation delay time in the second polynomial expander 208 is 2t*2t when an iterative equation is performed on maximum 2t syndromes. Such a latency can be compensated for by using a fast clock.
[0052] Namely, in order to correct errors without colliding with continuously input RS packets, expansion must be performed using all the previously stored α−ks before syndromes of the next packet is calculated. When the length of the codeword of the RS packet is N, the frequency of the clock CLK1 used by the first and second polynomial expanders 206 and 208 must be increased (2t)2/N times than a symbol frequency in order to perform a polynomial calculation without collision between adjacent packets. This value of times differs according to the given RS code, i.e., around 2 through 4. In order to perform multiplication in such a frequency, the multiplier used in the present invention is one step pipelined.
[0053] The number of multipliers and the processing time of the first and second polynomial expanders 206 and 208 having the serial architecture provided in the present invention are shown in Table 1.
[0054] According to the present invention, a very large scale integration (VLSI) circuit structure of an RS decoder is greatly simplified by minimizing the number of multipliers required for calculating a polynomial in an RS decoder using a modified Euclidean algorithm. Accordingly, expenses are reduced.
Claims
What is claimed is:
1. A Reed-Solomon (RS) decoder including a modified Euclidean algorithm processor for determining a location and a 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 of an initial error locator polynomial from erasure information of the received data, and a control signal indicating a new root for the initial error locator polynomial when new erasure information is input;
a first polynomial expander having a serial expansion architecture, for expanding the initial error locator polynomial using the root of the initial error locator polynomial and the control signal for the initial error locator polynomial and providing the result to the modified Euclidean algorithm processor; and
a second polynomial expander having a serial expansion architecture, for expanding a modified syndrome polynomial using the syndrome values, the root of the initial error locator polynomial and the control signal indicating a new root for the initial error locator polynomial, and providing the result to the modified Euclidean algorithm processor.
2. The RS decoder of claim 1, wherein the first polynomial expander comprises:
a first shift register for storing 2t+1 coefficients in accordance with a clock signal, wherein t is the number of errors capable of being corrected;
a first multiplier for multiplying an output of the first shift register by the root for the initial error locator polynomial;
a first logic circuit for outputting a previous coefficient stored in the first shift register in accordance with the control signal indicating the new root for the initial error locator polynomial for new erasure information; and
a first adder for adding the output of the first logic circuit to the output of the first multiplier and feeding the result back to the first shift register.
3. The RS decoder of claim 2, wherein the first multiplier has a one step pipeline architecture.
4. The RS decoder of claim 2, wherein the received data is a packet comprising N symbols and, when the number errors capable of being corrected is t, the frequency of the clock signal is increase (2t)2/N times a symbol frequency.
5. The RS decoder of claim 2, wherein the first logic circuit comprises an AND gate for performing an logical AND operation on the coefficient stored in the first shift register and the control signal, and the first adder comprises an exclusive-OR gate.
6. The RS decoder of claim 2, wherein the least significant coefficient is set to be “1” and the remaining coefficients are set to be “0” in the initial value of the first shift register.
7. The RS decoder of claim 1, wherein the second polynomial expander comprises:
a second shift register for storing 2t coefficients according to a clock signal;
a second multiplier for multiplying an output stored in the second shift register by the root for the initial error locator polynomial;
a second logic circuit for outputting the previous coefficient stored in the second shift register according to the control signal indicating the new root of the initial error locator polynomial on the new erasure information; and
a second adder for adding an output of the second logic circuit to an output of the second multiplier and feeding the result back to the second shift register.
8. The RS decoder of claim 7, wherein the second multiplier has a one step pipeline architecture.
9. The RS decoder of claim 7, wherein the received data is a packet comprising N symbols and, when the number of errors capable of being corrected is t, the frequency of the clock signal is increased (2t)2/N times the symbol frequency.
10. The RS decoder of claim 7, wherein the second logic circuit comprises an AND gate for performing an logical AND operation previous coefficient output from the second shift register and the control signal, and the second adder comprises an exclusive OR gate.
11. The RS decoder of claim 7, wherein the initial value of the second shift register is set to be the syndrome values calculated by the polynomial calculator.
12. An Reed-Solomon (RS) decoding method using a modified Euclidean algorithm, comprising the steps of:
(a) calculating syndrome values from received data;
(b) generating a root for an initial error locator polynomial from erasure information of the received data and a control signal indicating a new root for the initial error locator polynomial with respect to new erasure information;
(c) expanding an initial error locator polynomial in accordance with the root for the initial error locator polynomial and the control signal;
(d) expanding a modified syndrome polynomial based on the syndrome values, the root for the initial error locator polynomial, and the control signal; and
(e) calculating a location and a size of an error included in the received data by applying the modified Euclidean algorithm to the expanded initial error locator polynomial and the expanded modified syndrome polynomial.
13. The method of claim 12, wherein the step (c) comprises the steps of:
(c1) reading coefficients from a first shift register which stores 2t+1 coefficients, wherein t is a number of errors capable of being corrected, and multiplying the read coefficients by the root for the initial error locator polynomial; and
(c2) feeding back to the first shift register a multiplication result obtained by multiplying a least significant coefficient with the root for the initial error locator polynomial and a result obtained by adding the multiplication result to a previous coefficient.
14. The method of claim 13, wherein the least significant coefficient is set to be “1” and the remaining coefficients are set to be “0” in the initialized value of the first shift register.
15. The method of claim 12, wherein the step (d) comprises the steps of:
(d1) reading coefficients from a second shift register which stores 2t coefficients, and multiplying the read coefficients with the root for the initial error locator polynomial; and
(d2) feeding back to the second shift register a multiplication result obtained by multiplying the least significant coefficient with the root for the initial error locator polynomial and a result obtained by adding the multiplication result to a previous coefficient.
16. The method of claim 15, wherein the initial value of the second shift register is set to be the syndrome values calculated in the step (a).
Patent Citations (4)
Non-Patent Literature (6)
- 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.Applicant
- Shao et al., “A Systolic VLSI Design of a Pipeline Reed-Solomon Decoder”, Oct. 1983 pp. 99-113.Applicant
- Oh et al., “An Efficient Reed-Solomon Decoder VLSI with Erasure Correction”, May 1997 IEEE pp. 193-201.Applicant
- Kwon et al., “An Area-Efficient VLSI Architechture of a Reed-Solomon Decorder/Encoder for Digital VCRs”, Jun. 1997 IEEE pp. 1019-1027.Applicant
- 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.Applicant
- Youshi Xu, “A Modified Euclidean Algorithm and the VLSI Implementation” publication date May 13, 1996.Applicant