The Berlekamp-Massey algorithm and linear recurring sequences over a factorial domain
type: Item
instance of: scholarly article
title: The Berlekamp-Massey algorithm and linear recurring sequences over a factorial domain
zbMATH Open document ID: 0837.94025
DOI: 10.1007/BF01235722
author: Patrick Fitzpatrick
author: G. H. Norton
published in: Applicable Algebra in Engineering, Communication and Computing
publication date: 1995-08-02T00:00:00Z
review text: 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 \(UX\) 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.
Mathematics Subject Classification ID: 94B35
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 13F15
zbMATH DE Number: 780891
zbMATH Keywords: Berlekamp-Massey algorithm
zbMATH Keywords: existence
zbMATH Keywords: effective computation
zbMATH Keywords: minimal polynomial
zbMATH Keywords: linear recurring sequence
zbMATH Keywords: one variable codes
zbMATH Keywords: decoding algorithms
zbMATH Keywords: extended Euclidean algorithm
zbMATH Keywords: polynomial remainder sequence
zbMATH Keywords: factorial domains
reviewed by: Ian Blake
MaRDI profile type: Publication
cites work: Q3968873
cites work: Algebraic coding theory
cites work: Q4405003
cites work: Subresultants and Reduced Polynomial Remainder Sequences
cites work: Suites récurrentes linéaires. Propriétés algébriques et arithmétiques. (Linear recurrent sequences. Algebraic and arithmetic properties)
cites work: On the equivalence between Berlekamp's and Euclid's algorithms (Corresp.)
cites work: Q4732508
cites work: Finding a basis for the characteristic ideal of an n-dimensional linear recurring sequence
cites work: Linear recurring sequences and the path weight enumerator of a convolutional code
cites work: Q3509721
cites work: Shift-register synthesis and BCH decoding
cites work: Q4156696
description: scientific article; zbMATH DE number 780891