Tuesday, January 22, 2008

Half Adder, Full Adder and Multiple Bit Adder

Just like I told before in my previous posting titled “Making Arithmetic function from Logical function ( Pascal, C )”, there is something missing from my knowledge about how arithmetic function is performed by computers using their basic logical function. The missing part as I realized later, is the fact that the things done by programming functions I wrote in my previous posting, is not done at software level, but instead embedded as a firmware inside a computer’s Arithmetic Logic Unit.

Half Adder

I will rewrite Equation E1,E2,E3, and E4 from my previous posting stated above.
R = A xor B .…(E1)
C = A and B ….(E2)
A + B = C shl 1 + R ….(E3)
A + B = (A and B) shl 1 + (A xor B) ….(E4)

One of the basic function of a computer’s Arithmetic Logic Unit is Addition, which most basic part is a Half Adder. A Half Adder is a logic gate structure derived from equation E1 and E2, the C is actually an abbreviation for Carry, which means additional bit carried by the addition function to the More Significant Bit. Here is the structure of a Half Adder.

Several Symbol for Logic IO structure of a Half Adder

Full Adder

There is almost no use for us if computer is only capable of doing one bit addition. The Arithmetic function must be extended to Multiple Bit Addition. In order to add multiple bits, the Carry bit from Less Significant Bit must also be accommodated; this is why we have to make something called a Full Adder. A Full adder unit, have three inputs A,B,CI (Carry In) and two outputs FR (Full Result) and CO(Carry Out).

The relationship in a Full Adder is extended into equation E5 and E6 below :
FR = R xor CI ….(E5)
CO = (R and CI) or C ….(E6)

Several Symbol for Logic IO structure of a Full Adder

Multiple Bit Parallel Full Adder

Once the basic is in place, it is easy to make more advanced logical structure. Multiple Bit Parallel Full Adder is simply a structure made by connecting several Full Adder. The CO from a Less Significant Bit is connected as input for the CI of a More Significant Bit.

The input are vectors of bit, A (A0,A1,A2,A3) and B (B0,B1,B2,B3), with the result of vector R(R0,R1,R2,R3,R4), note that the A0,B0 and R0 are Least Significant Bits, while A3,B3 and R4 are Most Significant Bits.

Several Symbol for Logic IO structure of a 4 bits Parallel Full Adder
(click to view detail)

I realize later that Multiple Bit Full Adder is a basic component for other arithmetic function such as subtraction, multiplication and division. I will present the detail on how subtraction is done logically in the next posting in this blog.

No comments: