Faster List Decoding of AG Codes - Sorbonne Université
Pré-Publication, Document De Travail Année : 2023

Faster List Decoding of AG Codes

Résumé

In this article, we present a fast algorithm performing an instance of the Guruswami-Sudan list decoder for algebraic geometry codes. We show that any such code can be decoded in $\tilde{O}(s^2\ell^{\omega-1}\mu^{\omega-1}(n+g) + \ell^\omega \mu^\omega)$ operations in the underlying finite field, where $n$ is the code length, $g$ is the genus of the function field used to construct the code, $s$ is the multiplicity parameter, $\ell$ is the designed list size and $\mu$ is the smallest positive element in the Weierstrass semigroup of some chosen place.
Fichier principal
Vignette du fichier
ag-decoding-faster.pdf (639.63 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Licence

Dates et versions

hal-04069465 , version 1 (14-04-2023)

Licence

Identifiants

  • HAL Id : hal-04069465 , version 1

Citer

Peter Beelen, Vincent Neiger. Faster List Decoding of AG Codes. 2023. ⟨hal-04069465⟩
58 Consultations
48 Téléchargements

Partager

More