Method and apparatus for determining the coefficients of a locator polynomial

Claim 2

An error correction method of decoding a received codeword to obtain coefficients of a locator polynomial, said method comprising the steps of: (1) initializing a plurality of coefficient registers and loading a multiplicative identity field element expressed in a second basis representation into a first one of said coefficient registers; (2) loading syndrome values expressed in a first basis representation into appropriate ones of a plurality of syndrome registers; (3) using the contents of said coefficient registers and the contents of said syndrome registers to obtain a current discrepancy dn expressed in said second basis representation; (4) obtaining a quantity related to a multiplicative inverse d m -1 of a prior discrepancy d m , said quantity related to said multiplicative inverse d m -1 being expressed in said second basis representation; (5) multiplying said current discrepancy d n by said quantity related to said multiplicative inverse d m -1 to obtain a discrepancy product d n d m-1 ; (6) converting the contents of a plurality of said coefficient registers from said second basis representation to said first basis representation; (7) multiplying the converted contents of certain ones of said plurality of coefficient registers by the discrepancy product d n d m -1 to obtain a plurality of successions of products; (8) accumulating related ones of said products successively obtained in step (7) and loading said accumulations into appropriate ones of said coefficient registers.

Claim 3

The method of claim 1, wherein said step (3) of using the contents of said coefficient registers includes multiplying the contents of said coefficient registers by a field element and loading the product of said multiplication for each coefficient register back into those respective coefficient registers.

Claim 4

The method of claim 1, wherein said step (3) of using the contents of said coefficient registers and the contents of said syndrome registers to obtain a current discrepancy d n further comprises the steps of: determining an inner product using the contents of a plurality of pairs of coefficient registers and syndrome registers.

Claim 5

The method of claim 3, wherein said inner product is a serial output.

Claim 6

The method of claim 1, wherein said syndrome values are simultaneously loaded into appropriate ones of said plurality of syndrome registers.

Claim 7

The method of claim 1, wherein said current discrepancy d n is obtained as having a serial format, wherein said step (4) of obtaining said quantity related to said multiplicative inverse d m -1 comprises the steps of: converting said current discrepancy d n from a serial format to a parallel format; using said current discrepancy d n in a parallel format to determine a prior discrepancy d m in parallel format; and, determining the quantity related to the multiplicative inverse d m -1 of said prior discrepancy and expressing said quantity the in said second basis representation.

Claim 8

The method of claim 6, wherein the step of expressing the multiplicative inverse d m -1 of said prior discrepancy in said second basis representation involves selecting an appropriate value stored in a memory.

Claim 9

The method of claim 1, wherein said step (5) of multiplying said current discrepancy by said quantity related to said multiplicative inverse involves multiplying a serially formatted quantity by a parallel-formatted quantity.

Claim 10

The method of claim 8, wherein said serially formatted quantity is applied to first input terminals of a plurality of logical gates, wherein second input terminals of said logical gates are connected to a unique lead included in a bus comprising a plurality of parallel leads for transmitting said parallel-formatted quantity and wherein said gates perform a logical AND operation upon their respective inputs.

Claim 11

The method of claim 9, wherein the results of said logical AND operations are applied to a gate whereat an exclusive OR operation is performed.

Claim 12

The method of claim 1, wherein said step (6) of converting the contents of a plurality of said coefficient registers from said second basis representation to said first basis representation involves inputting the contents of a coefficient circuit into a converter circuit, the structure of said converter circuit being determined by a particular generator polynomial.

Claim 13

The method of claim 1, wherein said step (7) of multiplying the converted contents of certain ones of said plurality of coefficient registers by the discrepancy product d n d m -1 includes: multiplying the product d n d m -1 by a power i of a field member to obtain a product d n d m -1 α i ; applying the product d n d m -1 α i to first input terminals of a plurality of logical AND gates associated with respective certain ones of said coefficient registers; and, applying the converted contents of each of a plurality of coefficient registers to second input terminals of respective ones of said plurality of logical AND gates.

Claim 14

