An Architectural Framework for VLSI Time-Recursive Computation with Applications

Abstract

The time-recursive computation model has been proven as a particularly useful tool in audio, video, radar and sonar real- time data processing architectures. Unlike the FFT based architectures, the time-recursive ones require only local communication, they imply linear implementation cost and they operate in a single-input multiple-output (SIMO) manner. This is appropriate for the above applications since the data are supplied serially. Also, the time-recursive architectures are modular and regular and they allow high degree of parallelism; thus they are very appropriate for VLSI implementation.<P>In this dissertation, we establish an architectural framework for parallel time-recursive computation. We consider a class of linear operators (or signal transformers) that are characterized by discrete time, time invariant, compactly supported, but otherwise arbitrary kernel functions. We specify the properties of linear operators that can be implemented efficiently in a time-recursive way. Based on these properties, we develop a systematic routine that produces a time-recursive architectural implementation for a given operator. We demonstrate the use and effectiveness of this routine by means of specific examples, namely the Discrete Cosine Transform (DCT), the Discrete Fourier Transform (DFT) and the Discrete Wavelet Transform (DWT).<P>By using this architectural framework we obtain novel architectures for the uniform-DFT QMF bank, the cosine modulated QMF bank, the 1-D and 2-D Modulated Lapped Transform (MLT), as well as an Extended Lapped Transform (ELT). Furthermore, the architectural implementation of the Cepstral Transform and a Short Time Fourier Transform are considered based on the time-recursive architecture of the DFT. All of the above designs are modular, regular, with local communication and linear cost in operator counts. In particular, the 1-D MLT requires 1N + 3 adders and N - 1 rotation circuits, where N denotes the data block size. The 2-D MLT requires 3 1-D MLT circuits and no matrix transposition. The ELT has basis length equal to 4N and it requires 3N + 4 multipliers, 4N + 4 adders and N + 2 rotation circuits. These results are expected to have a significant impact on real-time audio and video data compression, in frequency domain adaptive filtering and in spectrum analysis.