Early-Stopped Approach and Analysis for the Berlekamp-Massey Algorithm

BCH codes are being widely used in commercial
NAND flash controllers, and the decoding algorithm based on
the Berlekamp-Massey (BM) algorithm is a classic solution
for solving the key equation used for error correction. The
latency of BM decoding is the bottleneck of the Bose-Chaudhuri Hocquenghem (BCH) decoder when correcting a high number of
bit errors. However, the flash memory has an error distribution
that degrades with usage: few errors occur in the new memory
and a low number of errors occur within a code block. With
usage, the system performance degrades and BM decoding needs
t iterations in order to correct a larger number t of errors. In
an attempt to improve the system performance for high speed
applications, early termination of the BM decoding is necessary
to overcome this degradation. In this paper, a practical solution
for early termination checking for BM algorithm is provided. The
analysis of proposed method is presented by means of considering
the weight distribution of BCH code and deriving the probability
of malfunction as the event of undetectable error. The proposed
method is presented to be effective by the numerical results
and the probability of malfunction for the proposed method is
lower than 10−26. As a result, the FPGA testing on a USB device
validate the reliability of the proposed method for applying to a
commercial product.