Optimized bitcounting on FPGA

Most Modern FPGAs have block RAM that can be used for look-ups. Use these as larger LUTs to get partial counts, and then sum up the partials. If you can afford a multiplied clock, you can time multiplex segments of your input vector into a smaller number of RAMs followed by accumulators.

Thank you, Ray. Let me just add that a dual-ported RAM can then be used as two separate look-up tables, by addressing the two ports independently, using common data. This is obvious once you think about it, and it cuts the number of BRAMs in half... Peter Alfke

There was a lengthy discussion about bitcounting in the FPGA forum on mikrocontroller.net:

You find the background in theoretical text books on parallel computing. Prefix sum is a fundamental sub problem and a lot has been written about the implementation of sums and prefix sums on various architecturs including networks of operators. The results translate directly to FPGAs. (Counting bits reduces to summing numbers, albeit small numbers).

Kolja Sulimma

Hi Ray,

That's indeed what I did, except that BRAM are somewhat overkill for the purpose.

So far, the best approach I came up with was to store in a LUT the bitcount of a 3 bit wide vector (after xoring the 2 operand for Hamming), and use an adder tree ot obtain the Hamming distance value.

Using larger tables (for vectors of 4 and more bits) ends up in a signifcant area penalty (~20%).

Steven

Ray Andraka a écrit :

mikrocontroller.net:http://www.mikrocontroller.net/topic/34231#newhttp://www.mikrocontroller.net/topic/34250#new

For the English-only readers: There is nothing of value in that German discussion, just repetitive trivialities. You don't miss anything if you cannot read it. Peter Alfke

You mean two LUTs for the 1's and 2's bit of the sum? That is the first level of a carry save adder tree.

For a true carry save adder tree you add the 1's to form a second set of 1's and 2's, add the 2's to form a set of 2's and 4's. Repeat as needed.

-- glen