The Berlekamp-Massey algorithm and linear recurring sequences over a factorial domain (Q1894579)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The Berlekamp-Massey algorithm and linear recurring sequences over a factorial domain |
scientific article |
Statements
The Berlekamp-Massey algorithm and linear recurring sequences over a factorial domain (English)
0 references
2 August 1995
0 references
The existence and effective computation of the minimal polynomial of a linear recurring sequence (lrs) with terms from a domain \(r\) is considered. Particular attention is given to the case when \(R=U\) is a factorial (unique factorization) domain. When \(U=K\), a field, the theory is well known and the Berlekamp-Massey (BM) algorithm computes the minimal polynomial. A more general approach is taken here to obtain information about lrs in domains such as \(\mathbb{Z}\) and \(K[X_1, X_2, \ldots, X_n ]\). The work is motivated by the desire to extend the theory of one variable codes and their decoding algorithms, such as BM and those based on the extended Euclidean algorithm (XE) to a multivariable theory. A generalization to XE and the polynomial remainder sequence (PRS) to \(R[X]\) is given. The extended algorithm (XRS) has certain invariance properties, similar to those of XE. XPRS is modified to an algorithm, BM/R, analogous to BM is given in section 3. Section 4 considers \(\text{lrs}(\alpha)= \alpha_0, \alpha_1, \ldots\) where \(\alpha_i\in U\). It is shown that the ideal of the characteristic polynomial of \((\alpha)\) is a principal ideal having a primitive polynomial generator. The factorial domains \(U\) for which the theory gives the strongest results are those for which \(U[[X]]\) are also factorial, called potential domains. This class includes all principal ideal domains and \(K[X_1, \ldots, X_n ]\). The final section contains algorithms for computing the characteristic polynomials of lrs's.
0 references
Berlekamp-Massey algorithm
0 references
existence
0 references
effective computation
0 references
minimal polynomial
0 references
linear recurring sequence
0 references
one variable codes
0 references
decoding algorithms
0 references
extended Euclidean algorithm
0 references
polynomial remainder sequence
0 references
factorial domains
0 references
0 references