Skip to content

Demo 5.2: Half Adders, Full Adders and Carry

Everything designed so far has been a circuit that answers a question. Is this code valid BCD, should this segment be lit, is this combination the one we are watching for. The answers were true or false and nothing more was expected of them.

This one does arithmetic, and that changes what you can do as a designer. You no longer have to be told what the output should be, because you can work it out. If the circuit says 1 + 1 is 1 then the circuit is wrong, and no specification document is needed to settle it.

The subject is also, for the first time, unavoidably about time. A seven-segment decoder is seven independent functions and they all settle at once. An adder is a chain, and the top of a sum cannot be worked out until the bottom of it has been. That has a large effect on speed, and the last part of this demonstration measures how large.

Adding two bits has four cases and three of them fit in one bit: 0 + 0 is 0, 0 + 1 is 1, 1 + 0 is 1. The fourth is 1 + 1, which is 2, and 2 does not fit in one bit. In binary it is 10, so the answer needs a second output to hold the twos column. That second output is the carry, and every complication in this demonstration comes from it.

The half adder gives you a four-row truth table and asks you to name the gate behind each output column before it will draw anything. There are six candidates and all six stay on offer. Wrong answers are explained by pointing at the row where they fail rather than just refused.

The full adder takes three bits instead of two and is shown twice: as two half adders with an OR gate, which is how it is built, and at gate level, which is what it reduces to. Toggle between them with the inputs untouched and the outputs do not move. There is also a panel that hides the truth table and asks you to fill in all eight rows yourself.

Four bits at once puts four full adders in a row. Set the two numbers with the bit toggles, or use the presets. Then press Watch the carry travel and step the carry along the chain by hand. Take this part slowly. The delay table underneath extrapolates what you have just watched out to 64 bits.

Half Adders, Full Adders and Carry

Arithmetic out of logic gates. Two bits, then three, then eight.

Add two bits and see what happens.

  • Three of the four sums fit in one bit.
  • The fourth does not: 1 + 1 is 2, which is 10 in binary, so the answer needs a second output to hold the twos column.
  • That second output is the carry, and every adder in this demonstration exists to deal with it.
Two bits in
1 + 1 = 2binary 10
ABSumCarryreads as
00000 + 0 = 00
01100 + 1 = 01
10101 + 0 = 01
11011 + 1 = 10
The Sum column

Read it downwards: 0 1 1 0. Which single gate turns A and B into that?

The Carry column

Read it downwards: 0 0 0 1. Which single gate turns A and B into that?

Name both columns and the schematic will be drawn. There is no trick to it: each column is a two-variable truth table, and you have already met all six candidates.

Open The half adder and look at the truth table before touching anything. Read the Sum column downwards, then the Carry column, and treat each as a two-variable function in its own right. This is the same approach used for the seven-segment decoder: a row tells you what the answer is, a column tells you what one output pin has to do.

The Carry column is the easier of the two. It is 0, 0, 0, 1, and the only row that needs a carry at all is the one where both bits are 1.

The Sum column is 0, 1, 1, 0, which is 1 when exactly one input is 1. If you pick wrongly you are told which row your gate fails on, which is more useful than being told no. Try OR anyway: it is right for three rows out of four and wrong for the one that matters.

When both are named the schematic appears. Two gates, two shared input pins, and two outputs that are computed independently.

Step 2: Notice what a half adder cannot do

Section titled “Step 2: Notice what a half adder cannot do”

Read the last paragraph on that tab. A half adder produces a carry but has no pin to receive one.

This limitation is the reason for the name. Try to imagine two of them side by side adding a two-bit number: the carry out of the right-hand one has nowhere to go. A half adder can only ever be the rightmost column of a sum, and every other column needs something with a third input.

Open The full adder. It starts on the two half adder construction. Read it as an assembly drawing rather than a circuit: both boxes are the part you just built, unchanged and unopened, and the only new component is the OR gate that collects the two carries.

