Index Mapping and Mixed-Radix FFTs
Eleanor Chu · 2008
In this chapter, the authors explore ways to organize the mixed-radix discrete Fourier transform (DFT) computation facilitated by index mapping via multidimensional arrays. This approach would allow to study a large number of mixed-radix fast Fourier transform (FFT) algorithms in a systematic manner, including the radix-2 special case. Index mapping plays a fundamental role in all mixed-radix algorithms efficient algorithms are developed by pairing up different index mapping schemes: one is deployed on the input data sequence, and the other one is deployed on the DFT output. The authors demonstrate how their systematic approach can be applied at once to obtain the Decimation-In-Frequency (DIF) form of the mixed-radix FFT.