Patent Publication Number: US-4839896-A

Title: Fast remainder decoding for a Reed-Solomon code

Description:
BACKGROUND OF THE INVENTION 
     This invention relates to information storage and retrieval systems, and more particularly to means for decoding codewords for use in error detection and correction in such systems. Even more particularly, this invention relates to Reed-Solomon codes and related codes, and to improved methods for the decoding of such codes. 
     In a typical decoder, the coefficients of the syndrome polynomial, called frequency-domain syndromes, are first calculated by dividing the received codeword by each factor of the code generator polynomial. This process is hardware-intensive and/or time-consuming, depending on implementation. 
     It is possible to efficiently generate the coefficients of the remainder polynomial, called time-domain syndromes, by dividing the received codeword by the entire code generator polynomial. The time-domain syndromes contain the same information as the frequency-domain syndromes. 
     Methods of decoding using frequency-domain syndromes are known in the prior art, for example see Chapter 3 Practical Error Correction Design for Engineers by Neal Glover and Chapter 5 of Error-Correction Coding for Digital Communications by Clark and Cain. For cases of one error, two frequency-domain syndromes can be used to generate an error location and value, which are then checked with other frequency-domain syndromes using a &#34;Newton&#39;s Identities&#34; test. A similar procedure starting with four frequency-domain syndromes may be used to decode cases of two errors. The calculation of frequency-domain syndromes adds significant additional hardware and/or time delay to decoding of cases of one and two errors. 
     For cases of more than two errors, the frequency-domain syndromes are typically used to iteratively generate an error locator polynomial and an error evaluator polynomial. The error locator polynomial is typically used in a &#34;Chien&#34; search to locate the symbols in error, and the error evaluator polynomial is used to calculate the values of the symbol errors. This process is inefficient when used to locate and evaluate errors in cases of less than five errors. 
     It is thus apparent that there is a need in the art for improved decoding methods for Reed-Solomon codes and related codes. 
     SUMMARY OF THE INVENTION 
     Accordingly, it is an object of the present invention to provide improved decoding methods which decrease the correction time required for cases of one and two errors by decoding directly from time-domain syndromes without generating frequency-domain syndromes. 
     Another object is to provide improved methods to decrease the correction time required for cases of more than two errors by eliminating the Chien search when the number of yet-to-be-located errors is or has been reduced to four or less. 
     Another object is to provide improved methods to decrease the correction time required for cases of more than two errors by calculating error values directly from the syndrome polynomial and error locator polynomial without generating the error evaluator polynomial. 
     Another object is to provide improved methods to decrease the correction time required for cases of more than two errors by reducing the degree of the error locator polynomial and adjusting the syndrome polynomial as each successive error is located. 
     Another object is to provide improved methods to decrease the correction time required for interleaved codewords of variable lengths by avoiding multiplications by maintaining a parameter for computing pointers to data symbols and remainder coefficients of the first such interleaved codeword and adjusting it as each successive codeword is corrected. 
     The above and other objects are attained by the present invention which comprises means and methods for fast decoding of Reed-Solomon and related codes. Cases of one and two symbols in error are decoded directly from the read remainder, without computing syndromes. The location of a single symbol in error is quickly determined using the result of a single finite field division as an index into a small precomputed table. Using another larger precomputed table, the value is calculated and the validity of the location and value are confirmed. The larger precomputed table is also used to calculate and validate the locations and values of two symbols in error. Fast decoding of cases of more than two symbols in error is accomplished by employing direct solution of an error locator polynomial to locate errors when four or fewer errors remain to be located and by employing an optimized Chien search to locate errors when more than four errors remain to be located. The invention further simplifies and speeds the decoding of all cases of more than two symbols in error by eliminating the need to compute an error evaluator polynomial and by adjusting the error locator and syndrome polynomials after each error is found. 
     The above and other objects, features, and advantages of the instant invention will be more apparent from the following more particular description thereof present in conjunction with the accompanying drawings. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 shows the environment in which the instant invention is used. 
     FIG. 2 illustrates the steps required to decode Cases B, C.1, and C.2. 
     FIG. 2A illustrates the steps required to validate the error location and value for Cases B, C.1, and C.2 using sequential repeated blocks. 
     FIG. 3 illustrates the steps required to calculate σ 1  and σ 2  for Case D using R 0  through R 3 . 
     FIG. 4 illustrates the steps required to decode Case A and calculate σ 1  and σ 2  for Case D using R T-3  to R T . 
     FIG. 5 illustrates the steps required to calculate the error locations and values for Case D. 
     FIG. 6 illustrates the steps required to validate the error locations and values for Case D. 
     FIG. 6A illustrates the steps required to validate the error locations and values for Case D using sequential repeated blocks. 
     FIG. 7 illustrates the steps required to decode Case C.3. 
     FIG. 8 illustrates the steps required to calculate the coefficients of S(x) required to decode cases of three and four errors for Case E. 
     FIG. 9 illustrates the steps required to iteratively generate the error locator polynomial for Case E. 
     FIG. 9A illustrates the steps required to calculate the nth discrepancy d n  using sequential repeated blocks. 
     FIG. 10 illustrates the steps required to calculate the additional coefficients of S(x) required to decode cases of more than four errors for Case E. 
     FIG. 11 illustrates the steps required to locate and evaluate errors by searching for roots of σ(x) for Case E. 
     FIG. 11A illustrates the modifications to FIG. 11 required to evaluate α -ji  *σ(x) at x=α i  using sequential repeated blocks. 
     FIG. 12 illustrates the steps required to divide σ(x) by (x⊕α L ), compute the error value E, and adjust the coefficients of S(x) for Case E. 
     FIG. 13 illustrates the steps required to transfer control to the appropriate special error location subroutine for Case E. 
     FIG. 14 illustrates the steps required to solve for a root X, and its log L, of a quadratic equation in a finite field. 
     FIG. 15 illustrates the steps required to solve for a root X, and its log L, of a cubic equation in a finite field. 
     FIG. 16 illustrates the steps required to solve for the log L of one of the four roots of a quartic equation in a finite field. 
     FIG. 17 illustrates the steps required to correct errors in interleaved codewords. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The following description is of the best presently contemplated mode of carrying out the instant invention. This description is not to be taken in a limiting sense but is made merely for the purpose of describing the general principles of the invention. The scope of the invention should be determined with reference to the appended claims. 
     In a finite field GF(2 m ), elements are composed of m binary bits and addition (⊕) consists of MODULO 2 summation of corresponding bits; this is equivalent to performing the bit-wise EXCLUSIVE-OR sum of operands: 
     
         x⊕y=xXORy. 
    
     Note that subtraction is equivalent to addition since the MODULO 2 difference of bits is the same as their MODULO 2 sum. 
     Multiplication (*) may be implemented using finite field logarithm and antilogarithm tables wherein LOG [α i  ]=i and A LOG [i]=α i  : ##EQU1## where the addition of the finite field logarithms is performed MODULO 2 m  -1. LOG [0] is undefined. 
     Division (/) may be implemented similarly: ##EQU2## Note that for non-zero x, LOG [1/x]=-LOG [x]=LOG [x] XOR 2 m  -1. 
     In a decoder for an error detection and correction system using a Reed-Solomon or related code of distance d for the detection and correction of a plurality of errors in codewords of n symbols comprised of n-(d-1) data symbols and d-1 check symbols, each symbol an element of GF(2 m ), a codeword C(x) is given by 
     
         C(x)=(x.sup.3-1 *I(x))⊕((x.sup.d-1 *I(x)) MOD G(x))    (1) 
    
     where I(x) is an information polynomial whose coefficients are the n-(d-1) data symbols and G(x) is the code generator polymomial ##EQU3## where m 0  is a parameter of the code. A code of distance d can be used to correct all cases of t=INT((d-1)/2) errors without pointers and is guaranteed to detect all cases of INT(d/2) errors. 
     When e errors occur, the received codeword C&#39;(x) consists of the EXCLUSIVE-OR sum of a transmitted codeword C(x) and the error polynomial E(x): 
     
         C&#39;(x)=C(x)⊕E(x)                                        (3) 
    
     where 
     
         E(x)=E.sub.1 *x.sup.L.sbsp.1 ⊕ . . . E.sub.e *x.sup.L.sbsp.e (4) 
    
     L i  and E i  are the locations and values, respectively, of the e symbol errors. 
     The remainder 
     
         R(x)=R.sub.d-2 *x.sup.d-2 ⊕ . . . ⊕R.sub.1 *x⊕R.sub.0 (5) 
    
     is given by 
     
         R(x)=C&#39;(x) MOD G(x)                                        (6) 
    
     that is, the remainder generated by dividing the received codeword C&#39;(x) by the code generator polynomial G(x). 
     By equation (1), 
     
         C(x) MOD G(x)=0                                            (7) 
    
     so from equation (3), 
     
         R(x)=E(x) MOD G(x)                                         (8) 
    
     For codes wherein d≧6, the time required to decode cases of one and two errors may be reduced by decoding directly from the remainder by the use of a large pre-computed table f(i,L). The value of each element of f(i,L) is the coefficient of the x i  term of the remainder generated when x L  is divided by G(x), that is, 
     
         f(d-2,L)*x.sup.d-2 ⊕ . . . ⊕f(0,L)=x.sup.L MOD G(x) (9) 
    
     Note that f(i,L)≠0 for all i=0 to d-2 and L=d-1 to 2 m  -2. 
     Hereafter, expressions using elements of f(i,L) are written using the finite field antilogarithmic form of equation (9). Note however, that in the preferred embodiment of this invention the elements of f(i,L) are stored in finite field logarithmic form for computational efficiency. Without loss of generality, discussion is limited to codes wherein t≧3. To reduce the amount of storage required for the f(i,L) table, the one and two error correction procedure is structured to require only those elements of f(i,L) for L=d-1 to 2 m  -2 and i=0 to T, where 
     
         T=2t-1 for t=3, 
    
     
         T=MAX(7,t+1) for t≧4, 
    
     and only such elements are stored. 
     From equations (4), (8), and (9), a single error at location L with value E will generate a remainder with coefficients 
     
         R.sub.i =E*f(i,L)                                          (10) 
    
     when e errors occur in a codeword, the coefficients of the remainder are the EXCLUSIVE-OR sum of the coefficients of the remainders for each error taken separately: ##EQU4## 
     CASE A 
     One or two check symbol errors 
     A.1: One error at location L&lt;d-1 with value E. From equation (10), the remainder R(x) has a single non-zero coefficient 
     
         R.sub.L =E. 
    
     A.2: Two errors at locations L 1  &lt;d-1 and L 2  &lt;d-1 with values E 1  and E 2 . From equation (11), the remainder R(x) has two non-zero coefficients 
     
         R.sub.L.sbsb.1 E.sub.1, 
    
     
         R.sub.L.sbsb.2 =E.sub.2. 
    
     Cases A.1 and A.2 may be decoded by inspection of the remainder by counting the number of non-zero coefficients R i . 
     In the preferred embodiment of this invention, non-zero coefficients R i  are counted for i=0 to t+1. If the total is less or equal to two, we are assured that there are at most d-t-1 errors, all at locations L i  &lt;d-1, none of which must be corrected since none affects a data symbol. The time required to decode cases of one or more data errors is reduced by counting non-zero coefficients only after a coefficient equal to zero has been detected in the course of decoding Cases B, C, or D. 
     CASE B 
     One error at location L≧d-1 with value E. From equation (10), the coefficients of R(x) are given by 
     
         R.sub.i =E*f(i,L). 
    
     For given a and b, a≠b, the ratio ##EQU5## is unique for each value of L such that d-1≦L&lt;2 m  -1. This yields a fast method for locating a single error. If either R a  =0 or R b  =0 there must be more than one error; otherwise the ratio R b  /R a  may be used as an index into a pre-computed location table L a ,b derived according to ##EQU6## since from equation (10), ##EQU7## Location table values corresponding to L&lt;d-1 are set to an invalid number, for example zero, to flag the existence of more than one error. 
     In the preferred embodiment of this invention, the time required to determine the error location is reduced by using LOG [R b  /R a  ] as an index into a location table L a ,b derived according to ##EQU8## 
     When the location L is known, the error value E may be trivially computed from equation (10): ##EQU9## 
     The computed error location and value may be rapidly validated by gain using equation (10); test 
     
         R.sub.i =E*f(i,L) 
    
     for values of i not equal to a or b, the indices of the coefficients R i  used to determine the error location and value. 
     In the preferred embodiment of this invention, R 0  and R 1  are used to determine L and E, and coefficients R i  are tested for i=2 to t. If all such coefficients are successfully tested, we are assured that there is one error at location L≦d-1 with value E and at most d-t-2 errors at locations t+1&lt;L i  &lt;d-1. 
     CASE C 
     Two errors, one error at location L 1  ≧d-1 with value E 1  and a second error at location L 2  &lt;d-1 with value E 2 . From equation (11), the coefficients of R(x) are given by 
     
         R.sub.i =E.sub.1 *f(i,L.sub.1), for i≠L.sub.2 ; 
    
     
         R.sub.i =E.sub.1 *f(i,L.sub.1)⊕E.sub.2, for i=L.sub.2. (12) 
    
     In the preferred implementation of this invention, this case is divided into three subcases: 
     C.1: t+1&lt;L 2  &lt;d-1 
     Decoding proceeds as in Case B: error location and value computations using R 0  and R 1  yield L 1  and E 1 , and coefficients R i  are tested successfully for i=2 to t. 
     C.2: 2≦L 2  ≦t Error location and value computations proceed as in Case B, yielding L 1  and E 1 , but the test of R L .sbsb.2 fails. If we perform one additional successful test of R t+1 , we are assured that there is one error at location L 1  ≦d-1 with value E 1  and at most d-t-2 errors at locations 2&lt;L i  &lt;d-1. 
     C.3: 0≦L 2  ≦1 
     If either R 0  or R 1  is equal to zero, the procedure of Case B detects more than one error. If both R 0  and R 1  are non-zero, the error location and value computations of Case B yield incorrect results and more than one test of the coefficients R i  fails. In either case we branch to Case D. 
     If either R 0  or R 1  is equal to zero and the computations of Case D are restricted to non-zero coefficients, the computation of the denominator of the coefficients of σ(x) using R T-3  to R T  will produce zero. If both R 0  and R 1  are non-zero or the computations of Case D are not restricted to non-zero coefficients, the error location computations of Case D using R 0  to R 3  will correctly locate the two errors, with one having location 0≦L i  &lt;1. In either case, we may then repeat the single error location and value computations of Case B but using R t  and R t+1  in place of R 0  and R 1 , determining L using from a location table L t ,t+1 derived from f(t+1,L)/f(t,L)), and validating the results by testing the coefficients R i  for i=0 to t-1, allowing one failure at i=0 or i=1. 
     Case C.3 occurs with sufficiently low frequency that table storage space may be reduced without signficantly degrading performance by eliminating the L t ,t+1 table and determining the location of the data symbol error by calculating L as a function of R t+1  /R t  : ##EQU10## where G i  &#39; is the coefficient of the x i  term of ##EQU11## 
     In the preferred implementation of this invention, L for Case C.3 is computed from equation (13) using a=t and b=t+1. One validation testing failure is allowed for any i=0 to t-1. If validation testing succeeds, we are assured that there is one error at location L 1  &gt;d-1 with the value E 1 , a second error at location 0≦L 2  ≦t-1, and at most d-t-3 errors at locations t+2≦L i  &lt;d-1. 
     CASE D 
     Two errors at locations L 1  &gt;d-1 and L 2  ≧d-1 with values E 1  and E 2 . From equation (11), the coefficients of the remainder R(x) are given by 
     
         R.sub.i =E.sub.1 *f(i,L.sub.1)⊕E.sub.2 *f(i,L.sub.2)   (14) 
    
     The coefficients σ 1  =α L .sbsp.1 ⊕α L .sbsp.2 and σ 2  =α L .sbsp.1 *α L .sbsp.2 of the error locator polynomial σ(x) may be computed from four coefficients R a , R b , R c , and R d  according to the equations ##EQU12## where the pre-computed constants A ab , B ab , C ab , etc. are functions of a, b, c, and d of the form ##EQU13## and G i  &#34; is the coefficient of the x i  term of ##EQU14## with G -1  &#34; defined as zero. 
     In the preferred embodiment of this invention, R 0  to R 3  are used in computing σ 1  and σ 2 . For codes wherein t≧4, the time required to compute σ 1  and σ 2  is reduced by choosing four non-zero zero coefficients of R(x): if any of R 0  to R 3  is equal to zero, σ 1  and σ 2  are computed using R T-3  to R T . If any of R T-3  to R T  is also equal to zero, there exist more than two errors. 
     We now have the coefficients of the error locator polynomial for the case of two errors 
     
         x.sup.2 ⊕σ.sub.1 *x⊕σ.sub.2 =0. 
    
     Solution of a quadratic equation in a finite field is known in the prior art; for example, see Chapter 3 of Practical Error Correction Design for Engineers by Neal Glover. Substituting x=y*σ 1  yields ##EQU15## 
     For each odd solution to this equation Y 1 , there is an even solution Y 2  =Y 1  ⊕1. Y 1  can be fetched from a pre-computed quadratic table derived according to 
     
         QUAD[i.sup.2 ⊕i]=i⊕1 for i=0, 2, . . . 2.sup.m -2 
    
     using c as an index. There are 2 m-1  such pairs of solutions; the other elements of the table are set to an invalid number, for example zero, to flag the existence of more than two errors. When Y 1  ≠0 and Y 2  ≠0 have been determined, reverse substitution yields expressions for the two error locations 
     
         L.sub.1 =LOG [σ.sub.1 *Y.sub.1 ] 
    
     
         L.sub.2 =LOG [σ.sub.1 *Y.sub.2 ] 
    
     If both L i  &lt;d-1 and neither L i  is not equal to a or b, the indices of the coefficients R i  used in Case B, there must exist more than two errors, otherwise the error situation of Case C.3 may exist. 
     In the preferred implementation of this invention, Case C.3 is attempted if L i  &lt;d-1, whether or not L i  is equal to a or b; Case C.3 will detect cases of more than two errors. 
     Solving the system of equations 
     
         R.sub.a =E.sub.1 *f(a,L.sub.1)⊕E.sub.2 *f(a,L.sub.2) 
    
     
         R.sub.b =E.sub.1 *f(b,L.sub.1)⊕E.sub.2 *f(b,L.sub.2) 
    
     yields expressions for the error values ##EQU16## 
     In the preferred embodiment of the invention, R 0  and R 1  are used in calculating error values if R 0  to R 3  were used in determining σ(x), while R T-3  and R T-2  are used in calcuating error values if R T-3  to R T  were used in determining σ(x). 
     The computed error locations and values may be rapidly validated using equation (11); test 
     
         R.sub.i =E.sub.1 *f(i,L.sub.1)⊕E.sub.2 *f(i,L.sub.2) 
    
     for values of i not equal to a, b, c, or d, the indices of the coefficients R i  used to determine the error locations and values. 
     In the preferred embodiment of this invention, coefficients R i  are tested for i=4 to t+1 if R 0  to R 3  were used in determining locations and values, and coefficients R i  are tested for i=0 to T-4 if R T-3  to R T  were used. If all such coefficients are successfully tested, we are assured that there are two errors at locations L 1  &gt;d-1 and L 2  &gt;d-1 with values E 1  and E 2  and at most d-t-3 errors at locations t+2≦L i  ≦d-1. 
     CASE E 
     More than two errors, at locations L i  with values E i . 
     SYNDROME POLYNOMIAL GENERATION: We compute the coefficients S i  of the frequency-domain syndrome polynomial 
     
         S(x)=S.sub.d-2 *x.sup.d-2 ⊕. . . ⊕S.sub.1 *x⊕S.sub.0 
    
     from the coefficients R i  of the remainder R(x) according to ##EQU17## 
     Sequential computation of each coefficient S i  would require d-1 references to each coefficient R j . Physical constraints and interleaving of multiple codewords often make each reference to a coefficient R j  difficult and time-consuming. 
     In the preferred embodiment of this invention, the time required to calculate the coefficients of S(x) is reduced by the following methods: 
     (1) Each coefficient R j  is referenced once and its contribution to each coefficient S i  is sequentially computed and added. 
     (2) A partial result for the contribution of each coefficient R j   to each coefficient S i  is maintained in finite field logarithmic form; 
     (3) The use of software loops is minimized by using repeated sequential blocks. 
     (4) The calculation of coefficients S i  required for the decoding of cases of more than four errors is deferred until the iterative error locator polynomial generation routine determines the existence of more than four errors. 
     ERROR LOCATOR POLYNOMIAL GENERATION: The coefficients of S(x) are used to iteratively generate the coefficients of the error locator polynomial σ(x). Such iterative algorithms are known in the prior art; for example, see Chapter 5 of Error-Correction Coding for Digital Communications by Clark and Cain. 
     In the preferred embodiment of this invention, the time required to evaluate each successive discrepancy value is reduced by using the current degree of σ(x) as an index into a table of software jump addresses of appropriate starting points for each evaluation in a sequence of repeated blocks. 
     ERROR LOCATION AND EVALUATION: If the degree of σ(x) indicates more than four errors exist, we evaluate σ(x) at x=α L  for each L, 0≦L&lt;2 m  -1, until the result is zero, which signifies that α L  is a root of σ(x) and L is an error location. 
     In the preferred embodiment of this invention, the time required to evaluate σ(x) at each successive location is reduced by maintaining a software address pointer to the appropriate starting point for each evaluation in a sequence of repeated blocks, and by evaluating α jL  *σ(x) at x=α -L  where j is the degree of σ(x), rather than evaluating σ(x) at x=α L . 
     When the location L of an error has been determined, σ(x) is divided by (x⊕α L ), producing a new error locator polynomial of degree one less than that of the old: ##EQU18## 
     The error value E may be calculated directly from S(x) and the new σ(x) using ##EQU19## where j is the degree of the new σ(x). 
     In the preferred embodiment of this invention, the division of σ(x) by (x⊕α L ) and the calculation of the numerator and denominator of E are all performed in a single software loop. 
     When the location L and value E of an error have been determined, the coefficients of S(x) are adjusted to remove its contribution according to 
     
         S.sub.i =S.sub.i ⊕E*α..sup.L(m.sbsp.0.sup.+i) 
    
     By reducing the degree of σ(x) and adjusting S(x) as the location and value of each error are determined, the time required to locate and evaluate each successive error is reduced. 
     When the degree of j of σ(x) is four or less, the time required to locate the remaining errors is reduced by using the special error locating routines below, each of which locates one of the remaining errors without using the Chien search. After the location of an error has been determined by one of the special error locating routines, its value is calculated σ(x) is divided by (x⊕α L ), and S(x) is adjusted in the same way as when an error is located by evaluating σ(x). 
     When j=1, the error locator polynomial is 
     
         x⊕σ.sub.1 =0 
    
     By inspection, the root of this equation is σ 1  =α L . Thus 
     
         L=LOG [σ.sub.1 ]. 
    
     When j=2, the error locator polynomial is 
     
         x.sup.2 ⊕σ.sub.1 *x⊕σ.sub.2 =0. 
    
     One of the roots of this equation may be found using the quadratic method of Case D: ##EQU20## 
     When j=3, the error locator polynomial is 
     
         x.sup.3 Γσ.sub.1 *x.sup.2 ⊕σ.sub.2 *x⊕σ.sub.3 =0. 
    
     Solution of a cubic equation in a finite field is known in the prior art; for example, see Flagg, U.S. Pat. No. 4,099,162. Substituting 
     
         x=w⊕σ.sub.1, w=t⊕B/t, and v=t/B.sup.3 /B 
    
     yields a quadratic equation in v: 
     
         v.sup.2 ⊕v⊕A.sup.3 /B.sup.2 =0 
    
     where 
     
         A=σ.sub.1.sup.2 ⊕σ.sub.2 and B=σ.sub.1 *σ.sub.2 ⊕σ.sub.1. 
    
     A root V of this equation may be found by the quadratic method above. Then by reverse substitution ##EQU21## 
     When j=4, the error locator polynomial is 
     
         x.sup.4 ⊕σ.sub.1 *x.sup.3 ⊕σ.sub.2 *x.sup.2 ⊕σ.sub.3 *x⊕σ.sub.4 =0. 
    
     Solution of a quartic equation in a finite field is known in the prior art; for example, see Deodhar, U.S. Pat. No. 4,567,594. If σ 1  =0, assign b i  =σ i  for i=2 to 4, otherwise substitute ##EQU22## to give 
     
         z.sup.4 ⊕b.sub.2 z.sup.2 ⊕b.sub.3 z⊕b.sub.4 =0 
    
     where ##EQU23## 
     The resulting affine polynomial may be solved in the following manner: 
     (1) Solve for a root Q of the equation q 3  ⊕b 2  *q⊕b 3  =0 by the cubic method above. 
     (2) Solve for a root S of the equation s 2  ⊕b 3  /Q*s⊕b 4  =0 by the quadratic method above. 
     (3) Solve for a root Z of the equation z 2  ⊕Q*z⊕S=0 by the quadratic method above. If σ 1  =0, L=LOG [Z], otherwise reverse substitution yields ##EQU24## 
     Referring to FIG. 1, a data controller 100 having a host interface 102 is connected to a host computer 104. The data controller 100 also has a device interface 101 which connects the data controller 100 to an information storage device 108. 
     In the process of reading data from information storage device 108, data bits from information storage device 108 are transferred through device information channel 116, through the device interface 101, and into the decoder 110. At the same time the data bits are being transferred into the encoder and time domain syndrome generator 110, they are transferred in parallel into the data buffer 106. As check bits are transferred into the decoder 110, remainder bits are generated by the decoder 110 and transferred to the remainder buffer 107. After the data bits have been transferred into the data buffer 106 and remainder bits transferred to the remainder buffer 107, the processor 105 uses the remainder bits from the remainder buffer 107 to detect and correct, if necessary, errors in the data bits in data buffer 106. After correction of any errors in the data buffer 106, the data bits are transferred through the host interface 102, through the information channel 118 through the host computer 104. 
     Referring to FIG. 2, if either R 0  or R 1  is equal to zero, Step 200 transfers control to FIG. 4, having detected more than one error. Otherwise Step 202 determines the location  L=L  0,1[R 1  /R 0  ]. If L is invalid, that is, less than d-1, Step 204 transfers control to FIG. 3. Otherwise Step 206 calculates the error value E=R 0  /f(O,L). Step 210 prepares to validate L and E by initializing counters i=1, j=t-1, and k=2. Step 212 increments counter i. If R i  ≠E*f(i,L), Step 214 transfers control to Step 220. Otherwise Step 216 decrements counter j. If counter j is then still greater than zero, step 218 transfers control back to Step 212 to continue testing coefficients R i . Otherwise L and E have been validated and Step 250 records them before transferring control to FIG. 17 for error correction. After a coefficient R i  fails the test of Step 214, Step 220 decrements counter k. If counter k is then still greater than zero, Step 222 transfers control back to Step 212 to continue testing coefficients R i . Otherwise L and E are invalid and control is transferred to FIG. 3. 
     The time required for executing looping control and maintaining counters in FIG. 2 may be eliminated by replacing Steps 210 to 222 of FIG. 2 with the repeated sequential blocks of FIG. 2A. Steps 230 through 23x sequentially test coefficients R i  for i=2 to t. If all of these tests succeed, L and E have been validated and Step 23x transfers control to Step 250 of FIG. 2. Otherwise control is transferred into Steps 240 to 24x, where sequential testing of coefficients R i  continues through i=t+1. If all of the remaining tests in this second set succeed, L and E have been validated and Step 24x transfers control to Step 250 of FIG. 2. If any of the tests of Steps 240 to 24x fails, L and E are invalid and control is transferred to FIG. 3. 
     Referring to FIG. 3, on entry both R 0  and R 1  are known to be non-zero. If t≧4 and either R 2  or R 3  is equal to zero, Step 300 transfers control to FIG. 4 to attempt calculation of σ 1  and σ 2  using R T-3  through R T . Otherwise Step 302 calculates the products of R 0  to R 3  taken two at a time. Step 304 computes the denominator of σ 1  and σ 2 . If the denominator is equal to zero, Step 306 transfers control to FIG. 8. Otherwise Step 308 computes the log of the denominator, and the numerator of σ 1 . If the numerator of σ 1  is equal to zero, Step 310 transfers control to FIG. 8. Otherwise Step 312 computes the log of σ 1 , and the numerator of σ 2 . If the numerator of σ 2  is equal to zero, Step 314 transfers control to FIG. 8. Otherwise Step 316 calculates the log of σ 2  and sets counter I=0 to signify that R 0  to R 3  were used in computing σ 1  and σ 2 , then transfers control to FIG. 5. 
     Referring to FIG. 4, on entry at least one of R 0  to R 3  is known to be equal to zero. Step 400 counts the number of non-zero coefficients R i  for i=0 to t+1. If the result is less than three, there are no data symbols in error; Step 402 exits the correction procedure successfully without correcting any data symbols, having decoded Case A. Otherwise if any of R T-3  to R T  are equal to zero, Step 404 transfers control to FIG. 8, having detected more than two errors. Otherwise Step 406 calculates the products of R T-3  to R T  taken two at a time. Step 408 computes the denominator of σ 1  and σ 2 . If the denominator is equal to zero, Step 410 transfers control to FIG. 7, having possibly detected Case C.3. Otherwise Step 412 computes the log of the demoninator, and the numerator σ 1 . If the numerator of σ 1  is equal to zero, Step 414 transfers control to FIG. 8. Otherwise Step 416 computes the log of σ 1 , and the numerator of σ 2 . If the numerator of σ 2  is equal to zero, Step 418 transfers control to FIG. 8. Otherwiste STep 420 calculates the log of σ 2  and sets counter I=T-3 to signify that R T-3  to R T  were used in computing σ 1  and σ 2 , then transfers control to FIG. 5. 
     In FIG. 5, which computes the error locations and values for Case D, Step 500 calculates the quantity c=σ 2  /(σ 1 ) 2  and fetches Y 1  =QUAD[c]; Y 1  is known to be not equal to one, since σ 2  is known to be non-zero. If Y 1  is equal to zero, Step 502 transfers control to FIG. 8. Otherwise Step 504 calculates locations L 1 . If L 1  is less than d-1, Step 506 transfers control to FIG. 7, having possibly detected Case C.3. Otherwise Step 508 calculates Y 2  and location L 2  ; Y 2  is known to be not equal to zero since Y 1  is not equal to one. If L 2  is less than d-1, Step 510 transfers control to FIG. 7, having possibly detected Case C.3. Otherwise Step 514 computes the denominator of error values E 1  and E 2 . If the denominator is equal to zero, Step 516 transfers control to FIG. 8. Otherwise Step 518 calculates the numerator of E 1 . If the numerator of E 1  is equal to zero, Step 520 transfers control to FIG. 8. Otherwise Step 522 calculates the numerator of E 2 . If the numerator of E 2  is equal to zero, Step 524 transfers control to FIG. 8. Otherwise Step 526 calculates E 1  and E 2 , then transfers control to FIG. 6. 
     Referring to FIG. 6, Step 600 initializes counter i=4. If counter I is equal to zero, Step 602 transfers control to Step 606. Otherwise Step 604 initializes counter i=0. Step 606 initializes counter j=t-2. If R i  ≠E 1  *f(i,L 1 )⊕E 2  *f(i,L 2 ), the computed error locations and values are invalid and Step 608 transfers control to FIG. 8. Otherwise Step 610 increments counter i and decrements counter j. If counter j is then still greater than zero, step 612 transfers control back to Step 608. Otherwise the error locations and values have been validated and Step 620 records them and transfers control to FIG. 17 for error correction. 
     The time required for executing looping control and maintaining counters in FIG. 6 may be eliminated by replacing FIG. 6 with the repeated sequential blocks of FIG. 6A. Steps 650 through 65x sequentially test coefficients R i  for i=I to I+t-3. If any of these tests fails, the locations and values are invalid and control is transferred to FIG. 8. Otherwise the locations and values bave been validated and Step 660 records them and transfers control to FIG. 17 for error correction. 
     Referring to FIG. 7, if either R t  or R t+1  is equal to zero, Step 700 transfers control to FIG. 8. Otherwise Step 702 calculates the location L from equation (13). If L is invalid, Step 704 transfers control to FIG. 8. Otherwise Step 706 calculates the error value E=R t  /f(t,L) and prepares to validate L and E by initializing counters i=t, j=t-1, and k=2. Step 710 decrements counter i. If R 1  ≠E*f(i,L), Step 712 transfers control to Step 720. Otherwise Step 714 decrements counter j. If counter j is then still greater than zero, step 716 transfers control back to Step 710. Otherwise L and E have been validated and Step 718 records them and transfers control to FIG. 17 for error correction. When a coefficient R i  fails the test of Step 712, Step 720 decrements counter k. If counter k is then still greater than zero, Step 722 transfers control back to Step 710. Otherwise L and E are invalid and control is transferred to FIG. 8. 
     Referring to FIG. 8, Step 800 initializes all S i  =R 0  and initializes counters j=1 and JXM=m 0 . The purpose of counter JXM is to maintain the quantity j*m 0  for successive values of j by repaeated additions of m 0  and not by multiplication. If R j  =0, Step 810 transfers control to Step 850 since R j  does not alter the coefficients S i . Otherwise Step 820 computes k=LOG [R j  ]+JXM and adds α k  to S 0 . Step 822 computes k=k+j and adds α k  to S 1 . Steps 824 to 8xx repeat the operations of Step 822 to compute and add the contribution of R j  to S i  for i=2 to MIN(2t-1,11). Step 850 increments counter j and computes JXM=JXM+m 0 . If counter j is then still less than d-1, Step 860 transfers control back to Step 810. Otherwise the coefficients S i  for i=0 to MIN(2t-1,11) have been calculated and control is transferred to FIG. 9. 
     Referring to FIG. 9, Step 900 initializes the polynomials, parameters, and counters. Step 910 computes the nth discrepancy value d n . If d n  is equal to zero, Step 950 transfers control to Step 960. Otherwise Step 952 updates σ(x). If 1 n  ≧1 k  +n-k, Step 954 transfers control to Step 958. Otherwise Step 956 updates σ k  (x) and other parameters. Step 958 updates σ p  (x). Step 960 increments counter n. If n&lt;t+1 n , Step 970 transfers control to Step 972. If n≠12, Step 972 transfers control back to Step 910 to perform another iteration; otherwise FIG. 10 computes the remaining coefficients S i  before transferring control back to Step 910. Otherwise if 1 n , the degree of σ(x), is greater than t, the number of errors the code can correct, Step 980 exits the correction procedure unsuccessfully. If 1 n  =t, Step 980 transfers control to Step 982; if n=d-2, one additional iteration is required before terminating the algorithm so Step 982 transfers control back to Step 910. Otherwise we are assured that we have generated a valid error locator polynomial and control is transferred to FIG. 11. 
     The evaluation of the nth discrepancy d n  of step 920 may be implemented with repeated sequential blocks as in FIG. 9A. Step 920 initializes d n  =0. Step 930 uses 1 n  as an index into a table of software jump addresses to transfer control to the appopriate starting point in Steps 940 to 94x for the evaluation of d n . Multiplying S n  by σ p0  is not required in Step 94x since σ p0  is always equal to one. When d n  has been computed, control is transferred to Step 950 of FIG. 9. 
     Referring to FIG. 10, operation is similar to that of FIG. 8. After the remaining coefficients of S(x) have been calculated, control is transferred back to Step 910 of FIG. 9. 
     Referring to FIG. 11, Step 1100 initializes counters i=0, j=1 n  =the degree of σ(x), and k=0=the number of error locations which have been found. If j is less than five, Step 1110 transfers control to FIG. 13. Otherwise Step 1130 evaluates α- ji  *σ(x) at x=α i . If the result A is equal to zero, a root of σ(x) has been found and Step 1160 transfers control to Step 1170, which forms L=-i before transferring control to FIG. 12. Otherwise Step 1180 decrements counter i in the finite field. If counter i is then not equal to zero, Step 1190 transfers control back to Step 1130 to evaluate σ(x) at the next location. Otherwise all possible locations have been tested without locating all the errors; therefore the correction correction procedure is exited unsuccessfully. 
     FIG. 11A shows modifications to FIG. 11 necessary for efficient evaluation of α- ji  *σ(x) using repeated sequential blocks. Step 1120 is added to use counter j to compute an initial software jump address PTR=ADR(Step 1140)+(t-j)*K where K is the size of each Step 1140 through 114x. Step 1130 initializes A=0, then Step 1132 uses PTR to transfer control into Steps 1140 to 114x, which sequentially evaluate α- ji  *σ(x) at x=α i  using Horner&#39;s rule. Step 1170 is modified to update PTR=PTR+K to reflect the decrementing of j performed in FIG. 12. 
     Referring to FIG. 12, Step 1200 increments counter k, records L, decrements counter j, then initializes D=1 and N=S j . Step 1202 divides σ(x) by (x⊕α L ) and calculates the numerator and denominator of E&#39;=E*α L*m  0. If the new σ j  is equal to zero, the new σ(x) has a root equal to zero, which is not the finite field antilogarithm of any error location; Step 1204 exits the correction procedure unsuccessfully. If the numerator is equal to zero, the computed error value is equal to zero, which is not a valid error value, so Step 1204 exits the correction procedure unsuccessfully. If the denominator is equal to zero, the error value cannot be computed, since division by zero in a finite field is undefined; Step 1204 exits the correction procedure unsuccessfully. If σ j , the numerator, and the denominator are each not eaqual to zero, Step 1204 transfers control to Step 1206, which calculates and records E=α -Lm  0*N/D. If counter j is equal to zero, Step 1208 transfers control to FIG. 17 for error correction. Otherwise Step 1210 adjusts the coefficients of S(x) to remove the effects of the error just found and transfers control to FIG. 13. 
     Referring to FIG. 13, if more than four errors remain, Step 1300 transfers control to Step 1180 of FIG. 11 to search for another error location by evaluating σ(x). If four errors remain, Step 1300 calls the quartic solution subroutine of FIG. 16. If three errors remain, Step 1302 transfers control to Step 1304, which sets parameters for and calls the cubic solution subroutine of FIG. 15. If two errors remain, Step 1302 transfers control to Step 1306, which sets parameters for and calls the quadratic solution subroutine of FIG. 14. Otherwise one error remains and Step 1302 transfers control to Step 1308. 
     If σ 1  is equal to zero, Step 1308 exits the correction procedure unsuccessfully, since the finite field logarithm of zero is undefined. Otherwise Step 1310 determines L=LOG [σ 1  ] and transfers control to FIG. 12. 
     Likewise, if one of the subroutines successfully determines an error location, Step 1320 transfers control to FIG. 12. Otherwise, the correction procedure is exited unsuccessfully. 
     On entry to FIG. 14, the parameters c 1  and c 2  describe the quadratic equation 
     
         x.sup.2 ⊕c.sub.1 *x⊕c.sub.2 =0. 
    
     If c 1  =0, the equation has a repeated root. If c 2  =0, one of the roots is zero, whose log is undefined. If c 1  =0 or c 2  =0, Step 1400 exits the subroutine unsuccessfully. Otherwise Step 1402 determines a transformed root Y 1 . If Y 1  is invalid, Step 1404 exits the subroutine unsuccessfully. Otherwise Step 1406 calculates the root X and its log L and returns successfully. 
     On entry to FIG. 15, the parameters c 1 , c 2 , and c 3  describe the cubic equation 
     
         x.sup.3 ⊕c.sub.1 *x.sup.2 ⊕c.sub.2 *x⊕c.sub.3 =0. 
    
     Step 1500 calculates the transform parameters A and B. If B is equal to zero, Step 1502 exits the subroutine unsuccessfully. Otherwise Step 1504 determines a root V of the quadratic equation ##EQU25## using the QUAD table. If no such root exists, Step 1504 produces zero and Step 1506 exits the subroutine unsuccessfully. Otherwise Step 1508 computes U. If U is not the cube of some finite field value T, Step 1510 exits the subroutine unsuccessfully. Otherwise Step 1512 calculates T and a root X of the cubic equation. If X is equal to zero, Step 1514 exits the subroutine unsuccessfully. Otherwise Step 1516 calculates the log L of the root X and returns successfully. 
     On entry to FIG. 16, the parameters σ 1 , σ 2 , σ 3 , and σ 4  describe the quartic equation 
     
         x.sup.4 ⊕σ.sub.1 *x.sup.3 ⊕σ.sub.2 *x.sup.2 ⊕σ.sub.3 *x⊕σ.sub.4 =0. 
    
     If σ 1  is equal to zero, Step 1600 transfers contol to Step 1610; if σ 3  is equal to zero, the quartic equation has repeated roots, so Step 1610 exits the subroutine unsuccessfully. Otherwise Step 1612 assigns b i  =σ i  for i=2 to 4 and transfers control to Step 1620. If σ 1  is not equal to zero, Step 1600 transfers control to Step 1602, which calculates the numerator and denominator of transform parameter b 4 . If the denominator of b 4  is equal to zero, Step 1604 exits the subroutine unsuccessfully. Otherwise Step 1606 calculates the transform parameters b 4 , b 3 , and b 2  and transfers control to Step 1620. 
     Step 1620 sets parameters for and calls the cubic solution subroutine of FIG. 15. If this returns unsuccessfully, Step 1622 exits the subroutine unsuccessfully. Otherwise Step 1630 assigns Q=X and sets parameters for and calls the quadratic solution subroutine of FIG. 14. If this returns unsuccessfully, Step 1632 exits the subroutine unsuccessfully. Otherwise Step 1640 sets parameters for and calls the quadratic solution subroutine of FIG. 14. If this returns unsuccessfully, Step 1642 exits the subroutine unsuccessfully. Otherwise if σ 1  is equal to zero, Step 1650 returns L successfully. Otherwise Step 1660 computes X. If X is equal to zero, Step 1662 exits the subroutine unsuccessfully. Otherwise Step 1670 computes and returns L successfully. 
     Referring to FIG. 17, on entry counter k is equal to the number of errors found, arrays L(*) and E(*) hold the pairs of error locations and values, D is the number of symbols in the data buffer and parameter DMN holds the reverse displacement plus one from the last symbol in the data buffer to the last data symbol in the current interleave. Step 1700 calculates the forward displacement from the first symbol in the data buffer to the last data symbol of the current interleave. Step 1710 fetches the location L=L(k) of the next error to be corrected. If L is less than d-1, the symbol in error is a check symbol and need not be corrected, so Step 1720 transfers control to 1760. Otherwise Step 1730 calculates a forward displacement F within the data buffer from the reverse displacement L within the codeword interleave based on the data buffer length and number of interleaved codewords. If F is less than zero and therefore invalid, Step 1740 exits the correction procedure unsuccessfully. Otherwise Step 1750 corrects the data symbol in error with the error value E(k). Step 1760 decrements counter k. If counter k is then still greater than zero, Step 1770 transfers control back to Step 1710 to correct additional errors. Otherwise all errors have been corrected and the correction procedure is exited successfully. 
     While the invention herein disclosed has been described by means of specific embodiments and applications thereof, numerous modifications and variations could be made thereto by those skilled in the art without departing from the spirit and scope of the present invention. It is therefore to be understood that within the scope of the appended claims, the invention may be practised otherwise than as specifically described herein.