ladderAIDigital logic
Building a four-bit adder out of NAND gates
A NAND gate wires into NOT, AND, OR and XOR. Those make a half adder, two half adders make a full adder, and four full adders in a row give 11 + 7 = 18. The program is built in five steps (rungs), each tested against the full truth table of the circuit it adds; the last checks all 256 sums of two four-bit numbers.
Open in the workbenchDownload .vivOutputs below are from the site build’s run; Run all runs it again in your browser.
Look inside this program
- Atlas
The program’s map: every function and which calls which.
There’s no recorded run of this program yet.
Bits here are the numbers 0 and 1, a gate is a function of its inputs, and a wire is a variable holding a bit. That models a circuit at the level of logic gates, above transistors and below an instruction set.
The last rung draws three pictures: the wiring of one column (one full adder), a timing diagram of that column as its three inputs count from 000 to 111, and the sum 11 + 7, where the carry has to pass through all four columns, one full-adder carry delay (two gate levels) each. That delay is what makes this design slow, and it is what a carry-lookahead adder removes.
NAND, and the three gates wired from it
NAND is an AND with its output inverted: . Tie its two inputs together and it inverts. Invert its output and it ANDs. Invert both inputs and De Morgan's law, , makes it an OR.
nand(0,0) is 1 because and the bar flips it; the other three rows follow the same way. A two-input gate has only four possible inputs, so a test of all four rows checks it completely.
new: nand, gate_not, gate_and, gate_or
Rung 1 tests 2 of 2 pass
- NAND is the AND of its inputs, inverted, in all four rows (passes)
- NOT, AND and OR built from NAND agree with the operations they name (passes)
XOR: on when the two inputs differ
: at least one input is on, and not both. Three of the gates above, in series.
Adding two bits gives a sum that is their XOR and a carry that is their AND, so XOR is the last gate an adder needs.
new: gate_xor
Rung 2 tests 1 of 1 pass
- XOR is on exactly when the two bits differ (passes)
A half adder: two bits in, a sum and a carry out
, , , . In one column that last one is a 0 with a 1 carried, so the sum bit is and the carry is : an XOR and an AND, side by side.
It is half an adder because it has nowhere to put a carry coming in. The test reads the two outputs as and asks for .
new: half_sum, half_carry
Rung 3 tests 1 of 1 pass
- a half adder's two outputs, read as 2c + s, are a + b (passes)
A full adder: three bits in, because a column has a carry
A column of a longer addition takes the two bits and whatever the column to its right carried. Add and with one half adder, add the carry to that sum with a second, and the column carries if either half adder did:
Three inputs is eight rows, and the test walks all eight.
new: full_sum, full_carry
Rung 4 tests 1 of 1 pass
- a full adder's outputs, read as 2c + s, are a + b + cin, in all eight rows (passes)
Four full adders in a row: a four-bit adder
Each column's carry out is the next column's carry in. Bit 3 cannot settle until bit 2 has, which cannot settle until bit 1 has, so the delay grows with the width. That is why this is called a ripple-carry adder, and why a carry-lookahead adder computes the carries instead of passing them along.
The test checks all 256 pairs of four-bit numbers, the fifth bit (the carry out) included.
new: ripple_add, pin_hi, pin_lo, net_x, net_y, net_values, live_x, live_y, step_x, step_y
Rung 5 tests 2 of 2 pass
- every one of the 256 four-bit sums comes out right, carry included (passes)
- 11 + 7 is 18: the low four bits are 0010 and the carry is 1 (passes)
Printed
a + b + c_in on this row 0
The ones column first, with nothing carried in