Time-frequency distributions: complexity, algorithms and architectures
Mohan Vishwanath · 1993
The inherent limitations of Fourier analysis coupled with some exciting new developments (Wavelet Transforms) and the increasing speed and availability of computers have resulted in a large amount of research being done with Time-Frequency Distributions (TFD), in the past decade. This activity has not been complemented by research in VLSI architectures and algorithms for TFDs. In this thesis lower bounds of the communication complexity and multiplicative complexity of a large range of TFDs are derived. The TFDs considered vary from the Discrete Short Time Fourier Transform, Discrete Wigner-Ville Distribution to the Discrete Wavelet Transform(DWT). A new algorithm for the DWT, the Recursive Pyramid Algorithm (RPA), is presented next. The RPA computes the DWT in a running fashion, using a very small amount of storage. The RPA maps in an elegant and efficient manner onto regular architectures. VLSI architectures for both the 1-D and the 2-D DWT are designed. Most of these architectures compute the RPA. The architectures are optimal under the word-serial I/O protocol. All the architectures are regular and easily scaled. Hidden Markov Model (HMM) based speech recognition systems have a very compute and communication intensive training phase. Fast VLSI architectures are designed for training both the implicit and explicit duration HMM speech recognizer. The Arithmetic Cube II is a Signal Processing board built by the VLSI/CAD Group at Penn State. Error analysis and the performance of various algorithms on this board are also presented in this thesis.