Reed-Solomon decoder for use in advanced television

• US 6,031,875 A
• Filed: 10/29/1997
• Issued: 02/29/2000
• Est. Priority Date: 10/29/1996
• Status: Expired due to Term

• Current Assignee: Wi-LAN Inc.
• Original Assignee: Daewoo Electronics (Government of South Korea)
• Inventors: Im, Yong-Hee
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): Bayard, Emmanuel
• Application Number:
  US08/960,232
• Time in Patent Office: 853 Days
• Field of Search: 375/262, 375/265, 375/243, 714/784, 714/785, 714/764, 714/768, 714/781, 714/783
• US Class Current: 375/262
• CPC Class Codes: H03M 13/151 using error location or error correction polynomials

Abstract

A Reed-Solomon decoder for use in ATV is disclosed. The Seed-Solomon decoder comprises: a clock generator for generating a faster RS clock as much as t than a symbol clock; a FIFO buffer for latching the received symbol according to the RS clock; a syndrome calculator for calculating syndrome values from the received symbol according to the RS clock; a syndrome selector for selecting one of the syndrome values supplied from the syndrome calculator and "0×00" value according to a syndrome selecting signal; an error locator polynomial calculating unit for calculating coefficients of an error locator polynomial by using the syndrome values supplied from the syndrome selector according to the RS clock and supplying the coefficients and the highest order thereof; an error corrector for generating an error value by using the syndrome values and the coefficients of the error locator polynomial according to the RS clock and supplying an error-corrected recovered symbol by adding the error value to the received symbol supplied from the FIFO buffer; and a controller for generating a plurality of control signals for controlling the syndrome calculator, the syndrome selector, the error locator polynomial calculating unit, and the error corrector.

Claims

1. A Reed-Solomon decoder for use in ATV for decoding and correcting errors in a received symbol encoded by a Reed-Solomon code having an error correcting capability of t multiples of 10, comprising:

clock generating means for generating a RS clock as much as t times the rate of a symbol clock;

input buffering means for latching the received symbol according to the RS clock;

FIFO buffering means for latching the received symbol provided from said input buffering means according to the RS clock;

syndrome calculating means for calculating syndrome values from the received symbol provided from said input buffering means according to the RS clock;

syndrome selecting means for selecting one of the syndrome values supplied from said syndrome calculating means and "0×

00" value according to a syndrome selecting signal;

error locator polynomial calculating means for calculating an error locator polynomial by using the syndrome values supplied from said syndrome selecting means according to the RS clock and supplying coefficients of the error locator polynomial and the highest order thereof;

error correcting means for generating an error value by using the syndrome values and the coefficients of the error locator polynomial according to the RS clock and supplying an error-corrected recovered symbol by adding the error value to the received symbol supplied from said FIFO buffering means; and

controlling means for generating a plurality of control signals and controlling said syndrome calculating means, said syndrome selecting means, said error locator polynomial calculating means, and said error correcting means.

2. The Reed-Solomon decoder of claim 1 further comprising bit error rate calculating means for calculating a bit error rate by comparing the received symbol supplied from said FIFO buffering means to the error-corrected recovered symbol in units of bit.

3. The Reed-Solomon decoder of claim 2, wherein said bit error rate calculating means comprises:

error bit detecting means for comparing the received symbol and the error-corrected recovered symbol in each bit, detecting unequal bits, and outputting the detected bits, in units of a predetermined symbol;

error bit counting means for counting the detected bits from said error bit detecting means and outputting a first error bit number generated for a predetermined codeword period; and

error bit number calculating means for receiving the first error bit number from said error bit counting means and outputting a second error bit number generated for a predetermined detection period as the bit error rate.

4. The Reed-Solomon decoder of claim 1, wherein said syndrome calculating means comprises:

counting means for counting the RS clock and outputting the counted value as an alpha root selecting signal;

a first storing unit for storing a first group of alpha roots;

a first syndrome calculating cell for receiving the received symbol supplied from said input buffering means and calculating a first group of syndrome values by using the first group of alpha roots stored in said first storing unit according to the alpha root selecting signal in the RS clock units;

a second storing unit for storing a second group of alpha roots;

a second syndrome calculating cell for receiving the received symbol supplied from said input buffering means and calculating a second group of syndrome values by using the second group of alpha roots stored in said second storing unit according to the alpha root selecting signal in the RS clock units;

first selecting means for sequentially selecting one of the first group of syndrome values according to a first syndrome selecting signal supplied from said controlling means;

second selecting means for sequentially selecting one of the second group of syndrome values according to a second syndrome selecting signal supplied from said controlling means; and

third selecting means for selecting one of the output from said first selecting means and the output from said second selecting means according to a third syndrome selecting signal supplied from said controlling means.

5. The Reed-Solomon decoder of claim 4, wherein said first syndrome calculating cell comprises:

a first shift register having a first group of registers, for storing intermediate syndrome values calculated from the first symbol to the second symbol from the last in one codeword, according to the RS clock;

