Pipeline Interleaving and Parallelism in Recursive Digital Filters—Part II: Pipelined Incremental Block Filtering

Keshab K. Parhi, David G. Messerschmitt

Research output: Contribution to journalArticlepeer-review

83 Scopus citations


In the companion paper, we proposed high speed pipelined realizations of recursive digital filters of logarithmic complexity with respect to the number of loop pipeline stages using scattered look-ahead and decomposition techniques. In this paper, we address block implementation and fine-grain pipelined block implementation of recursive digital filters. Recently, Wu and Cappello proposed a direct form block filter structure for second-order recursive filters of complexity linear in block size. We extend this linear complexity block filter structure to higher order systems, and refer to it as incremental block filter. Block implementation of state space recursive digital filters has been known for a long time. The two existing popular block structures are the block-state structure proposed by Barnes and Shinnaka, and the parallel block-state structure proposed by Nikias. However, the multiplication complexity of these structures is proportional to the square of the block size. The block-state update operation in these filter structures is performed based on the clustered look-ahead computation, and requires a linear complexity in block size. But, the output computation of the complete block is done all at once and requires a square complexity in block size. In this paper, we introduce a new technique of incremental output computation which requires a linear complexity in block size. Based on the clustered look-ahead and incremental output computation approaches, we derive our incremental block-state structure for block implementation of state space filters of multiplication complexity linear in block size. The incremental block-state structure is also extended for the multirate recursive filtering case. Finally, we combine the techniques of scattered look-ahead, clustered look-ahead, decomposition, and incremental output computation to introduce several pipeline stages inside the recursive loop of the block filter. We derive deeply pipelined block filter structures for implementation of direct form and state space form recursive digital filters. The multiplication complexity of these pipelined block filters is linear with respect to the block size, logarithmic with respect to the number of loop pipeline stages, and the complexities due to pipelining and block processing are additive.

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

Bibliographical note

Funding Information:
Manuscript received November 3. 1987; rcvised November 16, 1988. This work was supported in part by grants from the Advanced Research Project Agency monitored by the Naval Electronics Systems Command un- der Contract N00039-86-R-0365. the National Science Foundation under 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. Messerschrnitt is with the Department of Electrical Engineering and Computer Sciences, University of California, Berkeley. CA 94720. IEEE Log Number 892812 I.


Dive into the research topics of 'Pipeline Interleaving and Parallelism in Recursive Digital Filters—Part II: Pipelined Incremental Block Filtering'. Together they form a unique fingerprint.

Cite this