Error correction method and apparatus

A convolutional generator comprising:

• a first set of registers used to accumulate coefficients of an error locator polynomial for a codeword;
• a second set of registers used to update the first set of registers;
• a third set of registers into which syndromes for the codeword are at least initially loaded;
• a first multiplier which serially outputs, two bits at a time, an inner product of the syndromes in the third set of registers and contents of the first set of registers;
• an accumulator connected to the first multiplier for accumulating an accumulation value therein;
• an inverse generator which receives the accumulation value in β basis representation and which serially outputs, two bits at a time, an α basis representation of an inverse of the accumulation value;
• a second multiplier which uses the accumulation value and contents of the second set of registers to update the first set of registers and
• a third multiplier which uses the a basis representation of the inverse of the accumulation value and contents of the first set of registers to update the second set of registers.

A method of operating a convolutional generator which operates upon a codeword, the method comprising:

• using a first recursion rule to generate coefficients of an error locator polynomial σ(x) for the codeword in a first set of registers, the coefficients of the error locator polynomial being generated by multiplying contents τn(x) of a second set of registers by a current discrepancy quantity which includes a current discrepancy dn;
• updating the contents τn(x) of the second set of registers using a second recursion rule;
• the first recursion rule being:
• σ(n+1)(x)=αd(σ(n)−dnτ(n))=αdσ(n)(x)−αddnτ(n)(x)
• the second recursion rule being:
• τ(n)(x)=x*(τ(n−1)(x)+(αddn−1)−1σ(n)(x)CHANGE_L)
• wherein CHANGE_L refers to a change in the length of a connection polynomial, and wherein d is non-zero.

A slice of an error correction circuit for a Reed-Solomon decoder, the slice comprising:

• a first set of registers used to accumulate coefficients of an error locator polynomial for a codeword having t correction signals;
• a second set of registers used to update the first set of registers;
• a third set of registers into which syndromes for the codeword are at least initially loaded;
• the first set of registers, the second set of registers, and the third set of registers being distributed over t+1 component slices;
• a first multiplier which prepares an inner product of the syndromes in the third set of registers and contents of the first set of registers;
• an accumulator connected to the first multiplier for accumulating an accumulation value therein;
• an inverse generator which receives the accumulation value and outputs an inverse of the accumulation value;
• a second multiplier which uses the accumulation value and contents of the second set of registers to update the first set of registers;
• a third multiplier which uses the inverse of the accumulation value and contents of the first set of registers to update the second set of registers;
• wherein at least one of the first multiplier, second multiplier, and third multiplier also perform an αd multiplication (d not equal to zero) whereby no sets of registers other than the first set of registers, the second set of registers, and the third set of registers are utilized in the slices to determine coefficients of the error locator polynomial.

A convolutional generator comprising:

• a first set of registers;
• a second set of registers;
• an updating multiplier;
• a feedback multiplier;
• wherein the convolutional generator operates upon a codeword and syndromes generated for the codeword by using a first recursion rule to generate coefficients of an error locator polynomial σ(x) for the codeword in the first set of registers, the coefficients of the error locator polynomial being generated in the first set of registers using the updating multiplier, the updating multiplier updating the first set of registers by multiplying contents τn(x) of the second set of registers by a current discrepancy quantity, the current discrepancy quantity including a current discrepancy dn and being derived from values stored in the first set of registers and syndromes, and wherein the contents τn(x) of the second set of registers are updated by the convolutional generator using a second recursion rule;
• wherein the feedback multiplier is provided for the first set of registers whereby contents of the first set of registers are clocked with a feedback value on a clock of an error locator iteration;
• wherein the first recursion rule is an expression employed by the convolutional generator for updating the second set of registers and the second recursion rule is an expression employed by the convolutional generator for updating the first set of registers.