Multi-State Symbol Error Correction in Matrix Based Codes

• US 20090172501A1
• Filed: 03/10/2009
• Published: 07/02/2009
• Est. Priority Date: 03/03/2006
• Status: Active Grant

• Current Assignee: Ternarylogic LLC
• Original Assignee: Ternarylogic LLC
• Inventors: Lablans, Peter
• Granted Patent: US 8,832,523 B2
• Time in Patent Office: Days
• US Class Current: 714/784
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence
• CPC Class Codes: G06F 11/1028 Adjacent errors, e.g. error in n-bit (n>1) wide storage units, i.e. package error
• CPC Class Codes: G06F 11/1072 in multilevel memories
• CPC Class Codes: H03M 13/29 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes

Abstract

Methods and apparatus create codewords of n-state symbols having one of 3 or more states with n-state check symbols. Check symbols are created from independent expressions. Codewords are associated with a matrix for detection of one or more symbols in error and the location of such symbols in error. Symbols in error are reconstructed from symbols not in error, error syndromes and check symbols not in error. Deliberately created errors that can be corrected are used as nuisance errors.

Claims

1. An apparatus for correcting errors in a sequence of k n-state data symbols, an n-state symbol being represented by a signal, with n>

2, and k≧

1, comprising;

a memory enabled to store instructions;

a processor that retrieves and executes instructions from the memory to perform the steps of;

receiving on an input a plurality of signals representing the sequence of k n-state symbols and p n-state check symbols with p>

k, each of the signals representing p n-state check symbols being generated by an implementation of one of p independent reversible n-state expressions using the k n-state symbols as variables;

determining as an independent step which of up to p of the k n-state data symbols are potentially in error; and

solving as an independent step up to p independent n-state expressions to determine an n-state value for the up to p of the k n-state symbols that are potentially are in error, wherein the solving applies at least an implementation of an n-state reversible logic function that is determined by an n by n truth table.

2. The apparatus as claimed in claim 1, further comprising instructions to perform:

receiving on the input one or more signals representing one or more check-the-check symbols to correct an error in one or more of the p n-state check symbols.

3. The apparatus as claimed in claim 1, further comprising instructions to perform:

receiving on the input one or more signals representing one or more additional sequences of n-state symbols, each additional sequence containing k n-state data symbols and p n-state check symbols, each of the p n-state check symbols being generated by an implementation of one of p independent reversible n-state expressions with the k n-state symbols as variables;

receiving on the input signals representing at least q*k n-state check symbols with q≧

1 and q≦

p;

determining additional n-state data symbols in error by recalculating the n-state check symbols; and

solving any additional errors of up to p² errors.

4. The apparatus as claimed in claim 3, wherein a first plurality of n-state check symbols is determined by using a first arrangement of the k n-state data symbols in a first matrix and a second plurality of n-state check symbols is determined by using a second arrangement of the k n-state data symbols in a second matrix.

5. The apparatus as claimed in claim 1, wherein p errors have been introduced deliberately.

6. The apparatus as claimed in claim 5, wherein a position of an n-state data symbol in error is known to the apparatus.

7. The apparatus as claimed in claim 5, wherein instructions to solve the p errors are provided to the apparatus through a network.

8. The apparatus as claimed in claim 5, wherein instructions to solve the p errors are unique to the sequence of k n-state symbols.

9. The apparatus as claimed in claim 1, wherein the n-state reversible logic function is implemented in binary logic.

10. The apparatus as claimed in claim 1, wherein the apparatus is part of at least one of the group consisting of an audio player, a video player, a data storage device, and a communication device.

11. A method for correcting errors by a processor in a sequence of k n-state data symbols, an n-state symbol being represented by a signal, with n>

2, and k≧

1, comprising;

receiving on an input of the processor a plurality of signals representing the sequence of k n-state symbols and p n-state check symbols with p≦

k, each of the signals representing p n-state check symbols being generated by an implementation of one of p independent reversible n-state expressions using the k n-state symbols as variables;

determining as an independent step which of up to p of the k n-state data symbols are potentially in error; and

solving as an independent step up to p independent n-state expressions to determine an n-state value for the up to p of the k n-state symbols that are potentially are in error, wherein the solving applies at least an implementation of an n-state reversible logic function that is determined by an n by n truth table.

12. The method as claimed in claim 11, further comprising:

receiving on the input one or more signals representing one or more check-the-check symbols to correct an error in one or more of the p n-state check symbols.

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

receiving on the input one or more signals representing one or more additional sequences of n-state symbols, each additional sequence containing k n-state data symbols and p n-state check symbols, each of the p n-state check symbols being generated by an implementation of one of p independent reversible n-state expressions with the k n-state symbols as variables;

receiving on the input signals representing at least q*k n-state check symbols with q≧

1 and q≦

p;

determining additional n-state data symbols in error by recalculating the n-state check symbols; and

solving any additional errors of up to p² errors.

14. The method as claimed in claim 13, wherein a first plurality of n-state check symbols is determined by using a first arrangement of the k n-state data symbols in a first matrix and a second plurality of n-state check symbols is determined by using a second arrangement of the k n-state data symbols in a second matrix.

15. The method as claimed in claim 11, wherein p errors have been introduced deliberately.

16. The method as claimed in claim 15, wherein a position of an n-state data symbol in error is known to the apparatus.

17. The method as claimed in claim 15, wherein instructions to solve the p errors are provided to the processor through a network.

18. The method as claimed in claim 15, wherein instructions to solve the p errors are unique to the sequence of k n-state symbols.

19. The method as claimed in claim 11, wherein the processor is part of at least one of the group consisting of an audio player, a video player, a data storage device, and a communication device.

20. The method as claimed in claim 11, wherein the processor is part of a communication system.