A Generalization of the Massey-Ding Algorithm

Joachim Althaler; Arne Dür

doi:10.1007/s002000050092

A Generalization of the Massey-Ding Algorithm

Joachim Althaler, Arne Dür

Research Center Steyr

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

Abstract

The set of all linear recurrence relations satisfied by given sequences of finite length is described by the annihilator ideal of the sequences. The Massey-Ding algorithm to compute a linear recurrence relation of minimal order for several finite sequences of equal length is generalized to compute a minimal Gröbner basis of the annihilator ideal of several finite sequences of generally different lengths.

Original language	English
Pages (from-to)	1-14
Number of pages	14
Journal	Applicable Algebra in Engineering, Communication and Computing 9,
Volume	9
Issue number	1
DOIs	https://doi.org/10.1007/s002000050092
Publication status	Published - Apr 1998

Keywords

Annihilator ideal
Linear recurrence relation
Minimal Gröbner basis
Shift register synthesis problem

Access to Document

10.1007/s002000050092

Cite this

@article{fde7f69339da4017bc5fafac07016194,

title = "A Generalization of the Massey-Ding Algorithm",

abstract = "The set of all linear recurrence relations satisfied by given sequences of finite length is described by the annihilator ideal of the sequences. The Massey-Ding algorithm to compute a linear recurrence relation of minimal order for several finite sequences of equal length is generalized to compute a minimal Gr{\"o}bner basis of the annihilator ideal of several finite sequences of generally different lengths.",

keywords = "Annihilator ideal, Linear recurrence relation, Minimal Gr{\"o}bner basis, Shift register synthesis problem",

author = "Joachim Althaler and Arne D{\"u}r",

year = "1998",

month = apr,

doi = "10.1007/s002000050092",

language = "English",

volume = "9",

pages = "1--14",

journal = "Applicable Algebra in Engineering, Communication and Computing 9,",

number = "1",

}

TY - JOUR

T1 - A Generalization of the Massey-Ding Algorithm

AU - Althaler, Joachim

AU - Dür, Arne

PY - 1998/4

Y1 - 1998/4

N2 - The set of all linear recurrence relations satisfied by given sequences of finite length is described by the annihilator ideal of the sequences. The Massey-Ding algorithm to compute a linear recurrence relation of minimal order for several finite sequences of equal length is generalized to compute a minimal Gröbner basis of the annihilator ideal of several finite sequences of generally different lengths.

AB - The set of all linear recurrence relations satisfied by given sequences of finite length is described by the annihilator ideal of the sequences. The Massey-Ding algorithm to compute a linear recurrence relation of minimal order for several finite sequences of equal length is generalized to compute a minimal Gröbner basis of the annihilator ideal of several finite sequences of generally different lengths.

KW - Annihilator ideal

KW - Linear recurrence relation

KW - Minimal Gröbner basis

KW - Shift register synthesis problem

UR - http://www.scopus.com/inward/record.url?scp=0031681655&partnerID=8YFLogxK

U2 - 10.1007/s002000050092

DO - 10.1007/s002000050092

M3 - Article

VL - 9

SP - 1

EP - 14

JO - Applicable Algebra in Engineering, Communication and Computing 9,

JF - Applicable Algebra in Engineering, Communication and Computing 9,

IS - 1

ER -

A Generalization of the Massey-Ding Algorithm

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this