Extension of the Berlekamp-Massey algorithm to N dimensions (Q583882): Difference between revisions

We present an algorithm for finding a minimal set of linear recurring relations which are valid for a given n-dimensional array over any field, where the ``minimality'' is defined with respect to the partial order over the n-dimensional lattice. The algorithm is an extension of our two- dimensional version of the Berlekamp-Massey algorithm to more than two dimensions. The n-dimensional theory is based on more general concepts which can be reduced into those of the two-dimensional theory in the previous paper. In a typical case, the resulting set of polynomials characterizing the minimal linear recurring relations proves to be a Gröbner basis of the ideal defined by the array, and consequently the structure of an n-dimensional linear feedback shift register with the minimum number of storage devices which can generate the array is determined by it.