Fast constant weight codeword to index converter

Abstract

The 54th IEEE International Midwest Symposium on Circuits and Systems, Korea August 7-10, 2011, CDROM, pp.1-4. ; This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. As such, it is in the public domain, and under the provisions of Title 17, United States Code, Section 105, may not be copyrighted. ; Constant weight codewords, in which the number of 1's is constant, are essential to combinatorial computing. For example, it is often useful to generate all subsets of a set with a fixed number of elements. In this paper, we show an efficient circuit that converts a constant weight codeword into a unique index of that codeword. This circuit is a necessary part of a circuit that uses constant weight codewords to transmit data on and off chip. Our circuit is based on the combinatorial number system in which the digits are binomial coefficients n r. Experimental results show the efficiency of our design.