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.

Charlton

Hardware questions usually don't get great response on this forum. – Githens

Especially when they sound like homework questions. – Blackfish

It's not a homework question. I need to synthesize this circuit in the optimized way, but the FPGA synthesis tool uses 20 LUTs for it. it can be done better than that. – Charlton

I would consider FPGA design to be a form of programming, myself. – Chatelaine

I figured how to do it in 11 LUTs – Charlton

What synthesiser are you using? And what code? – Etna

Answer 1

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. (:

Gluten

Answer 2

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.

Botryoidal

Answer 3

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.

Shoal