0.10 Wavelet-based signal processing and applications  (Page 5/13)

Fast approximate fourier transform

The basic idea of the fast approximate Fourier transform (FAFT) is pruning ; i.e., cutting off part of the diagram. Traditionally, when only part of the inputs are nonzero, or only part of the outputs are required,the part of the FFT diagram where either the inputs are zero or the outputs are undesired is pruned [link] , so that the computational complexity is reduced. However, the classical pruning algorithm is quiterestrictive, since for a majority of the applications, both the inputs and the outputs are of full length.

The structure of the DWT-based FFT algorithm can be exploited to generalize the classical pruning idea for arbitrary signals.From the input data side, the signals are made sparse by the wavelet transform [link] , [link] , [link] , [link] ; thus approximation can be made to speed up the algorithm by dropping the insignificant data. In other words, although the input signal are normally not sparse, DWT creates the sparse inputs for thebutterfly stages of the FFT. So any scheme to prune the butterfly stages for theclassical FFT can be used here. Of course, the price we have to pay here is the computational complexity of the DWT operations. In actual implementation,the wavelets in use have to be carefully chosen to balance the benefit of the pruning and the price of the transform. Clearly, the optimal choicedepends on the class of the data we would encounter.

From the transform side, since the twiddle factors of the new algorithm have decreasing magnitudes, approximation can be made to speed up thealgorithm by pruning the sections of the algorithm which correspond to the insignificant twiddle factors. The frequency response of theDaubechies' wavelets are shown in [link] . We can see that they are monotone decreasing. As the length increases, more and morepoints are close to zero. It should be noted that those filters are not designed for frequency responses. They are designed for flatness at 0 and $\pi$ . Various methods can be used to design wavelets or orthogonal filter banks [link] , [link] , [link] to achieve better frequency responses. Again, thereis a tradeoff between the good frequency response of the longer filters and the higher complexity required by the longer filters.

Computational complexity

The wavelet coefficients are mostly sparse, so the input of the shorter DFTs are sparse. If the implementation scales well with respect to thepercentage of the significant input (e.g., it uses half of the time if only half of the inputs are significant), then we can further lower the complexity.Assume for $N$ inputs, $\alpha N$ of them are significant ( $\alpha \le 1$ ), we have

For example, if $\alpha =\frac{1}{2}$ , Equation  [link] simplifies to

which leads to

So under the above conditions, we have a linear complexity approximate FFT. Of course, the complexity depends on the inputdata, the wavelets we use, the threshold value used to drop insignificant data, and the threshold value used to prune the butterfly operations. It remains to find a good tradeoff. Also the implementation would be morecomplicated than the classical FFT.