The method of claim 12, wherein said codeword has n number of m bit symbols including K informational symbols, wherein said error locator polynomial has coefficients σ o , σ 1 , . . . π n-K , and wherein the converted contents of the coefficient register for coefficient σ c is applied to the second input terminal of a logical AND gate associated with the coefficient register for coefficient σ c+1 , for c=1 to n-K-1.

Claim 15

The method of claim 13, wherein a plurality of syndrome values are simultaneously loaded into appropriate ones of said syndrome registers.

Claim 16

An error correction method of decoding a received codeword, said codeword having n number m-bit symbols including K informational symbols, to obtain coefficients σ o , σ 1 , . . . σ n-K of a locator polynomial, said method comprising the steps of: (1) initializing a bank of n-K coefficient registers and loading a multiplicative identity field element expressed in a second basis representation into a first one of said coefficient registers; (2) loading a syndrome value of a first order S o and having a first basis representation into a first one of a bank of n-K syndrome registers; (3) multiplying, for each of a first set of clock cycles, the contents of each of said coefficient registers by a field element α and loading the result of said multiplication back into said coefficient registers for possible further multiplication by said field element α during a succeeding clock cycle; (4) determining the inner product of the contents of each of said coefficient registers and an associated one of said syndrome registers during each of a first set of clock cycles to obtain a serial output in said second basis representation indicative of a current discrepancy d n ; (5) obtaining, during said first set of clock cycles, an m-bit value in second basis representation of a quantity related to a multiplicative inverse d m -1 of a prior discrepancy d.sub. m; (6) during said first set of clock cycles, said serial output indicative of said current discrepancy dn by said quantity related to said multiplicative inverse d m -1 to obtain an m-bit second basis representation of a discrepancy product d n d m -1 and loading said product in a discrepancy product register; (7) multiplying, for clock cycles included in a second set of clock cycles, the contents of said discrepancy product register by a field element α to obtain a m-bit product related to d n d m -1 and storing said resultant product in said discrepancy register for possible further multiplication during a succeeding clock cycle; (8) converting, the contents of a plurality of said coefficient registers from an m-bit representation in said second basis to an m-bit representation in said first basis; (9) multiplying, during clock cycles included in said second set of clock cycles, the converted m-bit contents of certain ones of said plurality of said coefficient registers by the resultant m-bit product stored in step (8) in said discrepancy register to obtain a serial product; (10) serially accumulating, during clock cycles included in said second set of clock cycles, related ones of said serial products and loading said serial accumulations into appropriate ones of said coefficient registers; (11) shifting the syndrome values stored in said syndrome registers into higher order syndrome registers included in said bank of syndrome registers and loading a higher order syndrome value into said first one of said syndrome registers; (12) repeating steps (4) through (10); (13) repeating steps (11) and (12) for successive higher order syndrome values up to and including S n -K-1; and, (14) using the contents of the coefficient registers as coefficients of a locator polynomial.

Claim 17

