Pipeline Interleaving and Parallelism in Recursive Digital Filters—Part II

Pipelined Incremental Block Filtering

Keshab K Parhi, David G. Messerschmitt

Research output: Contribution to journalArticle

77 Citations (Scopus)

Abstract

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
Volume37
Issue number7
DOIs
StatePublished - Jan 1 1989

Fingerprint

Digital filters
Pipelines
Decomposition
Processing

Cite this

@article{26dd6c4384d64a899f9e97dfcedc6db6,
title = "Pipeline Interleaving and Parallelism in Recursive Digital Filters—Part II: Pipelined Incremental Block Filtering",
abstract = "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.",
author = "Parhi, {Keshab K} and Messerschmitt, {David G.}",
year = "1989",
month = "1",
day = "1",
doi = "10.1109/29.32287",
language = "English (US)",
volume = "37",
pages = "1118--1134",
journal = "IEEE Transactions on Signal Processing",
issn = "1053-587X",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "7",

}

TY - JOUR

T1 - Pipeline Interleaving and Parallelism in Recursive Digital Filters—Part II

T2 - Pipelined Incremental Block Filtering

AU - Parhi, Keshab K

AU - Messerschmitt, David G.

PY - 1989/1/1

Y1 - 1989/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0024702010&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024702010&partnerID=8YFLogxK

U2 - 10.1109/29.32287

DO - 10.1109/29.32287

M3 - Article

VL - 37

SP - 1118

EP - 1134

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

SN - 1053-587X

IS - 7

ER -