Lakhasly

Help us translate!
0:03
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.
0:17
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.
1:25
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.
1:35
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.
1:53
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.
2:46
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.
3:02
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.
3:49
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.
4:51
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.
5:09
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.
6:01
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.
7:18
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.
7:50
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.
8:31
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.
10:34
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.
10:45
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?
11:33
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.
13:42
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.
14:32
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.
15:00
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.
15:16
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.
15:31
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.