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

Approximate fft using the discrete wavelet transform

In this section, we give an example of wavelet domain signal processing. Rather than computing the DFT from the time domain signal using the FFTalgorithm, we will first transform the signal into the wavelet domain, then calculate the FFT, and finally go back to the signal domain which isnow the Fourier domain.

Most methods of approximately calculating the discrete Fourier transform (DFT) involve calculating only a few output points (pruning), using asmall number of bits to represent the various calculations, or approximating the kernel, perhaps by using cordic methods. Here we usethe characteristics of the signal being transformed to reduce the amount of arithmetic. Since the wavelet transform concentrates the energy ofmany classes of signals onto a small number of wavelet coefficients, this can be used to improve the efficiency of the DFT [link] , [link] , [link] , [link] and convolution [link] .

Introduction

The DFT is probably the most important computational tool in signal processing. Because of the characteristics ofthe basis functions, the DFT hasenormous capacity for the improvement of its arithmetic efficiency [link] . The classical Cooley-Tukey fast Fourier transform (FFT) algorithm has thecomplexity of $O\left(N{log}_{2}N\right)$ . Thus the Fourier transform and its fast algorithm, the FFT, are widelyused in many areas, including signal processing and numerical analysis. Any scheme to speed up the FFT would be very desirable.

Although the FFT has been studied extensively, there are still some desired properties that are not provided by the classical FFT. Here are some of thedisadvantages of the FFT algorithm:

1. Pruning is not easy. When the number of input points or outputpoints are small compared to the length of the DWT, a special technique called pruning [link] is often used. However, this often requires that the nonzero input data are groupedtogether. Classical FFT pruning algorithms do not work well when the few nonzero inputs are randomly located. In other words, a sparse signalmay not necessarily give rise to faster algorithm.
2. No speed versus accuracy tradeoff. It is common to have a situation where some error would be allowed ifthere could be a significant increase in speed. However, this is not easy with the classical FFTalgorithm. One of the main reasons is that the twiddle factors in the butterfly operations are unit magnitude complex numbers. Soall parts of the FFT structure are of equal importance. It is hard to decide which part of the FFT structure to omit when error is allowed andthe speed is crucial. In other words, the FFT is a single speed and single accuracy algorithm.
3. No built-in noise reduction capacity. Many real world signals are noisy. What people are really interested inare the DFT of the signals without the noise. The classical FFT algorithm does not have built-in noise reduction capacity. Even if other denoisingalgorithms are used, the FFT requires the same computational complexity on the denoised signal. Due to the above mentioned shortcomings, the factthat the signal has been denoised cannot be easily used to speed up the FFT.