SINGLE-STACK IMPLEMENTATION OF A REED-SOLOMON ENCODER/DECODER

The present invention is for a Error Correction Unit (ECU) that uses a single stack architecture for the generation, reduction and evaluation of the polynomials involved in the correction of a Reed-Solomon code. The circuit uses the same hardware to generate the syndromes, reduce the .OMEGA.(x) and .LAMBDA.(x) polynomials and evaluate the .OMEGA.(x) and .LAMBDA.(x) polynomials. Some of the specifics involved in calculating and reducing the polynomials mentioned above are novel as well. First, the implementation of the general Galois field multiplier is new and faster than previous implementations. Second, the circuit for implementing the Galois field inverse function has not appeared in prior art designs. Third, a novel method of generating the .OMEGA.(x) and .LAMBDA.(x) polynomials (including alignment of these polynomials prior to evaluation) is utilized. Fourth, corrections are performed in the same order as they are received using a premultiplication step prior to evaluation. Fifth, a novel method of implementing flags for uncorrectable errors is used. Sixth, the ECU is data driven in that nothing happens if no data is present. Finally, interleaved data is handled internally to the chip.