Back to Search
Start Over
Fast Encoding of AG Codes Over Cab Curves.
- Source :
-
IEEE Transactions on Information Theory . Mar2021, Vol. 67 Issue 32, p1641-1655. 15p. - Publication Year :
- 2021
-
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}}({\it\text { 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *PLANE curves
*ALGEBRAIC geometry
*ENCODING
*ALGEBRAIC codes
Subjects
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 67
- Issue :
- 32
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 148822587
- Full Text :
- https://doi.org/10.1109/TIT.2020.3042248