Towards a Flexible Hardware Implementation for Mixed-Radix Fourier Transforms

The discrete Fourier transform is a versatile math-ematical kernel widely used in a myriad of applications from physics, chemistry, and even machine learning. While most applications typically rely on power of two sizes for which high performance implementations have been developed as software libraries or custom hardware IPs, there are codes in chemistry or even machine learning that require non-power of two or even prime-sized Fourier transforms. Classic prime-sized Fourier transform implementations are more complicated and less per-formant both in software and in hardware compared to the power of two implementations. Recent work [1] has shown that casting small prime-sized Fourier transforms as specialized matrix operations, competitive codelets can be developed on CPU platforms. In this work, we focus on designing the corresponding hardware unit for prime-sized Fourier transforms and integrating the custom design within any mixed-radix Fourier transform. We provide a detailed analysis of the design and investigate the latency, throughput, and resource utilization on Xilinx FPGAs for the both standalone and mixed-radix designs. We show that even oddly shaped Fourier transforms can be appealing when building custom hardware designs for general size Fourier transforms.