Systematic Encoding of Elliptic Codes with Dynamic Information Sets

Systematic encoding is crucial in some decoding algorithms of algebraic-geometric (AG) codes. In the context of soft decoding that requires systematic encoding, the information set changes dynamically for each decoding event, presenting a challenge for systematic encoding of AG codes. This paper addresses this challenge for elliptic codes by proposing a fast construction algorithm for both the systematic encoding polynomial (SEP) and the systematic generator matrix (SGM) based on Gröbner bases of modules and backward interpolation. The proposed algorithm has a complexity of $\mathcal{O}\left( {{k^2}} \right)$ and $\mathcal{O}(kn)$ for constructing the SEP and SGM, respectively, where k and n denote the dimension and length of the elliptic code. Additionally, its computation can be highly parallelized, enhancing its implementation efficiency.