Skip to Main content Skip to Navigation
New interface
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 metadata

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/hal-00975927
Contributor : Alexander Zeh Connect in order to contact the contributor
Submitted on : Wednesday, April 9, 2014 - 8:42:05 PM
Last modification on : Tuesday, October 25, 2022 - 4:21:52 PM
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, 2014, pp.1-21. ⟨10.1007/s10623-014-9951-7⟩. ⟨hal-00975927⟩

Share

Metrics

Record views

230

Files downloads

90