Efficient look-up table methods for Reed-Solomon decoding

• US 6,263,470 B1
• Filed: 11/25/1998
• Issued: 07/17/2001
• Est. Priority Date: 02/03/1998
• Status: Expired due to Term

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Hung, Ching-Yu, Wolf, Tod D., Cheng, Yaqi
• Primary Examiner(s): MOISE, EMMANUEL LIONEL
• Application Number:
  US09/200,348
• Time in Patent Office: 965 Days
• Field of Search: 714/755, 714/756, 714/758, 714/752, 714/761, 714/762, 714/763, 714/784, 714/785, 714/759, 714/757, 714/765, 708/492
• US Class Current: 714/784
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes

Abstract

A programmable logic device (130) as may be used in a communication system device such as a digital subscriber line modem (408) to perform Reed-Solomon decoding upon a received frame of digital values is disclosed. The programmable logic device (130) may be implemented as a DSP (130) or a general purpose microprocessor, for example. According to one disclosed embodiment of the invention, a group of look-up tables (60) are arranged, each look-up table (60) associated with one of the possible power values of a finite field, number up to twice the number of correctable errors. The contents of each entry (SYN) of the look-up tables (60) correspond to the finite field (e.g., Galois field) multiplication of a primitive element raised to an index power with a character of the finite field alphabet. Galois field multiplications (62) in syndrome accumulation may now be performed with a single table look-up operation. According to other disclosed embodiments of the invention, look-up tables (60, 160) are similarly arranged to contain the contents of finite field (e.g., Galois field) multiplication products for use in a Chien search procedure. In a single-thread version of the disclosed Chien search procedure, a subset of the same look-up tables (60) as used in syndrome accumulation may be utilized.

Claims

1. A method of operating a programmable logic device to perform syndrome accumulation according to a Reed-Solomon coding protocol to produce a syndrome polynomial from an input frame sequence of digital values, comprising the steps of:

arranging a plurality of look-up tables in a memory, each of the plurality of look-up tables associated with one of a plurality of power index values, each of the plurality of look-up tables having one entry associated with each of a plurality of members of a finite field, each entry containing a finite field value corresponding to the finite field product of the associated finite field member and a finite field primitive raised to a power corresponding to the associated power index value of the look-up table; and

for each of a plurality of degrees of the syndrome polynomial, generating a syndrome polynomial coefficient by performing the operations of;

initializing a sum value to a first digital value of the input frame sequence;

accessing a selected one of the plurality of look-up tables, the selected look-up table corresponding to one of the plurality of power index values, to retrieve therefrom the contents of an entry corresponding to a current value of the sum value;

performing a finite field addition of the contents retrieved in the accessing step with a next digital value of the input frame sequence;

updating the sum value to the result of the performing step; and

repeating the accessing, performing, and updating operations for each of the digital value of the input frame sequence.

2. The method of claim 1, wherein the number of look-up tables is equal to twice the number of correctable errors in the Reed-Solomon coding protocol.

3. The method of claim 1, wherein the step of generating a syndrome polynomial coefficient comprises:

for at least a lowest order one of the plurality of degrees of the syndrome polynomial, performing a finite field multiplication of the finite field primitive raised to the lowest order with the current value of the sum value.

4. The method of claim 1, wherein the finite field is of the Galois field type.

5. The method of claim 1, wherein the programmable logic device comprises a digital signal processor.

6. A programmable system for performing syndrome accumulation according to a Reed-Solomon coding protocol to produce a syndrome polynomial from an input frame sequence of digital values, comprising:

a read/write memory, having a portion arranged as a plurality of look-up tables in a memory, each of the plurality of look-up tables associated with one of a plurality of power index values, each of the plurality of look-up tables having one entry associated with each of a plurality of members of a finite field, each entry containing a finite field value corresponding to the finite field product of the associated finite field member and a finite field primitive raised to a power corresponding to the associated power index value of the look-up table

at least one execution unit coupled to the read/write memory, for executing a sequence of program instructions; and

