Fast remainder decoding for a Reed-Solomon code

• US 4,839,896 A
• Filed: 02/10/1987
• Issued: 06/13/1989
• Est. Priority Date: 02/10/1987
• Status: Expired due to Fees

• Current Assignee: Data Speed Technology LLC (Empire IP LLC)
• Original Assignee: Data Speed Technology LLC (Empire IP LLC)
• Inventors: Glover, Neal, Dudley, Trent
• Primary Examiner(s): Fleming, Michael R.
• Application Number:
  US07/012,824
• Time in Patent Office: 854 Days
• Field of Search: 371/37, 371/38, 371/39, 371/40
• US Class Current: 714/759
• CPC Class Codes: H03M 13/151 using error location or error correction polynomials

Abstract

Apparatus and methods are disclosed for providing fast decoding of Reed-Solomon and related codes. Cases of one and two data symbol errors are decoded directly from the remainder using a large pre-computed table without calculating syndromes. Techniques for decoding cases of more than two errors are given where an optimized Chien search is used when more than four errors remain; when four or fewer errors remain, the Chien search is eliminated in favor of locating an error by direct solution of the error locator polynomial. The error locator and syndrome polynomials are adjusted after each error is found, and the error evaluator polynomial need not be computed.

Claims

1. A decoder for an error detection and correction system using a Reed-Solomon code or related code of degree d-1 for detection and correction of a plurality of errors in code words of n symbols comprised of k data symbols and d-1 check symbols, wherein each symbol is comprised of m binary bits of information and d, k, m, and n are positive integers, and further wherein t=INT((d-1)/2)≧

3, said decoder comprising;

data buffer means for storing said k data symbols;

remainder generator means for dividing a codeword polynomial C(x) by a generator polynomial G(x) of said code and producing a remainder polynomial R(x) having remainder coefficients R₁ ;

remainder buffer means for storing said remainder coefficients R_i produced by said remainder generator means;

first table means comprising a table f(i,L) wherein each element is comprised of error correction information, and wherein 0≦

i<

d-1, and d-1<

L<

2^m -1; and

processor means comprising

means for accessing said remainder buffer to retrieve said remainder,

means for applying said remainder to index said first table means and retrieve said correction information, and

means for applying said correction information to said data symbols in said data buffer to correct symbols that are in error.

2. The decoder of claim 1 wherein each element of said first table means is comprised of a coefficient of the xⁱ term of x^L MOD G(x).

3. The decoder of claim 1 wherein each element of said first table means is comprised of a finite field logarithm of a coefficient of the xⁱ term of x^L MOD G(x).

4. The decoder of claim 1 further comprising a second table means comprising a table L_a,b wherein each non-zero element is defined as ##EQU26## wherein f(i,L) is a coefficient of the xⁱ term of x^L MOD G(x), L varies from d-1 to 2^m -2 and further wherein 0<

a<

d-1, 0<

b<

d-1, and a≠

b.

5. The decoder of claim 1 further comprising a third table means comprising a table L_a,b wherein each non-zero element is defined as ##EQU27## wherein f(i,L) is a coefficient of the xⁱ term of x^L MOD G(x), LOG [f(b,L)/f(a,L)] is the finite field logarithm of f(b,L)/f(a,L), L varies from d-1 to 2^m -2 and further wherein 0<

a<

d-1, 0≦

b<

d-1, and a≠

b.

6. The decoder of claim 5 wherein said means for applying said remainder comprises:

means for determining a location L of a data symbol error;

means for calculating a value E of said data symbol error; and

means for validating said location L and said value E of said data symbol error.

7. The decoder of claim 6 wherein said means for determining said location L comprises:

means for calculating an index value ##EQU28## wherein R_a and R_b are two of said coefficients R_i ;

means for applying said index value to said third table means to retrieve said location L of said data symbol error.

8. The decoder of claim 6 wherein said means for determining said location L comprises:

means for calculating L according to ##EQU29## wherein G_i '"'"' is a coefficient of the xⁱ term of ##EQU30##

9. The decoder of claim 6 wherein said means for calculating said value E comprises:

