Pruning fast Fourier transform algorithm design using group-based method

摘要

In this paper, we propose the grouped scheme, which can be specially applied to compute the pruning fast Fourier transform (pruning FFT) with power-of-two partial transformation length. The group-based pruning FFT algorithm applies the scheme of the grouped frequency indices to accelerate computations of selected discrete Fourier transform (DFT) outputs. The proposed pruning FFT algorithm has fewer complex multiplications than the other pruning FFT algorithms when the number of the partial transformed outputs is equal to or larger than 1/16 total FFT transform length. Whereas the number of the partial transformed outputs is equal to or smaller than 1/32 total FFT transform length, the arithmetic complexity of the proposed algorithm will be larger than the other pruning FFTs. To compute all transformed outputs of the DFT, the multiplication complexities of the proposed pruning FFT method are fewer than those of the radix-2 method. Meanwhile, the multiplication complexities of the proposed fast method approximate to those of the radix-4 FFT algorithm with the power-of-four length. For the comparison of data transfer costs in the pruning FFT cases, the proposed pruning FFT algorithm has smaller data transfer costs than the other pruning FFT algorithms when the number of the partial transformed outputs is equal to or larger than 1/4 total FFT transform length. By sharing coefficients of the twiddle factors in the same frequency group and using the radix-2 FFT scheme, the proposed pruning FFT algorithm can be implemented with properties of sharing hardware and regular structures.