Half adders and full adders

The full adder's expressions, building it from half adders, and chaining full adders into a ripple carry adder.

A8.7Boolean algebra and logic circuitsA level20 min

Every calculation the robot does, from adding a distance to a position to working out a motor speed, ends up in the processor's arithmetic logic unit as binary addition done by gates. At GCSE (lesson F9.2) you built a half adder, which adds two bits. This lesson finds out why that is not enough, builds a full adder, and chains full adders together to add whole binary numbers.

The half adder, again

A half adder has two inputs, A and B, and two outputs: the sum S and the carry C.

S is 1 when the inputs differ, so S = A ⊻ B. C is 1 only when both are 1, so C = A ∧ B. In AQA notation, S = A ⊕ B and C = A · B. It needs one XOR gate and one AND gate.

Why "half"?

Add two binary numbers by hand and look at any column except the rightmost:

  carry in   1 1 0 0
             0 1 1 0      (6)
           + 0 1 1 1      (7)
           ---------
             1 1 0 1      (13)

The second column from the right adds 1 + 1 and a carry of 0 from the column before; the third adds 1 + 1 and a carry of 1. Every column except the first has three bits to add: A, B and the carry in from the column to its right. A half adder has only two inputs, so it can only do the first column. It does half the job.

The full adder

A full adder has three inputs, A, B and Cin (carry in), and two outputs, S and Cout (carry out). Adding three bits gives an answer from 0 to 3, which is two bits: Cout is the twos bit and S is the units bit.

S is 1 when an odd number of inputs are 1: S = A ⊻ B ⊻ Cin. Cout is 1 when two or more inputs are 1: Cout = (A ∧ B) ∨ (Cin ∧ (A ⊻ B)).

The Cout expression reads: carry out if A and B are both 1, or if exactly one of them is 1 and there is a carry in. A Karnaugh map of the Cout column gives another correct form, (A ∧ B) ∨ (A ∧ Cin) ∨ (B ∧ Cin), "any two of the three".

Two half adders and an OR gate

The expressions show how to build a full adder from the parts you have.

1. The first half adder adds A and B, giving a partial sum A ⊻ B and a carry A ∧ B.
2. The second half adder adds that partial sum to Cin, giving the final sum A ⊻ B ⊻ Cin and a second carry Cin ∧ (A ⊻ B).
3. The two carries can never both be 1 (if A and B are both 1, the partial sum is 0), so an OR gate combines them into Cout.

def half_adder(a, b):
    return a ^ b, a & b            # (sum, carry)

def full_adder(a, b, cin):
    s1, c1 = half_adder(a, b)
    s, c2 = half_adder(s1, cin)
    return s, c1 | c2              # (sum, carry out)

print("A B Cin | Cout S")
for a in [0, 1]:
    for b in [0, 1]:
        for cin in [0, 1]:
            s, cout = full_adder(a, b, cin)
            print(a, b, cin, "  |", cout, "  ", s)

Run this in the simulator

Adding whole numbers: the ripple carry adder

To add two 4-bit numbers, use four full adders, one per column. Each adder's Cout is wired to the Cin of the adder for the next column to the left. The rightmost adder has its Cin set to 0 (or it can be a half adder). The final Cout is the carry out of the whole addition.

This is a ripple carry adder, because the carry ripples from right to left through every adder. Here is 0110 + 0111, column by column from the right:

Reading S from column 4 down to column 1 gives 1101, which is 13, with a final carry out of 0.

If the final carry out is 1, the answer needs five bits. In an unsigned 4-bit register that is an overflow: 1111 + 0001 gives 0000 with a carry out of 1.

The ripple is also the design's weakness. Every gate takes a little time to settle, and the top bit's answer is not ready until the carry has passed through every column below it. A 64-bit ripple carry adder waits for 64 full adders, which is why real processors use faster designs that work out the carries in parallel.

Task: a 4-bit ripple carry adder

Write three functions. Every bit is the integer 0 or 1.

• half_adder(a, b) returns a tuple (sum, carry).
• full_adder(a, b, carry_in) returns a tuple (sum, carry_out), and must be built from two calls to half_adder and an OR.
• add4(x, y) takes two strings of four characters, each "0" or "1", with the most significant bit first. It adds them with a ripple of full_adder calls, starting from the rightmost bit with a carry in of 0, and returns a tuple (total, carry): total a 4-character string of the sum bits, most significant first, and carry the final carry out (0 or 1).

Your program may not use int(), bin(), format() or sum(). For each pair ("0110", "0111"), ("1011", "0110"), ("1111", "0001") and ("0101", "1010"), in that order, print one line in exactly this form:

0110 + 0111 = 1101 carry 0

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def half_adder(a, b):
    return 0, 0

def full_adder(a, b, carry_in):
    return 0, 0

def add4(x, y):
    return "0000", 0

Challenges

1. Change add4 to add numbers of any length, and add two 8-bit numbers.
2. Count the gates in your 4-bit adder, counting XOR, AND and OR as one gate each.
3. Two's complement subtraction A minus B is A plus (NOT B) plus 1. Use your adder with a carry in of 1 to subtract 0011 from 0110.