0.3 Filter banks and the discrete wavelet transform  (Page 6/6)

An alternative formulation that can be applied to finite duration signals or periodic signals (much as the Fourier series) is to make all of thefilter bank filters cyclic or periodic convolution which is defined by

for $n,\ell =0,1,\cdots ,N-1$ and all indices and arguments are evaluated modulo $N$ . For a length $N$ input at scale $j=J$ , we have after one stage two length $N/2$ sequences, after two stages, one length $N/2$ and two length $N/4$ sequences, and so on. If $N=2^J$ , this can be repeated $J$ times with the last stage being length one; one scaling function coefficient and onewavelet coefficient. An example of how the periodic DWT of a length 8 can be seen [link] .

The details of this periodic approach are developed in Chapter: Calculation of the Discrete Wavelet Transform showing the aliasing that takes place in this system because of the cyclic convolution [link] . This formulation is particularly clean because there are the same number of terms in the transform asin the signal. It can be represented by a square matrix with a simple inverse that has interesting structure. It can be efficiently calculatedby an FFT although that is not needed for most applications.

For most of the theoretical developments or for conceptual purposes, there is little difference in these two formulations. However, for actualcalculations and in applications, you should make sure you know which one you want or which one your software package calculates. As for the Fouriercase, you can use the periodic form to calculate the nonperiodic transform by padding the signal with zeros but that wastes some of the efficiencythat the periodic formulation was set up to provide.

The discrete wavelet transform versus the discrete-time wavelet transform

Two more points of view concern looking at the signal processing methods in this book as based on an expansion of a signal or on multiratedigital filtering. One can look at Mallat's algorithm either as a way of calculating expansion coefficients at various scales or as a filterbank for processing discrete-time signals. The first is analogous to useof the Fourier series (FS) where a continuous function is transformed into a discrete sequence of coefficients. The second is analogous to thediscrete Fourier transform (DFT) where a discrete function is transformed into a discrete function. Indeed, the DFT (through the FFT) is often usedto calculate the Fourier series coefficients, but care must be taken to avoid or minimize aliasing. The difference in these views comes partlyfrom the background of the various researchers (i.e., whether they are “wavelet people" or “filter bank people"). However, there are subtledifferences between using the series expansion of the signal (using the discrete wavelet transform (DWT)) and using a multirate digital filterbank on samples of the signal (using the discrete-time wavelet transform (DTWT)). Generally, using both views gives more insight into a problemthan either achieves alone. The series expansion is the main approach of this book but filter banks and the DTWT are also developed in  Section: Discrete Multiresolution Analysis and the Discrete-Time wavelet Transform and Chapter: Filter Banks and Transmultiplexers .

Numerical complexity of the discrete wavelet transform

Analysis of the number of mathematical operations (floating-point multiplications and additions) shows that calculating the DTWT of alength- $N$ sequence of numbers using Mallat's algorithm with filter banks requires $O\left(N\right)$ operations. In other words, the number of operations is linear with the length of the signal. What is more, the constant oflinearity is relatively small. This is in contrast to the FFT algorithm for calculating the DFT where the complexity is $O(Nlog(N\left)\right)$ or calculating a DFT directly requires $O\left(N^2\right)$ operations. It is often said that the FFT algorithm is based on a “divide and conquer" scheme, but thatis misleading. The process is better described as a “organize and share" scheme. The efficiency (in fact, optimal efficiency) is based onorganizing the calculations so that redundant operations can be shared. The cascaded filtering (convolution) and down-sampling of Mallat'salgorithm do the same thing.

One should not make too much of this difference between the complexity of the FFT and DTWT. It comes from the DTWT having a logarithmic division offrequency bands and the FFT having a uniform division. This logarithmic scale is appropriate for many signals but if a uniform division is usedfor the wavelet system such as is done for wavelet packets (see Section: Wavelet Packets ) or the redundant DWT (see  Section: Overcomplete Representations, Frames, Redundant Transforms, and Adaptive Bases ), the complexity of the wavelet system becomes $O(Nlog(N\left)\right)$ .

If you are interested in more details of the discrete wavelet transform and the discrete-time wavelet transform, relations between them,methods of calculating them, further properties of them, or examples, see Section: Discrete Multiresolution Analysis, the Discrete-Time Wavelet and Chapter: Calculation of the Discrete Wavelet Transform .