An error correction method of decoding a received codeword, said codeword having n number m-bit symbols including K informational symbols, to obtain coefficients σ o , σ 1 , . . . σ n-K of a locator polynomial, said method comprising the steps of: (1) initializing a bank of n-K coefficient registers and loading a multiplicative identity field element expressed in a second basis representation into a first one of said coefficient registers; (2) loading a syndrome value of a first order S o and having a first basis representation into a first one of a bank of n-K syndrome registers; (3) multiplying, for each of a first set of clock cycles, the contents of each of said coefficient registers by a field element α and loading the result of said multiplication back into said coefficient registers for possible further multiplication by said field element α during a succeeding clock cycle; (4) determining the inner product of the contents of each of said coefficient registers and an associated one of said syndrome registers during each of a first set of clock cycles to obtain a serial output in said second basis representation indicative of a current discrepancy d n ; (5) obtaining, during said first set of clock cycles, an m-bit value in second basis representation of a quantity related to a multiplicative inverse d m -1 of a prior discrepancy d.sub. m; (6) during said first set of clock cycles, said serial output indicative of said current discrepancy dn by said quantity related to said multiplicative inverse d m -1 to obtain an m-bit second basis representation of a discrepancy product d n d m -1 and loading said product in a discrepancy product register; (7) multiplying, for clock cycles included in a second set of clock cycles, the contents of said discrepancy product register by a field element α to obtain a m-bit product related to d n d m -1 and storing said resultant product in said discrepancy register for possible further multiplication during a succeeding clock cycle; (8) converting, the contents of a plurality of said coefficient registers from an m-bit representation in said second basis to an m-bit representation in said first basis; (9) multiplying, during clock cycles included in said second set of clock cycles, the converted m-bit contents of certain ones of said plurality of said coefficient registers by the resultant m-bit product stored in step (8) in said discrepancy register to obtain a serial product; (10) serially accumulating, during clock cycles included in said second set of clock cycles, related ones of said serial products and loading said serial accumulations into appropriate ones of said coefficient registers; (11) shifting the syndrome values stored in said syndrome registers into higher order syndrome registers included in said bank of syndrome registers and loading a higher order syndrome value into said first one of said syndrome registers; (12) repeating steps (4) through (10); (13) repeating steps (11) and (12) for successive higher order syndrome values up to and including S n -K-1; and, (14) using the contents of the coefficient registers as coefficients of a locator polynomial.

Claim 18

The method of claim 15, wherein said inner product is obtained by performing a logical AND operation of the contents of a plurality of pairs of coefficient register and syndrome registers and summing the results of the logical AND operation performed with respect to each register pairs.

Claim 19

The method of claim 15, wherein said current discrepancy dn is obtained as having a serial format, wherein said step (6) of obtaining said quantity related to said multiplicative inverse d m -1 comprises the steps of: converting said current discrepancy d n n from a serial format to a parallel format; using said current discrepancy d n in a parallel format to determine a prior discrepancy d m in parallel format; and, using the prior discrepancy d m to determine the quantity related to the multiplicative inverse d m -1 of the prior discrepancy.

Claim 20

The method of claim 17, wherein said quantity related to the multiplicative inverse d m -1 of said prior discrepancy is obtained by selecting an appropriate value stored in a memory.

Claim 21

The method of claim 15, wherein said step (6) of multiplying said current discrepancy dn by said quantity related to said multiplicative inverse d m -1 involves multiplying a serially formatted quantity d n by a parallel-formatted quantity d m -1 .

Claim 22

The method of claim 19, wherein said serially-formatted quantity is applied to first input terminals of a plurality of logical AND gates, wherein second input terminals of said logical gates are connected to a unique lead included in a bus comprising a plurality of parallel leads for transmitting said parallel-formatted quantity and wherein said gates perform a logical AND operation upon their respective inputs.

Claim 23

The method of claim 20, wherein the results of said logical AND operations are applied to a gate whereat an exclusive OR (XOR) operation is performed.

Claim 24

The method of claim 15, wherein said step (9) of converting the contents of a plurality of said coefficient registers from said second basis representation to said first basis representation involves inputting the contents of a coefficient circuit into a converter circuit, the structure of said converter circuit being determined by a particular generator polynomial.

Claim 25

The method of claim 15, wherein said step (10) of multiplying the converted contents of certain ones of said plurality of coefficient register by the discrepancy product d n d m -1 includes: multiplying the product d n d m -1 by a power i of a field member α to obtain a product d n d m -1 α i ; applying the product d n d m -1 α i to first input terminals of a plurality of logical AND gates associated with respective certain ones of said coefficient registers; and, applying the converted contents of each of a plurality of coefficient registers to second input terminals of respective ones of said plurality of logical AND gates.

Claim 26

The method of claim 23, wherein said codeword has n number of m-bit symbols including K informational symbols, and wherein said error locator polynomial has coefficients σ o , σ 1 , . . . σ n-K , and wherein the converted contents of the coefficient register for coefficient σ c is applied to the second input terminal of a logical AND gate associated with the coefficient register for coefficient σ c+1 , where c=1 to n-K-1.

Claim 27

