Fast Encoding of AG Codes over CabCurves

Peter Beelen, Johan Rosenkilde, Grigory Solomatov*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

1 Downloads (Pure)

Abstract

We investigate algorithms for encoding of one-point algebraic geometry (AG) codes over certain plane curves called C{ab} curves, as well as algorithms for inverting the encoding map, which we call 'unencoding'. Some C{ab} curves have many points or are even maximal, e.g. the Hermitian curve. Our encoding resp. unencoding algorithms have complexity tilde { mathcal {O}}(text {n}{3/2}) resp. tilde { mathcal {O}}({ittext { qn}}) for AG codes over any C{ab} curve satisfying very mild assumptions, where n is the code length and q the base field size, and tilde { mathcal {O}} ignores constants and logarithmic factors in the estimate. For codes over curves whose evaluation points lie on a grid-like structure, for example the Hermitian curve and norm-trace curves, we show that our algorithms have quasi-linear time complexity tilde { mathcal {O}}(text {n}) for both operations. For infinite families of curves whose number of points is a constant factor away from the Hasse-Weil bound, our encoding and unencoding algorithms have complexities tilde { mathcal {O}}(text {n}{5/4}) and tilde { mathcal {O}}(text {n}{3/2}) respectively.

Original languageEnglish
JournalIEEE Transactions on Information Theory
Volume67
Issue number3
Pages (from-to)1641-1655
ISSN0018-9448
DOIs
Publication statusPublished - Mar 2021

Bibliographical note

Funding Information:
Manuscript received January 14, 2020; revised August 6, 2020; accepted October 27, 2020. Date of publication December 3, 2020; date of current version February 17, 2021. This work was supported by The Danish Council for Independent Research (DFF-FNU) (the project Correcting on a Curve) under Grant 8021-00030B. (Corresponding author: Grigory Solomatov.) The authors are with the Department of Applied Mathematics and Computer Science, Technical University of Denmark, 2800 Kongens Lyngby, Denmark (e-mail: pabe@dtu.dk; jsrn@dtu.dk; gsol@dtu.dk). Communicated by C. Xing, Associate Editor for Coding Theory. Color versions of one or more figures in this article are available at https://doi.org/10.1109/TIT.2020.3042248. Digital Object Identifier 10.1109/TIT.2020.3042248

Publisher Copyright:
© 1963-2012 IEEE.

Keywords

  • AG code
  • Cab code
  • Encoding
  • Hermitian code
  • Norm-trace curve

Fingerprint Dive into the research topics of 'Fast Encoding of AG Codes over C<sub>ab</sub>Curves'. Together they form a unique fingerprint.

Cite this