A novel generic fast Fourier transform pruning technique and complexity analysis

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_in input or/and k_out output bins of an N point FFT, where k_in≤N, or/and k_out≤N are required. This method is then extended to arbitrary radix FFT pruning and simultaneous input and output pruning case.