Error correction apparatus for decoding a received codeword to obtain coefficients of a locator polynomial, said apparatus comprising: a plurality of syndrome registers into which syndrome values, expressed in a first basis representation, are loadable; a plurality of coefficient registers suited for storing therein coefficient values; convolution circuit means for obtaining a current discrepancy dn, said convolution circuit means comprising a first bank of a plurality of parallel-in serial-out (PISO) multipliers, each of said PISO multipliers being adapted to operate upon the contents of a syndrome register in said first basis representation and upon the contents of a coefficient register in said second basis representation to obtain said current discrepancy d n in said second basis representation; means for obtaining a quantity related to a multiplicative inverse d m -1 of a prior discrepancy dm, said quantity related to said multiplicative inverse d m -1 being expressed in said second basis representation; means for multiplying said current discrepancy d n by said quantity related to said multiplicative inverse d m -1 to obtain a discrepancy product d n d m -1 ; means for converting the contents of a plurality of said coefficient registers from said second basis representation to said first basis representation; a second bank of a plurality of parallel-in serial-out (PISO) multipliers, each of said PISO multipliers included in said second bank being adapted to multiply the converted contents of an appropriate one of said coefficient registers by the discrepancy product d n d m -1 to obtain a serial product; and, a plurality of accumulating means for accumulating, with respect to each of said PISO multipliers included in said second bank, successive serial products generated thereby, and for obtaining, with respect to each of said PISO multipliers included in said second bank, an accumulated value loadable into an appropriate on of said coefficient registers.

Claim 28

Error correction apparatus for decoding a received codeword to obtain coefficients of a locator polynomial, said apparatus comprising: a plurality of syndrome registers into which syndrome values, expressed in a first basis representation, are loadable; a plurality of coefficient registers suited for storing therein coefficient values; convolution circuit means for obtaining a current discrepancy dn, said convolution circuit means comprising a first bank of a plurality of parallel-in serial-out (PISO) multipliers, each of said PISO multipliers being adapted to operate upon the contents of a syndrome register in said first basis representation and upon the contents of a coefficient register in said second basis representation to obtain said current discrepancy d n in said second basis representation; means for obtaining a quantity related to a multiplicative inverse d m -1 of a prior discrepancy dm, said quantity related to said multiplicative inverse d m -1 being expressed in said second basis representation; means for multiplying said current discrepancy d n by said quantity related to said multiplicative inverse d m -1 to obtain a discrepancy product d n d m -1 ; means for converting the contents of a plurality of said coefficient registers from said second basis representation to said first basis representation; a second bank of a plurality of parallel-in serial-out (PISO) multipliers, each of said PISO multipliers included in said second bank being adapted to multiply the converted contents of an appropriate one of said coefficient registers by the discrepancy product d n d m -1 to obtain a serial product; and, a plurality of accumulating means for accumulating, with respect to each of said PISO multipliers included in said second bank, successive serial products generated thereby, and for obtaining, with respect to each of said PISO multipliers included in said second bank, an accumulated value loadable into an appropriate on of said coefficient registers.

Claim 29

The apparatus of claim 25, wherein said current discrepancy d n is expressed in said second basis representation with a serial format, wherein said quantity related to said multiplicative inverse d m -1 is expressed in said second basis representation with a parallel format, and wherein said means for multiplying said current discrepancy d n by said quantity related to said multiplicative inverse d m -1 comprises a serial-in, parallel-out (SIPO) multiplier adapted to multiply said serially-formatted current discrepancy dn by said parallel-formatted quantity related to said multiplicative inverse d m -1 to obtain a parallel-formatted discrepancy product d n d m -1 expressed in said second basis representation.

Claim 30

The apparatus of claim 26, wherein said SIPO multiplier comprises: a plurality of logical AND gates, each of said AND gates having first terminals thereof connected by a serial lead to said convolution circuit for receipt of said current discrepancy d n thereon, each of said AND gates having a second terminal connected to a unique lead in a m-bit lead cable emanating from said means for obtaining said quantity related to said multiplicative inverse d m -1 ; each of said AND gates having an output terminal; a logical exclusive OR (XOR) gate having input terminals including input terminals to which the output terminals of said AND gates comprising said SIPO multiplier are connected, said XOR gate also having an output terminal; register means for storing therein the result of a logical exclusive OR (XOR) operation performed by said XOR gate, said register having input terminals connected to the output terminal of said XOR gate.

