12.14 Dwt implementation using ffts

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^T$ .

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)

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

Next we treat the forward DWT. Recall that in the lowpass analysis branch, we circularly convolve the input with $H(z^{(-1)})$ 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^{(-1)})$ . 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\log_{2}M)$ operation.