Prime factor cyclotomic Fourier transforms with reduced complexity over finite fields

摘要

Discrete Fourier transforms (DFTs) over finite fields have widespread applications in various communication and storage systems. Hence reducing the computational complexities of DFTs is of great significance. Recently proposed cyclo-tomic fast Fourier transforms (CFFTs) are promising due to their low multiplicative complexities. Unfortunately, they have very high additive complexities. Techniques such as common subexpression elimination (CSE) can be used to reduce the additive complexities of CFFTs, but their effectiveness for long DFTs is limited by their complexities. In this paper, we propose prime factor cyclotomic Fourier transforms (PFCFTs), which use CFFTs as sub-DFTs via the prime factor algorithm. When the length has co-prime factors, the short lengths of the sub-DFTs allow us to use CSE to significantly reduce their additive complexities. In comparison to previously proposed fast Fourier transforms, our PFCFTs achieve reduced overall complexities when the lengths of DFTs are at least 255, and the improvement significantly increases as the length grows. This approach enables us to propose the first efficient DFTs with very long length (e.g., 4095-point) in the literature. Finally, our PFCFTs are also advantageous for hardware implementation due to their regular structure.