means for applying said location L to produce an index value for element f(a,L) of said first table means;

means for applying said index value to said first table means to retrieve said element f(a,L); and

means for dividing a coefficient R_a by said element f(a,L) to produce said value E of said data symbol error.

10. The decoder of claim 6 wherein said means for validating said location L and said value E comprises

means for calculating a finite field logarithm of said value E;

means for testing a plurality t of said remainder coefficients R_i wherein i≠

a and i≠

b, each test comprising a sequential repeated block comprising;

means for adding said finite field logarithm of said error value E to an element f(i,L) of said first table means to produce a finite field logarithm of a test value;

means for calculating a finite field antilogarithm of said finite logarithm of said test value; and

means for comparing said finite field antilogarithm of said test value to said coefficient R_i ;

means for counting a number of said tests wherein said finite finite field antilogarithm of said test value is not equal to said remainder coefficient R_i ;

means for recording an indicium when said number is less than two; and

means responsive to said indicium for using said location L and value E to correct said data symbol error.

11. The decoder of claim 5 wherein said means for applying said remainder comprises:

means for computing parameters σ

₁ and σ

₂ ;

means for determining locations L₁ and L₂ of two data symbol errors from σ

₁ and σ

₂ ;

means for calculating values E₁ and E₂ of said two data symbol errors; and

means for validating said locations and said values of said two data symbol errors.

12. The decoder of claim 11 wherein said means for computing said parameters σ

₁ and σ

₂ comprises;

means computing non-zero parameters D, N₁, and N₂ according to ##EQU31## wherein pre-computed constants A_ab, A_ac, A_ad, A_bc, A_bd, A_cd, B_ab, B_ac, B_ad, B_bc, B_bd, B_cd, C_ab, C_ac, C_ad, C_bc, C_bd, and C_cd are functions of a, b, c, and d given by;

##EQU32## and G_i " is a coefficient of the xⁱ term of ##EQU33## with G_-1 " defined as zero; and

means for computing σ

₁ =N₁ /D and σ

₂ =N₂ /D.

13. The decoder of claim 11 wherein t≧

4 and selected coefficients R_a, R_b, R_c, and R_d of said coefficients R_i are each not equal to zero.

14. The decoder of claim 11 wherein said means for calculating said values E₁ and E₂ of said two data symbol errors comprises:

means for computing non-zero parameters D, N₁, and N₂ according to ##EQU34## means for computing E₁ =N₁ /D and E₂ =N₂ /D.

15. The decoder claim 11 wherein said means for validating said locations and said values comprises:

means for calculating finite field logarithms of said values E₁ and E₂ ;

means for testing a plurality t-2 of said remainder coefficients R_i wherein i≠

a, i≠

b, i≠

c, and i≠

d, each test comprising a sequential repeated block comprising;

means for adding said finite field logarithms of said values E₁ and E₂ to respective elements f(i,L₁) and f(i,L₂) of said first table means to produce finite field logarithms of test values,

means for calculating finite field antilogarithms of said finite field logarithms of said test values;

means for calculating an EXCLUSIVE-OR sum of said finite field antilogarithms of said test values; and

means for comparing said EXCLUSIVE-OR sum of said finite field antilogarithms of said test values to said coefficient R_i ;

means for recording an indicium when each said EXCLUSIVE-OR sum of said finite field antilogarithms of said test values is equal to said coefficient R_i ; and

means responsive to said indicium for using said locations and values to correct said data symbol errors.

16. The decoder of claim 1 wherein said means for applying said remainder comprises:

means for counting a number of non-zero coefficients R_i in a plurality of t+1 of said coefficients R_i in said remainder buffer and recording an indicium when said number is less than three; and

means responsive to said indicium for terminating error correction successfully.

17. The decoder of claim 1 wherein said means for applying said remainder comprises:

means for validating locations L_j and values E_j of e errors comprising means for testing a plurality of said remainder coefficients R_i according to the equations ##EQU35##

18. The decoder of claim 1 wherein said processor means comprises:

means for computing a syndrome polynomial S(x) from said remainder polynomial R(x);

