Time-frequency distributions: Complexity, algorithms and architectures

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.