VLSI ARCHITECTURE FOR EFFICIENT COMPUTATION OF FAST FOURIER AND DISCRETE WAVELET TRANSFORMS

Abstract

This thesis proposes a novel algorithm and architecture for computing the fast Fourier transform (FFT), discrete wavelet transform (DWT), and discrete wavelet packet transform (DWPT) for continuous data flow. The data dependencies of DWT and inherent parallelism in FFT are key aspects that have been explored earlier to develop algorithms and architectures for computing DWT and bit-reversal in FFT. The bit-reversal circuits have already attained the optimum memory and circuit latency. Circuits published for multilevel DWT computation work for continuous data flow and require lesser hardware. Bit reversal is a major part of FFT computation, and thus bit reversal circuits have a considerable impact on the performance and area requirements of FFT architectures. The algorithm and circuit devised in the thesis, in particular, reorders the coefficients in the natural order for different common radices. The proposed architecture requires lesser hardware. Simultaneously, these architectures can be operated at a much higher frequency. Further, architectures suggested in the thesis can simultaneously compute bit reversal for different radices and a range of samples. The concept of bit reversal has now been extended to the multilevel decomposition of DWT and DWPT for continuous data flows. The thesis presents an efficient two-stage pipelined architecture for subband decomposition of multilevel DWT for the continuous data flow. The reordering of intermediate coefficients to form subbands helps in reducing the memory requirement by 50%, resulting in a significant reduction in area and power requirements. These subbands are used further to compute coefficients at subsequent levels. The two-stage computation developed in the thesis distributes the computational load between two stages; as such, the architecture supports a continuous flow of data from the input to the output end. On the other hand, the pipelined architecture proposed for computing DWPT for continuous data flow requires the least memory elements among existing DWPT architectures. The wavelet filter proposed for computing wavelet coefficients takes serial data and generates serial coefficients with lesser hardware. Further, this architecture has been optimized for computing DWPT for any generalized tree structure. The bypassed wavelet filter introduced in the architecture either computes or skips the incoming samples to accommodate any generalized tree structure. Control signals are generated with the help of counters only that further simplify the architecture. All the architectures suggested in this thesis are pipelined architectures and require lesser hardware for computing bit reversal or subband decomposition of wavelet transform for continuous data flow. These architectures have been implemented on a field-programmable gate array (FPGA) and simulated using Synopsys DC compiler. The result shows a significant improvement in the area, power, and operating frequency compared with existing architectures. The algorithms and architectures proposed in this thesis provide a feasible and practical solution for a wide range of signal processing applications, as well as open up new possibilities for future applications.