DWT Implementation using FFTs 2.0 2003/01/13 2003/01/13 Phil Schniter schniter@ee.eng.ohio-state.edu Charlet Reedstrom charlet@rice.edu Phil Schniter schniter@ee.eng.ohio-state.edu circular convolution DWT Finally, we say a few words about DWT implementation. Here we focus on a single DWT stage and assume circular convolution, yielding an MxM DWT matrix T M . In the general case, MxM matrix multiplication requires M 2 multiplications. The DWT matrices, however, have a circular-convolution structure which allows us to implement them using significantly less multiplies. Below we present some simple and reasonably efficient approaches for 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 circularly convolving 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 that the 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 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 and still results in major saving when M is large: it converts the O M 2 matrix multiply into an O M 2 M operation.