Pruning split-radix FFT with time shift
Longtao Yuan, Xiang Tian, Yaowu Chen · 2011
Eliminating computations on zeros when the number of nonzero inputs is considerably less than the length of Fast Fourier Transform (FFT) is considered as one of the methods to increase the computational efficiency of an FFT algorithm. This paper proposes a new split-radix FFT pruning algorithm with time shift for consecutive partial inputs. The shifting simplifies the flow graph in the first few stages of the pruning algorithm and makes the algorithm architecturally efficient. Comparisons of the computational complexity for the proposed split-radix FFT pruning algorithm with other algorithms show that the proposed method is more computationally efficient. Optimized hardware design based on this algorithm is also devised.