Generalised Multi-sequence Shift-Register Synthesis using Module Minimisation

2013/01/28 by Johan S. R. Nielsen, Nielsen, Johan S. R.
Computer Science · Mathematics · #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT

paper · pdf · doi:10.48550/arxiv.1301.6529

Version with full proofs. Fixed some typos in algorithm from last version. Presented at ISIT 2013

arxiv created 2013/11/29 · arxiv updated 2013/12/02

Abstract

We show how to solve a generalised version of the Multi-sequence Linear Feedback Shift-Register (MLFSR) problem using minimisation of free modules over \mathbb F[x]. We show how two existing algorithms for minimising such modules run particularly fast on these instances. Furthermore, we show how one of them can be made even faster for our use. With our modeling of the problem, classical algebraic results tremendously simplify arguing about the algorithms. For the non-generalised MLFSR, these algorithms are as fast as what is currently known. We then use our generalised MLFSR to give a new fast decoding algorithm for Reed Solomon codes.

Related

• Linear Shift-Register Synthesis for Multiple Sequences of Varying Length
• Parallel Generation of l-Sequences
• Syndrome Decoding of Reed-Solomon Codes Beyond Half the Minimum Distance based on Shift-Register Synthesis
• Solving Shift Register Problems over Skew Polynomial Rings using Module Minimisation
• An Algorithm for Constructing a Smallest Register with Non-Linear Update Generating a Given Binary Sequence