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

Review of the discrete fourier transform and fft

The discrete Fourier transform (DFT) is defined for a length-N complex data sequence by

where we use $j=\sqrt{-1}$ . There are several ways to derive the different fast Fourier transform (FFT)algorithms. It can be done by using index mapping [link] , by matrix factorization, or by polynomial factorization. In this chapter, weonly discuss the matrix factorization approach, and only discuss the so-called radix-2 decimation in time (DIT) variant of the FFT.

Instead of repeating the derivation of the FFT algorithm, we show the block diagram and matrix factorization, in an effort to highlight the basicidea and gain some insight. The block diagram of the last stage of a length-8 radix-2 DIT FFT is shown in [link] . First, the input data are separated into even and odd groups. Then, each group goes through alength-4 DFT block. Finally, butterfly operations are used to combine the shorter DFTs into longer DFTs.

The details of the butterfly operations are shown in [link] , where $W_N^i=e^{-j2\pi i/N}$ is called the twiddle factor . All the twiddle factors are of magnitude one on the unit circle. This is the main reason that there is nocomplexity versus accuracy tradeoff for the classical FFT. Suppose some of the twiddle factors had very small magnitude,then the corresponding branches of the butterfly operations could be dropped (pruned) to reducecomplexity while minimizing the error to be introduced. Of course the error also depends on the value of the data to be multiplied with the twiddlefactors. When the value of the data is unknown, the best way is to cutoff the branches with small twiddle factors.

The computational complexity of the FFT algorithm can be easily established. If we let $C_{FFT}\left(N\right)$ be the complexity for a length-N FFT, we can show

where $O\left(N\right)$ denotes linear complexity. The solution to Equation  [link] is well known:

This is a classical case where the divide and conquer approach results in very effective solution.

The matrix point of view gives us additional insight. Let ${\mathbf{F}}_N$ be the $N\times N$ DFT matrix; i.e., ${\mathbf{F}}_N(m,n)=e^{-j2\pi mn/N}$ , where $m,n\in \{0,1,...,N-1\}$ . Let ${\mathbf{S}}_N$ be the $N\times N$ even-odd separation matrix; e.g.,

Clearly ${\mathbf{S}}_N^{\text{'}}{\mathbf{S}}_N={\mathbf{I}}_N$ , where ${\mathbf{I}}_N$ is the $N\times N$ identity matrix. Then the DIT FFT is based on the following matrix factorization,

where ${\mathbf{T}}_{N/2}$ is a diagonal matrix with $W_N^i$ , $i\in \{0,1,...,N/2-1\}$ on the diagonal. We can visualize the above factorization as

where we image the real part of DFT matrices, and the magnitude of the matrices for butterfly operations and even-odd separations. $N$ is taken to be 128 here.

Review of the discrete wavelet transform

In this section, we briefly review the fundamentals of the discrete wavelet transform and introduce the necessary notation for future sections. Thedetails of the DWT have been covered in other chapters.

At the heart of the discrete wavelet transform are a pair of filters $\mathbf{h}$ and $\mathbf{g}$ — lowpass and highpass respectively. They have to satisfy a set of constraints Figure: Sinc Scaling Function and Wavelet [link] , [link] , [link] . The block diagram of the DWT is shown in [link] . The input data are first filtered by $\mathbf{h}$ and $\mathbf{g}$ then downsampled. The same building block is further iterated on the lowpass outputs.