Difference between revisions of "Binary Adders"

From Coder Merlin
Line 81: Line 81:


== Ripple Carry Adder ==
== 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?
[[File:Four-bit Ripple Carry Adder.png|thumb|link=|Four-bit 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? By '''cascading''' four adders such that the carry ''output'' of the prior adder feeds the carry ''input'' of the subsequent adder we can add two four-bit numbers.  This concept can be easily extended to an arbitrary number of bits.


== Key Concepts ==
== Key Concepts ==

Revision as of 10:28, 30 July 2019

Within these castle walls be forged Mavens of Computer Science ...
— Merlin, The Coder
Boy in sailor suit with blackboard with math

Prerequisites[edit]

Introduction[edit]

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[edit]

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
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.



ObserveObserveIcon.png
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[edit]

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:

Single-bit full-adder
Inputs Outputs
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.

ObserveObserveIcon.png
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[edit]

Four-bit 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? By cascading four adders such that the carry output of the prior adder feeds the carry input of the subsequent adder we can add two four-bit numbers. This concept can be easily extended to an arbitrary number of bits.

Key Concepts[edit]

Key ConceptsKeyConceptsIcon.png
  • 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.

Exercises[edit]

Template:W1017-Exercises

References[edit]

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