High-speed real-time Reed-Solomon decoder

• US 4,873,688 A
• Filed: 10/05/1987
• Issued: 10/10/1989
• Est. Priority Date: 10/05/1987
• Status: Expired due to Term

• Current Assignee: Idaho Research Foundation, Inc.
• Original Assignee: Idaho Research Foundation, Inc.
• Inventors: Cameron, Kelly B., Owsley, Patrick A., Maki, Gary K.
• Primary Examiner(s): ATKINSON, CHARLES
• Application Number:
  US07/105,401
• Time in Patent Office: 736 Days
• Field of Search: 371/37, 371/38, 371/39, 371/40
• US Class Current: 714/784
• CPC Class Codes: H03M 13/1535 using the Euclid algorithm

Abstract

A Galois Field error correction decoder is described which can correct an error in a received polynomial. The apparatus includes means for generating a plurality of syndrome polynomials. A magnitude polynomial and a location polynomial having a first derivative are calculated from the syndrome polynomials utilizing Euclid'"'"'s Algorithm. The module utilizing Euclid'"'"'s Algorithm includes a general Galois Field multiplier having combinational logic circuits. The magnitude polynomial is divided by the first derivative of said location polynomial to form a quotient. Preferrably the division includes finding the inverse of the first derivative and multiplying the inverse by the magnitude polynomial. The error is corrected by exclusive ORing the quotient with the received polynomial.

Claims

1. A Galois Field decoder for correcting an error in a received message comprising:

a. means for calculating a magnitude polynomial representing a portion of a magnitude of said error in said received message;

b. means for calculating a location polynomial representing a location of said error in said received message, said location polynomial having a first derivative polynomial;

c. means for calculating the first derivative polynomial of said location polynomial, said first derivative having a plurality of non-zero values, each of said non-zero values having an inverse;

d. means for calculating said inverse values;

e. means for multiplying each of said inverse values with a value of said magnitude polynomial for forming a correction polynomial; and

f. means for correcting said received message by combining the received polynomial with the correction polynomial.

2. The Galois Field decoder according to claim 1 wherein said means for calculating said inverse values includes a ROM for storing values of inverses for elements in said Galois Field.

3. A digital logic Galois Field polynomial solver which performs an operation during a clock pulse for correcting a received polynomial field element R(x), in a Galois Field in an (n, k) error correction code, wherein n is a number representing the number of unique elements in a code and k is number representing a number of elements of information in the code, comprising;

a. first means for evaluating Ω

(x), wherein Ω

(x) is a polynomial

whereby ##EQU15## represents a magnitude of an error said first means coupled within the poIynomial solver;

b. second means for evaluating Λ

(x) where Λ

(x) is a polynomial representing a location of an error said second means coupled within the polynomial solver;

c. third means for evaluating Λ

'"'"'(x), where Λ

'"'"'(x) is a polynomial representing a first derivative of Λ

(x);

said third means coupled within the polynomial solver and

d. fourth means for evaluating said polynomials for an arbitrary n in n clock pulses said fourth means coupled within the polynomial solver.

4. The Galois Field polynomial solver according to claim 3 wherein the improvement further comprises evaluating each polynomial for a highest order coefficient of an error polynomial first to a lowest order coefficient last.

5. A Galois Field syndrome generator of the type having a plurality of constant multipliers for generating a syndrome polynomial of 2t syndromes in n clock pulses, said generator having a register stack coupled to said multipliers for calculating said syndromes wherein the improvement comprises a shift register embodied coupled to said register stack and means for inhibiting said multipliers coupled to said multipliers.

6. A Galois Field syndrome generator according to claim 5 having a selectable basis convertor for generating a syndrome from an input that contains symbols in any basis.

7. The Galois Field syndrome generator according to claim 6 wherein the convertor is comprised of an array of Exclusive OR cells.

8. A Galois Field Euclid Algorithm apparatus for operating on an arbitrary received polynomial R(x), for calculating a magnitude polynomial, Ω

_i (x) having a first plurality of coefficients and a location polynomial, Λ

_i (x), having a second plurality of coefficients, said magnitude polynomial representing a magnitude of an error in said received polynomial and said location polynomial representing a location of said error in said received polynomial for use with a code having t correctable errors, said apparatus comprising;

a. a Euclid Algorithm divide module coupled to receive said received polynomial for implementing a first equation set forth below;

Ω

_i (x)=Ω

_i-2 (x) mod Ω

_i-1 (x); and

b. a Euclid Algorithm multiply module coupled to receive said received polynomial for implementing a second equation set forth below;

Λ

_i (x)=-q_i (x)Λ

_i-1 (x)+Λ

_i-2 (x).

