0.9 Calculation of the discrete wavelet transform  (Page 3/5)

Periodic or cyclic discrete wavelet transform

If $f\left(t\right)$ has finite support, create a periodic version of it by

where the period $P$ is an integer. In this case, $⟨f,{\phi }_{j,k}⟩$ and $⟨f,{\psi }_{j,k}⟩$ are periodic sequences in $k$ with period $P{2}^j$ (if $j\ge 0$ and 1 if $j<0$ ) and

where $\ell =<k{>}_{P{2}^j}$ ( $k$ modulo $P{2}^j$ ) and $l\in \{0,1,...,P{2}^j-1\}$ . An obvious choice for $J_0$ is 1. Notice that in this case given $L=2^{J_1}$ samples of the signal, $⟨f,{\phi }_{J_1,k}⟩$ , the wavelet transform has exactly $1+1+2+2^2+\cdots +2^{J_1-1}=2^{J_1}=L$ terms. Indeed, this gives a linear, invertible discrete transform which can be considered apart fromany underlying continuous process similar the discrete Fourier transform existing apart from the Fourier transform or series.

There are at least three ways to calculate this cyclic DWT and they are based on the equations [link] , [link] , and [link] later in this chapter. The first method simply convolves the scalingcoefficients at one scale with the time-reversed coefficients $h(-n)$ to give an $L+N-1$ length sequence. This is aliased or wrapped as indicated in [link] and programmed in dwt5.m in Appendix 3. The second method creates a periodic ${\tilde{c}}_j\left(k\right)$ by concatenating an appropriate number of $c_j\left(k\right)$ sections together then convolving $h\left(n\right)$ with it. That is illustrated in [link] and in dwt.m in Appendix 3. The third approach constructs a periodic $\tilde{h}\left(n\right)$ and convolves it with $c_j\left(k\right)$ to implement [link] . The Matlab programs should be studied to understand how these ideas are actually implemented.

Because the DWT is not shift-invariant, different implementations of the DWT may appear to give different results because of shifts of the signaland/or basis functions. It is interesting to take a test signal and compare the DWT of it with different circular shifts of the signal.

Making $f\left(t\right)$ periodic can introduce discontinuities at 0 and $P$ . To avoid this, there are several alternative constructions of orthonormalbases for $L^2[0,P]$ [link] , [link] , [link] , [link] . All of these constructions use (directly or indirectly) the concept of time-varyingfilter banks. The basic idea in all these constructions is to retain basis functions with support in $[0,P]$ , remove ones with support outside $[0,P]$ and replace the basis functions that overlap across the endpoints with special entry/exit functions that ensure completeness . These boundary functions are chosen so that the constructed basis isorthonormal. This is discussed in Section: Time-Varying Filter Bank Trees . Another way to deal with edges or boundaries uses “lifting" as mentioned in Section: Lattices and Lifting .

Filter bank structures for calculation of the dwt and complexity

Given that the wavelet analysis of a signal has been posed in terms of the finite expansion of [link] , the discrete wavelet transform (expansion coefficients) can be calculated using Mallat's algorithm implemented by afilter bank as described in Chapter: Filter Banks and the Discrete Wavelet Transform and expanded upon in   Chapter: Filter Banks and Transmultiplexers . Using the direct calculations described by the one-sided tree structure of filters and down-samplers in Figure: Three-Stage Two-Band Analysis Tree allows a simple determination of the computational complexity.