Methods and systems for rapid error correction by forward and reverse determination of coding states
An encoder creates an (p,k,n) n-state codeword with p n-state symbols of which k n-state symbols are data symbols, an n-state symbol being represented by a signal with n>2, p>2 and k>(p-k). Intermediate states of an encoder in forward and in reverse direction are provided in a comparative n-state expression and implemented on a processor. A plurality of signals representing a codeword with at least one n-state symbol in error is processed by the processor by evaluating the comparative n-state expression. A partial result of an expression is determined after a symbol has been received. An error location and an error magnitude are determined. The error is corrected by the processor.
1. A method for error correction of a codeword of n-state symbols with n>2 containing a plurality of n-state data symbols and a plurality of n-state check symbols generated by a coder, an n-state symbol being represented by a signal, each check symbol being determined by an n-state expression wherein the n-state data symbols are variables, comprising:
retrieving by a processor from a memory two or more expressions, each expression determining a comparative coding state of the coder, wherein the comparative coding state combines a first coding state of the coder operated in a first direction from a starting state to an ending state and a corresponding second coding state of the coder operated in a direction that is a reverse of the first direction;
the processor evaluating the two or more expressions, wherein received n-state data symbols and n-state check symbols are variables to determine a plurality of comparative coding states;
the processor locating an n-state symbol in error in the codeword based on the plurality of comparative coding states;
the processor determining an error value for the symbol in error in the codeword from at least one comparative coding state; and
the processor determining a correct state for the symbol in error by applying the error value to a state of the symbol in error.
2. The method of claim 1 , wherein the comparative coding state is determined by the processor by evaluating a pre-determined comparative coding expression that has at least a subset of the plurality of n-state symbols of the codeword as variables and wherein the coder is a Reed-Solomon coder.
3. The method of claim 2 , wherein a partial result of the comparative coding expression is evaluated after an n-state symbol in the codeword has been received by the receiver and before a final n-state symbol in the codeword is available for processing by the processor.
4. The method of claim 2 , wherein an n-state symbol that is generated by a comparative coding expression that determines a comparative coding state is applied to determine the error value.
5. The method of claim 2 , wherein the comparative coding expression applies an n-state logic function that is defined over a finite field GF(n).
6. The method of claim 2 , wherein the codeword is characterized by an n-state Linear Feedback Shift Register.
7. The method of claim 2 , wherein the comparative coding expression is represented by a plurality of coefficients.
8. The method of claim 1 , wherein no syndrome is applied to determine the error location.
9. The method of claim 1 , wherein an n-state symbol is represented by a plurality of binary signals.
10. The method of claim 1 , wherein the method is implemented in a mobile communication receiver.
11. An apparatus to process a received codeword of n-state symbols with n>2 containing a plurality of n-state data symbols and a plurality of n-state check symbols generated by a coder, an n-state symbol being represented by a signal, each check symbol being determined by an n-state expression wherein n-state data symbols are variables, and wherein the coder is defined by an n-state Linear Feedback Shift Register with an initial state and a final state of a shift register, comprising:
a memory to store and retrieve data, including instructions;
a processor enabled to execute instructions to perform the steps:
determining a plurality of comparative coding states, each comparative coding state in the plurality of comparative coding states being determined by evaluating an expression that is determined by combining a first intermediate coding state of the coder operated in a first direction determined by the initial state and final state with a corresponding second intermediate coding state of the coder operated in a second direction that is a reverse of the first direction;
locating a symbol in error in the codeword from at least one of the plurality of comparative coding states;
determining an error value for the symbol in error from at least one comparative coding state; and
determining a correct state for the symbol in error by combining a state of the symbol in error with the error value for the symbol in error.
12. The apparatus of claim 11 , wherein each of the comparative coding states is determined by evaluating an comparative coding expression that has at least a subset of the plurality of n-state symbols in the received codeword as variables.
13. The apparatus of claim 12 , wherein a partial result of the comparative coding expression is evaluated after an n-state symbol in the codeword has been received by the receiver and before a next n-state symbol in the codeword is available for processing by the processor.
14. The apparatus of claim 12 , wherein an n-state symbol that is generated by a comparative coding expression that determines a comparative coding state is applied to determine the error value.
15. The apparatus of claim 12 , wherein the comparative coding expression applies an n-state logic function that is defined over a finite field GF(n).
16. The apparatus of claim 11 , wherein an n-state symbol is represented by a plurality of binary words.
17. The apparatus of claim 11 , wherein the apparatus is part of a communication device.
18. The apparatus of claim 11 , wherein the apparatus is part of a mobile communication receiving device.
19. The apparatus of claim 11 , wherein the apparatus is part of a data storage device.