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

DOI10.1007/S10623-014-9951-7zbMATH Open1297.94129arXiv1404.3022OpenAlexW3102517494MaRDI QIDQ398959FDOQ398959

Authors: Alexander Zeh, Johan Rosenkilde né Nielsen 

Publication date: 18 August 2014

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

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.

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

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

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)

Cites Work

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

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

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)