Concurrent Architectures for Two-Dimensional Recursive Digital Filtering

Keshab K. Parhi, David G. Messerschmitt

Research output: Contribution to journalArticle

28 Citations (Scopus)

Abstract

This paper presents new efficient architectures for high-speed implementation of direct form and local state-space form two-dimensional recursive digital filters. Unlike one-dimensional recursive systems, two-dimensional recursive digital filter algorithms possess a large amount of inherent concurrency, which can be exploited for fine-grain pipelining and/or parallelism. The locus of these concurrent computations is referred to as the concurrent computation region. We exploit this concurrency to derive fine-grain pipelined and one-dimensional block architectures for implementation of two-dimensional recursive digital filters by appropriate interleaving (or indexing) of the input samples, without requiring any algorithm transformation and without any hardware overhead. We extend the lookahead computation and incremental computation techniques to two dimensions, and use these to derive new two-dimensional incremental block filter architectures. The multiplication complexity of our two-dimensional incremental block filter is 0(max [formula omitted], as opposed to [formula omitted] of existing block structures, where L1 X L2 corresponds to the block size. Fine-grain pipelined two-dimensional block structures are also presented. The index mapping functions are used to derive delay operators for various architectures.

Original languageEnglish (US)
Pages (from-to)813-829
Number of pages17
JournalIEEE Transactions on Circuits and Systems
Volume36
Issue number6
DOIs
StatePublished - Jan 1 1989

Fingerprint

Digital filters
Mathematical operators
Hardware

Cite this

Concurrent Architectures for Two-Dimensional Recursive Digital Filtering. / Parhi, Keshab K.; Messerschmitt, David G.

In: IEEE Transactions on Circuits and Systems, Vol. 36, No. 6, 01.01.1989, p. 813-829.

Research output: Contribution to journalArticle

@article{9d7c7653c64549fb8dd6555cbe106a30,
title = "Concurrent Architectures for Two-Dimensional Recursive Digital Filtering",
abstract = "This paper presents new efficient architectures for high-speed implementation of direct form and local state-space form two-dimensional recursive digital filters. Unlike one-dimensional recursive systems, two-dimensional recursive digital filter algorithms possess a large amount of inherent concurrency, which can be exploited for fine-grain pipelining and/or parallelism. The locus of these concurrent computations is referred to as the concurrent computation region. We exploit this concurrency to derive fine-grain pipelined and one-dimensional block architectures for implementation of two-dimensional recursive digital filters by appropriate interleaving (or indexing) of the input samples, without requiring any algorithm transformation and without any hardware overhead. We extend the lookahead computation and incremental computation techniques to two dimensions, and use these to derive new two-dimensional incremental block filter architectures. The multiplication complexity of our two-dimensional incremental block filter is 0(max [formula omitted], as opposed to [formula omitted] of existing block structures, where L1 X L2 corresponds to the block size. Fine-grain pipelined two-dimensional block structures are also presented. The index mapping functions are used to derive delay operators for various architectures.",
author = "Parhi, {Keshab K.} and Messerschmitt, {David G.}",
year = "1989",
month = "1",
day = "1",
doi = "10.1109/31.90397",
language = "English (US)",
volume = "36",
pages = "813--829",
journal = "IEEE Transactions on Circuits and Systems",
issn = "0098-4094",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "6",

}

TY - JOUR

T1 - Concurrent Architectures for Two-Dimensional Recursive Digital Filtering

AU - Parhi, Keshab K.

AU - Messerschmitt, David G.

PY - 1989/1/1

Y1 - 1989/1/1

N2 - This paper presents new efficient architectures for high-speed implementation of direct form and local state-space form two-dimensional recursive digital filters. Unlike one-dimensional recursive systems, two-dimensional recursive digital filter algorithms possess a large amount of inherent concurrency, which can be exploited for fine-grain pipelining and/or parallelism. The locus of these concurrent computations is referred to as the concurrent computation region. We exploit this concurrency to derive fine-grain pipelined and one-dimensional block architectures for implementation of two-dimensional recursive digital filters by appropriate interleaving (or indexing) of the input samples, without requiring any algorithm transformation and without any hardware overhead. We extend the lookahead computation and incremental computation techniques to two dimensions, and use these to derive new two-dimensional incremental block filter architectures. The multiplication complexity of our two-dimensional incremental block filter is 0(max [formula omitted], as opposed to [formula omitted] of existing block structures, where L1 X L2 corresponds to the block size. Fine-grain pipelined two-dimensional block structures are also presented. The index mapping functions are used to derive delay operators for various architectures.

AB - This paper presents new efficient architectures for high-speed implementation of direct form and local state-space form two-dimensional recursive digital filters. Unlike one-dimensional recursive systems, two-dimensional recursive digital filter algorithms possess a large amount of inherent concurrency, which can be exploited for fine-grain pipelining and/or parallelism. The locus of these concurrent computations is referred to as the concurrent computation region. We exploit this concurrency to derive fine-grain pipelined and one-dimensional block architectures for implementation of two-dimensional recursive digital filters by appropriate interleaving (or indexing) of the input samples, without requiring any algorithm transformation and without any hardware overhead. We extend the lookahead computation and incremental computation techniques to two dimensions, and use these to derive new two-dimensional incremental block filter architectures. The multiplication complexity of our two-dimensional incremental block filter is 0(max [formula omitted], as opposed to [formula omitted] of existing block structures, where L1 X L2 corresponds to the block size. Fine-grain pipelined two-dimensional block structures are also presented. The index mapping functions are used to derive delay operators for various architectures.

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

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

U2 - 10.1109/31.90397

DO - 10.1109/31.90397

M3 - Article

AN - SCOPUS:34250885644

VL - 36

SP - 813

EP - 829

JO - IEEE Transactions on Circuits and Systems

JF - IEEE Transactions on Circuits and Systems

SN - 0098-4094

IS - 6

ER -