A novel generic fast Fourier transform pruning technique and complexity analysis

Abstract

The fast Fourier transform (FFT) is an essential tool in digital signal processing and communications. In the applications of the FFT where the required outputs are very sparse, for example, in digital filtering, one may only require the spectrum corresponding to certain bins of the FFT or in narrow frequency windows. In these cases, most of the FFT outputs are not required. Some pruning algorithms have been proposed to deal with such cases. However, most of the pruning algorithms require that the outputs be in continuous windows. This paper develops a traced FFT Pruning method (TFFTP), which is a novel technique and does not require this condition. Under some circumstances, considerable savings in computational complexity and power consumption can be realized using the TFFTP compared to the FFT. This paper derives the average number of butterflies that need to be executed when only k/sub in/ input or/and k/sub out/ output bins of an N point FFT, where k/sub in//spl les/N, or/and k/sub out//spl les/N are required. This method is then extended to arbitrary radix FFT pruning and simultaneous input and output pruning case.