Symbol Error Correction by Error Detection and Logic Based Symbol Reconstruction

• US 20080104479A1
• Filed: 01/04/2008
• Published: 05/01/2008
• Est. Priority Date: 09/08/2004
• Status: Active Grant

• Current Assignee: Ternarylogic LLC
• Original Assignee: Ternarylogic LLC
• Inventors: Lablans, Peter
• Granted Patent: US 8,046,661 B2
• Time in Patent Office: Days
• US Class Current: 714/757
• CPC Class Codes: G06F 11/08 Error detection or correction by redundancy in data representation, e.g. by using checking codes
• CPC Class Codes: H04L 1/0065 Serial concatenated codes

Abstract

Methods and apparatus for creating codewords of n-valued symbols with one or more n-valued check symbols are disclosed. Associating the codewords with a matrix allows for detection of one or more symbols in error and the location of such symbols in error. Methods to reconstruct symbols in error from other symbols not in error are also disclosed. Systems for using the methods of error detection and error correction by symbol reconstruction are also disclosed. Using two or more matrices to determine check symbols is also provided.

Claims

1. A method for coding of a plurality of n-valued data symbols with n>

2, comprising;

associating the plurality of n-valued data symbols with a first and a second 2-dimensional matrix; and

generating a plurality of check symbols along each dimension of the first and second matrix, a check symbol being generated by applying an n-valued logic expression wherein data symbols are variables.

2. The method as claimed in claim 1, wherein the n-valued logic expression uses an n-valued non-adder function.

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

receiving of the plurality of n-valued data symbols and the plurality of check symbols;

associating the plurality of received n-valued data symbols with the first and the second matrix;

generating a plurality of recalculated check symbols along each dimension of the first and the second matrix, a recalculated check symbol being generated by applying an n-valued logic expression wherein received data symbols are variables.

4. The method as claimed in claim 3, further comprising locating one or more symbols for error correction by applying only received and recalculated check symbols.

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

error-correcting by applying an n-valued logic expression having an symbol for error correction as an unknown.

6. The method as claimed in claim 5, wherein the n-valued logic expression uses an n-valued non-adder function.

7. The method as claimed in claim 6, wherein the n-valued logic expression is part of applying Cramer'"'"'s rule.

8. The method for error correction as claimed in claim 1, further comprising applying check symbols generated in accordance with one or more additional matrices.

9. The method as claimed in claim 1, wherein a check symbol is generated by using an n-valued Linear Feedback Shift Register (LFSR).

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

generating one or more n-valued check symbols from the plurality of check symbols.

11. A system for coding a plurality of n-valued data symbols with n>

2, comprising;

a coding processor, the coding processor operative to perform the steps of;

associating the plurality of n-valued data symbols with a first and a second 2-dimensional matrix; and

generating a plurality of check symbols along each dimension of the first and second matrix, a check symbol being generated by applying an n-valued logic expression wherein data symbols are variables.

12. The system as claimed in claim 11, wherein n>

2.

13. The system as claimed in claim 11, further comprising:

a decoding processor, the decoding processor operative to perform the steps of;

associating a plurality of received n-valued data symbols with the first and the second matrix;

generating a plurality of recalculated check symbols along each dimension of the first and the second matrix, a recalculated check symbol being generated by applying an n-valued logic expression wherein received data symbols are variables.

14. The system as claimed in claim 13, further comprising locating one or more symbols for error correction by applying only received and recalculated check symbols.

15. The system as claimed in claim 14, further comprising error-correcting by applying an n-valued logic expression having the symbol for error correction as an unknown.

16. The system as claimed in claim 11, further comprising generating of additional check symbols from a plurality of check symbols.

17. The system as claimed in claim 16, further comprising correcting errors in the check symbols.

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

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

20. The system as claimed in claim 11, wherein n-valued symbols are represented by binary symbols.

21. A method for coding a plurality of n-valued data symbols with n>

2, comprising;

generating a first n-valued check symbol from a first plurality of symbols selected from the plurality of n-valued data symbols;

generating a second n-valued check symbol from a second plurality of symbols selected from the plurality of n-valued data symbols, the first and the second plurality of n-valued data symbols having at least one n-valued data symbol in common; and

generating of at least one check symbol by an n-valued logic expression using an n-valued non-adder function.

22. The method as claimed in claim 21, further comprising:

generating an additional n-valued check symbol from an additional plurality of symbols selected from the plurality of n-valued data symbols, the additional plurality of symbols having at least one n-valued data symbol in common with another plurality of symbols associated with a check symbol; and

repeating the previous step until each symbol of the plurality of n-valued data symbols is associated with at least two check symbols.