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.

author list (cited authors)

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

citation count

  • 1

publication date

  • May 2009

publisher