Sorting Binary Numbers in Hardware - A Novel Algorithm and its Implementation Conference Paper uri icon

abstract

  • This paper describes a novel algorithm for sorting binary numbers in hardware, along with a custom VLSI hardware design for the same. For sorting n, k-bit binary numbers, our proposed algorithm takes O(n + 2k) time. Sorting is performed by assigning relative ranks to the input numbers. A rank matrix of size n x n is used to store ranks. Each row of the rank matrix corresponds to one of the n numbers, and it stores a single non-zero entry. The position of this entry represents the relative rank of the corresponding number. In the worst case, our algorithm requires n+2k clock cycles for assigning the final ranks. We start with a condition in which each number has an identical rank. In each of clock cycle, ranks are iteratively updated until the final ranks are determined after n+2k clock cycles. The proposed algorithm is implemented in a 65nm process, using a custom design approach to obtain a fast circuit. Our design is significantly faster than the fastest reported hardware sorting engine, with area performance which is superior for larger numbers. 2009 IEEE.

name of conference

  • 2009 IEEE International Symposium on Circuits and Systems

published proceedings

  • ISCAS: 2009 IEEE INTERNATIONAL SYMPOSIUM ON CIRCUITS AND SYSTEMS, VOLS 1-5

author list (cited authors)

  • Alaparthi, S., Gulati, K., & Khatri, S. P.

citation count

  • 3

complete list of authors

  • Alaparthi, Srikanth||Gulati, Kanupriya||Khatri, Sunil P

publication date

  • May 2009