A simple Hankel interpretation of the Berlekamp-Massey algorithm

DOI10.1016/0024-3795(89)90032-3MaRDI QIDQ1825176zbMATH OpenOpenAlexWikidataFDO

Authors Edmund Jonckheere, Chingwo Ma

Publication date 1989

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0024-3795(89)90032-3

zbMATH Keywords

Berlekamp-Massey algorithmdecoding Bose-Chaudhuri-Hocquengheim codesHankel matricesHankel system of equationsIohvidov indexlinear feedback shift register lengthLU factorization of the Hankel matrix

Mathematics Subject Classification ID

Recurrences (11B37) Decoding (94B35)

Review text

The Berlekamp-Massey algorithm is known for decoding Bose-Chaudhuri- Hocquengheim codes. In this paper it is provided an interpretation in the light of the algebraic theory of Hankel matrices. It is proved first that the jump of the linear feedback shift register length can be derived from the so-called Iohvidov index of the Hankel matrix. Next, the Hankel system of equations that yields the updated connection polynomial is solved via the LU factorization of the Hankel matrix.

Recommendations

• scientific article; zbMATH DE number 820495
• On Berlekamp-Massey and Berlekamp-Massey-Sakata algorithms
• Computational Science - ICCS 2004
• ON THE BERLEKAMP — MASSEY ALGORITHM AND ITS APPLICATION FOR DECODING ALGORITHMS
• On the Berlekamp/Massey algorithm and counting singular Hankel matrices over a finite field

Cites work

• A simple derivation of the Berlekamp- Massey algorithm and some applications (Corresp.)
• Certain continued fractions associated with the Padé table
• Combined sequence of Markov parameters and moments in linear systems
• Expansion of power series into \(P\)-fractions
• Fast solution of toeplitz systems of equations and computation of Padé approximants
• scientific article; zbMATH DE number 3138903 (Why is no real title available?)
• scientific article; zbMATH DE number 3845443 (Why is no real title available?)
• scientific article; zbMATH DE number 3661196 (Why is no real title available?)
• scientific article; zbMATH DE number 3775748 (Why is no real title available?)
• scientific article; zbMATH DE number 3318360 (Why is no real title available?)
• On the partial realization problem
• Shift-register synthesis and BCH decoding

Cited in

(18)

• A fast method to diagonalize a Hankel matrix
• The Lanczos algorithm and Hankel matrix factorization
• A look-ahead algorithm for the solution of general Hankel systems
• An algorithm for constructing a minimal partial realization in the multivariable case
• Sparse FGLM algorithms
• Recursive partial realization from the combined sequence of Markov parameters and moments
• Linear feedback shift registers and the minimal realization problem
• In-depth comparison of the Berlekamp-Massey-Sakata and the Scalar-FGLM algorithms: the adaptive variants
• The Berlekamp-Massey algorithm revisited
• Block diagonalization and LU-equivalence of Hankel matrices
• Linear algebra for computing Gröbner bases of linear recursive multidimensional sequences
• A simple derivation of the Berlekamp- Massey algorithm and some applications (Corresp.)
• On the Berlekamp/Massey algorithm and counting singular Hankel matrices over a finite field
• Minimal partial realization by descriptor systems
• Interpolation of dense and sparse rational functions and other improvements in \texttt{FireFly}
• A non-Gaussian limit for linear eigenvalue statistics of Hankel matrices
• Counting minors of a Hankel matrix
• Polynomial-division-based algorithms for computing linear recurrence relations

This page was built for publication: A simple Hankel interpretation of the Berlekamp-Massey algorithm

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