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

47 Downloads (Pure)


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
Issue number3
Pages (from-to)1641-1655
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:;; Communicated by C. Xing, Associate Editor for Coding Theory. Color versions of one or more figures in this article are available at Digital Object Identifier 10.1109/TIT.2020.3042248

Publisher Copyright:
© 1963-2012 IEEE.


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


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

Cite this