An algorithm and a VLSI architecture for Reed-Solomon decoding

Reed-Solomon decoding can be carried out in the time domain or frequency domain. The authors present a new version of the time domain algorithm which has only about 40% of the multiplications of published time domain techniques. The approach adopted in the algorithm development is as follows: obtain a new frequency domain decoding algorithm, with the number of Galois field multiplications and polynomial shift operations minimized; and take the Galois field inverse and discrete Fourier transforms of all the sequences and operators of this frequency domain decoding algorithm. Methods of mapping these algorithms into regular and flexible VLSI architectures are described. Both parallel and pipelined architectures are considered. It is shown that this algorithm can also be used very efficiently for decoding truncated Reed-Solomon codes