|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
THE FULL ADDER
|
0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | |||||||
0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | |||||||
+ 0 | + 1 | + 0 | + 1 | + 0 | + 1 | + 0 | + 1 | |||||||
0 | 1 | 1 | 10 | 1 | 10 | 10 | 11 |
The reason the Full-Adder can perform 8 different calculations lies in the fact that 2^3 = 8: the 2 is because a bit has 2 possible values (0 or 1), and the 3 is because there are 3 single-bit numbers to be added.
TRUTH TABLE | |||||
---|---|---|---|---|---|
Input | Output | ||||
A | B | Cin | Sum | Cout | |
0 | 0 | 0 | 0 | 0 | |
0 | 0 | 1 | 1 | 0 | |
0 | 1 | 0 | 1 | 0 | |
0 | 1 | 1 | 0 | 1 | |
1 | 0 | 0 | 1 | 0 | |
1 | 0 | 1 | 0 | 1 | |
1 | 1 | 0 | 0 | 1 | |
1 | 1 | 1 | 1 | 1 |
The relationship between the Full-Adder and the Half-Adder is similar to the relationship between the amino acid and the gene, respectively. Whereas amino acids are coded from genes, the amino acid is what the body actually uses to create proteins. Similarly, whereas the Full-Adder is constituted of two Half-Adders, the Full-Adder is the actual block that engineers use to create the arithmetic circuits that go in everyday machines and computers. The reason is simple: long chains of Full-Adders, like long chains of amino acids, are easy to build. And some chains of Full-Adders are used to perform addition, some to perform subtraction, some to perform multiplication, and some to perform division. Circuit 2 below is an example of a chain of 4 Full-Adders used to perform 4–bit addition.
The construction of a Full-Adder circuit is simple: all you need are two Half-Adders and an OR gate. This viewpoint makes the analysis of the Full-Adder very simple and straightforward. The Full-Adder above, for instance, has three input ports (A, B, Cin) and two output ports (Sum, Cout). However, between the inputs and the outputs are a number of intermediate ports through which the first Half-Adder connects to the second Half-Adder. To understand how the inputs (A, B, Cin) control the outputs (Sum, Cout) therefore, we need to analyze the intermediate ports: which we shall call T1, T2, X1 and X2, as shown in figure 1.
Figure 1
We start with the ports closest to the inputs —which are both T1 and T2. Observe that the only object between T1 and the inputs A and B is an XOR gate. So we say that T1 = A B, where
is the symbol for the XOR function. Similarly, notice that the only object between T2 and the inputs A and B is an AND gate. And so we say T2 = A B, where is the symbol for the AND gate.
Now we move to the next set of intermediate ports, which are X1 and X2. As in the previous paragraph, we notice that X1 is a function of T1 and Cin through an XOR gate. So we write X1 = T1 Cin. Similarly, we observe that X2 = T1 Cin.
At this point we only have two signals left to compute: Sum and Cout, which happen to be the outputs. Sum is just X1; so we say Sum = X1. Cout, however, is a function of X2 and T2 through an OR gate; so we say Cout = X2 + T2, where + is the symbol for the OR gate.
This is a good point for us to summarize what we have accomplished so far before proceeding to the final stretch. So let's recap:
T1 = A ![]() | was our first observation | |
T2 = A B | was our second observation | |
X1 = T1 ![]() | was our third observation | |
X2 = T1 Cin | was our fourth observation | |
Sum = X1 | was our fifth observation | |
Cout = X2 + T2 | was our sixth observation |
But we can't leave the answer like that. We have to use algebraic substitution to give the outputs (Sum and Cout) in terms of the inputs (A, B, Cin). So let's do some basic algebra to simplify our result, starting with Sum:
Sum = X1 | ||||
Sum = T1 ![]() |
after substituting for | X1 = T1 ![]() |
||
Sum = (A ![]() ![]() |
after substituting for | T1 = A ![]() |
Now let's simplify Cout:
Cout = X2 + T2 | ||||
Cout = (T1 Cin) + T2 | after substituting for | X2 = T1 Cin | ||
Cout = (T1 Cin) + (A B) | after substituting for | T2 = A B | ||
Cout = ((A![]() |
after substituting for | T1 = A ![]() |
Hence, our verification shows that the switch function for the Full-Adder is the compound equation
Sum = (A B)
Cin
Cout = ((A B) Cin) + (A B).
We're done!
A note of caution before we dive in: Unless you are already very good at creating truth tables, it is important that you follow along with pencil and paper by filling your own tables as we go.
Getting the truth table from the switching function is straightforward: we just plug 0s and 1s into the equation. Let's start with Sum = (A B) Cin. Since the output Sum depends on three inputs (A, B, Cin), we need a table with 2^3 rows: The 2 means we have two possible values (0 or 1) and the 3 means we have three different variables (A, B, Cin). Since 2^3 = 8, we will fill the 8 rows of the table by counting from 0 to 7 in binary (for a more intuitive explanation on how to build truth tables, see the Half-Adder article).
A | B | Cin | Sum | |
---|---|---|---|---|
0 | 0 | 0 | ||
0 | 0 | 1 | 0 | 1 | 0 |
0 | 1 | 1 | 1 | 0 | 0 |
1 | 0 | 1 | 1 | 1 | 0 |
1 | 1 | 1 |
Notice that I took the liberty of adding the Sum column. This is because the point of the table is to see how different values of the inputs affect the output. We will solve for Sum by applying a process of combining two inputs at a time. The process is not really necessary here, but it is good practice. So let's solve for A B (and let's call the answer T1). Recall that the output of the XOR gate is true only when one of the inputs is true.
A | B | Cin | T1=A![]() |
Sum | |
---|---|---|---|---|---|
0 | 0 | 0 | 0 | ||
0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 |
0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
1 | 1 | 1 | 0 |
Table 1
Note that the grayed out values (Cin) are not use in the computation.
Now that we have computed A B, let's solve for Sum which is (A
B)
Cin or simply T1
Cin.
A | B | Cin | T1=A![]() |
Sum | |
---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | |
0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
1 | 1 | 1 | 0 | 1 |
Table 2
Now let's repeat the same process for Cout. Since Cout = ((A B) Cin) + (A B), we have three different input variables (A, B, Cin), which means we need 2^3 rows. The 2 means we have two possible values (0 or 1) and the 3 means we have three different variables (A, B, Cin). Since 2^3 = 8, we will fill the 8 rows of the table by counting from 0 to 7 in binary.
A | B | Cin | Cout | |
---|---|---|---|---|
0 | 0 | 0 | ||
0 | 0 | 1 | 0 | 1 | 0 |
0 | 1 | 1 | 1 | 0 | 0 |
1 | 0 | 1 | 1 | 1 | 0 |
1 | 1 | 1 |
Table 3
As we did in solving for Sum, we will solve for Cout by combining two variables at a time. As in regular algebra, the rule here is to eliminate the parentheses. Consequently, we start by computing A B and call it T1. Recall, again, that the output of the XOR function is asserted (equals to 1), only when one of the inputs is asserted; otherwise, the output is OFF (equals to 0). Also, we gray out the variables we are not using.
A | B | Cin | T1=A![]() |
Cout | |
---|---|---|---|---|---|
0 | 0 | 0 | 0 | ||
0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 |
0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
1 | 1 | 1 | 0 |
Table 4
Now we are going to add Cin into the mix to eliminate those parentheses: (A B) Cin: T1 Cin:
A | B | Cin | T1=A![]() |
X2=T1Cin | Cout | |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | ||
0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 |
1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
1 | 1 | 1 | 0 | 0 |
Table 5
The next pair of parentheses to tackle is (A B). So
A | B | Cin | T1=A![]() |
X2=T1Cin | T2=AB | Cout | |
---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | ||
0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
1 | 1 | 1 | 0 | 0 | 1 |
Table 6
Now all we have left is to fill the Cout column. From Cout = ((A B) Cin) + (A B), we have used the process of combining two variables at a time to arrive at Cout = X2 + T2. You don’t remember the steps? First we combined A
B and called the result T1 (column 4 above). Second we combined the result of A
B with Cin to get X2 (column 5). Third, we solved for (A B) and called it T2 (column 6). If this quick recap did not help, review the tables you created as you followed along with us. If you did not follow along with your own tables, now is a good time to go back and follow with us.
Below we fill the Cout table.
A | B | Cin | T1=A![]() |
X2=T1Cin | T2=AB | Cout =T2+X2 | |
---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | |
0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
1 | 1 | 1 | 0 | 0 | 1 | 1 |
Table 7
Our final step is to have a table with only the input and the output variables — no intermediate variables. Such a table is shown near the Full-Adder applet at the top of this page. If your professor asks you to show your work, then you can turn in Table 2, Table 7, and the table at the top of the page.