Retimed decomposed serial berlekamp-massey architecture for high-speed reed-solomon decoding

Abstract

Reed-Solomon code is a linear systematic block code based on finite field theory. The systematic format, the efficient encoding/decoding algorithm, and the powerful random/burst error correction capability of the code make it one of the most widely used error correction code in the industry. In RS decoders, the throughput bottleneck is the key equation solver (KES) block. We have adopted the Berlekamp-Massey (BM) algorithm for solving the key equation because it leads to more efficient hardware and software implementation. Because of the presence of feed back signals in the original BM algorithm it is hard to pipeline this block to improve the speed. We have proposed a retimed decomposed inversion less serial BM architecture that improves the speed and throughput by almost 76%. This improvement has been achieved at the expense of some extra registers. The key ideas include, the updating of the error locator polynomial and the discrepancy value computation in parallel in 2t + 2 cycles per iteration plus using the retiming technique to achieve a high speed architecture. In addition standard basis irregular fully parallel multiplier with separate partial product generation (PPG) and partial product reduction (PPR) stages has been used in our design, which leads to improved performance.