means for generating an error location polynomial σ

(x) from said syndrome polynomial S(x);

means responsive to said error locator polynomial σ

(x) for locating errors; and

means responsive to said error locator polynomial σ

(x) and said syndrome polynomial S(x) for evaluating errors.

19. The decoder of claim 18 wherein said means for computing said syndrome polynomial comprises:

(1) means for initializing a coefficient S₀ and all other coefficients S_i of said syndrome polynomial S(x) to a coefficient R₀ of said remainder polynomial R(x);

(2) means for initializing a counter j to l;

(3) means for computing a finite field logarithmic partial result comprising a MODULO 2^m -1 sum of a finite field logarithm of a non-zero coefficient R_j and j*m₀ ;

(4) means for calculating a finite field antilogarithm of said partial result;

(5) means for EXCLUSIVE-OR adding said finite field antilogarithm of said partial result to said coefficient S₀ ;

(6) means for MODULO 2^m -1 adding said counter j to said partial result;

(7) means for calculating a finite field antilogarithm of said partial result;

(9) means for EXCLUSIVE-OR adding said finite field antilogarithm of said MODULO 2^m -1 sum and one of said coefficients S_i ;

(10) means for repeating said means (6) through (9) for said coefficients S_i wherein i=2 to MIN(d-2,11);

(11) means for incrementing said counter j; and

(12) means for repeating said means (3) through (11) for said coefficients R_j wherein j=2 to d-2.

20. The decoder of claim 18 wherein said means for generating said error locator polynomial comprises:

means for computing an nth discrepancy d_n comprising sequential repeated blocks, each said block comprising means for calculating a MODULO 2^m -1 sum of said nth discrepancy d_n and a finite field product of a coefficient σ

_pi and a coefficient S_n-i ;

means using a degree l_n of the nth error locator polynomial as an index into a table of software addresses of each said block;

means for recording an indicium when said parameter n is equal to twelve; and

means responsive to said indicium for generating coefficients S_i for i=11 to d-2.

21. The decoder of claim 18 wherein said means for locating said errors comprises:

means for recording an indicium when said error locator polynomial σ

(x) is of degree j greater than four;

means responsive to said indicium for locating one of said errors comprising evaluating said error locator polynomial σ

(x) for successive values of L until ##EQU36## said means for evaluating comprising a sequence of repeated blocks each said block comprising means for calculating a finite field product of α

^-L and an EXCLUSIVE-OR sum of said parameter A and a coefficient σ

_i of said error locator polynomial σ

(x); and

means for maintaining a software address of a starting point for next said evaluation.

22. The decoder of claim 18 wherein said means for locating said errors comprises:

means for recording an indicium when said error locator polynomial σ

(x) is of degree j less than or equal to four; and

means responsive to said indicium for locating one of said errors comprising;

means for calculating a finite field logarithm of a root of a quartic equation in a finite field;

means for calculating a root and a finite field logarithm of said root of a cubic equation in a finite field;

means for calculating a root and a finite field logarithm of said root of a quadratic equation in a finite field; and

means for calculating a finite field logarithm of a root of a linear equation in a finite field.

23. The decoder of claim 18 wherein said means for evaluating said errors comprises:

means for dividing said error locator polynomial σ

(x) by (x ⊕

α

^L) to produce a new error locator polynomial σ

(x) and calculating an error value E from said syndrome polynomial S(x) and said new error locator polynomial σ

(x), comprising a single software loop comprising;

(1) means for initializing a counter g=1, a remainder R=1, a denominator D=1, and a numerator N=σ

_j ;

(2) means for calculating a MODULO 2^m -1 sum of said remainder R and a finite field product of a finite field antilogarithm of said location L and said remainder R;

(3) means for storing said MODULO 2^m -1 sum as said remainder R and as a coefficient σ

_g of said error locator polynomial σ

(x);

(4) means for calculating a MODULO 2^m -1 sum of said remainder R and a finite field product of a finite field antilogarithm of said location L and said denominator D;

(5) means for storing said MODULO 2^m -1 sum as said denominator D;

