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 journalArticle

211 Citations (Scopus)

Abstract

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

Fingerprint

Pipelines
Decomposition
Digital filters
Sampling
Systolic arrays
Feedback
Hardware

Cite this

@article{c2edd599ff234c8baa84b44b67b0ea9a,
title = "Pipeline Interleaving and Parallelism in Recursive Digital Filters—Part I: Pipelining Using Scattered Look-Ahead and Decomposition",
abstract = "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.",
author = "Parhi, {Keshab K.} and Messerschmitt, {David G.}",
year = "1989",
month = "7",
doi = "10.1109/29.32286",
language = "English (US)",
volume = "37",
pages = "1099--1117",
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 I

T2 - Pipelining Using Scattered Look-Ahead and Decomposition

AU - Parhi, Keshab K.

AU - Messerschmitt, David G.

PY - 1989/7

Y1 - 1989/7

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

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

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

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

U2 - 10.1109/29.32286

DO - 10.1109/29.32286

M3 - Article

AN - SCOPUS:0024700229

VL - 37

SP - 1099

EP - 1117

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

SN - 1053-587X

IS - 7

ER -