Fast Encoding of Hermitian Codes Based on Lin-Chung-Han Fast Fourier Transform
Suihua Cai, Chao Chen, Yunqi Wan, Xiao Ma · 2023
In this paper, we present fast encoding algorithms for Hermitian codes based on the Lin-Chung-Han fast Fourier transform (LCH-FFT). For non-systematic encoding, we extend the LCH basis to the bivariate polynomial space and develop a two-dimensional FFT algorithm. For systematic encoding, we propose a modified partial FFT algorithm and present a procedure for computing the unknown intermediates. For a Hermitian code of length $n$, the computational complexity of the presented non-systematic and systematic encoding algorithms are both $O(n{\text{log}}n)$, improving upon the currently best-known encoding complexity $O\left( {n{\text{lo}}{{\text{g}}^2}n{\text{loglog}}n} \right)$.