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

DOI10.1007/S10623-014-9951-7MaRDI QIDQ398959zbMATH OpenOpenAlexFDO

Authors Alexander Zeh, Johan Rosenkilde né Nielsen

Publication date 18 August 2014

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.3022

zbMATH Keywords

Reed-Solomon codeslist decodingGuruswami-Sudanmulti-trialre-encoding transformation

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Decoding (94B35)

Abstract: 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"otter and Vardy into our iterative algorithm.

Recommendations

• A Note on the Generalisation of the Guruswami–Sudan List Decoding Algorithm to Reed–Muller Codes
• scientific article; zbMATH DE number 5380293
• A modified Guruswami-Sudan algorithm for decoding Reed-Solomon codes
• List decoding of Reed-Solomon codes from a Gröbner basis perspective
• Improved decoding of Reed-Solomon and algebraic-geometry codes

Cites work

• scientific article; zbMATH DE number 3167429 (Why is no real title available?)
• scientific article; zbMATH DE number 1936673 (Why is no real title available?)
• scientific article; zbMATH DE number 2151192 (Why is no real title available?)
• scientific article; zbMATH DE number 3410920 (Why is no real title available?)
• Algebraic soft-decision decoding of reed-solomon codes
• An Interpolation Procedure for List Decoding Reed–Solomon Codes Based on Generalized Key Equations
• Decoding of Reed Solomon codes beyond the error-correction bound
• Efficient decoding of Reed-Solomon codes beyond half the minimum distance
• Efficient list decoding of a class of algebraic-geometry codes
• Factoring multivariate polynomials over finite fields
• Faster Algorithms for Multivariate Interpolation With Multiplicities and Simultaneous Polynomial Approximations
• Improved decoding of Reed-Solomon and algebraic-geometry codes
• Key equations for list decoding of Reed-Solomon codes and how to solve them
• Linear Diophantine Equations Over Polynomials and Soft Decoding of Reed–Solomon Codes
• List Decoding for Binary Goppa Codes
• List decoding of Reed-Solomon codes from a Gröbner basis perspective
• Multi-trial Guruswami-Sudan decoding for generalised Reed-Solomon codes
• On Rational Interpolation-Based List-Decoding and List-Decoding Binary Goppa Codes
• On lattice reduction for polynomial matrices
• On the Average Complexity of Reed–Solomon List Decoders
• The Re-Encoding Transformation in Algebraic List-Decoding of Reed–Solomon Codes

Cited in

(4)

• Multi-trial Guruswami-Sudan decoding for generalised Reed-Solomon codes
• A modified Guruswami-Sudan algorithm for decoding Reed-Solomon codes
• A Note on the Generalisation of the Guruswami–Sudan List Decoding Algorithm to Reed–Muller Codes
• Guruswami-Sudan Decoding of Elliptic Codes Through Module Basis Reduction

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: Multi-trial Guruswami-Sudan decoding for generalised Reed-Solomon codes

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