Circuit that counts the number of set bits in 15-bit input

Question

How to build an area-efficient circuit that counts the number of set bits in 15-bit input using 4-input LUTs (look-up tables). The output is obviously 4-bit (counts 0-15). Some claim that it's possible to do using 9 LUTs.

Answer 1

Well, I'll get you started. 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

Spread four of them across your fifteen-bit input, take the outputs and pass them through two new lookup tables that 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're going to have to solve the problem of all zeroes and all ones producing the same output in the first layer.

And I may be totally wrong.

Answer 2

Here some C code that counts the number of bits: C code to count the number of '1' bits. You'll have to convert this into your hardware.

Answer 3

I can do it in 10. It’s a first counter stage (4 tables), then a 2 stage adder with carry (3 and 3 tables).

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

Good luck on your homework. (: