Tuesday, November 18, 2008

Count the amount of '1' in a 7-bit vector

4 full-adder units are necessary to count the amount of “1″s in a 7-bit vector.

fa_01.png The most important thing to notice is that a full-adder “counts” the amount of “1″s of it’s inputs. If you are not convinced , then a brief look in the component’s truth table will prove this to you. The output is a binary represented 2-bit number.

The next picture shows how to connect the four full-adders in the desired way. The first stage generates two 2-bit numbers, each represents the amount of “1″s among its respected three input bits. The second stage adds those two binary numbers together and uses the carry_in of one full-adder for the 7th bit. fa_solution.png

As I mentioned when I posted the puzzle, I used this in an actual design. In clock and data recovery circuits (CDRs) it is necessary to integrate the amount of “ups” and “downs” a phase detector outputs (if this tells you nothing, please hold on till the CDR post I am planning). Basically, you receive two vectors of a given length, one represents “ups” the other “downs”. You have to sum up the amount of “1″s in each vector and subtract one from the other. Summing up the amount of “1″s is done using this full-adder arrangement. Another way would be using a LUT (posts on LUTs are planned as well…).

No comments: