Pruning fast Fourier transform algorithm design using group-based method

Chih‐Peng Fan

doi:10.1016/j.sigpro.2007.05.012

Return

Pruning fast Fourier transform algorithm design using group-based method

2007-11-01

PRE

Chih‐Peng Fan *

Guo-An Su

DOI：10.1016/j.sigpro.2007.05.012

Original

Original request for help

Save

Abstract

En 中文

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 priming 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. (c) 2007 Elsevier B.V. All rights reserved.

Keywords:

fast Fourier transform

pruning FFT algorithm

grouped scheme

selective transformed outputs

arithmetic complexity

data transfer cost

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.