a program memory, coupled to the at least one execution unit, for storing a sequence of program instructions for controlling the operation of the at least one execution unit to generate a sequence of syndrome polynomial coefficients by performing, for each of a plurality of degrees of the syndrome polynomial, the operations of;

initializing a sum value to a first digital value of the input frame sequence;

accessing a selected one of the plurality of look-up tables, the selected look-up table corresponding to one of the plurality of power index values, to retrieve therefrom the contents of an entry corresponding to a current value of the sum value;

performing a finite field addition of the contents retrieved in the accessing step with a next digital value of the input frame sequence;

updating the sum value to the result of the performing step; and

repeating the accessing, performing, and updating operations for each of the digital value of the input frame sequence.

7. The programmable system of claim 6, wherein the program memory, read/write memory, and at least one execution unit are implemented in a single integrated circuit.

8. The programmable system of claim 6, wherein the number of look-up tables is equal to twice the number of correctable errors in the Reed-Solomon coding protocol.

9. A method of operating a programmable logic device to perform a Chien search procedure according to a Reed-Solomon coding protocol to identify roots of an input polynomial expressed as a sequence of input polynomial terms, comprising the steps of:

arranging a plurality of look-up tables in a memory, each of the plurality of look-up tables associated with one of a plurality of power index values, each of the plurality of look-up tables having one entry associated with each of a plurality of members of a finite field, each entry containing a finite field value corresponding to the finite field product of the associated finite field member and a finite field primitive raised to a power corresponding to the associated power index value of the look-up table; and

for each of a plurality of degrees of the input polynomial, initializing a product term to an input polynomial term of the corresponding degree in the input polynomial; and

for each of a plurality of iterations numbering the number of elements in the finite field, less one, generating a sum value by;

initializing the sum value to a lowest order input polynomial term;

initializing a loop index value;

combining the sum value with a current value of the product term associated with the loop index value, and setting the current sum value to the result of the combining;

accessing one of the plurality of look-up tables, the selected look-up table corresponding to the loop index value, to retrieve therefrom the contents of an entry corresponding to a current value of the product term;

updating the current value of the product term associated with the loop index value with the retrieved contents;

incrementing the loop index value;

repeating the combining, accessing, updating, and incrementing steps for a selected number of iterations; and

responsive to the sum value to zero, storing a root indicator of the iteration in a memory location, indicating the iteration for which a root of the input polynomial was detected.

10. The method of claim 9, wherein the selected number of iterations corresponds to the number of correctable errors for the Reed-Solomon protocol.

11. The method of claim 9, wherein the number of look-up tables is equal to the number of correctable errors in the Reed-Solomon coding protocol.

12. The method of claim 9, wherein the combining step comprises:

performing a finite field addition the sum value with a current value of the product term associated with the loop index value, and setting the current sum value to the result of the addition.

13. The method of claim 9, wherein the step of generating a sum value is performed simultaneously for a group of the plurality of iterations.

14. The method of claim 13, wherein the plurality of look-up tables are arranged so that each entry contains a group of finite field values, a first one of the group of finite field values corresponding to the finite field product of the associated finite field member and a finite field primitive raised to a power corresponding to the associated power index value of the look-up table, and a second one of the group of finite field values corresponding to the finite field product of the associated finite field member and a finite field primitive raised to twice the power corresponding to the associated power index value of the look-up table.

15. A programmable system for performing a Chien search procedure according to a Reed-Solomon coding protocol to identify roots of an input polynomial expressed as a sequence of input polynomial terms, comprising:

a read/write memory, having a portion arranged as a plurality of look-up tables in a memory, each of the plurality of look-up tables associated with one of a plurality of power index values, each of the plurality of look-up tables having one entry associated with each of a plurality of members of a finite field, each entry containing a finite field value corresponding to the finite field product of the associated finite field member and a finite field primitive raised to a power corresponding to the associated power index value of the look-up table

at least one execution unit coupled to the read/write memory, for executing a sequence of program instructions; and

a program memory, coupled to the at least one execution unit, for storing a sequence of program instructions for controlling the operation of the at least one execution unit to perform the operations of;

for each of a plurality of degrees of the input polynomial, initializing a product term to an input polynomial term of the corresponding degree in the input polynomial; and

