Skip to Main content Skip to Navigation
Journal articles

Multi-Trial Guruswami--Sudan Decoding for Generalised Reed--Solomon Codes

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ötter and Vardy into our iterative algorithm.
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/hal-00975927
Contributor : Alexander Zeh <>
Submitted on : Wednesday, April 9, 2014 - 8:42:05 PM
Last modification on : Tuesday, December 17, 2019 - 10:10:03 AM
Long-term archiving on: : Wednesday, July 9, 2014 - 12:11:52 PM

Files

hal-arxiv20140409.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Johan Sebastian Rosenkilde Nielsen, Alexander Zeh. Multi-Trial Guruswami--Sudan Decoding for Generalised Reed--Solomon Codes. Designs, Codes and Cryptography, Springer Verlag, 2014, pp.1-21. ⟨10.1007/s10623-014-9951-7⟩. ⟨hal-00975927⟩

Share

Metrics

Record views

578

Files downloads

334