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

Johan Sebastian Rosenkilde Nielsen, Alexander Zeh

Research output: Contribution to journalJournal articleResearchpeer-review

46 Downloads (Pure)

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.
Original languageEnglish
JournalDesigns, Codes and Cryptography
Volume73
Issue number2
Pages (from-to)507-527
ISSN0925-1022
DOIs
Publication statusPublished - 2014
Externally publishedYes

Keywords

  • Guruswami{Sudan
  • List Decoding
  • Multi-Trial
  • Reed{Solomon Codes
  • Re-Encoding Transformation

Fingerprint

Dive into the research topics of 'Multi-Trial Guruswami–Sudan Decoding for Generalised Reed–Solomon Codes'. Together they form a unique fingerprint.

Cite this