Multi-trial Guruswami–Sudan decoding for generalised Reed–Solomon codes

An iterated refinement procedure for the Guruswami–Sudan list decoding algorithm for Generalised Reed–Solomon codes based on Alekhnovich’s module minimisation is proposed. The method is parametrisable and allows variants of the usual list decoding approach. In particular, finding the list of closest codewords within an intermediate radius can be performed with improved average-case complexity while retaining the worst-case complexity. We provide a detailed description of the module minimisation, reanalysing the Mulders–Storjohann algorithm and drawing new connections to both Alekhnovich’s algorithm and Lee–O’Sullivan’s. Furthermore, we show how to incorporate the re-encoding technique of Kötter and Vardy into our iterative algorithm.

• Publication year

  2013

• Venue

  Designs, Codes and Cryptography

• Publication date

  2013-01-26

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s10623-014-9951-7arXiv 1301.6236
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Faster Algorithms for Multivariate Interpolation With Multiplicities and Simultaneous Polynomial Approximations

  2014cited by this paper
• List Decoding of Algebraic Codes

  2013cited by this paper
• On the Average Complexity of Reed–Solomon List Decoders

  2013cited by this paper
• Progressive List-Enlarged Algebraic Soft Decoding of Reed-Solomon Codes

  2012cited by this paper
• On Rational Interpolation-Based List-Decoding and List-Decoding Binary Goppa Codes

  2012cited by this paper
• List Decoding for Binary Goppa Codes

  2011cited by this paper
• Author manuscript, published in "IEEE Transactions on Information Theory (2011)" DOI: 10.1109/TIT.2011.2162160 An Interpolation Procedure for List Decoding Reed–Solomon Codes Based on Generalized Key Equations

  2011cited by this paper
• Key equations for list decoding of Reed-Solomon codes and how to solve them

  2010influential reference
• The Re-Encoding Transformation in Algebraic List-Decoding of Reed–Solomon Codes

  2010cited by this paper
• Interpolation and List Decoding of Algebraic Codes

  2010cited by this paper
• On the estimation and application of max-stable processes

  2010influential reference
• Linear diophantine equations over polynomials and soft decoding of Reed-Solomon codes

  2005influential reference
• On the complexity of polynomial matrix computations

  2003cited by this paper
• A complexity reducing transformation in algebraic list decoding of Reed-Solomon codes

  2003cited by this paper
• On lattice reduction for polynomial matrices

  2003cited by this paper
• Modern computer algebra

  2002cited by this paper
• Algebraic soft-decision decoding of Reed-Solomon codes

  2000cited by this paper
• Improved decoding of Reed-Solomon and algebraic-geometry codes

  1999cited by this paper
• Efficient decoding of Reed-Solomon codes beyond half the minimum distance

  1998cited by this paper
• Decoding of Reed Solomon Codes beyond the Error-Correction Bound

  1997influential reference
• Factoring multivariate polynomials over finite fields

  1983cited by this paper
• A new upper bound for error-correcting codes

  1962cited by this paper

• decoding for

  2022cites this paper
• Algebraic Soft Decoding of Elliptic Codes

  2021cites this paper
• A Groebner-bases approach to syndrome-based fast Chase decoding of Reed-Solomon codes

  2020cites this paper
• Low-Complexity Chase Decoding of Reed-Solomon Codes Using Module

  2020cites this paper
• Module minimisation based low-complexity soft decoding of Reed-Solomon codes

  2019cites this paper
• Progressive Algebraic Soft-Decision Decoding of Reed–Solomon Codes Using Module Minimization

  2019influential citation
• Algebraic Soft Decoding Algorithms for Reed-Solomon Codes Using Module

  2017cites this paper
• Progressive Algebraic Soft Decoding of Reed-Solomon Codes Using Module Minimization

  2017influential citation
• Algebraic soft decoding of Reed-Solomon codes with improved progressive interpolation

  2016cites this paper
• Algebraic chase decoding of Reed-Solomon codes using module minimisation

  2016cites this paper
• Solving generalised Padé approximations over polynomial rings

  2014cites this paper
• Generalised Multi-sequence Shift-Register synthesis using module minimisation

  2013cites this paper
• List Decoding of Algebraic Codes

  2013cites this paper
• Algebraic soft- and hard-decision decoding of generalized reed-solomon and cyclic codes

  2013cites this paper