Encoding of non-binary quasi-cyclic codes by Lin-Chung-Han transform

Recently, Lin, Chung, and Han presented an efficient additive fast Fourier transform based on a novel polynomial basis. This paper explains clearly and proves the convolution theorem of Lin-Chung-Han (LCH) transform. It demonstrates that the corresponding convolutions of LCH transform can be equivalent to cyclic convolutions by preprocessed modulo and polynomial bases conversion. As a result, this paper proposes a fast algorithm for the multiplication of a vector and a circulant matrix. It shows that the algorithm performs very efficient for the encoding of nonbinary quasi-cyclic codes. For an (ne, ke) quasi-cyclic code with circulant size of e, the encoding algorithm needs approximately ₄¹ n(e + 1) log²₂(e + 1) + k(n − k)(e + 1) multiplications and additions, which is much less than the number (n − k)ke² of traditional encoding algorithm.