Time-recursive computation and real-time parallel architectures: a framework

The time-recursive computation has been proven a particularly useful tool in real-time data compression, in transform domain adaptive filtering, and in spectrum analysis. Unlike the FFT-based ones, the time-recursive architectures require only local communication. Also, they are modular and regular, thus they are very appropriate for VLSI implementation and they allow a high degree of parallelism. In this two-part paper, we establish an architectural framework for parallel time-recursive computation. We consider a class of linear operators that consists of the discrete time, time invariant, compactly supported, but otherwise arbitrary kernel functions. We show that the structure of the realization of a given linear operator is dictated by the decomposition of the latter with respect to proper basis functions. An optimal way for carrying out this decomposition is demonstrated. The parametric forms of the basis functions are identified and their properties pertinent to the architecture design are studied. A library of architectural building modules capable of realizing these functions is developed. An analysis of the implementation complexity for the aforementioned modules is conducted. Based on this framework, the time-recursive architecture of a given linear operator can be derived in a systematic routine way