Symbol error correction by error detection and logic based symbol reconstruction
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.
1. A method for coding of a plurality of n-valued data symbols with n>2, comprising:
a processor associating the plurality of n-valued data symbols with a first and a second 2-dimensional matrix; and
the processor generating a plurality of check symbols along each dimension of the first and second matrix, each of the plurality of check symbols being generated by evaluating 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:
the processor receiving of the plurality of n-valued data symbols and the plurality of check symbols;
the processor associating the plurality of received n-valued data symbols with the first and the second matrix;
the processor generating a plurality of recalculated check symbols along each dimension of the first and the second matrix, each of the plurality of recalculated check symbols being generated by evaluating 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 a 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 the processor applying check symbols generated in accordance with one or more additional matrices.
9. The method as claimed in claim 1 , wherein an additional check symbol is generated by using an n-valued Linear Feedback Shift Register (LFSR).
10. The method as claimed in claim 1 , further comprising:
the processor 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, each of the plurality of check symbols being generated by evaluating 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, each of the plurality of recalculated check symbols being generated by evaluating 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 evaluating 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 the 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 the first plurality of symbols selected from the plurality of n-valued data symbols;
the processor 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
the processor generating 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:
the processor 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 selected from the plurality of n-valued data symbols; and
repeating the previous step until each symbol of the plurality of n-valued data symbols is associated with at least two check symbols.