A generalization of the Massey-Ding algorithm

DOI10.1007/S002000050092MaRDI QIDQ1389143zbMATH OpenOpenAlexFDO

Authors Joachim Althaler, Arne Dür

Publication date 12 August 1998

Published in Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s002000050092

zbMATH Keywords

annihilator ideallinear recurrence relationMassey-Ding algorithmminimal Gröbner basisshift register synthesis problem

Mathematics Subject Classification ID

Recurrences (11B37) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55)

Review text

In [Finite linear recurring sequences and homogeneous ideals, same journal 7, 377-390 (1996; Zbl 0870.11009)], the authors described the complete solution of the synthesis problem by computing a Gröbner basis of the annihilator ideal for a set of finite linear recurring sequences. In the present paper the authors use their ideal theoretic approach in order to generalize the Massey-Ding algorithm. The latter one computes a linear recurrence relation of minimal order for several finite sequences of equal length, while the generalization allows the computation of a minimal Gröbner basis of the annihilator ideal of several finite sequences of generally different lengths.

Recommendations

• scientific article; zbMATH DE number 5984
• The Berlekamp-Massey algorithm revisited
• A generalization of the Katzman-Zhang algorithm
• A generalization of Gosper's algorithm
• Generalized Cheney-Loeb-Dinkelbach-Type Algorithms
• A generalisation of the Cantor-Zassenhaus algorithm
• A generalization of Takane's algorithm for DEDICOM
• A generalized Apagodu-Zeilberger algorithm
• Generalization of the Zionts-Wallenius algorithm
• scientific article; zbMATH DE number 820495

Cited in

(8)

• A generalization of Gröbner bases and a synthesis algorithm of multisequence over \(\mathbb{Z}/(m)\)
• Finite linear recurring sequences and homogeneous ideals
• Linear feedback shift registers and the minimal realization problem
• On the annihilator ideal of an inverse form
• The Berlekamp-Massey algorithm revisited
• A generalization of Takane's algorithm for DEDICOM
• A simple derivation of the Berlekamp- Massey algorithm and some applications (Corresp.)
• scientific article; zbMATH DE number 820495 (Why is no real title available?)

This page was built for publication: A generalization of the Massey-Ding algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1389143)