Claim 31

The apparatus of claim 25, wherein each of said PISO multipliers included in said convolutional circuit means comprises: means for multiplying the contents of a respective one of said coefficient registers by a field element; logical AND gate means for performing a logical AND operation on the second basis-expressed contents of said respective one of said coefficient registers and on the first basis-expressed contents of a paired one of said syndrome registers to form an output; and, means for using said output from said AND gate in a logical exclusive OR (XOR) operation.

Claim 32

The apparatus of claim 28, wherein said means for multiplying the contents of a respective one of said coefficient registers by said field element includes: a feedback loop connecting an output terminal of said coefficient register with an input terminal thereof; multiplier means included in said feedback. loop for multiplying the contents of said coefficient register by said field element to obtain a product; and, means for loading the product of said multiplier means into said coefficient register.

Claim 33

The apparatus of claim 25, wherein said current discrepancy d n is obtained as having a serial format, and wherein the means for obtaining the quantity related to to the multiplicative inverse d m -1 comprises: the multiplicative inverse d m -1 comprises means for converting said current discrepancy d n from a serial format to a parallel format; means for using said current discrepancy d n in a parallel format to determine a prior discrepancy d m in parallel format; means for using the prior discrepancy d m to obtain the quantity related to the multiplicative inverse d m -1 of prior discrepancy and for expressing the quantity related to the multiplicative inverse d m -1 of said prior discrepancy in said second basis representation.

Claim 34

The apparatus of claim 30, wherein said means for obtaining said quantity related to the multiplicative inverse d m -1 comprises a memory wherein a table of values are stored, and wherein said memory is addressable using a power of a field element.

Claim 35

The apparatus of claim 25, wherein each of said PISO multipliers comprising said second bank of PISO multipliers comprises: a discrepancy product register having a feedback loop connecting an output terminal thereof with its input terminal, said feedback loop including a multiplier for multiplying the contents of said discrepancy product register by a field element, said discrepancy product register and feedback loop being common to said plurality of PISO multipliers comprising said second bank of PISO multipliers; means for performing a logical AND operation on the contents of said discrepancy product register and the converted contents of an appropriate one of said coefficient registers and for obtaining a result; and, means for performing a logical exclusive 0R (XOR) operation using said result from said logical AND operation.

Claim 36

The apparatus of claim 25, wherein one of said accumulating means comprises: a serial-to-parallel shift register loadable with the serial product of an appropriate one of said PISO multipliers included in said second bank of PISO multipliers; and, means for performing an exclusive OR (XOR) operation with respect to output data from said shift register and with respect to said serial product from said appropriate PISO multiplier.

Claim 39

The method of claim 34, further comprising the step of using said modified syndrome values stored in said syndrome registers to determine error magnitudes.

Claim 40

Apparatus for decoding a codeword to find coefficients of a locator polynomial, said apparatus comprising: means for loading syndrome values into a plurality of syndrome registers, said syndrome registers being connected together in a manner wherein data stored in one of said registers is shiftable in a circular path to others of said registers; means for initializing a plurality of coefficient registers with initialization values, each of said coefficient registers being paired with a corresponding one of said syndrome registers; means for multiplying the contents of said syndrome registers and the contents of said coefficient registers in a manner to obtain a current discrepancy; means for multiplying said current discrepancy by a value related to a multiplicative inverse of a prior discrepancy in a manner to obtain a discrepancy product; means for using a value related to the contents of said coefficient registers and said discrepancy product in a manner to obtain an updated value for at least one of said coefficiency registers; means for shifting the contents of each of said syndrome registers to an adjacent syndrome register said shifting occurring in a first direction along said circular path; means for multiplying the contents of at least one of said syndrome registers by the contents of a paired one of said coefficient registers to obtain a modified syndrome value; means for shifting the contents of each of said syndrome registers to an adjacent syndrome register, said shifting occurring in a second direction along said circular path; and, means for storing said modified syndrome value in a select one of said syndrome registers.

