This page describes material that is not in the book.
Chapter 14 of Code demonstrates how a digital adder can be built from logic gates. Chapter 15 then continues the discussion showing how such an adder became one of the crucial components of early computers in the 1930s, and how later developments allowed logic gates to be built from vacuum tubes, transistors, and eventually, integrated circuits.
Regardless how logic gates are built, they always have a finite propagation delay. This is the time it takes for a change in an input to be reflected in the output. When outputs of logic gates become inputs to other logic gates, the propagation delay of each individual gate affects the overall speed of the circuit.
The 8-bit adder shown towards the end of Chapter 14 is constructed from a series of cascaded one-bit adders. Each bit potentially generates a Carry value that is required for the next more significant bit. This is known as a “ripple carry.” The overall speed of the adder is the product of the propagation delay of the one-bit adder and the number of bits.
Towards the end of Chapter 15, mention is made of a “look-ahead carry generator,” also known as a “carry lookahead adder” or a “fast adder” (such as in this Wikipedia article). This is a circuit that takes a different approach to determining each Carry bit, and the result is an overall increase in speed.
In general, sometimes a circuit can be made faster by removing logic gates to make it simpler and more efficient. But other times, making a circuit faster requires additional logic gates. This is the case with the look-ahead carry generator. These additional logic gates are required for a faster calculation of the Carry bits.
Here is the one-bit full adder built from two half adders, each of which requires an XOR gate for the sum and an AND gate for the carry:
As with the adders shown in Chapter 14, you can click on the square input buttons at the left and on the top to change the results shown at the right.
This circuit can also be shown using the separate NAND, OR, and AND gates that make up each XOR gate:
This circuit is just slightly different from the One-Bit Full Adder on the Chapter 14 page. The OR and NAND gates that contribute to the XOR gate have been switched around so that the NAND gate is now above the OR gate. It makes no difference in how the circuit works. It's really just a cosmetic difference that will help with a variation of this circuit coming up.
In either case, all the combinations of inputs are summarized by this logic table, where CI stands for Carry In and CO stands for Carry Out:
| Inputs | Outputs | |||
|---|---|---|---|---|
| A | B | CI | Sum | CO |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
As a first step in building a look-ahead carry generator, it's useful to analyze the different ways that a Carry Out bit can become 1:
In some cases, the Carry Out bit is generated, which means that it results from values of the A and B inputs. Specifically, Carry Out is generated if both A and B are 1.
In other cases, the Carry Out bit is propagated, which means that it results from a Carry In value of 1 in combination with the A and B inputs. This table shows the cases where the Carry Out bit is generated and propagated:
| Inputs | Outputs | Carry Type | ||||
|---|---|---|---|---|---|---|
| A | B | CI | Sum | CO | Generate | Propagate |
| 0 | 0 | 0 | 0 | 0 | ||
| 0 | 1 | 0 | 1 | 0 | ||
| 1 | 0 | 0 | 1 | 0 | ||
| 1 | 1 | 0 | 0 | 1 | ✓ | |
| 0 | 0 | 1 | 1 | 0 | ||
| 0 | 1 | 1 | 0 | 1 | ✓ | |
| 1 | 0 | 1 | 0 | 1 | ✓ | |
| 1 | 1 | 1 | 1 | 1 | ✓ | ✓ |
Let's define two values named G (for Generate) and P (for Propagate):
G is 1 if both A and B are 1, which indicates when a Carry Out value of 1 is generated:
P is 1 if either A or B is 1:
The value P by itself does not indicate that the Carry bit is propagated; instead, the Carry bit is propagated if both P and Carry In are 1.
The final column in this table shows how the Carry Out bit can be calculated from G, P, and Carry In:
| Inputs | Outputs | Carry Calculation | |||||
|---|---|---|---|---|---|---|---|
| A | B | CI | Sum | CO | G = A AND B | P = A OR B | CO = G OR (P AND CI) |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Interestingly, the previous one-bit adder does not calculate the Carry Out bit exactly like the final column of this table indicates, but the circuit can be modified slightly so that it does:
What's interesting is that this circuit is a little speedier than the previous circuit. The Carry Out is now calculated through a chain of the three logic gates at the bottom of the circuit rather than four logic gates used in the previous circuit. Progress is already being made!
Suppose you have four one-bit adders that you want to use to add a pair of four-bit binary numbers. Each of the four addition operations can be can be associated with a subscript: 0 for the least significant bit, 1 for the next bit, then 2, and 3 for the most significant bit.
For each of the four one-bit adders, the Carry Out bit can be calculated using the formula shown in the previous table:
But the Carry Out bit of each bit adder becomes the Carry In bit for the next most signficant bit, so the Carry In bits can also be calculated:
Notice that the formula for CI2 ends with CI1, but the line above it indicates that CI1 is equal to a combination of G0, P0, and CI0, so you can rewrite that formula like this:
This formula no longer requires CI1, which means that CI2 can be calculated without the previous Carry bit.
At this point, using the words OR and AND become a little awkward, and it's best to switch to the algebraic notation where + is used for OR and · is used for AND. Each of the Carry In bits can be shown as a combination of the various G and P values and CI0. If only a four-bit addition is desired, then CI0 is normally set to 0, but let's make it more generalized:
For more bits, the pattern continues, but let's stop here.
The following circuit contains both a four-bit adder with a ripple carry, and a four-bit adder with look-ahead circuitry. The four expressions shown above for the Carry In bits of the look-ahead adder are realized with OR and AND gates at the bottom of the figure.
Use the square buttons at the top to set two four-bit values. The least-significant bit is on the right, and the most-significant bit is on the left. You can also select a Carry In value at the far right.
Two rows of circular lights show the result. The top row shows the result of the adder with the ripple carry, while the bottom row displays the result of the look-ahead carry. The circles at the far left display the final Carry bit.
This circuit has been set up so that each logic gate has a propagation delay of 250 milliseconds or 1/4 second. This highlights the difference between the two circuits.
The logic gates above the top row of result lights are dedicated to the adder using the ripple carry. This circuitry is the same as the most recent one-bit adder you saw. Notice that the Carry Out value becomes the Carry In value of the next more significant bit.
The top four gates under the pairs of buttons are also shared by the look-ahead carry adder. These gates perform the sum of the two bits, and also provide the crucial G and P signals. Those three signals — the Sum, G, and P — are the vertical wires to the left of the result lights.
The three gates below the second row of results add the Carry bit to the sum, but for all bits except the first, that's provided by the complex array of OR and AND gates at the bottom.
For the most dramatic display of the speed difference, set the top row of buttons to 1111 and then press the CI button at the far right.
(Thanks to Elyjah Kiehne of SOU for detecting an error in this circuit!)