
The "Berlekamp algorithm" best known to coding theorists is a fast way to invert matrices with constant diagonals. It works over any field, with the finite fields that occur in coding theory being the most popular. Massey's variation on the algorithm, used to synthesize linear feedback shift registers having a specified output sequence, became known as the "BerlekampMassey algorithm". The algorithm is also helpful for decoding various classes of algebraic codes. Since the goal is an algorithm whose work and storage requirements will be comparable to or better than n^{2}, the crucial step is to reformulate the problem in a way that avoids thinking about n by n matrices explicitly. This is done via this congruence: (1 + S(z)) (z) (z) mod z^{2n+1}.
Implementations of that algorithm varied greatly in efficiencies. The special purpose hardware implemented in Cyclotomics' GF1 computer was by far the best. For some applications with very high reliability requirements, most of the decoding effort was typically spent calculating the syndromes, S(z). Another ReedSolomon decoding algorithm patented by Berlekamp and Welch in 1986 bypassed this problem, using parity checks much more easily recomputed by Berlekamp's 1983 BitSerial Encoder in lieu of the syndromes. Yet more refinements and improvements were presented in Berlekamp's 1996 paper, "Soft Decision+1 ReedSolomon Decoding". Some of these algorithms were applied to probabilistic checking of proofs by Madhu Sudan and his colleagues, who also devised ingenious algorithms to implement list decoding in a way which discovers all codewords that lie within some multiple of half the minimum distance. Although significantly slower than WelchBerlekamp, Sudan's enhanced methods attain significantly improved performance when the code rate is low and the noise level is very high.

