Hardware-Efficient Twiddle Factor Generator for Mixed-Radix-2/3/4/5 FFTs

Abstract

Twiddle factors are an integral part of FFT computations. Conventionally, they are either computed in run-time, hence increasing computational complexity, or pre-calculated and stored in RAM memory, which requires large memory footprint and increases power consumption. We created a systematic approach for designing digital circuits that generate twiddle factors based on reduced ROM tables. The approach supports radix-2, radix-3, radix-4, radix-5, and mixed radix-2/3/4/5 algorithms and several transform lengths. Number of complex twiddle factors stored in the memory equals only ⌊Nmax/8 ⌋ + 1 for transform lengths up to Nmax.