Error correction in multi-valued (p,k) codes

• US 9,203,436 B2
• Filed: 07/11/2007
• Issued: 12/01/2015
• Est. Priority Date: 07/12/2006
• Status: Expired due to Fees

• Current Assignee: Ternarylogic LLC
• Original Assignee: Ternarylogic LLC
• Inventors: Lablans, Peter
• Primary Examiner(s): Torres, Joseph D
• Application Number:
  US11/775,963
• Publication Number:
  US 20080016432A1
• Time in Patent Office: 3,065 Days
• Field of Search: 714/781, 714/755, 714/756
• US Class Current: 1/1
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/151 using error location or error correction polynomials
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/154 Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial
• CPC Class Codes: H03M 13/1545 Determination of error locations, e.g. Chien search or other methods or arrangements for the determination of the roots of the error locator polynomial
• CPC Class Codes: H03M 13/157 Polynomial evaluation, i.e. determination of a polynomial sum at a given value
• CPC Class Codes: H03M 13/1575 Direct decoding, e.g. by a direct determination of the error locator polynomial from syndromes and subsequent analysis or by matrix operations involving syndromes, e.g. for codes with a small minimum Hamming distance
• CPC Class Codes: H03M 13/158 Finite field arithmetic processing
• CPC Class Codes: H03M 13/1585 Determination of error values
• CPC Class Codes: H03M 13/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations

Abstract

Methods, apparatus and systems for error correction of n-valued symbols in (p,k) codewords including Reed Solomon codes of p n-valued symbols with n>2 and k information symbols have been disclosed. Coders and decoders using a Linear Feedback Shift Registers (LFSR) are applied. An LFSR can be in Fibonacci or Galois configuration. Errors can be corrected by execution of an n-valued expression in a deterministic way. Error correcting methods using Galois arithmetic are disclosed. Methods using Cramer'"'"'s rule are also disclosed. Deterministic error correction methods based on known symbols in error are provided, making first determining error magnitudes not necessary. An error location methods using up and down state tracking is provided. Methods and apparatus executing the methods with binary circuits are also disclosed. Systems using the error correcting methods, including communication systems and data storage systems are also provided.

Claims

1. A method for correcting an n-valued symbol in error in an n-valued codeword of a (p,k) code having p n-valued symbols of which k n-valued symbols are information symbols and (p−

k) symbols are check symbols with p>

1, n>

2 and k>

1, comprising;

receiving by a processor of the n-valued codeword that is a Reed-Solomon codeword wherein each n-valued symbol in the n-valued codeword is represented by a signal;

determining by the processor of a location of the n-valued symbol in error in the n-valued codeword based on check symbols in the n-valued codeword;

selecting by the processor of a pre-determined n-valued expression from a plurality of pre-determined expressions based on the location of the n-valued symbol in error; and

calculating by the processor a correct value of the n-valued symbol in error by evaluating the predetermined n-valued expressions which applies one or more of the p n-valued symbols not in error as an input variable and wherein the predetermined n-valued expression applies at least one n-valued logic function and outputs the correct value of the n-valued symbol in error.

2. The method as claimed in claim 1, further comprising:

locating by the processor of the n-state symbol in error in the n-state codeword by determining a plurality of intermediate comparative coding states associated with the Reed-Solomon codeword.

3. The method as claimed in claim 1, wherein determining the location of the symbol in error is performed by calculating a syndrome.

4. The method as claimed in claim 1, further comprising determining that errors have not occurred exclusively in a check symbol.

5. The method as claimed in claim 1, wherein the n-valued expression uses addition and multiplication over GF(n).

6. The method as claimed in claim 5, wherein n=2^m and m is an integer greater than 1, an n-valued symbol is represented by a plurality of binary symbols, and the addition and multiplication over GF(n) are executed by binary functions.

7. The method as claimed in claim 1, wherein each codeword of the (p,k) code has at most k symbols in common in corresponding positions with any other codeword of the (p,k) code.

8. The method as claimed in claim 1, wherein each codeword of the (p,k) code has at most (k−

1) symbols in common in corresponding positions with any other codeword of the (p,k) code.

9. The method as claimed in claim 1, wherein a check symbol in the codeword is created by executing a check symbol determining n-valued expression.

10. The method as claimed in claim 9, wherein each check symbol is represented by a plurality of binary symbols and is created by applying a binary logic function.

11. The method of claim 1, wherein the method is used in a receiver of a communication system.

12. An apparatus for correcting an n-valued symbol in error in an n-valued codeword of a (p,k) code having p n-valued symbols of which k n-valued symbols are information symbols and (p−

k) symbols are check symbols with p>

1, n>

2 and k>

1, comprising;

a processor executing instructions to perform the steps of;

receiving the n-valued codeword that is a Reed-Solomon codeword wherein each n-valued symbol in the n-valued codeword is represented by a signal and an n-valued symbol is in error with an unknown location in the Reed-Solomon codeword;

determining the location of the n-valued symbol in error in the n-valued Reed-Solomon codeword;

selecting a predetermined n-valued expression based on the location of the n-valued symbol in error from a plurality of predetermined expressions; and

determining a correct value of the n-valued symbol in error by evaluating the predetermined n-valued expression which applies one or more of the p n-valued symbols not in error directly as an input variable and wherein the pre-determined n-valued expression applies at least one n-valued logic function and outputs the correct value of the n-valued symbol in error.

13. The apparatus as claimed in claim 12, further performing the step of determining that errors have not occurred exclusively in a check symbol.

14. The apparatus of claim 12, wherein the apparatus in a storage device.

15. A system for processing a (p,k) codeword having p n-valued symbols of which k n-valued symbols are information symbols and (p−

k) symbols are check symbols with p>

1, n>

2 and k>

1, the codeword having a symbol in error, comprising;

a receiver which receives the p symbols of the (p,k) codeword;

a processor performing the steps of;

receiving the (p,k) codeword that is a Reed-Solomon codeword wherein each n-valued symbol in the n-valued codeword is represented by a signal and an n-valued symbol is in error with an unknown location in the Reed-Solomon codeword;

determining the location of the n-valued symbol in error in the Reed-Solomon codeword; and

calculating a correct value of the n-valued symbol in error by non-iteratively evaluating a single predetermined n-valued expression that is selected from a plurality of at least three predetermined n-valued expressions based on the location of the n-valued symbol in error, the selected single predetermined n-valued expression outputting the correct value.

16. The system as claimed in claim 15, wherein the system is a communication system.

17. The system as claimed in claim 15, wherein the system is a data storage system.

18. The system of claim 15, wherein the processor locates the n-state symbol in error in the n-state codeword by determining a plurality of intermediate comparative coding states.