ERROR CORRECTION BY SYMBOL RECONSTRUCTION IN BINARY AND MULTI-VALUED CYCLIC CODES

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

• Current Assignee: Peter Lablans
• Original Assignee: Peter Lablans
• Inventors: Lablans, Peter
• Granted Patent: US 9,203,438 B2
• Time in Patent Office: Days
• US Class Current: 714/777
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• 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/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• 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/3776 using a re-encoding step during the decoding process

Abstract

Methods, apparatus and systems for error correction of n-valued symbols in codewords of p n-valued symbols with n>2 and for n=2 and k information symbols have been disclosed. Coders and decoders using a Linear Feedback Shift Registers (LFSR) are applied to generate codewords and detect the presence of errors. An LFSR can be in Fibonacci or Galois configuration. Errors can be corrected by execution of an n-valued expression in a deterministic non-iterative way. Deterministic error correction methods based on known symbols in error are provided. Corrected codewords can be identified by comparison with received codewords in error. N-valued LFSR based pseudo-noise generators and methods to determine if an LFSR is appropriate for generating error correcting codes are also disclosed. Methods and apparatus applying error free assumed windows and error assumed windows are disclosed. Systems using the error correcting methods, including communication systems and data storage systems are also provided.

Claims

1. A method for error correction decoding comprising:

receiving a codeword having p n-valued symbols with n≧

2 of which k n-valued symbols are information symbols and (p−

k) n-valued symbols are check symbols; and

executing non-iteratively an n-valued logic expression for calculating an n-valued symbol in an error corrected codeword.

2. The method as claimed in claim 1, further comprising determining a correctness of the error corrected codeword by comparing it to the codeword.

3. The method as claimed in claim 1, wherein n>

2.

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

generating a codeword of p n-valued symbols by processing k n-valued information symbols by an n-valued Linear Feedback Shift Register (LFSR) based coder.

5. The method as claimed in claim 1, wherein p>

n.

6. The method as claimed in claim 1, wherein up to t errors can be corrected in the codeword of p n-valued symbols and k information symbols when 2*t+1≦

(p−

k).

7. The method as claimed in claim 1, wherein the codeword is one of a plurality of codewords and the codeword has no more than k symbols in k positions in common with k symbols in like positions in any other codeword in the plurality of codewords.

8. The method as claimed in claim 4, wherein the LFSR is in Fibonacci configuration.

9. The method as claimed in claim 4, wherein the LFSR is in Galois configuration.

10. The method as claimed in claim 1, wherein the n-valued logic expression reflects a plurality of symbols assumed to be not in error in the codeword.

11. The method as claimed in claim 1, wherein an n-valued symbol is represented as one or more binary symbols.

12. An apparatus for error correction of up to t n-valued symbols of a codeword of p n-valued symbols with n≧

2 of which k n-valued symbols are information symbols, comprising;

an input enabled for receiving the codeword;

an n-valued logic unit executing in a non-iterative manner an n-valued logic expression for calculating at least one n-valued symbol in a calculated codeword; and

an output providing at least k n-valued symbols.

13. The apparatus as claimed in claim 12, further comprising a decision unit for comparing the calculated codeword with the codeword.

14. The apparatus as claimed in claim 12, wherein n>

2.

15. The apparatus as claimed in claim 12, wherein p>

n.

16. The apparatus as claimed in claim 12, further comprising:

an LFSR based unit for processing k n-valued symbols of the codeword into a check codeword of p n-valued symbols; and

a unit for comparing the check codeword with the codeword.

17. The apparatus as claimed in claim 12, wherein the maximum number of t symbols in error that can be corrected in a codeword of p n-valued symbols with k n-valued information symbols is provided by the expression 2*t+1=(p−

k).

18. A system for error correction of up to t n-valued symbols with n≧

2 in a codeword of p n-valued symbols of which k n-valued symbols are information symbols, comprising;

a processor; and

a memory in communications with the processor, the memory including program code executable by the processor to perform the following steps;

receiving the codeword of p n-valued symbols of which k n-valued symbols are information symbols on an input; and

executing non-iteratively an n-valued logic expression for calculating an n-valued symbol in an error corrected codeword.

19. The system as claimed in claim 18 further enabled to perform a step of determining a correctness of the error corrected codeword by comparing it to the codeword.

20. The system as claimed in claim 18, wherein n>

2.

21. The system as claimed in claim 18, wherein p>

n.

22. The system as claimed in claim 18, wherein up to t errors can be corrected in the codeword of p n-valued symbols and k information symbols when 2*t+1≦

(p−

k).

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

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

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

26. The system as claimed in claim 18, wherein an n-valued symbol is represented by one or more binary symbols.