Fast Decoding of AG Codes

Peter Beelen, Johan Rosenkilde, Grigory Solomatov

Research output: Contribution to journalJournal articleResearchpeer-review

81 Downloads (Pure)

Abstract

We present an efficient list decoding algorithm in the style of Guruswami-Sudan for algebraic geometry codes. Our decoder can decode any such code using Õ(slw μw-1(n + g)) 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, l is the designed list size and μ is the smallest positive element in the Weierstrass semigroup at some chosen place; the “soft-O” notation Õ(∙) is similar to the “big-O” notation O(∙), but ignores logarithmic factors. For the interpolation step, which constitutes the computational bottleneck of our approach, we use known algorithms for univariate polynomial matrices, while the root-finding step is solved using existing algorithms for root-finding over univariate power series.
Original languageEnglish
JournalIEEE Transactions on Information Theory
Volume68
Issue number11
Pages (from-to)7215-7232
ISSN0018-9448
DOIs
Publication statusPublished - 2022

Keywords

  • Algebraic Geometry Codes
  • Codes
  • Complexity theory
  • Computer science
  • Costs
  • Decoding
  • Geometry
  • Interpolation

Fingerprint

Dive into the research topics of 'Fast Decoding of AG Codes'. Together they form a unique fingerprint.

Cite this