(6) means for calculating a MODULO 2^m -1 sum of said numerator N and a finite field product of said remainder R and a coefficient S_j-g of said syndrome polynomial S(x);

(7) means for storing said MODULO 2^m -1 sum as said numerator N;

(8) means for incrementing said counter g; and

(9) means for repeating said means (2) through (8) for values of said counter g up to and including j;

means for recording an indicium when R, D, or N is equal to zero after the operation of said means (1) through (9);

means responsive to said indicium for terminating error correction unsuccessfully;

means for calculating a finite field quotient of said numerator N and said denominator D;

means for recording a finite field logarithm of said finite field quotient as a parameter E'"'"';

means for calculating a finite field product of said finite field quotient and a finite field antilogarithm of -L*m₀ ;

means for recording said finite field product as said error value E; and

means for adjusting coefficients of said syndrome polynomial S(x) comprising a software loop comprising;

(a) means for initializing a counter g=0;

(b) means for calculating a finite field antilogarithm of said parameter E'"'"';

(c) means for calculating a MODULO 2^m -1 sum of said finite field antilogarithm and a coefficient S_i of said syndrome polynomial S(x);

(d) means for storing said MODULO 2^m -1 sum as said coefficient S_i ;

(e) means for calculating a MODULO 2^m -1 sum of said parameter E'"'"' and said location L;

(f) means for storing said MODULO 2^m -1 sum as said parameter E'"'"';

(g) means for incrementing said counter g; and

(h) means for repeating said means (b) through (g) for values of said counter g up to and including j.

24. The decoder of claim 1 wherein m=8, t=8, G(x) is a GF(256) polynomial ##EQU37## and α

ⁱ are elements of a finite field generated by a GF(2) polynomial

space="preserve" listing-type="equation">x.sup.8 ⊕

x.sup.4 ⊕

x.sup.3 ⊕

x.sup.2 ⊕

1.

25. The decoder of claim 1 wherein m=8, t=8, G(x) is a GF(256) polynomial ##EQU38## m₀ =120, and α

ⁱ are given by

space="preserve" listing-type="equation">α

.sup.i =(beta.sup.i).sup.88,

wherein betaⁱ are elements of a finite field generated by a GF(2) polynomial

space="preserve" listing-type="equation">x.sup.8 ⊕

x.sup.5 ⊕

x.sup.3 ⊕

x.sup.2 ⊕

1.

26. The decoder of claim 1 wherein m=8, t=4, G(x) is a GF(256) polynomial ##EQU39## m₀ =124, and α

ⁱ are given by α

ⁱ =(betaⁱ)⁸⁸,

wherein betaⁱ are elements of a finite field generated by a GF(2) polynomial

space="preserve" listing-type="equation">x.sup.8 ⊕

x.sup.5 ⊕

x.sup.3 ⊕

x.sup.2 ⊕

1.

27. The decoder of claim 1 wherein m=8, t=2, G(x) is a GF(256) polynomial ##EQU40## m₀ =126, and α

ⁱ are given by

space="preserve" listing-type="equation">α

.sup.i =(beta.sup.i).sup.88,

wherein betaⁱ are elements of a finite field generated by a GF(2) polynomial

space="preserve" listing-type="equation">x.sup.8 ⊕

x.sup.5 ⊕

x.sup.3 ⊕

x.sup.2 ⊕

1.

28. In a decoder for an error detection and correction system using a Reed-Solomon code or related code of degree d-1 for detection and correction of a plurality of errors in codewords of n symbols comprised of k data symbols and d-1 check symbols, wherein each symbol is comprised of m binary bits of information and d, k, m, and n are positive integers, and further wherein t=INT((d-1)/2)≧

3, an error decoding method comprising the steps of;

storing said k data symbols in a data buffer;

generating a remainder polynomial R(x) having remainder coefficients R_i by dividing a codeword polynomial C(x) by a generator polynomial G(x) of said code;

storing said remainder coefficients in a remainder buffer;

