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.
Asked
Active
Viewed 1,901 times
6
-
Hardware questions usually don't get great response on this forum. – samoz Jul 15 '09 at 01:00
-
Especially when they sound like homework questions. – Steven Sudit Jul 15 '09 at 04:50
-
4It'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. – OutputLogic Jul 16 '09 at 13:11
-
I would consider FPGA design to be a form of programming, myself. – bdonlan Jul 17 '09 at 18:49
-
I figured how to do it in 11 LUTs – OutputLogic Jul 23 '09 at 03:40
-
What synthesiser are you using? And what code? – Martin Thompson Oct 26 '12 at 14:09
3 Answers
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.
Robert Harvey
- 178,213
- 47
- 333
- 501
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. (:
Erik Olson
- 1,154
- 8
- 18
-5
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.
Community
- 1
- 1
Robert Deml
- 12,390
- 20
- 65
- 92