Fast algorithm and architecture for computation of the discrete wavelet transform
Sri-Krishna Aditya, Harold H Szu, Chee‐Hung Henry Chu · 1996
In this dissertation, I describe a new architecture and algorithm for computing the Discrete Wavelet Transform (DWT) of one dimensional discrete signals. The new architecture and algorithm are based on the Fast Fourier Transform (FFT). The presented scheme is nonrecursive unlike a dyadic subband decomposition. Thus, the Discrete Wavelet Transform coefficients at all resolutions are generated simultaneously, without having to wait for the generation of coefficients at a higher resolution. This new architecture is faster than existing DWT computation architectures that are based on time-domain convolvers. This architecture can be fully pipelined, and complexity of control circuits for this architecture is much lower than previously suggested systolic array architectures, which involve complex routing of data. In time-domain convolution based architectures, with a single set of convolvers, the computation of DWT for an N-point signal takes a minimum of N cycles, whereas the same computation by the new architecture, with full hardware implementation (no multiplexing of hardware) and fully pipelined, takes only a fraction of N cycles. The speed advantage is due to the use of FFT-based frequency-domain convolutions and also due to the concomitant introduction of more parallelism. Advantages gained by this method over time-domain convolvers will be more pronounced in applications where filters tend to be long. If the basis functions (in this case Wavelets) of a transformation have a large number of vanishing moments, there will be a greater number of near zero coefficients in the transformed domain, resulting in superior compression. Basis functions having large numbers of vanishing moments, lead to an increase in the length of the filters used. When long filters are used in DWT computation, the new architecture becomes particularly suitable. Also, because of the speedup in computation, it is possible to transform signals with higher sampling rates. This allows for the original analog signals to have larger bandwidths. In this dissertation, I have also reviewed fundamentals of Wavelets, Wavelet Transforms and surveyed the existing architectures for computation of Discrete Wavelet Transform for one dimensional signals.