On-the-fly error correction

Abstract

On-the-fly error correction is provided by using the remainder from division of the encoded codeword by its generator polynomial to look up error values and locations in a memory. Alternatively, the syndromes are so employed. The values in the memory are predetermined and preassociated with each remainder or syndrome set. Alternatively, syndrome S 0 directly yields the error value.

We claim: 
     
       1. On-the-fly error correction apparatus comprising: means for reading an encoded codeword from a data storage device and simultaneously supplying said codeword, symbol by symbol, to a buffer and to a divider means for dividing the encoded codeword by its generator polynomial;   said divider means comprising at least two registers and a corresponding number of Galois field multipliers, and resultant in said registers after all symbols of the codeword have been divided comprising a remainder;   means responsive to said divider registers after all said codeword symbols have been divided for looking up an error location and value in a memory and for outputting the error value to a latch and the error location to a counter; and   means responsive to said latch; said counter, and said buffer for correcting an incorrect symbol of said codeword using the error value in said latch as located by the error location contained in said counter.   
     
     
       2. On-the-fly error correction apparatus comprising: means for reading an encoded codeword from a data storage device and simultaneously supplying said codeword, symbol by symbol, to a buffer and to a divider means for generating from the encoded codeword at least two syndromes;   said divider means comprising at least two registers and a corresponding number of Galois field multipliers, the values of the multipliers being chosen such that the resultant in said register after all symbols of the codeword and a number of zero-valued symbols, the number corresponding to the number of registers, have been divided comprising syndromes S 0  and S1;   means responsive to said at least two syndromes contained in said divider means registers for looking up an error location and value in a memory and for outputting the error value to a latch and the error location to .Iadd.a .Iaddend.counter; and   means responsive to said latch, said counter, and said buffer for correcting an incorrect symbol of said codeword using the error value in said latch as located by the error location contained in said counter.   
     
     
       3. On-the-fly error correction apparatus comprising: means for reading an encoded codeword from a data storage device and simultaneously supplying said codeword, symbol by symbol, to a buffer and to a divider means for generating from the encoded codeword a syndrome and a remainder, said syndrome comprising an error value;   said divider means comprising at least two registers and a corresponding number of Galois field multipliers, the values of the multipliers being chosen such that the resultant in said the lowest-order register after all symbols of the codeword and a number of zero-valued symbols, the number corresponding to the number of registers, have been divided comprising syndrome S 0  ;   means responsive to the remainder in said registers for looking up an error location in a memory and for outputting the error value to a latch and the error location to .Iadd.a .Iaddend.counter; and   means responsive to said latch, said counter, and said buffer for correcting an incorrect symbol of said codeword using the error value in said latch as located by the error location contained in said counter.   
     
     
       4. Apparatus according to claim 3 wherein codeword is formed from a generator polynomial having the root α 0  and said syndrome is the formed from the root α 0 . 
     
     
       5. On-the-fly error correction apparatus comprising: means for reading an encoded codeword from a data storage device and simultaneously supplying said codeword, symbol by symbol, to a buffer and to a divider means for generating from the encoded codeword at least two syndromes, a first of said syndromes comprising an error value;   said divider means comprising at least two registers and a corresponding number of Galois field multipliers, the values of the multipliers being chosen such that the resultant in the lowest-order register after all symbols of the codeword and a number of zero-valued symbols, the number corresponding to the number of registers, have been divided comprising syndrome S 0  ;   means responsive to said at least two syndromes in said registers for looking up an error location in a memory and for outputting the error value to a latch and the error location to .Iadd.a .Iaddend.counter; and   means responsive to said latch, said counter, and said buffer for correcting an incorrect symbol of said codeword using the error value in said latch as located by the error location contained in said counter.   
     
     
       6. Apparatus according to claim 5 wherein said codeword is formed from a generator polynomial having the root α 0  and said first syndrome is the formed from the root α 0 . .[.7. On-the-fly error correction apparatus comprising: means for reading an encoded codeword from a data storage device and simultaneously supplying said codeword, symbol by symbol, to a buffer and to a divider means for generating two syndromes in a pair of registers from a codeword encoded by means of an irreducible polynomial P(X) having a root α and a finite field of elements α i  modulo P(X), a first of said syndromes in a first register comprising an error value;   locator means responsive to said first register and a second register containing the second of said syndromes for comparing the value of the first syndrome with the value of the field element α i  times the second syndrome until the values are equal, the power of α i  when the values are equal comprising the error location; and   means responsive to said first register, said locator means, and said buffer for correcting an incorrect symbol of said codeword using the error value in said first register as located by the error location determined by said locator means..]. .[.8. Apparatus according to claim 7 wherein said codeword is formed from a generator polynomial having the root α 0  and said first syndrome is the formed from the root α 0 ..]. .[.9. Apparatus according to claim 8 wherein said codeword is formed from a generator polynomial having the root α 1  and said second syndrome is the formed from the root   
     
     
        α 1 ..]. .Iadd.10.  An on-the-fly error correction apparatus, comprising: reading means for reading an encoded codeword from data storage media, the codeword encoded by means of an irreducible polynomial P(X) having a root α and a finite field of elements α i  modulo P(X);   a buffer, coupled to the reading means, for storing the codeword;   divider means, coupled to the reading means and including first and second divider registers and first and second Galois field multipliers, for generating a first divider register value and a second divider register value from the codeword, for storing the first divider register value in the first divider register, and for storing the second divider register value in the second divider register;   first syndrome generating means, coupled to the divider means, for summing the first divider register value and the second divider register value to obtain a first syndrome of the codeword, the first syndrome comprising an error value;   second syndrome generating means, coupled to the divider means, for summing the first divider register value and the output of the first Galois field multiplier to obtain a second syndrome of the codeword;   error locator means, coupled to the second syndrome generating means and the first syndrome generating means, for comparing the error value with the value of the second syndrome times the field element α i  until the values are equal, the power of α i  when the values are equal comprising an error location corresponding to the error value; and   correction means responsive to the buffer, the error locator means, and the first syndrome generating means, for correcting an incorrect symbol of the codeword using the error value as located by the error location determined   
     
     
        by the error locator means. .Iaddend. .Iadd.11.  Apparatus according to claim 10 wherein said codeword is formed from a generator polynomial having the root α 0  and said first syndrome is formed from the root α 0 . .Iaddend. .Iadd.12. Apparatus according to claim 11 wherein said codeword is formed from a generator polynomial having the root α 1  and said second syndrome is formed from the root α 1 . .Iaddend.