A split-radix partial input/output fast Fourier transform algorithm

摘要

A fast discrete Fourier transform (DFT) computing algorithm used in situations where part of the data is zero and only the first transform elements are to be calculated is proposed. The method is based on the pruning of a split-radix decimation-time (DIT) fast Fourier transform (FFT) diagram. It has the advantage of providing gains as a result of pruning computation and the use of a split radix.