Abstract:
Reed-Solomon coding is a popular scheme in forward error correction coding. It is
widely used in communication systems and data storages for correction of errors that
occur during transmission and while retrieving the data from disc. With modern day
communication systems and storage capabilities ever increasing demand for high
throughput data rates require high speed Reed Solomon decoders. The most
computationally intensive and complex part of the RS codec is the computation of
error locator and error evaluator polynomials over GF (;tn). First the decoding of
Reed Solomon codes involves computation of the Syndrome from the received
codeword. The error locator and error evaluator polynomials are calculated from the
syndrome components. Berlekamp Massey algorithm is among the best known
techniques for solving the key equation which equate syndrome, error locator and
error evaluator polynomials. The original algorithm involves the successive inversion
of the field elements. Inversion in a finite field either requires long time or space.
Iterative computations are involved first to find the discrepancy and then to update
the error locater polynomial. This is the most time consuming step which makes the
algorithm slow while the requirement for high throughput data rates is always rising.
The reformulated Berlekamp Massey algorithm is employed here for implementation.
The implementation is done for RS (255,223) code which has a error correcting
capability of 16 errors. The calculation of error locator and error evaluator polynomial
occur in 32 clock cycles. Further speed optimization is achieved by implementing a
low complexity bit parallel multiplier. A high speed implementation of the BM
algorithm is presented. This high speed implementation supports data throughput
rates in Gbits per second.