Stop on the explanation of why an OR gate is enough. The two half adders can never both produce a carry, so the case that would distinguish OR from XOR cannot arise. That is a don’t-care condition, like the six impossible BCD codes, appearing in a different circuit.

Then switch to Gate level with the inputs left alone. Every gate changes and the two output values do not move. One is the circuit as it is assembled, the other is the circuit as the truth table minimises, and both are the same function.

Open Predict the outputs. The eight rows are there with the outputs hidden, and you are asked for the two output bits one row at a time. There is no logic to do: add the three input bits as ordinary numbers, write the total in binary using two bits, and the left-hand bit is the carry.

Finish all eight, then read the two output columns as patterns rather than as answers. Sum is 1 whenever an odd number of the three inputs is 1. Carry out is 1 whenever at least two of them are. Go back to the gate level view and those are the two circuits on the sheet: a chain of XOR gates for the first, and a majority vote for the second.

Step 5: Chain four of them and step the carry

Section titled “Step 5: Chain four of them and step the carry”

Open Four bits at once. The four stages each handle one column of the sum, and the wire in each gap is the key part: it is one wire with two names, called Cout at the right-hand end and Cin at the left-hand end, because it is an output of one stage and an input of the next.

Set the preset Ripple all the way, which is 7 + 1. Now press Watch the carry travel and step through it. Every stage has had its two operand bits since the beginning, and three of the four cannot produce a valid output yet, because a full adder’s outputs are not valid until its carry in is. The chain resolves from right to left one stage at a time.

Try No carries at all and step through that too. Nothing has to travel, but anything reading the result still has to wait the same time, because a carry in that is a final 0 looks the same as one that has not changed yet.

Then set The largest it goes and look at the carry out. It is 1, the four sum bits read 15 when the answer is 31, and this adder has nowhere to put the missing bit. Whether that is an error depends on what is wired to that pin.

The aside at the bottom is the reason the previous step was worth doing slowly.

Adding a stage to a ripple-carry adder adds to the length of the wait, because the new stage cannot start until the one below it has finished. The table follows that out to 64 bits, where the adder on its own would hold a clock down to about 128 MHz.

The solution is in the last paragraph, and it returns to the half adder from Step 1. For column i, the AND of the two bits says the column generates a carry no matter what arrives, and the XOR says it would propagate a carry that did arrive. Write those as G and P and every carry in the word can be expressed in terms of the operand bits alone, with no reference to the stage below, so they can all be computed at once. That is carry-lookahead, and the two gates it is built out of are the two gates you named in Step 1.

Quiz
Select 0/1

Why is a half adder called half an adder?

Quiz
Select 0/1

A full adder is built from two half adders and an OR gate. Why is an OR gate sufficient to combine the two carries?

Concept Match

Match each part of an adder to what it is responsible for

Quiz
Select 0/1

You set a four-bit ripple-carry adder to compute 5 + 10, which produces no carry from any stage. How long does the result take to settle compared with 7 + 1, where a carry travels the whole chain?

Quiz
Select 0/1

A ripple-carry adder is extended from 4 bits to 64 bits. What happens to the worst-case settling time?

Four things to take from this.

  1. Two bits cannot be added into one bit, so an adder has two outputs. Everything else follows from that one overflow.
  2. A full adder is a half adder problem solved twice. Recognising a part you already have inside a part you are about to build is a large part of design work.
  3. Two different-looking circuits can be the same function. The assembled version and the minimised version of the full adder produce identical outputs, and choosing between them is a matter of what you are optimising for.
  4. In a ripple-carry chain, each stage waits for the carry from the one below. The delay is small at four bits and large at 64 bits, and the fix is to compute the carries from the operands rather than from each other.

The circuits here are still combinational: the outputs depend only on what the inputs are doing now, and given long enough they settle to one answer. An adder stores nothing.

Next comes the rest of the standard combinational toolkit, and it is largely about routing rather than arithmetic. Decoders turn a binary code into one active line out of many, encoders do the reverse, and multiplexers and demultiplexers use those ideas to select one signal path out of several. Between them they are how a value gets from where it is to where it is needed, which is the other main job of a digital system.