A chain that counts the number of bits set in a 15-bit input

Question

How to build an area-efficient circuit that counts the number of bits set in a 15-bit input using 4-input LUTs (lookup tables). The output is obviously 4-bit (number 0-15). Some argue that this can be done using the 9 LUT.

Answer 1

I can do this in 10. Its first counting step (4 tables), then a two-stage adder with carry (3 and 3 tables).

I suspect there is a way to do better, because I did not use every LUT completely, but sometimes a simple design is worth the extra cost. I tried other approaches and still needed 10.

Good luck with your homework. (

Answer 2

Alright, I'll start. Your first layer of lookup tables will look like this:

0 0 0 0 = 00 0 0 0 1 = 01 0 0 1 0 = 01 0 0 1 1 = 10 0 1 0 0 = 01 0 1 0 1 = 10 0 1 1 0 = 10 0 1 1 1 = 11 1 0 0 0 = 01 1 0 0 1 = 10 1 0 1 0 = 10 1 0 1 1 = 11 1 1 0 0 = 10 1 1 0 1 = 11 1 1 1 0 = 11 1 1 1 1 = 00 

Place four of them on your fifteen-bit input, take out the outputs, and pass them through two new lookup tables, which look like this:

 0 0 0 0 = 000 0 0 0 1 = 001 0 0 1 0 = 010 0 0 1 1 = 011 0 1 0 0 = 001 0 1 0 1 = 010 0 1 1 0 = 011 0 1 1 1 = 100 1 0 0 0 = 010 1 0 0 1 = 011 1 0 1 0 = 100 1 0 1 1 = 101 1 1 0 0 = 011 1 1 0 1 = 100 1 1 1 0 = 101 1 1 1 1 = 110 

... and so on. Of course, you have to solve the problem of all zeros, and they all produce the same output in the first layer.

And I can be absolutely wrong.

Answer 3

Here's some C code that counts the number of bits: A C code to count the number of bits "1" . You will have to convert this to your equipment.