for each of a plurality of iterations numbering the number of elements in the finite field, less one, generating a sum value by;

initializing the sum value to a lowest order input polynomial term;

initializing a loop index value;

combining the sum value with a current value of the product term associated with the loop index value, and setting the current sum value to the result of the combining;

accessing one of the plurality of look-up tables, the selected look-up table corresponding to the loop index value, to retrieve therefrom the contents of an entry corresponding to a current value of the product term;

updating the current value of the product term associated with the loop index value with the retrieved contents;

incrementing the loop index value;

repeating the combining, accessing, updating, and incrementing steps for a selected number of iterations; and

responsive to the sum value to zero, storing a root indicator of the iteration in a location of read/write memory, indicating the iteration for which a root of the input polynomial was detected.

16. The system of claim 15, wherein the selected number of iterations corresponds to the number of correctable errors for the Reed-Solomon protocol.

17. The system of claim 15, wherein the number of look-up tables is equal to the number of correctable errors in, the Reed-Solomon coding protocol.

18. The system of claim 15, wherein the combining operation comprises:

performing a finite field addition the sum value with a current value of the product term associated with the loop index value, and setting the current sum value to the result of the addition.

19. The system of claim 15, wherein the step of generating a sum value is performed simultaneously for a group of the plurality of iterations.

20. The system of claim 19, wherein the plurality of look-up tables are arranged so that each entry contains a group of finite field values, a first one of the group of finite field values corresponding to the finite field product of the associated finite field member and a finite field primitive raised to a power corresponding to the associated power index value of the look-up table, and a second one of the group of finite field values corresponding to the finite field product of the associated finite field member and a finite field primitive raised to twice the power corresponding to the associated power index value of the look-up table.

21. A method of operating a programmable logic device to perform Reed-Solomon decoding upon an input frame sequence of digital values, comprising the steps of:

arranging a plurality of look-up tables in a memory, each of the plurality of look-up tables associated with one of a plurality of power index values, each of the plurality of look-up tables having one entry associated with each of a plurality of members of a finite field, each entry containing a finite field value corresponding to the finite field product of the associated finite field member and a finite field primitive raised to a power corresponding to the associated power index value of the look-up table; and

performing a syndrome accumulation procedure comprising the steps of;

for each of a plurality of degrees of the syndrome polynomial, generating a syndrome polynomial coefficient by performing the operations of;

initializing a sum value to a first digital value of the input frame sequence;

accessing a selected one of the plurality of look-up tables, the selected look-up table corresponding to one of the plurality of power index values, to retrieve therefrom the contents of an entry corresponding to a current value of the sum value;

performing a finite field addition of the contents retrieved in the accessing step with a next digital value of the input frame sequence;

updating the sum value to the result of the performing step; and

repeating the accessing, performing, and updating operations for each of the digital value of the input frame sequence;

performing a Euclidean array function upon the syndrome polynomial coefficients;

then performing a Chien search procedure according to the Reed-Solomon coding protocol to identify roots of an input polynomial expressed as a sequence of input polynomial terms, comprising the steps of;

for each of a plurality of degrees of the input polynomial, initializing a product term to an input polynomial term of the corresponding degree in the input polynomial; and

for each of a plurality of iterations numbering the number of elements in the finite field, less one, generating a sum value by;

initializing the sum value to a lowest order input polynomial term;

initializing a loop index value;

combining the sum value with a current value of the product term associated with the loop index value, and setting the current sum value to the result of the combining;

accessing one of the plurality of look-up tables, the selected look-up table corresponding to the loop index value, to retrieve therefrom the contents of an entry corresponding to a current value of the product term;

updating the current value of the product term associated with the loop index value with the retrieved contents;

incrementing the loop index value;

repeating the combining, accessing, updating, and incrementing steps for a selected number of iterations; and

responsive to the sum value to zero, storing a root indicator of the iteration in a memory location, indicating the iteration for which a root of the input polynomial was detected; and

then using the identified roots of the Chien search procedure to correct errors in the digital values of the input frame sequence.