Encoding of Algebraic Geometry Codes With Quasi-Linear Complexity O(NlogN)
Songsong Li, Shu Liu, Liming Ma, Yunqi Wan, Chaoping Xing · IEEE Transactions on Information Theory · 2025
Fast encoding and decoding of codes have always been an important topic in coding theory as well as complexity theory. Although encoding is easier than decoding in general, designing an encoding algorithm of codes of lengthNwith quasi-linear complexityO(NlogN) is not an easy task. Despite of the fact that algebraic geometry codes (AG codes) were discovered in the early 1980s, encoding algorithms of algebraic geometry codes with quasi-linear complexityO(NlogN) have not been found except for the simplest algebraic geometry codes–Reed-Solomon codes. The best-known encoding algorithm of algebraic geometry codes based on a class of plane curves has quasi-linear complexity at leastO(Nlog2N) (Beelen et al. IEEE Trans. Inf. Theory 2021). In this paper, we design an encoding algorithm for algebraic geometry codes with quasi-linear complexityO(NlogN). Moreover, for these fast encodable AG codes, the inverse of encoding, that is, interpolating the message function from the corresponding codeword, can be computed with the same complexityO(NlogN). Our algorithms are applicable to a large class of algebraic geometry codes based on both plane and non-plane curves, including Kummer extensions, Artin-Schreier extensions, and Hermitian field towers.