Methods and systems for rapid error correction of Reed-Solomon codes
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, comprising:
receiving by a processor of a Reed-Solomon codeword of n-state symbols with n>2 containing a plurality of n-state data symbols and a plurality of n-state check symbols, an n-state symbol being represented by a signal;
the processor determining a plurality of comparative coding states of a coder enabled to determine the plurality of n-state check symbols, each comparative coding state of the plurality of comparative coding states being determined by combining one of a first plurality of intermediate coding states of the coder with a corresponding one of a second plurality of intermediate coding states of the coder, wherein each of the first plurality of intermediate coding states is a state of the coder being operated from a first initial state towards a first final state and each of the second plurality of intermediate coding states is a state of the coder being operated from a second final state towards a second initial state;
the processor locating a symbol in error in the Reed-Solomon codeword based on the plurality of comparative coding states; and
the processor determining a correct state for the symbol in error in the Reed-Solomon codeword.
2. The method of claim 1 , wherein a comparative coding state is determined by the processor by evaluating a pre-determined comparative coding expression that has at least a subset of the n-state symbols in the Reed-Solomon codeword as variables.
3. The method of claim 2 , wherein the pre-determined comparative coding expression is represented by a plurality of coefficients.
4. The method of claim 2 , wherein the coder is characterized by an n-state Linear Feedback Shift Register including at least one multiplier not being 0 or 1 over a finite field GF(n) that is operated in a forward and in a reverse direction.
5. The method of claim 2 , wherein the pre-determined 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 a partial result of the pre-determined comparative coding expression is evaluated after an n-state symbol in the Reed-Solomon codeword has been received by the processor and before a next n-state symbol in the Reed-Solomon codeword is available for processing by the processor.
7. The method of claim 1 , wherein a partial result of the correct state of the symbol in error is generated by an n-state expression.
8. The method of claim 1 , wherein the first initial state of a coder to generate the Reed-Solomon codeword is not determined by all 0 state n-state symbols.
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, comprising:
a memory to store and retrieve data, including instructions;
a processor enabled to execute instructions to perform the steps:
processing 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, an n-state symbol being represented by a signal;
determining a plurality of comparative coding states of a coder enabled to determine the plurality of n-state check symbols, each comparative coding state of the plurality of comparative coding states being determined by combining one of a first plurality of intermediate coding states of the coder with a corresponding one of a second plurality of intermediate coding states of the coder wherein each of the first plurality of intermediate coding states is a state of the coder being operated from a first initial state towards a first final state and each of the second plurality of intermediate coding states is a state of the coder being operated from a second final state towards a second initial state;
locating a symbol in error in the codeword from the plurality of comparative coding states; and
determining a correct state for the symbol in error in the codeword.
12. The apparatus of claim 11 , wherein a comparative coding state is determined by evaluating an comparative coding expression that has at least a subset of the plurality of n-state data symbols and the plurality of n-state check 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 processor and before a next n-state symbol in the codeword is available for processing by the processor.
14. The apparatus of claim 12 , wherein a partial result of the correct state of the symbol in error is generated by an n-state expression.
15. The apparatus of claim 11 , wherein the codeword is corrected before a symbol in a next codeword is received.
16. 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).
17. The apparatus of claim 11 , wherein an n-state symbol is represented by a plurality of binary signals.
18. The apparatus of claim 11 , wherein the apparatus is part of a communication device.
19. The apparatus of claim 11 , wherein the apparatus is part of a mobile communication receiving device.
20. The apparatus of claim 11 , wherein the apparatus is part of a data storage device.