Hardware-Efficient Index Mapping for Mixed Radix-2/3/4/5 FFTs

Abstract

Orthogonal frequency-division multiplexing modulators and demodulators for modern communication standards require efficient implementation of the fast Fourier transform (FFT). Traditionally, radix-2 and radix-4 FFT algorithms have been used. Over the last few years, support for the non-power-of-two transform sizes, with the emphasis on radix-3 and radix-5, started to become a standard. We have created a systematic approach for designing simple digital circuits that compute array access indices for the mixed radix-2/3/4/5 FFT computations. Proposed index mapping, allows for the use of a bit rotation instead of the add/modulo and multiply operations. Index generation circuits, implementing the proposed index mapping, have hardware complexity comparable to index generation circuits for power-of-two FFTs.