scientific article; zbMATH DE number 1498815
The Berlekamp-Massey algorithm over an arbitrary finite ring with identity \(e\) is presented. Let \(R\) be a finite ring with identity \(e\). A polynomial \(f(x)=x^s-c_{s-1}x^{s-1}-\dots-c_1x-c_0 \in R[x]\) generates (from the left) a sequence \(u(0,\dots,l-1)=\bigl(u(0),u(1),\dots,u(l-1)\bigr)\in R^l\) if \(s\geq l\) or \(s< l\) and \[ u(i+s)=c_{s-1}u(i+s-1)+\dots +c_1u(i+1)+c_0u(i), \quad i=1,\dots,l-s-1. \] A monic polynomial of the smallest degree which generates \(u(0,\dots,l-1)\) is called its (left) minimal polynomial. The Berlekamp-Massey algorithm finds a minimal polynomial of a sequence of operations of \(R\) which has length \(l\) and complexity \(O(l^2)\). Many versions are available of the Berlekamp-Massey algorithm over fields as well as its generalization for some commutative rings. The complexity (the number of operations of the ring \(R\)) of the algorithm proposed is at most \[ (2M^2+10M)l^2 + O(l), \quad l\to \infty, \] where \(M\) is the number of classes of left-associated nonzero elements of \(R\); in particular, \(M<|R|\). For the entire collection see [Zbl 0918.00043].
- scientific article; zbMATH DE number 1567893
- On the matrix Berlekamp-Massey algorithm
- The Berlekamp-Massey algorithm and linear recurring sequences over a factorial domain
- Construction of the annihilator of a linear recurring sequence over finite module with the help of the Berlekamp-Massey algorithm
- The Berlekamp-Massey algorithm and linear recurring sequences over a factorial domain
- On Berlekamp-Massey and Berlekamp-Massey-Sakata algorithms
- A fraction free matrix Berlekamp/Massey algorithm
- The Berlekamp-Massey algorithm revisited
- On the matrix Berlekamp-Massey algorithm
- A simple derivation of the Berlekamp- Massey algorithm and some applications (Corresp.)
- An approach to an arithmetic analog of Berlekamp's algorithm (Corresp.)
- Construction of the annihilator of a linear recurring sequence over finite module with the help of the Berlekamp-Massey algorithm
- scientific article; zbMATH DE number 1567893 (Why is no real title available?)
- scientific article; zbMATH DE number 820495 (Why is no real title available?)
- An algorithm for construction of the annihilator of a polylinear recurring sequence over a finite commutative ring
- On minimal polynomials over \(\mathbb F_{q^m}\) and over \(\mathbb F_q\) of a finite-length sequence over \(\mathbb F_{q^m}\)
- Computational Science - ICCS 2004
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4501006)
