HIGH SPEED IMPLEMENTATION OF BERLEKAMP MASSEY ALGORITHM FOR READ SOLOMON CODEC

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.