Now, we're ready to build a circuit that can add two numbers,
and this will be representative of the kind of
calculations that we want to do with our computing devices.
Let's make an adder. So we're going to do an 8-bit adder.
And so what we want to do is say that we have two binary integers x and y,
in this, case eight bits and we want to compute the value of their sum.
Here's an example and we've done binary addition in many cases before.
So this is 00010111 so that's 16 plus four plus two plus one is 23,
and then the other one is 32 plus 16 plus one, 49.
So 23 plus 49 is 72.
That's what we're trying to compute here.
What we'll do is in our adder circuit,
we'll take inputs and we're going to need those inputs all the way through the circle.
At the top is the first binary number 00010111,
which is 23 and then the next input is the bottom binary number 00110001, that's 49.
That's our inputs to the circuit and,
again, usually inputs come at top or left.
Then the outputs come out on the bottom in this case 01001000, which is 72.
We want to build a circuit that has this behavior.
We're going to ignore
overflow because actually if the number gets too big then it would carry out a one.
We could catch that but we're going to ignore it for now.
In general, this is with all the inputs labelled symbolically,
we're going to have 8-bit numbers x_7 down x_0,
y_7 down to y_0.
Our inputs and our outputs are z_7 down to z_0,
and then we're computing the sum symbolically shown at the bottom left,
and we're going to ignore the carry on.
So we just learned how to implement a circuit that can implement any binary function.
And this is a binary function so one thing that
we might consider doing is build a truth table for each output bit.
So for 8-bit adder,
well we've got 16 inputs and then we've got,
if you count the carry, nine output bits.
There's way too many rows.
It's two to the 16 different possibilities of the inputs, 65,000 rows.
That doesn't seem bad saying a real computer you might want to 64, 128-bit adder.
If you were to use this method for that kind of application,
you'd have two do the 256 rows,
and we've already calculated that bigger than the number of electrons in the universe.
What Shannon and Boulle tell us is that it's possible to build such a circuit but
not necessarily the most efficient way so we're going to look at
a much more efficient way to build an adder circuit.
It's a very simple idea that corresponds to what we do when we're trying to add.
We're going to do one bit at a time.
What do we need to do to implement the carry bit when we're adding the first two bits.
Well, the carry bit if x,
y and the carry n are zero,
then it's going to be zero.
Whereas if it's 001, it's going to be zero.
It's only going to be one if we have two ones or three ones.
Does that sound familiar?
Well, it is and we'll see in a second.
And similarly, the sum bit,
it's going to be one if exactly one of them
are one or if all three are one and then there's a carry out.
All three are one, the sum is one and there's carry out.
Those are the functions that we need to compute.
But those are the functions that we now.
The carry bit is the majority function,
the sum bit is the odd parity function.
We already have the circuits that we need to compute one bit at a time,
compute the carry and the sum.
All we need to do is connect those circuits
together to get our job done and that's what this does.
At the top is a majority function for each bit.
At the bottom is an odd parity function or the sum for each bit.
Both of those functions take three inputs.
The three inputs are our input bits x and y and a carry bit,
and the carry bit comes from the circuit to the right,
starting with a zero over at the left.
Then the output of the majority function,
I'm sorry, over at the right.
The output of the majority function on the rightmost is routed through the middle
and up over to be carry input into the second most from the right and so forth.
It carries or routed out and up to the next one to its left.
These one bit adders are chained together with the carry which ripples through.
This design is called a carry ripple adder.
Obviously, the same design extends to any number of bits,
and that's our adder circuit.
So here's our adder circuit magnified.
And we take the covers off to reveal the circuits inside that we've already talked about.
On the top is majority circuit for each bit,
at the bottom is odd parity for each bit.
If you examine this closely,
you can see the sums being computed and the carries coming out exactly as in our example.
A circuit for adding two 8-bit numbers
where we can see the function of every switch in the circuit.
This example illustrates, again,
the lessons of software design that really applied to hardware.
The interface gives the behavior.
The circuit the implementation gives the details of how to build
it and we just exploit our understanding of the behavior at each level.
In order to implement the add,
we needed to implement a Boolean function.
We knew how to implement those Boolean functions.
We start with a controlled switch.
We build gates. From the gates,
we can implement Boolean functions and after a while, we have an adder.
Next, we'll look at how to incorporate the adder into
an arithmetic logic unit and eventually to
an entire central processing unit in the next lecture.
This approach vastly simplifies,
not just vastly simplifies,
it makes possible the design of complex computer systems.
Not only that, it enables the use of new technology at any layer.
If we want to work hard on developing a better adder,
we can plug that in at any level.
In fact, computers today use a more efficient adder.
This one takes time proportional to the number of bits to ripple the carries through.
It's possible to cut down on that time by log factor.
Next, we'll look at the arithmetic logic unit.
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Kevin WaynePhillip Y. Goldman '86 Senior Lecturer
