A matrix-vector based approach to FFT implementations

Today discrete Fourier transforms (DFTs) are applied in various radio standards based on OFDM (orthogonal frequency division multiplex). To achieve a high computational speed with low power consumption, specialized fast Fourier transform (FFT) engines are used in mobile devices. However, in face of the software defined radio (SDR) development, more general (parallel) processor architectures are often desirable, which are not necessarily tailored to FFT computations. Therefore, alternative approaches are required to reduce the complexity of the DFT. Starting from a matrix-vector based description of the FFT idea, we will present different factorizations of the DFT matrix, which allow a reduction of the complexity. The resulting complexity lies between the original DFT and the minimum FFT complexity. The computational complexities of these factorizations and their suitability for implementation on different processor architectures are investigated.