Methods and Systems for Rapid Error Location in 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 or error value are determined. The error is corrected by the processor.
1 . A method for error location in a codeword of p n-state symbols with n>2 and p>2, comprising:
receiving by a processor of the codeword of p n-state symbols containing a plurality of n-state data symbols and at least one n-state check symbol, an n-state symbol being represented by a signal, wherein the codeword is determined by a coder;
the processor determining a plurality of comparative coding states of the coder, based on the coder being operated from a first initial state to a first end state and from a second final state towards a second initial state; and
the processor locating a symbol in error in the codeword based on the plurality of comparative coding states.
2 . The method of claim 1 , further comprising the processor determining a correct state for the symbol in error in the codeword
3 . The method of claim 1 , wherein the coder includes an n-state linear feedback shift register.
4 . 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 codeword as variables.
5 . The method of claim 1 , wherein the processor determines an error value of the symbol in error from at least one of the plurality of comparative coding states.
6 . The method of claim 1 , wherein the coder is a Reed-Solomon coder.
7 . The method of claim 1 , wherein the symbol in error is part of a plurality of adjacent n-state symbols in the codeword that is in error.
8 . The method of claim 1 , wherein an n-state symbol is represented by a plurality of binary signals.
9 . The method of claim 1 , wherein the processor is part of a mobile computing device.
10 . The method of claim 3 , wherein the comparative coding expression is represented by a plurality of coefficients stored in a memory.
11 . An apparatus, comprising:
a memory to store and retrieve data, including instructions;
a processor enabled to execute instructions to perform the steps:
receiving a codeword of p n-state symbols with n>2 and p>2 containing a plurality of n-state data symbols and at least one n-state check symbol, an n-state symbol being represented by a signal, wherein the codeword is determined by a coder;
determining a plurality of comparative coding states of the coder, based on the coder being operated from a first initial state to a first end state and from a second final state towards a second initial state; and
locating a symbol in error in the codeword based on the plurality of comparative coding states.
12 . The apparatus of claim 11 , wherein the coder includes an n-state linear feedback shift register.
13 . The apparatus of claim 11 , 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 codeword as variables.
14 . The apparatus of claim 11 , wherein the processor determines an error value of the symbol in error from at least one of the plurality of comparative coding states which is combined with a state of the n-state symbol in error to determine the correct state of the n-state symbol in error.
15 . The apparatus of claim 11 , wherein the symbol in error is part of a plurality of adjacent n-state symbols in the codeword that is in error.
16 . The apparatus of claim 11 , wherein the codeword is a Reed-Solomon codeword.
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 computing device.
19 . The apparatus of claim 11 , wherein the apparatus is part of a data storage device.
20 . The apparatus of claim 13 , wherein a partial result of the pre-determined 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 has been processed by the processor.