Answers are grounded in this paper and cite their sources.
The Berlekamp‐Massey algorithm and the Euclidean algorithm are well known as decoding methods for Reed‐Solomon codes. Sakata's algorithm, which finds the minimal set of polynomials that generate a given two‐dimensional (2‐D) array, is used as a decoding method for algebraic‐geometric codes; Reed‐Solomon codes are a subclass of the algebraic‐geometric 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. Theorems are presented here to demonstrate in general the equivalence between the Berlekamp‐Massey algorithm and the Euclidean algorithm and from 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 Berlekamp‐Massey algorithm and to the Kamiya‐Miura algorithm, a modification of the Sakata algorithm. The algorithms proposed in this paper may be implemented at high speeds with parallel processing, a difficult task for the Berlekamp‐Massey algorithm.
No takes yet. Share an insight, caveat, or question.
Iwamura et al. (1994) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: