An iterative algorithm for parametrization of shortest length linear shift registers over finite chain rings
From MaRDI portal
Publication:522204
DOI10.1007/S10623-016-0226-3zbMATH Open1381.94054arXiv1201.5921OpenAlexW3105539080MaRDI QIDQ522204FDOQ522204
Authors: Raquel Pinto, Margreta Kuijper 
Publication date: 13 April 2017
Published in: Designs, Codes and Cryptography (Search for Journal in Brave)
Abstract: The construction of shortest feedback shift registers for a finite sequence S_1,...,S_N is considered over the finite ring Z_{p^r}. A novel algorithm is presented that yields a parametrization of all shortest feedback shift registers for the sequence of numbers S_1,...,S_N, thus solving an open problem in the literature. The algorithm iteratively processes each number, starting with S_1, and constructs at each step a particular type of minimal Gr"obner basis. The construction involves a simple update rule at each step which leads to computational efficiency. It is shown that the algorithm simultaneously computes a similar parametrization for the reciprocal sequence S_N,...,S_1.
Full work available at URL: https://arxiv.org/abs/1201.5921
Recommendations
- scientific article; zbMATH DE number 4012492
- A linear algebraic approach to multisequence shift-register synthesis
- Linear feedback shift registers and the minimal realization problem
- Shift Register Synthesis (Modulo m)
- A new algorithm on the minimal rational fraction representation of feedback with carry shift registers
Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Finite rings and finite-dimensional associative algebras (16P10)
Cites Work
- Minimal Bases of Rational Vector Spaces, with Applications to Multivariable Linear Systems
- Algebraic coding theory
- Title not available (Why is that?)
- Convolutional codes I: Algebraic structure
- Analysis and design of stream ciphers
- Linear recurring sequences over rings and modules
- Shift-register synthesis and BCH decoding
- Cyclic codes and minimal strong Gröbner bases over a principal ideal ring.
- Hamming metric decoding of alternant codes over Galois rings
- Gröbner bases over Galois rings with an application to decoding alternant codes
- Title not available (Why is that?)
- List decoding of Reed-Solomon codes from a Gröbner basis perspective
- On the key equation
- An efficient algorithm for constructing minimal trellises for codes over finite abelian groups
- An Algorithm for Computing Minimal Bidirectional Linear Recurrence Relations
- A Parametric Approach to List Decoding of Reed-Solomon Codes Using Interpolation
- On minimal realization over a finite chain ring
- The predictable degree property and row reducedness for systems over a finite ring
- Comparison of two algorithms for decoding alternant codes
- Linear recurring sequences over modules
- New List Decoding Algorithms for Reed–Solomon and BCH Codes
- Shift Register Synthesis (Modulo m)
- Linear recurrence sequences over commutative rings
- On the decoding of Reed-Solomon and BCH codes over integer residue rings
- On constructing a shortest linear recurrence relation
- The Berlekamp–Massey algorithm over finite rings, modules, and bimodules
- Canonical generating system of a monic polynomial ideal over a commutative Artinian chain ring
- Standard basis of a polynomial ideal over commutative Artinian chain ring
- Minimal Polynomial Algorithms for Finite Sequences
- Minimal Gröbner bases and the predictable leading monomial property
Cited In (5)
- A matrix based list decoding algorithm for linear codes over integer residue rings
- Noncatastrophic convolutional codes over a finite ring
- State representations of convolutional codes over a finite ring
- Searching Short Recurrences of Nonlinear Shift Registers via Directed Acyclic Graphs
- On lattice-based algebraic feedback shift registers synthesis for multisequences
This page was built for publication: An iterative algorithm for parametrization of shortest length linear shift registers over finite chain rings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q522204)