Claim 41

Apparatus for decoding a codeword to find coefficients of a locator polynomial, said apparatus comprising: means for loading syndrome values into a plurality of syndrome registers, said syndrome registers being connected together in a manner wherein data stored in one of said registers is shiftable in a circular path to others of said registers; means for initializing a plurality of coefficient registers with initialization values, each of said coefficient registers being paired with a corresponding one of said syndrome registers; means for multiplying the contents of said syndrome registers and the contents of said coefficient registers in a manner to obtain a current discrepancy; means for multiplying said current discrepancy by a value related to a multiplicative inverse of a prior discrepancy in a manner to obtain a discrepancy product; means for using a value related to the contents of said coefficient registers and said discrepancy product in a manner to obtain an updated value for at least one of said coefficiency registers; means for shifting the contents of each of said syndrome registers to an adjacent syndrome register said shifting occurring in a first direction along said circular path; means for multiplying the contents of at least one of said syndrome registers by the contents of a paired one of said coefficient registers to obtain a modified syndrome value; means for shifting the contents of each of said syndrome registers to an adjacent syndrome register, said shifting occurring in a second direction along said circular path; and, means for storing said modified syndrome value in a select one of said syndrome registers.

Claim 42

Error correction apparatus for decoding a received codeword, the apparatus comprising a plurality of registers for storing therein syndromes of the codeword, a plurality of coefficient registers wherein coefficients of a locator polynomial are accumulated, means for operating upon the contents of said syndrome registers and the contents of said coefficient registers to determine a current discrepancy, means for obtaining a discrepancy product by multiplying the current discrepancy by a multiplicative inverse of a prior discrepancy, means for multiplying the discrepancy product by the contents of the coefficient registers and for accumulating the product in the coefficient registers, characterized in that said means for operating upon said syndrome registers and said coefficient registers operates upon syndromes having a first basis representation and upon values in said coefficient registers having a second basis representation; the means for obtaining the discrepancy product obtains such a product having a second basis representation; means are provided to convert the contents of said coefficient register from a second basis representation to a first basis representation; and, the means for multiplying the discrepancy product multiplies such product by values related to the converted first basis representation of the coefficient registers for accumulating the resultant product in second basis representation in said coefficient registers.

Claim 43

Error correction apparatus for decoding a received codeword, the apparatus comprising a plurality of registers for storing therein syndromes of the codeword, a plurality of coefficient registers wherein coefficients of a locator polynomial are accumulated, means for operating upon the contents of said syndrome registers and the contents of said coefficient registers to determine a current discrepancy, means for obtaining a discrepancy product by multiplying the current discrepancy by a multiplicative inverse of a prior discrepancy, means for multiplying the discrepancy product by the contents of the coefficient registers and for accumulating the product in the coefficient registers, characterized in that said means for operating upon said syndrome registers and said coefficient registers operates upon syndromes having a first basis representation and upon values in said coefficient registers having a second basis representation; the means for obtaining the discrepancy product obtains such a product having a second basis representation; means are provided to convert the contents of said coefficient register from a second basis representation to a first basis representation; and, the means for multiplying the discrepancy product multiplies such product by values related to the converted first basis representation of the coefficient registers for accumulating the resultant product in second basis representation in said coefficient registers.

Claim 44

The apparatus of claim 37, wherein the means for multiplying the current discrepancy product by values related to the converted first basis representation of the coefficient registers can multiply the values related to the converted first basis representation of the coefficient registers by erasure locator values having a second basis representation.

Claim 45

The apparatus of claim 37, wherein the means for operating upon the contents of the syndrome registers and the contents of the coefficient register determines an inner product using the contents of the syndrome registers and the contents of the coefficient registers, and wherein said inner product is in a serial format.

Claim 46

