Pipeline Interleaving and Parallelism in Recursive Digital Filters—Part I: Pipelining Using Scattered Look-Ahead and Decomposition

Keshab K. Parhi, David G. Messerschmitt

Research output: Contribution to journalArticlepeer-review

218 Scopus citations


The computational latency associated with the internal recursion or feedback in recursive systems limits the opportunities to use a pipelining technique to achieve high sampling rate realizations. Pipelining recursive loops by simply inserting latches is useful for applications requiring moderate sampling rates and where multiple independent computations are available to be interleaved in the pipeline; but not where a single recursive operation needs to be performed at very high sampling rates. In this paper, we introduce a new look-ahead approach (referred to as scattered look-ahead) to pipeline recursive loops in a way that guarantees stability. We also propose a new decomposition technique to implement the nonrecursive portion (generated due to the scattered look-ahead process) in a decomposed manner to obtain concurrent stable pipelined realizations of logarithmic implementation complexity with respect to the number of loop pipeline stages (as opposed to linear). The upper bound on the roundoff error in these pipelined filters is shown to improve with increase in the number of loop pipeline stages. We study efficient pipelined realizations of both direct form and state space form recursive digital filters. Based on the scattered look-ahead technique, we present fully pipelined and fully hardware efficient linear bidirectional systolic arrays for recursive digital filters. The decomposition technique is also extended to time varying recursive systems.

Original languageEnglish (US)
Pages (from-to)1099-1117
Number of pages19
JournalIEEE Transactions on Acoustics, Speech, and Signal Processing
Issue number7
StatePublished - Jul 1989

Bibliographical note

Funding Information:
Contract DCI-85.17339, an IBM Graduate Fellowship, and a University of California Regents Fellowship. K. K. Parhi is with the Department of Electrical Engineering, University of Minnesota, Minneapolis, MN 55455. D. G. Messerschmitt is with the Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, CA 94720. IEEE Log Number 89281 19.

Funding Information:
Manuscript received November 3, 1987; revised November 16, 1988. This work was supported in part by grants from the Advanced Research Project Agency monitored by the. Naval Electronics Systems Command under Contract N00039-86-R-0365, the National Science Foundation under


Dive into the research topics of 'Pipeline Interleaving and Parallelism in Recursive Digital Filters—Part I: Pipelining Using Scattered Look-Ahead and Decomposition'. Together they form a unique fingerprint.

Cite this