<< Chapter < Page Chapter >> Page >

Finally, we say a few words about DWT implementation. Here we focus on a single DWT stage and assume circularconvolution, yielding an M x M DWT matrix T M . In the general case, M x M matrix multiplication requires M 2 multiplications. The DWT matrices, however, have a circular-convolution structure which allows us toimplement them using significantly less multiplies. Below we present some simple and reasonably efficient approachesfor the implementation of T M and T M .

We treat the inverse DWT first. Recall that in the lowpass synthesis branch, we upsample the input before circularlyconvolving with H z . Denoting the upsampled coefficient sequence by a n , fast circular convolution a n h n can be described as follows (using Matlab notation)

ifft( fft(a).*fft(h,length(a)) )

where we have assumed that length(a)≥length(h) .

When implementing the multi-level transform, you must ensure thatthe data length does not become shorter than the filter length!
The highpass branch is handled similarly using G z , after which the two branch outputs are summed.

Next we treat the forward DWT. Recall that in the lowpass analysis branch, we circularly convolve the input with H z and then downsample the result. The fast circular convolution a n h n can be implemented using

wshift('1', ifft(fft(a).*fft(flipud(h),length(a))), length(h)-1 )

where wshift accomplishes a circular shift of the ifft output that makes up for the unwanted delay of length(h)-1 samples imposed by the flipud operation. The highpass branch is handled similarly but with filter G z . Finally, each branch is downsampled by factor two.

We note that the proposed approach is not totally efficient because downsampling is performed after circular convolution(and upsampling before circular convolution). Still, we have outlined this approach because it is easy to understand andstill results in major saving when M is large: it converts the O M 2 matrix multiply into an O M 2 logbase --> M operation.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Digital signal processing (ohio state ee700). OpenStax CNX. Jan 22, 2004 Download for free at http://cnx.org/content/col10144/1.8
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Digital signal processing (ohio state ee700)' conversation and receive update notifications?

Ask