Error Correction in Multi-Valued (p,k) Codes

• US 20080016432A1
• Filed: 07/11/2007
• Published: 01/17/2008
• Est. Priority Date: 07/12/2006
• Status: Active Grant

• Current Assignee: Ternarylogic LLC
• Original Assignee: Ternarylogic LLC
• Inventors: Lablans, Peter
• Granted Patent: US 9,203,436 B2
• Time in Patent Office: Days
• US Class Current: 714/784
• 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;

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

calculating a correct value of the symbol in error from an n-valued expression that does not use any of the p n-valued symbols that are in error.

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

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 (p,k) code is a Reed Solomon code.

6. The method as claimed in claim 1, wherein the correct value of the symbol in error is calculated by applying Cramer'"'"'s rule.

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

8. The method as claimed in claim 7, 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.

9. 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.

10. 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.

11. 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.

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

2. The method as claimed in claim 2, wherein determining the location of the symbol in error is performed by applying up-and-down state tracking.

13. 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 unit for determining a location of the symbol in error in the n-valued codeword; and

a unit for calculating a correct value of the symbol in error from an n-valued expression that does not use any of the p n-valued symbols that are in error.

14. The apparatus as claimed in claim 13, further comprising a unit determining that errors have not occurred exclusively in a check symbol.

15. The apparatus as claimed in claim 13, wherein the (p,k) code is a Reed Solomon code.

16. The apparatus as claimed in claim 13, wherein the unit for calculating the correct value of the symbol in error applies addition and multiplication over GF(n).

17. The apparatus as claimed in claim 16, wherein an n-valued symbol is represented by a plurality of binary symbols and addition and multiplication over GF(n) are performed with binary logic functions.

18. 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 unit for receiving the (p,k) codeword;

a processor; and

software operable on the processor to;

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

calculating a correct value of the symbol in error from an n-valued expression that does not use any of the p n-valued symbols that are in error.

19. The system as claimed in claim 18, wherein the system is a communication system.

20. The system as claimed in claim 18, wherein the system is a data storage system.