A METHOD TO DETERMINE A MINIMAL SET OF POLYNOMIALS CAPABLE OF GENERATING A GIVEN FINITE N-DIMENSIONAL ARRAY

The Berlekamp-Massey algorithm and the Euclidean algorithm are well kn own as decoding methods for Reed-Solomon codes. Sakata's algorithm, wh ich finds the minimal set of polynomials that generate a given two-dim ensional (2-D) array, is used as a decoding method for algebraic-geome tric codes; Reed-Solomon codes are a subclass of the algebraic-geometr ic codes. The Sakata algorithm is an extension of the Berlekamp-Massey algorithm to two dimensions, but there is no corresponding extension of the Euclidean algorithm to give it the edge in implementation. Theo rems are presented here to demonstrate in general the equivalence betw een the Berlekamp-Massey algorithm and the Euclidean algorithm and fro m these theorems a 2-D Euclidean algorithm that corresponds to the 2-D Berlekamp-Massey algorithm (Sakata algorithm) is developed. Moreover, the algorithms described here correspond to the multidimensional Berl ekamp-Massey algorithm and to the Kamiya-Miura algorithm, a modificati on of the Sakata algorithm. The algorithms proposed in this paper may be implemented at high speeds with parallel processing, a difficult ta sk for the Berlekamp-Massey algorithm.