On constructing a shortest linear recurrence relation

DOI10.1109/9.649704MaRDI QIDQ4373060zbMATH OpenOpenAlexFDO

Authors Jan C. Willems, Margreet Kuijper

Publication date 21 January 1998

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/9.649704

zbMATH Keywords

behavioral approach of linear systems theoryBerlekamp-Massey algorithmcoding theorypartial realization problem

Mathematics Subject Classification ID

Minimal systems representations (93B20)

Review text

The following problem is addressed: Let \(\{a_1,a_2,\dots, a_N\}\) be a finite subset from a field \(F\). Problem: Find reals \(e_0,e_1,\dots, e_{L-1}\), such that \(a_{j+L}+ e_{L- 1} a_{j+L- 1}+\cdots+ e_0 a_j=0\) for \(j=1,2,\dots, N-L\), such that \(L\) is as small as possible. After reformulating this problem, originating in coding theory, as a partial realization problem, an iterative solution, the Berlekamp-Massey algorithm, is derived by means of J. C. Willems' behavioral approach of linear systems theory.

Recommendations

• Linear feedback shift registers and the minimal realization problem
• scientific article; zbMATH DE number 820495
• On shortest linear recurrences

Cited in

(9)

• On shortest linear recurrences
• An algorithm for constructing a minimal partial realization in the multivariable case
• Linear feedback shift registers and the minimal realization problem
• Recursive exact \(H_{\infty }\)-identification from impulse-response measurements
• On recursiveness and related topics in linear systems
• scientific article; zbMATH DE number 4118432 (Why is no real title available?)
• An Algorithm for Computing Minimal Bidirectional Linear Recurrence Relations
• An iterative algorithm for parametrization of shortest length linear shift registers over finite chain rings
• scientific article; zbMATH DE number 975570 (Why is no real title available?)

This page was built for publication: On constructing a shortest linear recurrence relation

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