Subband DFT-interpretation, accuracy, and computational complexity

Abstract

A detailed analysis of a newly proposed fast Fourier transform (FFT) type algorithm is presented. Several variants are introduced in the form of signal-flow graph (SFG) descriptions. The main characteristic of the approach is the frequency-separation property of the subsequences involved in the decomposition process. A novel filter-bank interpretation of the procedure is presented, allowing understanding of the errors occurring in the method's use for an appropriate partial-band transform. These errors are studied in depth to obtain general formulas describing their nature, whatever the number and type of decomposition stages might be. The computational complexity of the algorithm is analyzed both theoretically and in terms of running-time measurements. With these insights, the novel algorithm is compared to existing methods especially for the computation of a limited number of frequency points. Previously reported complexity estimates are refined and extended.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>