Computing the Scaling Function: The Cascade Algorithm 2.5 2002/02/01 2005/09/20 15:43:10.603 GMT-5 Phil Schniter schniter@ee.eng.ohio-state.edu Charlet Reedstrom charlet@rice.edu Phil Schniter schniter@ee.eng.ohio-state.edu cascade algorithm DWT Scaling function wavelet This module shows how to compute the scaling function. It also has a section with a proof for an assumption made for the computation. Given coefficients h n that satisfy the regularity conditions, we can iteratively calculate samples of φ t on a fine grid of points t using the cascade algorithm. Once we have obtained φ t , the wavelet scaling equation can be used to construct ψ t . In this discussion we assume that H z is causal with impulse response length N. Recall, from our discussion of the regularity conditions, that this implies φ t will have compact support on the interval 0 N 1 . The cascade algorithm is described below. Consider the scaling function at integer times t m 0 … N 1 : φ m 2 n 0 N 1 h n φ 2 m n Knowing that φ t 0 for t 0 N 1 , the previous equation can be written using an NxN matrix. In the case where N 4 , we have φ 0 φ 1 φ 2 φ 3 2 h 0 0 0 0 h 2 h 1 h 0 0 0 h 3 h 2 h 1 0 0 0 h 3 φ 0 φ 1 φ 2 φ 3 where H h 0 0 0 0 h 2 h 1 h 0 0 0 h 3 h 2 h 1 0 0 0 h 3 The matrix H is structured as a row-decimated convolution matrix. From the matrix equation above (), we see that φ 0 φ 1 φ 2 φ 3 must be (some scaled version of) the eigenvector of H corresponding to eigenvalue 2 -1 . In general, the nonzero values of φ n n , i.e., φ 0 φ 1 … φ N 1 , can be calculated by appropriately scaling the eigenvector of the NxN row-decimated convolution matrix H corresponding to the eigenvalue 2 -1 . It can be shown that this eigenvector must be scaled so that n 0 N 1 φ n 1 . Given φ n n , we can use the scaling equation to determine φ n 2 n : φ m 2 2 n 0 N 1 h n φ m 2 n This produces the 2 N 1 non-zero samples φ 0 φ 12 φ 1 φ 32 … φ N 1 . Given φ n 2 n , the scaling equation can be used to find φ n 4 n : φ m 4 2 n 0 N 1 h n φ m 2 n 2 p p even h p 2 φ m p 2 2 p p h ↑ 2 p φ 1 2 m p where h ↑ 2 p denotes the impulse response of H z 2 , i.e., a 2-upsampled version of h n , and where φ 1 2 m φ m 2 . Note that φ n 4 n is the result of convolving h ↑ 2 n with φ 1 2 n . Given φ n 4 n , another convolution yields φ n 8 n : φ m 8 2 n 0 N 1 h n φ m 4 n 2 p p h ↑ 4 p φ 1 4 m p where h ↑ 4 n is a 4-upsampled version of h n and where φ 1 4 m φ m 4 . At the ℓ th stage, φ n 2 ℓ is calculated by convolving the result of the ℓ − 1 th stage with a 2 ℓ 1 -upsampled version of h n : φ 1 2 ℓ m 2 p p h ↑ 2 ℓ − 1 p φ 1 2 ℓ − 1 m p For ℓ 10 , this gives a very good approximation of φ t . At this point, you could verify the key properties of φ t , such as orthonormality and the satisfaction of the scaling equation. In we show steps 1 through 5 of the cascade algorithm, as well as step 10, using Daubechies' db2 coefficients (for which N 4 ).