Efficient Berlekamp-Massey Algorithm And Architecture For Reed-Solomon Decoder

This dissertation presents a novel area-efficient compensated simplified reformulated inversionless Berlekamp-Massey(CS-RiBM) algorithm and its key equation solver(KES)architecture for the syndrome-based Reed-Solomon(RS) decoders. We analyze the conventional reformulated inversionless Berlekamp-Massey(RiBM) algorithm and discuss how the RiBM algorithm updates the involved polynomials as well as its drawbacks. Based on the discussion, the proposed CS-RiBM algorithm is proved to successfully remove unnecessary zero-in-zero-out computations in the RiBM algorithm and generate the same solution as the RiBM algorithm via adopting a new polynomial update method with simple compensation. Thus, the CS-RiBM algorithm can achieve higher execution efficiency.Since the proposed algorithm reduces lots of redundant computations, the KES architecture implementing the CS-RiBM algorithm requires much fewer processing elements and significantly simplifies the hardware complexity. Moreover, it can be implemented as a regular homogenous systolic architecture that is favorable for VLSI architecture design.The RS(255, 239) and RS(255, 223) decoders using the CS-RiBM architecture have been designed with Verilog HDL and synthesized with TSMC 90 nm CMOS technology library by the Design Compiler in order to compare with other related architectures. The synthesis results show that the CS-RiBM architecture can reduce 15% to 44% area compared with the prior KES architectures based on the Berlekamp-Massey(BM) and modified Euclidean(ME) algorithms. The proposed RS decoders achieve similarly high throughput to the RS decoders using the RiBM architecture with lower hardware complexity and are 11% to 16%more efficient. As the error-correcting capability of the RS code increases, The RS decoder using the CS-RiBM architecture can further reduce the required area and achieve higher efficiency.