Methods and Systems for Rapid Error Location in Reed-Solomon Codes

Abstract

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.