Closed solution of the Berlekamp-Massey algorithm for fast decoding of BCH codes

The most complicated step in decoding BCH codes is the algebraic operation of converting the syndrome vector derived from a received data vector into an error location polynomial over the finite field GF (2^m). The classic method uses Berlekamp´s iterative algorithm to fill rows of a table with various quantities including partial polynomials until a maximum row is reached. Where this occurs depends on the distance of the code. This process is tedious, time-consuming, and is difficult to realize in hardware. The complete closed solution to the algorithm for each t⩽5 is presented as a set of decision trees. The only computation required is the numeric evaluation of one formula over GF (2^m) at each level of the tree as well as the evaluation of a formula for each coefficient in the resulting polynomial. The closed solution is more easily realized in hardware or software than the iterative algorithm, and it is shown by simulation that the closed solution is considerably faster even though some of the formulas are rather long. Also, the closed formulas can be proven correct, where it is almost impossible to totally verify an implementation of the iterative method