applying said remainder coefficients to index a first table f(i,L), each element of said table being comprised of a coefficient of the xⁱ term of x^L MOD G(x) wherein L varies from d-1 to 2^m -2 and i varies from 0 to d-2, to produce correction information;

applying said correction information to said data symbols in said data buffer to correct symbols that are in error.

29. The method of claim 28 wherein said step of applying said remainder coefficients further comprises the steps of:

counting a number of non-zero coefficients R_i in a plurality t+2 of said coefficients R_i in said remainder buffer; and

terminating error correction successfully when said number is less than three.

30. The method of claim 28 wherein said step of applying said remainder coefficients further comprises the steps of:

determining a location L of a data symbol error;

calculating a value E of said data symbol error; and

validating said location L and said value E of said data symbol error.

31. The method of claim 30 wherein said step of determining said location L comprises the steps of:

calculating an index value from two coefficients R_a and R_b of said coefficients R_i ;

##EQU41## applying said index value to a second table L_a,b wherein each non-zero element is given by ##EQU42## for L=d-1 to 2^m -1 to retrieve said location L of said data symbol error.

32. The method of claim 30 wherein said step of determining said location L comprises calculating L according to ##EQU43## wherein G_i '"'"' is a coefficient of the xⁱ term of ##EQU44##

33. The method of claim 30 wherein said step of calculating said value E comprises the steps of:

using said location L and a number a wherein 0≦

a<

d-1 to produce an index value for an element f(a,L) of said first table;

retrieving said element f(a,L) of said first table referenced by said index value;

dividing a coefficient R_a by said element f(a,L) to produce said value E of said data symbol error.

34. The method of claim 30 wherein said step of validating said location L and said value E comprises the steps of:

calculating a finite field logarithm of said value E;

testing a plurality t of said remainder coefficients R_i wherein i≠

a and i≠

b, each test comprising a sequential repeated block comprising the steps of;

adding said finite field logarithm of said error value E to an element f(i,L) of said first table to produce a finite field logarithm of a test value;

calculating a finite field antilogarithm of said finite field logarithm of said test value; and

comparing said finite field antilogarithm of said test value to said coefficient R_i ;

counting a number of said tests wherein said finite finite field antilogarithm of said test value is not equal to said remainder coefficient R_i ; and

correcting said data symbol error using said location L and said value E when said number is less than two.

35. The method of claim 28 wherein said step of applying said remainder coefficients further comprises the steps of:

computing parameters σ

₁ and σ

₂ ;

determining locations L₁ and L₂ of two data symbol errors from σ

₁ and σ

₂ ;

calculating values E₁ and E₂ of said two data symbol errors; and

validating said locations and said values of said two data symbol errors.

36. The method of claim 35 wherein said step of computing said parameters σ

₁ and σ

₂ comprises the steps of;

computing non-zero parameters D, N₁, and N₂ according to ##EQU45## wherein pre-computed constants A_ab, A_ac, A_ad, A_bc, A_bd, A_cd, B_ab, B_ac, B_ad, B_bc, B_bd, B_cd, C_ab, C_ac, C_ad, C_bc, C_bd, and C_cd are functions of a, b, c, and d given by;

##EQU46## and G_i " is a coefficient of the xⁱ term of ##EQU47## with G_-1 " defined as zero; and

computing σ

₁ =N₁ /D and σ

₂ =N₂ /D.

37. The method of claim 35 wherein t>

4 and selected coefficients R_a, R_b, R_c, and R_d of said coefficients R_i are each not equal to zero.

38. The method of claim 35 wherein said step of calculating said values E₁ and E₂ of said two data symbol errors comprises the steps of:

computing non-zero parameters D, N₁, and N₂ according to ##EQU48## wherein R_a, R_b, R_c, and R_d are selected coefficients of said coefficients R_i ; and

computing E₁ =N₁ /D and E₂ =N₂ /D.

39. The method of claim 35 wherein said step of validating said locations and said values of said two data symbol errors comprises the steps of:

calculating finite field logarithms of said values E₁ and E₂ ;

testing a plurality t-2 of said remainder coefficients R_i wherein i≠

a, i≠

b, i≠

c, and i≠