9. The Galois Field Euclid Algorithm apparatus according to claim 8 wherein:

a. said divide module comprises;

(1) a quotient bus;

(2) a plurality of first cells, each first cell having;

(a) a first input and a first output;

(b) a first register having a second input and a second output, said second input coupled to a said first input;

(c) a second register having a third input and a third output;

(d) a first 2 input/2 output multiplexer coupled to receive having a fourth input, a fifth input, a fourth output and a fifth output, said fourth input coupled to said second output, said fifth input coupled to said third output and said fourth output coupled said third input; and

(e) a first Galois Field multiplier having a sixth input, a seventh input and a sixth output, said sixth input coupled to said fourth output and to said third input and said seventh input coupled to said quotient bus;

(f) a Galois Field adder having an eighth input, a ninth input and a seventh output, said eighth input coupled to said sixth output, said ninth input coupled to said fifth output and said seventh output coupled to said first output; and

(3) a second cell having;

(a) a third register having a tenth input and an eighth output;

(b) a fourth register having an eleventh input and a ninth output;

(c) a second 2 input/2 output multiplexer having a twelfth input, a thirteenth input, a tenth output and an eleventh output said eighth output coupled to said twelfth input, said ninth output coupled to said thirteenth input and said eleventh output coupled to said eleventh input;

(d) means for calculating an inverse value having a twenty-second input and an eighteenth output, said twenty-second input coupled to said eighth output;

(e) a latch means having a twenty-third input and a nineteenth output, said twenty-third input coupled to said eighteenth output; and

(f) a second Galois Field multiplier having a twenty-fourth input, a twenty-fifth input and a twentieth output, said twenty-fourth input coupled to said nineteenth output, said twenty-fifth input coupled to said tenth output and said twentieth output coupled to said quotient bus; and

b. said multiply module comprises;

(1) said quotient bus; and

(2) a plurality of third cells, each said third cell having;

(a) a first register having a fourteenth input and a twelfth output;

(b) a second register having a fifteenth input and a thirteenth output;

(c) a third 2 input/2 output multiplexer having a sixteenth input, a seventeenth input, a fourteenth output and a fifteenth output, said sixteenth input coupled to said twelfth output;

(d) a Galois Field multiplier having an eighteenth input, a nineteenth input and a sixteenth output, said eighteenth input coupled to said fifteenth output and said ninteenth input coupled to said quotient bus; and

(e) a Galois Field adder having a twentieth input, a twent-first input and a seventeenth output, said twentieth input coupled to said sixteenth output, said twenty-first input coupled to said fourteenth output and said seventeenth output coupled to said fourteenth input.

10. A Galois Field error correction decoder comprising:

a. means for receiving a received polynomial;

b. means for generating a plurality of syndrome polynomials, for said received polynomial;

c. means for calculating a magnitude polynomial and a location polynomial having a first derivative from said syndrome polynomials utilizing Euclid'"'"'s Algorithm, said means for calculating including a general Galois Field multiplier comprised of combinational logic circuits;

d. means for dividing said magnitude polynomial by said first derivative of said location polynomial comprised of means for calculating an inverse of said first derivative and multiplying said inverse by said magnitude polynomial for forming a correction polynomial; and

a. means for correcting an error in said received polynomial by combining the received polynomial with the correction polynomial.

11. A commutative general purpose multiplier in a GF(2ⁿ) Galois Field having a plurality of sets of elements, each element having a plurality of binary bits, with each set corresponding to a polynomial p(x) having one or more terms in said Galois Field, said multiplier for multiplying a first element by a second element comprising:

a. an n×

n array of multiplier cells arranged in n columns of multiplier cells, each column having n multiplier cells 0 through n-1, by n rows of multiplier cells, each row having n multiplier cells 0 through n-1, the column cells 0 through n-1 corresponding to the bits of a first element and the row cells 0 through n-1 corresponding to the bits of a second element such that each ith multiplier cell in each jth column is coupled to each (i+1)th multiplier cell in the jth column and to the (i+1)th multiplier cell in the (j+1)th column;

b. a plurality of input means, one of said input means coupled to each said multiplier cell; and

c. a plurality of feedback means, one or more in each row corresponding to said terms of said polynomial p(x) coupled between each said ith cell in the jth column and the (i+1)th cell in the (j+1)th column where appropriate according to p(x), and means for receiving an input from one of said columns of said array and for providing a feedback signal to one or more multiplier cells,

whereby a product of said multiplier is one element of said set of elements.

12. The multiplier according to claim 11 wherein said multiplier is asynchronous.

13. The multiplier according to claim 12 wherein said multiplier cells and said feedback means are comprised of combinational logic circuits.