An adder is a device that will add together two bits and give the result as the output. The bits being added together are called the "addends". Adders can be concatenated in order to add together two binary numbers of an arbitrary length.
There are two kinds of adders - half adders and full adders. A half adder just adds two bits together and gives a two-bit output. A full adder adds two inputs and a carried input from another adder, and also gives a two-bit output.
When adding two separate bits together there are four possible combinations. Each of these is shown the the left with its solution.
It can easily be seen that the bit in the right-hand column (the "ones" column) is a 1 only when the addends are different. XORing the addends together can therefore give us the right-hand bit. This bit is called the sum and is the modulo-2 sum of the addends (i.e. the solution if you loop round to zero again once you pass one).
The left-hand bit reads 1 only when both addends are 1, so an AND gate can be used to generate this bit, called the carried bit. As a summary:
The diagram to the left shows the complete half adder with the addends being represented by A and B, the sum represented by S and the carried bit represented by C.
The truth table is as follows (the number in the brackets are the weights of the bits - each addend is one, as is the sum - the carried bit is two)
|A (1)||B (1)||S (1)||C (2)|
The downfall of half adders is that while they can generate a carry out output, they cannot deal with a carry in signal. This means that they can only ever be stand-alone units, and cated to add multiple bit numbers.
A full adder solves this problem by adding three numbers together - the two addends as in the half adder, and a carry in input.
A full adder can be constructed from two half adders by connecting A and B to the input of one half adder, connecting the sum from that to an input to the second adder, connecting the carry in, Cin, to the other input and ORing the two half adder carry outputs to give the final carry output, Cout.
The digram below shows a full adder at the gate level.
A version of this diagram showing the two half adder modules outlined is available here. The output of the full adder is the two-bit arithmetic sum of three one-bit numbers.
The logic expressions for this full adder are:
By applications of boolean algebra, the second statement simplifies to
Giving the inputs a a three digit number where the first is the state of A, the second the state of B and the third the state of Cin, below is a description of the function of this full adder:
- All combinations resultings in one (100, 010, 001) produce a high at the sum output, as the presence of only one high at the second XOR gate (the first gate gives a low when A and B are low and a high when either A or B is high) gives a high output at the sum output. The fact that only one input is ever high prevents either AND gate from going high and give a high Cout.
- All combinations resulting in two (011, 101, 110) produce a high carry out and a low sum:
- 011 sends the first XOR gate high as A and B are different. Combined with the high at Cin, this sends the top AND gate high and therefore the carry output high as well. The presence of two highs at the second XOR gate hold the sum low.
- 101 works in exactly the same way as 011, as A and B are interchangeable.
- 110: The high A and B force the first XOR low; this low, combined with the low from Cin gives a low at the sum. The highs at A and B send the lower AND gate high and therefore Cout is high.
- When the inputs are 111, the first XOR gate is low due to the two high inputs, and the second XOR gate goes high, as it has one low input (from the first XOR gate) and one high input (from the Cin input). This gives a high sum output. The fact that both A and B are high triggers the lower AND gate, and the Cout output goes high as well.
The truth table for a full adder is given below with the weights of the inputs and outputs:
|A (1)||B (1)||Cin (1)||S (1)||Cout (2)|
If A and B are both high then the AND gate connected to them gives a high output, but the XOR gate gives a low, forcing the other AND gate low. If the "sum" output of the first half adder is high, then one of A or B must be low, meaning that the AND gate connected to them is force low. This means that two inputs to the OR gate combining the half adder carry outs can never both be high, this gate can be replaced with an XOR gate (OR and XOR differ only when both inputs are high). This means that only two kinds of gates are needed, and a full adder can be realised with only two ICs.
These can be run in stages, with the carry out of one stage driving the carry in of the next. This is discussed in the next section.
In the previous section we said how we could add two one-bit binary numbers, taking into account any carried digits from the previous binary order of magnitude (BOOM) and any digits carried to the next BOOM. By concatenating (stringing together) these one-bit adders, we can make an adder to add an arbitrary length binary number.
To do this, connect the carry in of the first stage to ground, as no bits are carried in from before the least significant bit. Then connect the carry out of the first stage to the carry in of the next, and so on for as many stages as you like.
Below is the layout for a 4-bit adder:
Bear in mind that the result will only be complete when the carry output have registered in each of the stages in turn. This ripple effect is why this kind of adder is called a ripple carry adder. This takes a small amount of time, and for large (32-bit or more) adders it may take several hundred nanoseconds, which may be a problem if high speed is needed.
There are much faster adders that can be made that don't have a ripple effect, such as carry lookahead adders.
The 4008 IC is a 4-bit full adder, which can in turn be concatenated with others to provide any length of number.