Input compression and efficient VLSI architectures for rank order and stack filters

George B. Adams, Edward J. Coyle, Liangchien Lin, Lori E. Lucke, Keshab K Parhi

Research output: Contribution to journalArticle

14 Citations (Scopus)

Abstract

Rank-order-based filters include rank-order filters, stack filters, and weighted order statistic filters. The output of a rank-order-based filter is always one of the sample points in its input window; which one is chosen depends only upon the ranks and positions of the samples within the window. This paper introduces new architectures for rank-order-based filters. They all achieve fast, efficient operation by exploiting an algorithm called input compression. Under this algorithm, the sample points in the input window are first mapped to their relative ranks - the sample points in a window of size N + 1 would thus be mapped to the integers 0-N. The rank-order-based filter to be implemented is then applied directly to this compressed input, and the rank chosen is then mapped back to the sample of that rank in the original data to obtain the final output. This approach has been used to implement rank-order filters, in which case the same rank is always chosen from the compressed data. In this paper, which rank is chosen also depends on the positions of the ranks in the compressed data. Implementations employing input compression have several advantages. They are computationally efficient like running order sorters, yet can be pipelined to a fine degree like sorting networks. In stack filter implementations, the threshold decomposition circuitry can be eliminated when input compression is combined with unary encoding of the ranks. Weighted order statistic filter implementations based on input compression can support programmable, noninteger weights.

Original languageEnglish (US)
Pages (from-to)441-453
Number of pages13
JournalSignal Processing
Volume38
Issue number3
DOIs
StatePublished - Jan 1 1994

Fingerprint

Statistics
Sorting
Decomposition

Keywords

  • Input compression
  • Rank-order filters
  • Stack filters
  • Unary encoded rank
  • VLSI architecture
  • Weighted order statistic filters

Cite this

Input compression and efficient VLSI architectures for rank order and stack filters. / Adams, George B.; Coyle, Edward J.; Lin, Liangchien; Lucke, Lori E.; Parhi, Keshab K.

In: Signal Processing, Vol. 38, No. 3, 01.01.1994, p. 441-453.

Research output: Contribution to journalArticle

Adams, George B. ; Coyle, Edward J. ; Lin, Liangchien ; Lucke, Lori E. ; Parhi, Keshab K. / Input compression and efficient VLSI architectures for rank order and stack filters. In: Signal Processing. 1994 ; Vol. 38, No. 3. pp. 441-453.
@article{b32927c78c2e4649965790d211fa85e2,
title = "Input compression and efficient VLSI architectures for rank order and stack filters",
abstract = "Rank-order-based filters include rank-order filters, stack filters, and weighted order statistic filters. The output of a rank-order-based filter is always one of the sample points in its input window; which one is chosen depends only upon the ranks and positions of the samples within the window. This paper introduces new architectures for rank-order-based filters. They all achieve fast, efficient operation by exploiting an algorithm called input compression. Under this algorithm, the sample points in the input window are first mapped to their relative ranks - the sample points in a window of size N + 1 would thus be mapped to the integers 0-N. The rank-order-based filter to be implemented is then applied directly to this compressed input, and the rank chosen is then mapped back to the sample of that rank in the original data to obtain the final output. This approach has been used to implement rank-order filters, in which case the same rank is always chosen from the compressed data. In this paper, which rank is chosen also depends on the positions of the ranks in the compressed data. Implementations employing input compression have several advantages. They are computationally efficient like running order sorters, yet can be pipelined to a fine degree like sorting networks. In stack filter implementations, the threshold decomposition circuitry can be eliminated when input compression is combined with unary encoding of the ranks. Weighted order statistic filter implementations based on input compression can support programmable, noninteger weights.",
keywords = "Input compression, Rank-order filters, Stack filters, Unary encoded rank, VLSI architecture, Weighted order statistic filters",
author = "Adams, {George B.} and Coyle, {Edward J.} and Liangchien Lin and Lucke, {Lori E.} and Parhi, {Keshab K}",
year = "1994",
month = "1",
day = "1",
doi = "10.1016/0165-1684(94)90159-7",
language = "English (US)",
volume = "38",
pages = "441--453",
journal = "Signal Processing",
issn = "0165-1684",
publisher = "Elsevier",
number = "3",

}

TY - JOUR

T1 - Input compression and efficient VLSI architectures for rank order and stack filters

AU - Adams, George B.

AU - Coyle, Edward J.

AU - Lin, Liangchien

AU - Lucke, Lori E.

AU - Parhi, Keshab K

PY - 1994/1/1

Y1 - 1994/1/1

N2 - Rank-order-based filters include rank-order filters, stack filters, and weighted order statistic filters. The output of a rank-order-based filter is always one of the sample points in its input window; which one is chosen depends only upon the ranks and positions of the samples within the window. This paper introduces new architectures for rank-order-based filters. They all achieve fast, efficient operation by exploiting an algorithm called input compression. Under this algorithm, the sample points in the input window are first mapped to their relative ranks - the sample points in a window of size N + 1 would thus be mapped to the integers 0-N. The rank-order-based filter to be implemented is then applied directly to this compressed input, and the rank chosen is then mapped back to the sample of that rank in the original data to obtain the final output. This approach has been used to implement rank-order filters, in which case the same rank is always chosen from the compressed data. In this paper, which rank is chosen also depends on the positions of the ranks in the compressed data. Implementations employing input compression have several advantages. They are computationally efficient like running order sorters, yet can be pipelined to a fine degree like sorting networks. In stack filter implementations, the threshold decomposition circuitry can be eliminated when input compression is combined with unary encoding of the ranks. Weighted order statistic filter implementations based on input compression can support programmable, noninteger weights.

AB - Rank-order-based filters include rank-order filters, stack filters, and weighted order statistic filters. The output of a rank-order-based filter is always one of the sample points in its input window; which one is chosen depends only upon the ranks and positions of the samples within the window. This paper introduces new architectures for rank-order-based filters. They all achieve fast, efficient operation by exploiting an algorithm called input compression. Under this algorithm, the sample points in the input window are first mapped to their relative ranks - the sample points in a window of size N + 1 would thus be mapped to the integers 0-N. The rank-order-based filter to be implemented is then applied directly to this compressed input, and the rank chosen is then mapped back to the sample of that rank in the original data to obtain the final output. This approach has been used to implement rank-order filters, in which case the same rank is always chosen from the compressed data. In this paper, which rank is chosen also depends on the positions of the ranks in the compressed data. Implementations employing input compression have several advantages. They are computationally efficient like running order sorters, yet can be pipelined to a fine degree like sorting networks. In stack filter implementations, the threshold decomposition circuitry can be eliminated when input compression is combined with unary encoding of the ranks. Weighted order statistic filter implementations based on input compression can support programmable, noninteger weights.

KW - Input compression

KW - Rank-order filters

KW - Stack filters

KW - Unary encoded rank

KW - VLSI architecture

KW - Weighted order statistic filters

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

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

U2 - 10.1016/0165-1684(94)90159-7

DO - 10.1016/0165-1684(94)90159-7

M3 - Article

VL - 38

SP - 441

EP - 453

JO - Signal Processing

JF - Signal Processing

SN - 0165-1684

IS - 3

ER -