The apparatus of claim 37, wherein the means for operating upon the contents of the syndrome registers and the contents of the coefficient registers comprises a first bank of a plurality of parallel-in serial-out (PISO) multipliers, each of said PISO multipliers being adapted to operate upon the contents of a syndrome register in said first basis representation and upon the contents of a coefficient register in said second basis representation to obtain the current discrepancy in said second basis representation, and wherein each of the PISO multipliers comprises: means for multiplying the contents of a respective one of said coefficient registers by a field element; logical AND gate means for performing a logical AND operation on the second basis-expressed contents of said respective one of said coefficient registers and on the first basis-expressed contents of a paired one of said syndrome registers to form an output; and, means for using said output from said AND gate in a logical exclusive OR (XOR) operation.

Claim 47

The apparatus of claim 40, wherein said means for multiplying the contents of a respective one of said coefficient registers by said field element includes: a feedback loop connecting an output terminal of said coefficient register with an input terminal thereof; multiplier means included in said feedback loop for multiplying the contents of said coefficient register by said field element to obtain a product; and, means for loading the product of said multiplier means into said coefficient register.

Claim 48

The apparatus of claim 37, wherein said current discrepancy is expressed in said second basis representation with a serial format, wherein a quantity related to said multiplicative inverse is expressed in said second basis representation with a parallel format, and wherein the current discrepancy is multiplied by a quantity related to the multiplicative inverse by a serial-in, parallel-out (SIPO) multiplier adapted to multiply the serially-formatted current discrepancy by a parallel-formatted quantity related to the multiplicative inverse to obtain a parallel-formatted discrepancy product expressed in said second basis representation.

Claim 49

The apparatus of claim 42, wherein said SIPO multiplier comprises: a plurality of logical AND gates, each of said AND gates having first terminals thereof connected by a serial lead to said convolution circuit for receipt of said current discrepancy thereon, each of said AND gates having a second terminal connected to a unique lead in a cable emanating from said means for obtaining said quantity related to said multiplicative inverse, each of said AND gates having an output terminal; a logical exclusive OR (XOR) gate having input terminals including input terminals to which the output terminals of said AND gates comprising said SIPO multiplier are connected, said XOR gate also having an output terminal; means for converting said current discrepancy from a serial format to a parallel format; means for using said current discrepancy in a parallel format to determine a prior discrepancy in parallel format; means for using the prior discrepancy to obtain the quantity related to the multiplicative inverse of prior discrepancy and for expressing the quantity related to the multiplicative inverse of said prior discrepancy in said second basis representation.

Claim 50

The apparatus of claim 37, wherein the means for multiplying the discrepancy product by a value related to the converted first basis representation of the coefficient registers comprises a second bank of a plurality of parallel-in serial-out (PISO) multipliers, and wherein each of said PISO multipliers comprising said second bank of PISO multipliers comprises: a discrepancy product register having a feedback loop connecting an output terminal thereof with its input terminal, said feedback loop including a multiplier for multiplying the contents of said discrepancy product register by a field element, said discrepancy product register and feedback loop being common to said plurality of PISO multipliers comprising said second bank of PISO multipliers; means for performing a logical AND operation on the contents of said discrepancy product register and the converted contents of an appropriate one of said coefficient registers and for obtaining a result; and, means for performing a logical exclusive OR (XOR) operation using said result from said logical AND operation.

Claim 51

The apparatus of claim 44, further comprising a plurality of accumulating means, and wherein one of said accumulating means comprises: a serial-to-parallel shift register loadable with the serial product of an appropriate one of said PISO multipliers included in said second bank of PISO multipliers; and, means for performing an exclusive OR (XOR) operation with respect to output data from said shift register and with respect to said serial product from said appropriate PISO multiplier.

Claim 52

The apparatus of claim 37, further comprising: means for multiplying the contents of at least one of said syndrome registers by the contents of a paired one of said coefficient registers to obtain a modified syndrome value in a second basis representation.

Claim 53

