(A) New early stopping BM algorithm and VLSI architecture for reed-solomon decoders

Abstract

In this paper, we devise new high-speed decoder architecture for Reed-Solomon codes using the Berlekamp-Massey (BM) algorithm. The speed bottleneck of the Reed-Solomon decoder is that the BM algorithm is needed to operate fixed 2t iterations to calculate error-locator polynomial and error-evaluator polynomial. In order to reduce iterative operations, we first present a new early stopping criterion for BM algorithm to reduce the number of iterations according to errors in the codeword. The derivative early stopping BM (ESBM) architecture is scalable systolic architecture in which a single array of processors computes both the error-locator polynomial and the discrepancy polynomial. We next concern critical path delay of the ESBM architecture. The ESBM architecture has long path delay, which is not appropriate high-speed RS decoders. Therefore, we second devise early stopping inversionless BM (ESiBM) architecture that effectively reduces critical path delay of the ESBM architecture. Furthermore, we lastly devise early stopping reformulated iBM (ESriBM) architecture to eliminate multiplexer delays of ESiBM architecture. In contrast to existing BM-based architecture, the ESriBM architecture has a smaller average latency due to the early stopping operation. Moreover, the ESriBM architecture has the same critical path delay and almost same hardware complexity as the state-of-the-art BM architecture.