Binary Adders

Within these castle walls be forged Mavens of Computer Science ...

— Merlin, The Coder

Boy in sailor suit with blackboard with math

Prerequisites

• W1011 Number Systems
• W1012 Alternative Base Addition
• W1013 Boolean Algebra
• W1014 Logic Gates
• W1015 Bitwise Operations
• W1016 Logic Composition

Introduction

One of the most fundamental operations performed by computers, aside from the logical operations that we've already discussed, is the arithmetic operation of addition.

Half-Adder

Let's consider what's required to add two, single-bit binary integers. We'll need one bit to represent the sum of the integers, and another to handle the carry. Representing this in the form of a truth table yields:

Single-bit half-adder

Inputs		Outputs
$a$	$b$	$C_{out}$	$S$
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

This is formally termed a half-adder, a logic circuit capable of adding two bits.

Observe

Observe, Ponder, and Journal: Section 1

1. What truth table do you recognize that produces the output of the Carry column?
2. What truth table do you recognize that produces the output of the Sum column?

Full-Adder

In order to add two single-bit binary integers PLUS a carry, we need an adder capable of adding three single-bit binary numbers. Again, we'll need one bit to represent the sum of the integers, and another to handle the carry. Representing this in the form of a truth table yields:

Inputs			Outputs
$a$	$b$	$c_{in}$	$C_{out}$	$S$
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

This is formally termed a full-adder, a logic circuit capable of adding three bits.

Observe

Observe, Ponder, and Journal: Section 2

1. What do you notice about the relationship between the first-half (top four rows) of the full-adder as compared to all of the rows of the half-adder?
2. Why is this true?

Ripple Carry Adder

We've learned that a half-adder can add two bits and full-adder can add three bits. How can we add a multi-bit number such as a 16-bit word?

Key Concepts

Key Concepts

• A half-adder is a logic circuit capable of adding two bits and output a carry bit and a sum bit.
• A full-adder is a logic circuit capable of adding three bits and output a carry bit and a sum bit.

References

• Adder (Wikipedia)
• Schocken, Simon and Nisan, Noam. The Elements of Computing Systems. MIT Press, 2005.