d, and further wherein each test comprises a sequential repeated block comprising the steps of;

adding said finite field logarithms of said values E₁ and E₂ to respective elements f(i,L₁) and f(i,L₂) of said first table to produce finite field logarithms of test values,

calculating finite field antilogarithms of said finite field logarithms of said test values;

calculating an EXCLUSIVE-OR sum of said finite field antilogarithms of said test values;

comparing said EXCLUSIVE-OR sum of said finite field antilogarithms of said test values to said coefficient R_i ;

correcting said two data symbol errors using said locations and values when each said EXCLUSIVE-OR sum of said finite field antilogarithms of said test values is equal to said coefficient R_i.

40. The method of claim 28 wherein said step of applying said remainder coefficients further comprises validating locations L_j and values E_j of a plurality e of symbol errors by testing a plurality of said remainder coefficients R_i according to the equations ##EQU49##

41. The method of claim 28 wherein said step of applying said remainder coefficients further comprises the steps of:

computing a syndrome polynomial S(x) from said remainder polynomial R(x);

generating an error locator polynomial σ

(x) from said syndrome polynomial S(x);

locating errors using said error locator polynomial σ

(x); and

evaluating errors using said error locator polynomial σ

(x) and said syndrome polynomial S(x).

42. The method of claim 41 wherein said step of computing said syndrome polynomial comprises the steps of:

(1) initializing a coefficient S₀ and all other coefficients S_i of said syndrome polynomial S(x) to a coefficient R₀ of said remainder polynomial R(x);

(2) initializing a counter j to 1;

(3) computing a finite field logarithmic partial result comprising a MODULO 2^m -1 sum of a finite field logarithm of a non-zero coefficient R_j and j*m₀ ;

(4) calculating a finite field antilogarithm of said partial result;

(5) EXCLUSIVE-OR adding said finite field antilogarithm of said partial result to said coefficient S₀ ;

(6) MODULO 2^m -1 adding said counter j to said partial result;

(7) calculating a finite field antilogarithm of said partial result;

(9) EXCLUSIVE-OR adding said finite field antilogarithm of said MODULO 2^m -1 sum and one of said coefficients S_i ;

(10) repeating said steps (6) through (9) for said coefficients S_i wherein i=2 to MIN(d-2,11);

(11) incrementing said counter j; and

(12) repeating said steps (3) through (11) for said coefficients R_j wherein j=2 to d-2.

43. The method of claim 41 wherein said step of generating said error locator polynomial comprises the steps of:

computing an nth discrepancy d_n using sequential repeated blocks, each said block comprising calculating a MODULO 2^m -1 sum of said nth discrepancy d_n and finite field product of a coefficient σ

_pi and a coefficient S_n-i ;

using a degree 1_n of an nth error locator polynomial σ

(x) as an index into a table of software addresses of each said block;

generating coefficients S_i for i=11 to d-2 when said parameter is equal to twelve.

44. The method of claim 41 wherein said step of locating said errors when said error locator polynomial σ

(x) is of degree j greater than four comprises the steps of;

evaluating said error locator polynomial σ

(x) for successive values of L until ##EQU50## said step of evaluating comprising a sequence of repeated blocks, each said block comprising calculating a finite field product of α

^-L and an EXCLUSIVE-OR sum of said parameter A and a coefficient σ

_i of said error locator polynomial σ

(x); and

maintaining a software address of a starting point for next said evaluation.

45. The method of claim 41 wherein said step of locating said errors when said error locator polynomial σ

(x) is of degree j less than or equal to four comprises locating one of said errors using one of the steps of;

when j is equal to four, calculating a finite field logarithm of a root of a quartic equation in a finite field;

when j is equal to three, calculating a root and a finite field logarithm of said root of a cubic equation in a finite field;

when j is equal to two, calculating a root and a finite field logarithm of said root of a quadratic equation in a finite field;

or

when j is equal to one, calculating a finite field logarithm of a root of a linear equation in a finite field.

46. The method of claim 41 wherein said step of evaluating said errors comprises the steps of:

dividing said error locator polynomial σ

