你将完成的是： 在本课程中， 你将从最底层开始， 构建一个现代计算机系统。 我们将这段激动人心的路程划分成六个需要上交的项目作业， 从构造基本的逻辑门到完成一个功能完全的通用目的计算机。 你将通过一种直接而有效的方式来完成学习，即了解计算机是如何工作的以及他们是如何被设计出来的。 你需要准备的是： 这是一门自包含的课程：所有需要用来完成课程以及构建一台计算机的知识都会包含你的学习经历中。 所以， 我们预设学习者没有学过任何计算机科学及电子工程学， 并欢迎所有层次的学习者。 你不需要任何实际的材料， 你将使用基于软件的硬件模拟器在自己的个人电脑上构建一台计算机， 就像在真正的工业界中， 计算机也是被工程师在电脑上设计构建的。 在你注册这门课程后， 硬件模拟器及其他配套软件将会免费提供。 课程组成： 这门课程包含六个模块， 每个模块包括一系列的视频课程以及一个项目作业。 每个模块大概需要花费两到三个小时来观看视频课程， 以及五到十个小时来完成项目作业。 整个课程将在六周内完成， 不过你也可以根据需要自己把握进度。 谷歌搜索“nand2tetris” 会出现一个与这门课程有关的TED演讲。 关于 以项目为中心的课程： 以项目为中心的课程是被设计来帮助你完成一个有意义的实际项目， 期间会有你的指导者以及一个有着共同目标的学习者的社区来提供指导和建议。 通过活学活用你学习到的新概念， 你将会更有效地掌握课程的内容； 这也是你将你学习到的技能用来改进你的生活或职业生涯的一个开始。 当你完成课程时， 你将完成一个可以引以为豪的用来使用或者分享的项目。
Unit 3.2: Flip Flops
Loading...
来自 Hebrew University of Jerusalem 的课程
依据基本原理构建现代计算机：从与非门到俄罗斯方块（基于项目的课程）
1158 个评分
从本节课中
Memory
Having built the computer's ALU, this module we turn to building the computer's main memory unit, also known as Random Access Memory, or RAM. This will be done gradually, going bottom-up from elementary flip-flop gates to one-bit registers to n-bit registers to a family of RAM chips. Unlike the computer's processing chips, which are based on combinational logic, the computer's memory logic requires a clock-based sequential logic. We will start with an overview of this theoretical background, and then move on to build our memory chipset.
与讲师见面
Shimon SchockenProfessor
Computer Science
Noam NisanProfessor
Computer Science and Engineering
In a previous unit, we discussed how we're dealing with time and
sequential logic in computing systems.
What we'll do in this unit is actually talk about the actual elements,
the chips that will allow us to do, provide this kind of functionality.
So, let us say, let us recall how we started the last unit
where we started the way we deal with time, we add integer time units.
At every time unit t, we want something that can depend with value to compute some
kind of function and the output.
Some kind of function and the value at the previous time unit, the time t minus 1.
So what kind of element do we need in order to provide such a functionality?
Well, the missing element, we need something as a very basic point,
is we need something to actually remember one bit of information,
move one bit of information from time t minus 1 to time t.
This is what we have missing.
We have lots of combinatorial log, logic so
far that can do any kind of manipulations that we want within a single time unit.
But actually moving information from time t minus 1 to time t is
something that is still missing.
Now, if we look about that kind of thing in the way we're,
we're in this abstract way that we're thinking about these discrete time units,
at that exact time when we switch between time unit t minus 1 to time unit t.
This new element must remember the bit.
At that point it has to remember what happened previously and
carry it on to the next stage.
Without that we cannot have this kind of functionality.
Now, this means that at this transition point between two consecutive time units
it must have state.
It must remember whether it's now remembering 0 or it's now remembering 1.
That means it has to be in two different physical states in, in its implementation.
These two physical states, it must be able to move
between them according to the logic of the previous time unit.
Which means, which means it needs to be able to flip between these two
kind of different, two, two different physical states.
An element that can do that thing, that can flip change situation between
two different kind of such states are called Flip-Flops.
They flip to 0 and then can flop back to 1, and
the point is that this flipping and flopping is something they remember.
It's not just a function of the current input, but
its something internal to them they remember between time units.
So let us view now the basic flip flops that we will you,
be using in this course which is called the Clocked Data Flip Flop.
This flip flop has a single input and a single output and it basically
remembers the input from last time unit and outputs it in the next time unit.
So, if we again look at the diagram of our time units and
assume that our input looks like this.
If it starts with a value of 1, its time unit 1 goes down to 0 for
time units 2 and 3, and then goes up to 1 and down to 0 again.
Then when we look at what the D flip flop will do, at any time unit it
will actually return the value that was in the input in the previous time unit.
So at time 1, we don't exactly know what our output will be because we haven't
specified what happened in the previous time unit.
So for us, it's gray, we just don't know what the output is.
But once we get to time unit 2, then we know exactly what the output needs to be.
It needs to be exactly what the input was at time 1.
Similarly at time unit 3, we know it has to be 0 because that was what
was the input was at time 2, and so on.
At every time point we are having simply the previous signal that was fed to
the input, shifted one time unit to the right.
And this is what the Clocked Data Flip Flop does.
And this is going to be the only element that will provide
all the sequential logic that we need in this course.
And from this we'll need all the kinds of the sequential circuitry that we need,
memories, counters, and so on.
One thing that I'd like to mention at this point is the meaning of the little
triangles that we see at the bottom, at the bottom of the D flip flop diagram.
The meaning of this is that we have a sequential chip,
a chip that depends on time.
As opposed to all previous chips are all combinatorial chips that we had so
far, whose output only depended on their own inputs at any given point in time.
Here we have a chip whose output also depends on what happened previously and
state that's kept inside this chip.
This is the only point that we care for this logical dependency of time.
Although it's probably also interesting to note that in any physical
implementation of a D flip flop.
This means that the implementation will also need some kind of
access to this clock that we mentioned in the last unit,
that actually breaks down the physical continuous time into discrete time units.
Again we won't care about this because we're living in our abstraction of
discrete time, but
from our point of view this is just a way to remember that this chip has state.
And can remember and ha, and, and,
depends out and its output also depends on what happens in previous time units.
Now at this point, let us say,
just say one word about the implementation of the D Flip Flop.
In this course, we are going to deal with it as a completely primitive operation.
This is something given to you that cannot be manufactured from anything else.
But just, you are going to use it, just like you viewed the Nand gate and
from D Flip Flop, and
the Nand gate you will provide, you will actually build everything in the course.
In many other courses,
you actually eh, follow what happens in most real life hardware.
You can actually construct the flip flop from Nand gates eh, when you actually
take the Nand gate and put them into some kind of a loop eh, between each other.
This kind of loop basically has them amplifying the same signal again and
it allows them to get stuck either in a zero or one state.
And with some additional logic you will also be able to manipulate this
date from the outside.
Eh, this kind of logic usually has two steps.
The first step is one, is what I've just described having this kind of cycle that
allows it to somehow remember information.
And the second type step is to actually have some kind of logic that actually
provide isolation between subsequent time units.
We will not describe in this course how this is done even though it's extremely
elegant and beautiful because we basically think it's confusing.
We do not think that is the right way to think about a logical circuitry.
We think that it's cont, completely worthwhile to keep separate in your head.
The combinatorial logic which happens instantaneously and
the sequential logic which we don't want to, to thinking about how it,
how it is constructed from lower levels combinatorial stuff.
But rather think about it as its own primitive block.
So now that we can remember one bit from this, we can build everything else.
In fact, there is a generic paradigm of how we're going to build
all our logic in the computer, and it's going to be a combination of
remembering information via this basic D flip flops.
And then manipulating them using combinatorial logics that we built in
the first two lectures.
So in particular the usual way we do things is we have an array of D flip flops
which basically compromise all of our memory in the system.
Their output is going to be fed into some combinatorial logic
together with the new input that you get in this time unit.
And all of this is going to change the state that we have in the D flip flop for
the next time unit.
This is the general way we're going to build everything whether it's a memory or
a counter.
For example, if it's a counter we're going to remember a number in all these flip
flops and the combinatorial logic will basically add one to the counter.
In this way, every time unit,
the new value that we have will be 1 more than the old unit.
Let us say, actually now look at the first bit that we're actually going to the first
device, the first chip that we're going to actually be, build from a D flip flop.
And this is a device that actually builds, remembers a bit forever.
So the D flip flop provided the basic functionality of remembering a bit for
one time unit.
If we want to build a memory we want something that can remember a bit forever.
We store it, we tell now start remembering this bit and
then it keeps on remembering the bit.
Such a device, such as chip eh, is defined by the following API,
by the following chip that we have that we call the bit chip.
It has two inputs, an input bit and a load bit.
Once we take the load bit and
put the 1 into it we want to remember the input bit at that time.
When the load bit goes down to zero we want to the, the chip to
keep remembering the last time that the, the last input that was loaded into it for
infinity until a new load operation is performed.
So this is basically the logic that we have.
If load at time t minus 1 is 1, then we want to the, the next out,
the out at time t to be exactly the input at time t minus 1.
Otherwise, we want to output the time t to just keep on being what it is now.
Basically the old value that we remember the same as out t minus 1.
How can we build such a chip from our humble D flip flop?
Before we look at that, let us see what this bit chip needs to do.
So again, let's look at two possible signals for load and for in.
So for example, we ask for loading in time units 1 and time unit 4, while input is,
let's say it's 1 in the first time unit and then it goes down, down to 0.
So let's see what do we expect the output of this bit gate to be.
Well on the first time unit we don't know the history so
we have no idea what the output is, let's put it in gray.
Now in time unit 2, it's supposed to be, since we asked for
a load at time unit 1, we, what we want in time unit 2 is for
the output is to be exactly like the input at time unit 1.
Because we have a load at time 1, the value of any time 1 is 1,
the output at time 2 should be 1.
Now after that, load goes down to 0 for the next 2 time units.
So basically what we want is we want the same output to, the same output to remain,
just because load is going to 0 even if input changes.
So we're going to keep on maintaining the same value for the next 2 time units
until load goes up to 1 and then we'll have to see what we're going to do.
Now notice at for this time units, whatever input was,
whether input went up or down, it does not matter.
In any case, we will not change the output of our chip.
Now let's see what happened at the fourth time unit.
At thefourth time unit, load goes up to 1.
Load goes up to 1, so now we're asking the chip to load the value again,
and the value that we load is the value of in right now,
which is the value at time four which is zero.
Notice that, that we have to load at time four, but this will only affect the output
at time five, because the output at time five is basically
the change to the input at time four, only if load at time four asked it to do it.
So that means that at time 5, our output will go down to 0 as planned.
So this is the intended functionality of the 1-Bit Register.
How can we do that?
How can we pipe and pipe the value that we remember so
it will keep on being remembered until we ask, we ask to change it?
Well here is the first naive approach.
We will take the output, what we currently remember and
let's plug it back into the input of the D flip flop.
And this way, the D flip flop, unless we tell it to load the new value,
we just keep on having the same value and looping inside it if you wish.
This is a very basic the ba, the correct idea in general but
of course this is not the real chip.
How do we connect?
How do we put the real input in,
if we want to also put the output of the D flip flop back into itself?
How does this connection done?
So this doesn't quite work, really the way to combine these two possible sources
into the D flip-flop, one source which is an output from the previous stage, and
another source which is a new input.
And which one of them we want to actually plug into the D flip-flop depends of
course on whether the load bit is set or not.
But we already know exactly how to combine two sources into one output and
this is exactly the multiplexer.
So, if we actually take the input and fit it into one input of the multiplexer.
Take the previous output and fit it into another input of the multiplexer and
then load, choose between them, this is exactly the correct functionality.
We can actually see how that works by following step by step.
So, let's try to follow this implementation and
see how it works eh, real time.
Again, let us take two possible example inputs,
load them in that we get from some other source that we don't care about.
And see what our new implementation does when it's fed these two signals and
inputs, and what it produces as output.
Let us start with time step 1, at time step 1 the ma, there is 1 point,
piece of information that we don't know.
We don't know what the previous state of the D flip flop was,
what the previous out was because it's not specified in this example.
So for us it's going to be a question mark.
All the other bits we can complete.
We know that in is one because that's what we see in our input.
We know that load is 1 and so on.
Now notice that the multiplexer here, because load is 1 and
because in is 1 even though we don't know what is the input to its other input.
To its eh, down to its lower input, we still can tell very well
what the output is, what the output of the multiplexer is and that's going to be 1.
Now eh, that we know what the input to the D flip flop at time unit 1 is, so
even though we don't know the output at this point time unit
we know everything about the input.
Now we can see,
now this implies exactly what is going to happen in the next time step.
In the next time step, the one that was the input
of the D flip flop is going to be passed and is going to be the output of the D
flip flop in the next time unit exactly when we switch between time units.
Now we can fill up the rest of the information about what
happens in the second time unit.
In the second time unit, we know what in is, that was our input.
We know what load is, we have the previous out so
we can calculate exactly what the multiplexer does.
And the multiplexer basically, basically picks the previous output
from the ori, from the old value of the DFF.
And then we exactly, we again, we know what the input to the, to the D, D,
D flip flop is going to be.
It is going to be again a 1, and this we can keep on doing step after step.
At each point in time we know the previous values.
We know what load is, we know what in is, we can compute what the next situation is,
and at every given point in time, we can write down the values and
all the different wires just like we did, did in combinatorial logic.
And as we see, this implementation actually provides the required
functionality, the functionality of whenever load is being pulled to high.
We load the input from in and keep it until the next time that a load is asked.
So at this point, we've looked, we've, we've looked at
what is the basic unit that allows us to do sequential logic on a computer.
And we've built the first interesting element from it, our one bit memory.
Once we have a one bit memory, in the next unit we'll actually build a whole
huge memory of lots and lots of bytes and words.
