We investigate algorithms for encoding of one-point algebraic geometry (AG) codes over certain plane curves called c-abcurves, as well as algorithms for inverting the encoding map, which we call "unencoding"...
详细信息
We investigate algorithms for encoding of one-point algebraic geometry (AG) codes over certain plane curves called c-abcurves, as well as algorithms for inverting the encoding map, which we call "unencoding". Some c-abcurves have many points or are even maximal, e.g. the Hermitian curve. Our encoding resp. unencoding algorithms have complexity (O) over tilde (n(3/2)) resp. (O) over tilde (qn) for AG codes over any c-abcurve satisfying very mild assumptions, where n is the code length and q the base field size, and (O) over tilde 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 (O) over tilde (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 (O) over tilde (n(5/4)) and (O) over tilde (n(3/2)) respectively.
暂无评论