Adder circuit

Loading...

Do curso por Princeton University

Computer Science: Algorithms, Theory, and Machines

64 classificações

Princeton University

Computer Science: Algorithms, Theory, and Machines

64 classificações

This course introduces the broader discipline of computer science to people having basic familiarity with Java programming. It covers the second half of our book Computer Science: An Interdisciplinary Approach (the first half is covered in our Coursera course Computer Science: Programming with a Purpose, to be released in the fall of 2018). Our intent is to demystify computation and to build awareness about the substantial intellectual underpinnings and rich history of the field of computer science. First, we introduce classic algorithms along with scientific techniques for evaluating performance, in the context of modern applications. Next, we introduce classic theoretical models that allow us to address fundamental questions about computation, such as computability, universality, and intractability. We conclude with machine architecture (including machine-language programming and its relationship to coding in Java) and logic design (including a full CPU design built from the ground up). The course emphasizes the relationships between applications programming, the theory of computation, real computers, and the field's history and evolution, including the nature of the contributions of Boole, Shannon, Turing, von Neumann, and others. All the features of this course are available for free. No certificate will be offered upon completion.

Na lição

COMBINATIONAL CIRCUITS

Starting with a few simple abstractions (wires that can carry on/off values and switches that can control the values carried by wires), we address in this lecture the design of the circuits that implement computer processors. We consider gates that implement simple logical functions and components for higher-level functions, such as addition. The lecture culminates with a full circuit for an arithmetic/logic unit.

Boolean algebra13:34

Digital circuits21:54

Adder circuit8:00

Arithmetic/logic unit7:19

Conheça os instrutores

Robert Sedgewick
William O. Baker *39 Professor of Computer Science
Computer Science
Kevin Wayne
Senior Lecturer
Computer Science

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.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2018 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play