yeolyi.comSeongyeol's CS

Half Adder

So far we have used logic gates to build circuits that select and route signals. This time, let’s combine gates to build a circuit that does addition.

The calculator app on your phone handles a sum like 999,999 + 888,888 in an instant. Yet at its core, that calculator is also nothing more than a combination of the logic gates we have learned.

Decimal addition

How do we usually add? Let’s calculate 179 + 287.

  11  <-- (carry)
  179
+ 287
-----
  466
  1. 9 + 7 = 16, so write 6 and carry 1.
  2. 1 + 7 + 8 = 16, so write 6 and carry 1.
  3. 1 + 1 + 2 = 4.

We work one digit at a time from the right, and each digit produces two things:

But computers only know 0 and 1. How do we carry this idea over to a world of 0s and 1s?

Binary addition

Computers write numbers in binary, which uses only the two digits 0 and 1. Each place is worth twice the one before it. Adding works the same way as in decimal. Let’s calculate 310 + 110 in binary.

  11   <-- (carry)
   11
+  01
-----
  100
  1. 1 + 1 is 102. Write 0 in this place and carry 1 to the next.
  2. 1 (carry) + 1 + 0 = 102, so write 0 in this place and carry 1 to the next.

The result, 1002, is 4 in decimal. Here too, each place produces a Sum and a Carry.

Half adder

Let’s start with the simplest case, adding two one-digit binary numbers, and turn it into a circuit. There are four possible cases:

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10

In the last case, Sum is 0 and Carry is 1. Looking at the truth table, Sum is 1 only when A and B differ, and Carry is 1 only when A and B are both 1.

SumCarry
0000
0110
1010
1101

Carry is A ∧ B. Sum is “A or B is 1, but not both”, so it is (A ∨ B) ∧ ¬(A ∧ B). Turn these expressions into gates and you have a calculator for adding one-digit binary numbers.

Set both A and B to 1. Sum is 0 and Carry is 1.

This circuit is called a half adder. From now on, to keep things simple, we will wrap it into a single block labeled HALF ADDER.

Wrapping up

A half adder only handles adding two one-digit binary numbers. In real addition, though, we also have to add the carry coming up from the place below. In the next post, let’s build a full adder that solves this.

Challenge

Using three half adders, build a circuit that adds three one-digit binary numbers A, B, and C. Output the result (0~3) as two bits: the 2s place and the 1s place.