In 1968, Berlekamp and Massey presented an algorithm to compute a shortest linear recurrence relation for a finite sequence of numbers. It was originally designed for the purpose of decoding certain types of block codes. It later became important for cryptographic applications, namely for determining the complexity profile of a sequence of numbers. Here, the authors interpret the Berlekamp-Massey algorithm in a system-theoretic way. The authors explicitly present the algorithm as an iterative procedure to construct a behavior. The authors conclude that this procedure is the most efficient method for solving the scalar minimal partial realization problem.
展开▼