Preprint article · Journal article
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.
Language: | English |
---|---|
Publisher: | Springer US |
Year: | 2014 |
Pages: | 507-527 |
Journal subtitle: | An International Journal |
ISSN: | 15737586 and 09251022 |
Types: | Preprint article and Journal article |
DOI: | 10.1007/s10623-014-9951-7 |
Coding and Information Theory Combinatorics Data Encryption Data Structures, Cryptology and Information Theory Discrete Mathematics in Computer Science Guruswami–Sudan Information and Communication, Circuits List decoding Mathematics Mathematics and Statistics Multi-trial Re-encoding transformation Reed–Solomon codes cs.IT math.IT