Hamming weight (12 bit adder tree)

Description

This circuit counts the number of active (1) bits in the input word (also known as the Hamming weight). Obviously, a single full-adder can be used to calculate the Hamming weight of a three bit input word. For larger input word width, a tree of adders can be used to combine the intermediate sums from the previous stages.

Click the input switches or type the '0'..'9' and 'a', 'b' bindkeys to play with the circuit. See the next applet for an animated demonstration of the Hamming weight adder-tree.

To keep the circuit layout readable, the carry-in inputs of the multi-bit adders are tied to GND (logical 0) in the example. Naturally, these carry-in inputs could be connected to additional input pins, which would allow for 15-bits of input with the same number of adders. As 15 is also the highest number that one three-bit adder can generate, a 16-bit bitcounter would obviously require another adder, etc.

Run the applet | Run the editor (via Webstart)