The apparatus of claim 46, further comprising: means for using the contents of the coefficient registers to locate bytes in a codeword wherein an error or erasure occurs and to generate a divisor; means for using modified syndromes stored in the syndrome registers to generate an error pattern dividend; means for multiplying the divisor by the dividend to obtain a product and for accumulating the products of successive each multiplications; and, means for converting the accumulated product from a second basis representation to a first basis representation.

Claim 54

The method of claim 37, wherein the values related to the converted first basis representation of the coefficient registers are multiplied by erasure locator values having a second basis representation rather than by said discrepancy product.

Claim 55

An error correction method for decoding a received codeword, the method being of the type wherein a plurality of syndrome registers are loaded to store therein syndromes of the codeword, wherein a current discrepancy is determined by operating upon the contents of the syndrome registers and a plurality of coefficient registers wherein coefficients of a locator polynomial are accumulated, wherein a discrepancy product is obtained by multiplying the current discrepancy by a multiplicative inverse of a prior discrepancy, wherein the discrepancy product is multiplied by the contents of the coefficient registers to obtain products accumulated in the coefficient registers, wherein the improvement comprises the steps of: determining the current discrepancy by operating upon the contents of the syndrome registers having a first basis representation and upon values in the coefficient registers having a second basis representation; obtaining a discrepancy product having a second basis representation; converting the contents of the coefficient registers from a second basis representation to a first basis representation; multiplying the discrepancy product in a second basis representation by values related to the converted first basis representation of the coefficient registers; and, accumulating the resulting product in second basis representation in said coefficient register.

Claim 56

An error correction method for decoding a received codeword, the method being of the type wherein a plurality of syndrome registers are loaded to store therein syndromes of the codeword, wherein a current discrepancy is determined by operating upon the contents of the syndrome registers and a plurality of coefficient registers wherein coefficients of a locator polynomial are accumulated, wherein a discrepancy product is obtained by multiplying the current discrepancy by a multiplicative inverse of a prior discrepancy, wherein the discrepancy product is multiplied by the contents of the coefficient registers to obtain products accumulated in the coefficient registers, wherein the improvement comprises the steps of: determining the current discrepancy by operating upon the contents of the syndrome registers having a first basis representation and upon values in the coefficient registers having a second basis representation; obtaining a discrepancy product having a second basis representation; converting the contents of the coefficient registers from a second basis representation to a first basis representation; multiplying the discrepancy product in a second basis representation by values related to the converted first basis representation of the coefficient registers; and, accumulating the resulting product in second basis representation in said coefficient register.

Claim 57

The method of claim 49, wherein said step 21 of obtaining a current discrepancy comprises the step of: determining an inner product using the contents of a plurality of pairs of coefficient registers and syndrome registers, and wherein said inner product is a serial format.

Claim 58

The method of claim 49, wherein syndrome values are simultaneously loaded into appropriate ones of said plurality of syndrome registers.

Claim 59

The method of claim 49, wherein the current discrepancy is obtained as having a serial format, wherein a quantity related to said multiplicative inverse comprises the steps of: converting said current discrepancy from a serial format to a parallel format; using said current discrepancy in a parallel format to determine a prior discrepancy in parallel format; and, determining the quantity related to the multiplicative inverse of said prior discrepancy and expressing said quantity the in said second basis representation.

Claim 60

The method of claim 49, further comprising the step of: shifting the contents of each of the syndrome registers to an adjacent syndrome register, said shifting occurring in a first direction along a circular path connecting the syndrome registers.

Claim 61

The method of claim 49, wherein after all syndromes have been obtained, the contents of at least one of the syndrome registers is multiplied by the contents of a paired one of the coefficient registers to obtain a modified syndrome value having a second basis representation.

Claim 62

The apparatus of claim 54, further comprising: using the contents of the coefficient registers to locate bytes in a codeword wherein an error or erasure occurs and to generate a divisor; using modified syndromes stored in the syndrome registers to generate an error pattern dividend; multiplying the divisor by the dividend to obtain a product and accumulating the products of successive such multiplications; and, converting the accumulated product from a second basis representation to a first basis representation.