PPT based fast architecture & algorithm for discrete wavelet transforms
A non recursive (unlike classical dyadic decomposition) and Fast Fourier Transform based architecture for computing Discrete Wavelet Transforms (DWT) of a one dimensional sequence is presented. DWT coefficients at all resolutions can be generated simultaneously without waiting for generation of coefficients at a lower octave level. This architecture is faster than architechlres proposed so far [l] for DWT decomposition (which are implementations based on recursion) and can be fully pipelined. Complexity of control circuits for this architecture is much lower as compared to implementation of recursive methods. Now consider computation of DWT (four octaves) of a sequence. Recursive dyadic decomposition can be converted to non recursive method as shown in the figure. We can move all the decimators shown to the extreme right (towards output end) and have a single filter and a single decimator in each path. we note that a decimator (of factor k) when so moved across a filter of length L will increase the length of the filter by a factor of k Thus we will get first octave DWT coefficients by convolving input sequence with a filter of length L and decimating the output by a factor of 2. Second octave coefficients are generated by convolving input sequence with a filter of length 3L and decimating the outpul by a factor of 4. 3rd and 4th octaves are got by convolving with filters of length 7L and decimating by a factor of 8. Now all the convolutions can be done in frequency domain by overlap save method, for example. Input is divided into overlapping (with a overlap of L) blocks of length N1 = 2JL where j is the maximum octave generated (4 here). DFT coefficients of the input sequence block is computed by any of the FFT algorithm implementation and multiplied with precomputed DFT coefficients of all the four filter blocks. First L results of each of these block outputs are discarded. ( N I -L ) length IDFTs of each of these block outputs are found and each of the resulting block outputs are decimated, by appropriate factors. For example to generate first octave DWT, the corresponding output from the convolver is decimated by a factor of 2 etc., Note that decimation does not involve any hardware. Hardware complexity of the whole scheme is O(NlZogN1) i.e, 0 [ (J + L)2JL], whereas the recursive implementations have a complexity of only O(L) (this is without considering overhead due to maintenance of intermediate result queues). The new architecture is faster than recursive methods by an order of O(23L)