Low-cost sorting network circuits using unary processing

Research output: Contribution to journalArticlepeer-review

39 Scopus citations

Abstract

Sorting is a common task in a wide range of applications from signal and image processing to switching systems. For applications that require high performance, sorting is often performed in hardware with application-specified integrated circuits or field-programmable gate arrays. Hardware cost and power consumption are the dominant concerns. The usual approach is to wire up a network of compare-and-swap units in a configuration called the Batcher (or bitonic) network. Such networks can readily be pipelined. This paper proposes a novel area-efficient and power-efficient approach to sorting networks, based on 'unary processing.' In unary processing, numbers are encoded uniformly by a sequence of one value (say 1) followed by a sequence of the other value (say 0) in a stream of 0's and 1's with the value defined by the fraction of 1's in the stream. Synthesis results of complete sorting networks show up to 92% area and power saving compared to the conventional binary implementations. However, the latency increases. To mitigate the increased latency, this paper uses a novel time-encoding of data. The approach is validated with two implementations of an important application of sorting: median filtering. The result is a low cost, energy-efficient implementation of median filtering with only a slight accuracy loss, compared to conventional implementations.

Original languageEnglish (US)
Pages (from-to)1471-1480
Number of pages10
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume26
Issue number8
DOIs
StatePublished - Aug 2018

Bibliographical note

Publisher Copyright:
© 1993-2012 IEEE.

Keywords

  • Low cost design
  • median filtering
  • sorting networks
  • stochastic computing
  • time-encoding data
  • unary processing

Fingerprint

Dive into the research topics of 'Low-cost sorting network circuits using unary processing'. Together they form a unique fingerprint.

Cite this