a second shift register having a second group of registers, for storing final syndrome values calculated from the first symbol to the last symbol in the codeword, according to the RS clock;

control signal generating means for generating a plurality of control signals to control said first and second shift registers;

term selecting means for selecting the intermediate syndrome values supplied from said first shift register while receiving the first symbol to the second symbol from the last in the codeword, and selecting the final syndrome values supplied from said second shift register while receiving the last symbol in the codeword; and

syndrome term operating means for Galois multiplying the first group of alpha roots selected according to the alpha root selecting signal by the intermediate syndrome values, Galois adding the multiplied value and the received symbol in the RS clock units, and supplying the added value as the intermediate and final syndrome values to said first and second shift registers, respectively.

6. The Reed-Solomon decoder of claim 4, wherein said second syndrome calculating cell comprises:

a first shift register having a first group of registers, for storing intermediate syndrome values calculated from the first symbol to the second symbol from the last in one codeword, according to the RS clock;

a second shift register having a second group of registers, for storing final syndrome values calculated from the first symbol to the last symbol in the codeword, according to the RS clock;

control signal generating means for generating a plurality of control signals to control said first and second shift registers;

term selecting means for selecting the intermediate syndrome values supplied from said first shift register while receiving the first symbol to the second symbol from the last in the codeword and selecting the final syndrome values supplied from said second shift register while receiving the last symbol in the codeword; and

syndrome term operating means for Galois multiplying the second group of alpha roots selected according to the alpha root selecting signal by the intermediate syndrome values, Galois adding the multiplied value and the received symbol in the RS clock units, and supplying the added value as the intermediate and final syndrome values to said first and second shift registers, respectively.

7. The Reed-Solomon decoder of claim 1, wherein said error locator polynomial calculating means comprises:

discrepancy calculating means for delaying an updated error locator polynomial, and calculating 2t number of discrepancies by using the syndrome values outputted from said syndrome selecting means and the updated error locator polynomial;

variable generating means for outputting an index and the highest order of the error locator polynomial, under the control of said discrepancy calculating means;

a storing unit for storing reciprocals of late discrepancies in the form of look-up table, and outputting the reciprocal of late discrepancy corresponding to the index;

a first Galois multiplier for Galois multiplying the discrepancy outputted from said discrepancy calculating means by the reciprocal of the late discrepancy outputted from said storing unit;

a shift register for storing an intermediate value used to update the error locator polynomial;

selecting means for selecting one of the last updated error locator polynomial outputted from said discrepancy calculating means and the output of said shift register, and supplying the selectant to said shift register;

a second Galois multiplier for Galois multiplying the output of said first Galois multiplier by the output of said shift register; and

a Galois adder for Galois adding the output of said second Galois multiplier and the error locator polynomial delayed by said discrepancy calculating means, and supplying the added value to said discrepancy calculating means as the updated error locator polynomial.

8. The Reed-Solomon decoder of claim 1, wherein said error correcting means comprises:

a common element storing unit for storing t number of initial roots corresponding to a reciprocal of a Galois field element for processing an evaluation from the highest order symbol of the Reed-Solomon code, and for storing t number of update roots corresponding to the Galois field element for updating the order for the next symbol;

an error evaluator polynomial calculating unit for calculating an error evaluator polynomial by Galois multiplying the syndrome values outputted from said syndrome selecting means by the coefficients of the error locator polynomial, and outputting coefficients of the error evaluator polynomial;

an error evaluator polynomial evaluating unit for evaluating the error evaluator polynomial by using the coefficients of the error evaluator polynomial, the initial roots and the update roots outputted from said common element storing unit, and outputting the evaluation result as an error evaluation value;

an error locator polynomial evaluating unit for outputting an error location signal by evaluating the error locator polynomial from the coefficients of the error locator polynomial by using the initial roots and the update roots, and for outputting a differentiation evaluation value by evaluating a differentiation polynomial of the error locator polynomial;

an error value calculating and correcting unit for calculating the error value by using the differentiation evaluation value and the error evaluation value, and outputting the error-corrected recovered symbol by adding the error value to the received symbol according to the error location signal; and

a recovery failure decision unit for determining whether the error-corrected recovered symbol is correct, and outputting a recovery failure signal according to the result.

9. The Reed-Solomon decoder for use in ATV of claim 8, wherein said common element storing unit comprises:

a first storing unit comprising a first group of storing areas, for storing the initial roots;

a second storing unit comprising a second group of storing areas, for storing the update roots;

a first selector for selecting and outputting sequentially the initial root of said first storing unit according to an initial root selecting signal supplied from said controlling means; and

a second selector for selecting and outputting sequentially the update root of said second storing unit according to an update root selecting signal supplied from said controlling means.

10. The Reed-Solomon decoder of claim 8, wherein said error evaluator polynomial calculating unit comprises:

a Galois multiplier for Galois multiplying the coefficients of the error locator polynomial by the syndrome values outputted from said syndrome selecting means;

