Parallel spectral reed-solomon encoder and decoder

• US 6,308,295 B1
• Filed: 10/07/1997
• Issued: 10/23/2001
• Est. Priority Date: 10/08/1996
• Status: Expired due to Fees

• Current Assignee: Arizona Board of Regents (University of Arizona)
• Original Assignee: Arizona Board of Regents (University of Arizona)
• Inventors: Sridharan, Satish, Neifeld, Mark A.
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): JUNG, DAVID YIUK
• Application Number:
  US08/946,166
• Time in Patent Office: 1,477 Days
• Field of Search: 375/200-315, 370/200-479, 371/30-72, 707/1-206, 714/781-785, 714/746-759
• US Class Current: 714/755
• CPC Class Codes: A61H 2203/0425 Sitting on the buttocks
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/1595 Parallel or block-wise remainder calculation
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

In the disclosed error correcting scheme, information data is encoded and decoded in parallel and in the spectral or frequency domains based on a Reed-Solomon (RS) code. As a result, when compared with space domain decoding, the spectral decoding scheme of the present invention shifts some of the computationally intensive modules into the encoder thus reducing decoder complexity. Thus, integrated circuit implementations of the error correcting scheme of the present invention are faster, have reduced power dissipation and occupy less chip area than serial encoders and decoders.

Claims

1. An encoding/decoding system, comprising:

a first integrated circuit including an encoder circuit symbols in response to second selected symbols of said spectral domain data and said plurality of error coefficients; and

a comparison circuit comparing said error symbols with said spectral domain symbols to obtain said user information data as a result of said comparison.

2. An encoding/decoding system in accordance with claim 1, wherein said encoder circuit comprises:

a space domain transforming circuit acting on said user information data in parallel to transform said user information data into space domain data to thereby generate said encoded data for transmission through said transmission medium.

3. An encoding/decoding system in accordance with claim 2, wherein said space domain transforming circuit comprises an inverse finite field fast Fourier transform circuit.

4. An encoding/decoding system in accordance with claim 2, wherein said user information data comprises a plurality of information symbols, said encoder further comprising:

an appending circuit for attaching a plurality of error correcting symbols to k information symbols where k is an integer, each said error correcting symbols being substantially the same, said appending circuit outputting a codeword to said space domain transforming circuit, said codeword being n symbols in length, where n is an integer greater than k, said codeword including said k information symbols and n−

k error correcting symbols.

5. An encoding/decoding system in accordance with claim 4, wherein each said plurality of error correcting symbols comprises zeros.

6. An encoding/decoding system in accordance with claim 1, wherein said spectral domain transforming circuit comprises a finite field fast Fourier transform circuit.

7. An encoding/decoding system in accordance with claim 1, wherein said comparison circuit comprises a summing circuit for adding said error bits to said spectral domain bits to thereby obtain said user information data.

8. An encoding/decoding system in accordance with claim 1, wherein said comparison circuit comprises a difference circuit for subtracting said error bits from said spectral domain bits to thereby obtain said user information data.

9. An encoding/decoding system in accordance with claim 1, further comprising a memory for storing said spectral domain symbols and supplying said spectral domain data to said comparison circuit.

10. An integrated circuit including a decoder circuit configured to correct errors present in Reed-Solomon encoded data and decoding said encoded data to output user information data, said decoder circuit comprising:

a spectral domain transforming circuit transforming said Reed-Solomon encoded data into parallel spectral domain data, said parallel spectral domain data comprising a plurality of spectral domain symbols;

an error signal generating circuit coupled to said inverse spectral domain transforming circuit, said error signal generating circuit outputting a plurality of error symbols in response to said parallel spectral domain symbols, said error signal generating circuit further comprising;

a Berlekamp algorithm circuit acting on parallel first selected symbols of said spectral domain symbols to output a plurality of error coefficients in parallel, said Berlekamp algorithm circuit including at least t stages, where 2t=n−

k, n being a number of symbols in a code word generated by said encoding circuit and k being a number of information symbols, each of said stages being spaced from one another and outputting a corresponding one of a term of an error locator polynomial; and

a recursive extension circuit acting on said plurality of parallel error coefficients and second parallel selected symbols of said spectral domain data to output said error symbols; and

a comparison circuit comparing said error symbols with said spectral domain symbols to obtain said user information data as a result of said comparison.

11. A decoder circuit in accordance with claim 10, wherein said spectral domain transforming circuit comprises a finite field fast Fourier transform circuit.

12. A decoder circuit in accordance with claim 10, wherein said comparison circuit comprises a summing circuit for adding said error symbols to said spectral domain symbols to thereby obtain said user information data.

13. A decoder in accordance with claim 10, wherein said comparison circuit comprises a difference circuit for subtracting said error bits from said spectral domain bits to thereby obtain said user information data.

14. A decoder circuit in accordance with claim 10, further comprising a memory for storing said spectral domain symbols and supplying said spectral domain symbols to said comparison circuit.