EFFICIENT HARDWARE ALGORITHMS FOR N CHOOSE K COUNTERS USING THE BITONIC MERGER
Abstract
An "n choose k" counter (C(n,k) counter for short) is a counter which lists all n-bit numbers with (n - k) 0's and k 1's. The C(n,k) counters have applications to solving combinatorial optimization problems and image processing. The main contribution of this work is to present an efficient hardware implementation of the C(n,k) counter. In some applications, C(n,k) counters are used only for small k. The second contribution is to show more efficient implementations that support C(n,k) counters only for small k. We evaluate the performance of our new implementation and known implementations in terms of the number of used slices and the clock frequency for the Xilinx VirtexII family FPGA XC2V3000-4. Although the theoretical analysis shows that our implementation is not the best, it runs in higher clock frequency using fewer number of slices than the other implementations.
