Berlekamp-Massey Algorithm

If a sequence takes only a small number of different values, then by regarding the values as the elements of a finite field, the Berlekamp-Massey algorithm is an efficient procedure for finding the shortest linear recurrence from the field that will generate the sequence.

REFERENCES:

Berlekamp, E. R. Ch. 7 in Algorithmic Coding Theory. New York: McGraw-Hill, 1968.

Berlekamp, E. R.; Fredricksen, H. M.; and Proto, R. C. "Minimum Conditions for Uniquely Determining the Generator of a Linear Sequence." Util. Math. 5, 305-315, 1974.

Brent, R. P.; Gustavson, F. G.; and Yun, D. Y. Y. "Fast Solution of Toeplitz Systems of Equations and Computation of Padé Approximants." J. Algorithms 1, 259-295, 1980.

Dickinson, B. W.; Morf, M.; and Kailath, T. "A Minimal Realization Algorithm for Matrix Sequences." IEEE Trans. Automatic Control 19, 31-38, 1974.

Gustavson, F. G. "Analysis of the Berlekamp-Massey Linear Feedback Shift-Register Synthesis Algorithm." IBM J. Res. Dev. 20, 204-212, 1976.

MacWilliams, F. J. and Sloane, N. J. A. Ch. 9 in The Theory of Error-Correcting Codes. New York: Elsevier, 1978.

Massey, J. L. "Shift-Register Synthesis and BCH Decoding." IEEE Trans. Information Th. 15, 122-127, 1969.

McEliece, R. J. The Theory of Information Coding. Reading, MA: Addison-Wesley, 1977.

Mills, W. H. "Continued Fractions and Linear Recurrences." Math. Comput. 29, 173-180, 1975.

Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego, CA: Academic Press, pp. 25-26, 1995.