a Galois adder for Galois adding the output of said Galois multiplier to a feedback value;

a multiplexer for selectively outputting one of the coefficients of the error locator polynomial and the output from said Galois adder, under the control of said controlling means; and

a shift register for storing the coefficients of the error evaluator polynomial by shifting the output of said multiplexer being synchronized with the RS clock, and supplying the stored value to said Galois adder as the feedback value.

11. The Reed-Solomon decoder of claim 8, wherein said error evaluator polynomial evaluating unit comprises:

an initializing unit for Galois multiplying the initial roots supplied from said common element storing unit in the RS clock units by the coefficients of the error evaluator polynomial supplied from said error evaluator polynomial calculating unit in the symbol clock units, and outputting the multiplied value as an initial term value;

a term selector for selecting one of the initial term value and an updated intermediate term value under the control of said controlling means;

an order updating unit for updating a term value of the error locator polynomial for the next symbol by the output of said term selector, and outputting the updated intermediate term value;

a term operator for adding term values outputted from said order updating unit during one symbol clock, and outputting the added value; and

an error evaluation value outputting unit for adding the output of said term operator to 0 order coefficient of the error locator polynomial, and outputting the added value as the error evaluation value.

12. The Reed-Solomon decoder of claim 8, wherein said error locator polynomial evaluation unit comprises:

an initializing unit for Galois multiplying the initial roots supplied from said common element storing unit in the RS clock units by the coefficients of the error locator polynomial supplied from said error locator polynomial calculating unit in the symbol clock units, and outputting the multiplied value as an initial term value;

a term selector for selecting one of the initial term value and an intermediate term value under the control of said controlling means;

a first order updating unit for updating a term value of the error locator polynomial for the next symbol by the output of said term selector, and outputting the updated term value as the intermediate term value;

a first term operator for adding term values outputted from said first order updating unit during one symbol clock;

a second term operator for adding the output of said first term operator to 0 order coefficient of the error locator polynomial and outputting the added value as the error locator evaluation value;

a decision unit for determining whether an error is generated from the error locator evaluation value outputted from said second term operator, and generating the error location signal;

an odd order term selector for receiving the output of said first order updating unit, and outputting selectively an odd order term of the error locator polynomial;

a second order updating unit for updating the order of an alpha root from the highest order by "1"; and

a third term operator for adding the odd order terms outputted from said odd order term selector, Galois multiplying the added value by the output of said second order updating unit, and outputting the multiplied value as the differentiation value.

13. The Reed-Solomon decoder of claim 8, wherein said error value calculating and correcting unit comprises:

a first memory for storing reciprocals of the differentiation evaluation values in the form of look up table, and outputting a reciprocal of the differentiation evaluation value according to the differentiation evaluation value from said error locator polynomial evaluating unit;

a first Galois multiplier for Galois multiplying the error evaluation value outputted from said error evaluator polynomial evaluating unit by the reciprocal of the differentiation evaluation value outputted from said first memory;

a second memory for storing primitive elements of the Galois field in the form of look up table, and outputting the primitive element corresponding to a symbol order therefrom, under the control of said controlling means;

a second Galois multiplier for Galois multiplying the output of said first Galois multiplier by the primitive element outputted from said second memory, and outputting the multiplied value as the error value;

a third memory for storing "0×

00";

a multiplexer for selectively outputting one of the "0×

00" outputted from said third memory and the error value outputted from said second Galois multiplier according to the error location signal; and

a Galois adder for Galois adding the received symbol to the output of said multiplexer and outputting the added value as the error-corrected recovered symbol.

14. The Reed-Solomon decoder of claim 8, wherein said error value calculating and correcting unit comprises:

a first memory for storing reciprocals of the differentiation evaluation values in the form of look up table, and outputting a reciprocal of the differentiation evaluation value according to the differentiation evaluation value from said error locator polynomial evaluating unit;

a first Galois multiplier for Galois multiplying the error evaluation value outputted from said error evaluator polynomial evaluating unit by the reciprocal of the differentiation evaluation value outputted from said first memory;

a second memory for storing a primitive element corresponding to the highest symbol of one codeword;

a third memory for storing α

^-1 to update the primitive element;

a second Galois multiplier for Galois multiplying the α

^-1 of said third memory by a feedback value, and outputting the primitive element of the order decreased by order of one;

a first multiplexer for selectively outputting one of the output of said second memory and the output of said third memory, under the control of said controlling means;

a register for latching the primitive element outputted from said first multiplexer and outputting the latched value to said second Galois multiplier as the feed back value;

a third Galois multiplier for Galois multiplying the primitive element outputted from said register by the output of said Galois multiplier, and outputting the multiplied value as the error value;

a fourth memory for storing "0×

00";

a second multiplexer for selectively outputting one of the "0×

00" outputted from said fourth memory and the error value outputted from said third Galois multiplier according to the error location signal; and

a Galois adder for Galois adding the received symbol to the output of said second multiplexer and outputting the added value as the error-corrected recovered symbol.