(x) by (x⊕

α

^L) to produce a new error locator polynomial S(x) and calculating an error value E from said syndrome polynomial S(x) and said new error locator polynomial σ

(x), all in a single software loop comprising steps of;

(1) initializing a counter g=1, a remainder R=1, a denominator D=1, and a numerator N=σ

_j ;

(2) calculating a MODULO 2^m -1 sum of said remainder R and a finite field product of a finite field antilogarithm of said location L and said remainder R;

(3) storing said MODULO 2^m -1 sum as said remainder R and as a coefficient σ

_g of said error locator polynomial σ

(x);

(4) calculating a MODULO 2^m -1 sum of said remainder R and a finite field product of a finite field antilogarithm of said location L and said denominator D;

(5) storing said MODULO 2^m -1 sum as said denominator D;

(6) calculating a MODULO 2^m -1 sum of said numerator N and a finite field product of said remainder R and a coefficient S_j-g of said syndrome polynomial S(x);

(7) storing said MODULO 2^m -1 sum as said numerator N;

(8) incrementing said counter g; and

(9) repeating said steps (2) through (8) for values of said counter g up to and including j;

terminating error correction unsuccessfully when R, D, or N is equal to zero after completion of said steps (1) through (9);

calculating a finite field quotient of said numerator N and said denominator D;

recording said a finite field logarithm of said finite field quotient as a parameter E'"'"';

calculating a finite field product of said finite field quotient and a finite field antilogarithm of -L*m₀ ;

recording said finite field product as said error value E; and

adjusting coefficients of said syndrome polynomial S(x) using steps of;

(a) initializing counter g=0;

(b) calculating a finite field antilogarithm of said parameter E'"'"';

(c) calculating a MODULO 2^m -1 sum of said finite field antilogarithm and a coefficient S_i of said syndrome polynomial S(x);

(d) storing said MODULO 2^m -1 sum as said coefficient S_i ;

(e) calculating a MODULO 2^m -1 sum of said parameter E'"'"' and said location L;

(f) storing said MODULO 2^m -1 sum as said parameter E'"'"';

(g) incrementing said counter g; and

(h) repeating said steps (b) through (g) for values of said counter g up to and including j.

47. In a decoder for an error detection and correction system using a Reed-Solomon code or related code of degree d-1 for detection and correction of a plurality of errors wherein a message block is comprised of N interleaved codewords of said code wherein codeword i is comprised of n_i -(d-1) data symbols and d-1 check symbols comprising a total of D data symbols stored in a data buffer means and N*(d-1) check symbols stored in a remainder buffer means where d, i, N, and n_i are positive integers, and further wherein the first check symbol in said remainder buffer means is remainder coefficient R_d-2 of codeword D MOD N and the last symbol in said remainder buffer means is remainder coefficient R₀ of codeword (D-1) MOD N, with other coefficients interleaved between, a method for accessing said data buffer means and said remainder buffer means for detection and correction of said errors comprising the steps of:

(1) initializing a parameter DMN equal to said number of data symbols D MODULO said number of interleaves N and initializing a counter I to zero;

(2) if said parameter DMN is equal to zero, resetting said parameter DMN to said number of interleaves N;

(3) computing a forward displacement within said remainder buffer means of coefficient R₀ of codeword I by calculating N*(d-1)-DMN;

(4) computing forward displacements within said remainder buffer means of other coefficients R_i of said codeword I by repeated subtraction of said number of interleaves N from said forward displacement of said coefficient R₀ of said codeword I;

(5) determining location(s) L_i and value(s) E_i of error(s) in said codeword I;

(6) computing a forward displacement within said data buffer means of a last data symbol within said codeword I as F_max =d-DMN;

(7) computing a forward displacement within said data buffer means of an error at a location L_i >

d-1 as F_i =F_max -N*L_i ;

(8) correcting said error at said forward displacement F_i using error value E_i ;

(9) repeating said steps (7) and (8) for all errors in said codeword I;

(10) decrementing said parameter DMN and incrementing said counter I; and

(11) repeating said steps (2) through (10) for values of said counter I up to and including N-1.