Improved Berlekamp-Massy Algorithm and Its Software Implementation on DSP

Based on the Berlekamp-Massy (BM) algorithm for Reed-Solomon(RS) decoding, an improved version is proposed, which focuses on how to find the error locator polynomial using least iterative operations. The conditions to end the iterative operations is derived. As a special case, criterion of only one error symbol in one received codeword is derived as well. Steps are listed concerning the implementation of the improved iterative decoding algorithm, which is carried out as software on the platform of TIs C6416 DSP. Decoding performance and decoding-delay of both improved and original algorithms under different ( n,k) conditions are simulated. The results of simulations demonstrate that the improved algorithm has less computational complexity when the number of errors in a received codeword is relatively small. Therefore, in channels with low noise power spectrum density, the improved algorithm results in less decoding-delay than BM algorithm.