On constructing a shortest linear recurrence relation

Abstract

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, we interpret the Berlekamp-Massey algorithm in a system-theoretic way. We explicitly present the algorithm as an iterative procedure to construct a behavior. We conclude that this procedure is the most efficient method for solving the scalar minimal partial realization problem.