Combinational circuits that we considered in the last lecture, just compute and just do their thing. It provide values on wires as inputs and the computed values available in the outputs. What we want to look at now is a very important idea that we want to have circuits that remember things. Unfortunately, as with the switch that we used as the basis for combinational circuits, there's a very tiny component that we can use as the basis for all of the circuits with memory. That's what we're going to consider next. So, a sequential circuit is a circuit that has feedback, that has loops in it. Now, just as with computer programs, when you add loops to a circuit, you're introducing a whole new level of complexity in the behavior of the circuit. One would be extremely careful about how we introduce feedback. And the reason that we use sequential circuits is the idea of memory. It really makes the difference between a calculator and a computer, but fortunately we can get by with a pretty small set of basic abstractions just as with combinational circuits. Again, we have on and off, we have wires that propagate on and off values, we have switches that we can control propagation through the wires, we're automatically controlling the switches. And now we're going to add something new which is called a flip flop and that's a very simple circuit with feedback that remembers a value. That's what we're going to talk about next. So the thing is, if you have loops and circuits, then the behavior is going to depend on the sequence of switch operations, and so we need some very tight control on this. So here's just the simplest possible example. If you have two switches that are each blocked by the other, so these are two switches connected in power dots and they each block the other one. Now we're going to pay attention to the value on the wire that comes out of this little unit, but the thing about it is that the state is determined by whichever one switches first. So for example, if the one on the bottom is the first to switch and therefore block the power dot on the bottom from going to the output, then the state is going to be zero, that output line will be off. But if the one at the top switches first, then the power dot on the left is connected to the output and the output is the one. And the thing about this is, depending on which one switches first, if it gets in one of these two states, it's going to stay in that state. So once it's set, the state never changes, but the thing is it's dependent on this kind of random event of which is going to switch first. One of them will switch first even if it's only by a tiny amount, and as soon as it does, then the circuit enters the stable state. So that's our basic building block for memory circuits. This is a tiny circuit, the tiniest that we can imagine that remembers something. It remembers which one switched first. What we're going to do is add some controls so we control which one switches first. But once we've done that, we're going to take advantage of the fact that the circuit remembers. Now, this is the main feedback, like 99.99 percent of the feedback on our circuits are a little tight, things like this, little memory bits, and the reason is that if you have bigger feedback loops, you can get unpredictable behavior. So here's the same thing extended to three switches that block one another. And again, the state is determined by whichever one switches first, but it's not stable. These switches keep blocking each other and switching around and goes in the cycle. That's called a buzzer, and actually, if you build your switches with the relays, the physical electromagnets we talked about last time, it actually makes a buzzing sound and actually old doorbells or old-sounding buzzer is exactly that. It's just a relay turning on and off through and that stable cycle like this. So because of that kind of behavior, we want to stay away from long feedback loops or at least make sure we have very tight control over long feedback loops. The main way is to put all our feedback just in the two-switch feedback. So there we go. That's the idea of memory and now what we want to do is control when the switch switches and that's what a flip-flop is. We'll use the old historical terms. There are many different types of flip-flops initially, but we're going to use what's called an SR flip-flop and the idea is to add control lines to the switches to set the state, basically determine which switch switches first. So the R line which is called reset sets the state to zero and the S line which is called set sets the state to the one and the output is called Q and that's always available. So this is what it looks like. So you can see if the R line is on, then it's going to block the switch at the bottom from switching and then the state is going to be zero. That's just as if that switch switched first. In contrast, the S line, and we'll look at more detail, is going to set it so the other one as if the other one switched first and it'll always remember that. If you look at these as components, it's two NOR gates that are interconnected. The classic notation is that it is called a cross-coupled NOR gates. So two simple NOR gates that are cross-coupled, that's a flip-flop. So just look at an example, so if R is up, so in this example R is set to one and S is zero, and you can see R blocks the power dot at the left and that means the other switch, the other power dot at the right is on, and now even when we turn R off, then the power at the left is going to be blocked. So it's as if the switch at the bottom switched first and we kind of forced it by putting R on and that means the output is zero. On the other hand, if we set S to one, then it's as if the switch at the top has switched which connects the power dot at the left to the output puts the thing in state one and then even when S goes off and it stays in that state. We never put both R and S on at the same time, so we don't have to worry about that then we're talking about which one goes off first and they have the same kind of problem. So with the R and S line, we can control what value goes in to the feedback loop and that's the essence of a circuit with memory. Now there are some physical considerations that come into play here depending on the switch technology. So if the switches are really slow versus the delay, but we're not going to worry about those. We're going to assume that we've got a difference in that switching time in the delay through the wires. It's sufficient that we don't have those kinds of problems. In real life, you might have to worry about timing a bit. So I don't want to minimize those, but let's just abstract them away because it does depend on the technology. So we're going to assume when R goes one, then we set it to zero. When S goes one, we set it to one and that happens pretty quickly compared to everything else. So what we're going to do now is implement a memory bit that even give us more precise control. What we want to do is provide data value on an input wire instead of fooling with too much with the S and R controls directly and we're going to have a control wire for every memory bit that if that's the one that enables the actual change in the flip-flop value and then the flip-flop value is always available as output,and you know this is the reason that we don't need to worry so much about timing as we have these extra controls to make sure that things happen in the way that we want. We'll talk a little bit about that a little later, but it's just one piece of operation that makes our circuits reliable. It's possible to make our circuits reliable and lots of technologies. So if we want to set the value of our flip-flop to one, then we put one on the input and then we turn this write control wire on. Usually, we think of turning this on just briefly, just enough to get the flip-flop to flip for a few gates and then we turn it off right away. So now you can see with that write on and the input one, we end those two signals and then feed that to S, so S is going to be one if and only if both R input is one and write is on, and when S is one, then the flip-flop gets the value one, and at the same time the other end gate on the left has the second input is the opposite. It is going to block and so R will be zero always when the input is one and then when write goes off, then the flip-flop has its new value. So all we assume is that a quick write pulse gets the flip-flop to change and that time it's pretty small by comparison with everything else in the circuit, and similarly, with zero we do the opposite. Zero signal in is going to wind up with R being one and S being zero always, and when the write pulse comes on which sets the flip-flop value to zero, and then even when right goes away, it stays zero. That's our basic unit of memory, memory bit that operates in this way. You give it an input, give it a write pulse, remembers that input value until the next time it gets it write pulse and the output value is always available. Our computers and our computer circuits are filled, filled, filled with memory bits as most of it is these. So it's important to understand how they work. Again we're exercising very tight control over what happens in the feedback loop and that's how we get our circuits to be reliable. So here's an application of memory bit. It's a circuit that's got just one memory bit in it and we're going to use it to implement the clock that drives our computer. So we'll have another assumption about the physical world and that is that we can get a regular on-off pulse from the physical world somewhere. Even Von Neumann needed this and imagined it in the terms of oscillations of some physical material and we make two assumptions about our clock signal. First is that the duration of the time when it's one is just enough to trigger a flip-flop, and number two, and we'll talk about this a little more later, is that the duration between pulses is pretty long. There might be lots of flip-flops that have to stabilize and we assume that that duration between pulses is long enough for the longest chain of flip-flops to stabilize. Analysis of this is sometimes difficult and actually in real computers what they do is make that interval very long to make sure the computer works and then they make it shorter and shorter until it stops working, make it a little bit longer and then sell it to you. That's absolutely what they do, build computers nowadays. Okay, so what we're going to do now is attach that clock signal to a memory bit and that it's going to give us the signals that we need to get the fetch to execute that we use to drive the computer. So you can think of this physical clock as just the minute hand spinning around and every time it hits that little triangle at the left, it makes a pulse, and again, there's lots of ways we could do that and the clock itself in the physical world has a run control wire that starts the clock. So when you press the run button on the front of the computer that turns on the clock, it starts spinning around and makes the clock pulses. There's also a halt control wire that stops it. So now what we do is, so we get the run to start, a halt to stop, what we do is we take the output of the memory bit, what it remembers and we take the output and the negation of that output. So right at the bottom, we put a not gate. So we have two signals that we give out, one called fetch and one called execute, and they are always the opposite of one another. So our computer, when it's running, it either got fetch high or it's got execute high and the other one is zero always. They are absolutely the negation of one another and then we take that signal and we feed it back in to the input to the flip-flop and so what's going to happen is since the write enable line is fed by the clock pulse, every time the clock ticks, the flip-flop is going to change its value. It remembers what its value was the last time the clock ticked and it changes to the new value. That one bit is what we need to implement the sequence of fetch and execute that control the CPU. That's a very useful one bit circuit, one memory bit. It's a circuit with that one little loop of feedback. It's quite useful. We actually use a more complicated one that we want to add in the write pulses. So I might as well talk about that one now. It's just a slightly more complicated version of this clock. What we want is we want to have a fetch signal and then fetch write pulse. So the fetch part of the computation, things happen but nothing gets written until the write pulse happens and that write pulse is a short one that just gets flip-flops to change and same with execute, and to get that, we just end our two signals to the fetch-execute clock. So the fetch write pulse is just fetch and clock and the execute write pulse is just execute and clock. And that's what we're going to use to implement our fetch/execute cycles, the ones that these signals are going to turn on control wires that change the state of all our components. And this diagram looks complicated, but it's really just pointing out that there's going to be four distinct times in this clock cycle, which repeats endlessly where interesting things happen. So fetch comes high, and then some control lines come along. And then fetch right happens, and that causes certain flip flops to change. And execute comes high, and certain control lines go on, and then execute right happens and certain flip flops change. And that cycle is going to continue over and over and over again. And that's what's going to drive the changes in the circuit that implement our instructions. And all of this is made possible by a single bit connected to a simple clock. But of course most of our memory circuits are more complicated. So, let's look at registers. So, a register is a bunch of bits. So, here's a 4-bit register. And again, our convention is to take inputs at the top, and provide outputs at the bottom, and to have blue control lines in the middle. So we have an input bus in this example. This input bus is representing the 4-bit values zero one zero one, or maybe five. And then those are available on the input bus, but they're just sitting there, they're not being used, because the right control is off. So we might have different values on the output bus, those are the current values of what's in the memory bit. In this case one one zero zero, which maybe represents 12. And so, if we give it a right pulse, then what's supposed to happen is, the values and the input bus go into the memory bit, and are available on the output bus. So, in this case right is off, so now when we turn right on, then we get those values put into the memory bits, and available on the output bus. And the implementation is quite simple, it's just a sequence of memory bits, just connected to the buses. And the right pulse controls all of them. And in TOY-8, this is precisely what holds the address for the PC or for a bit register like this. We need an 8-bit register to hold the current instruction. It's the same thing just with eight bits. And our actual processor register also is an 8-bit register that's exactly like this. So, sequence of memory bits connected with buses and the right pulse, that's a register and that's three of the main components of our CPU circuit. And then we can extend the same idea to get a memory bank. So, now we've got two to the n words. In the case of TOY-8 little n is three 8-bit words. In this example that will show right here, we're going to have a four word memory that are each six bits just so you can see all the gates. And again to emphasize that our design is parametrized just by really the number of bits in a word, in the number of words or the number of bits in the address. So, this is the exact same design, it's going to work even when the end is 30 or in which case they'd be a billion words. In this case when n is two and this case this is four words. So we have to give in bits of address input that's over the left, and then however many bits per word, we have an input bus, and then the value of some word, the word whose address we give, is the one that's available on the output bus. That's a memory bank. And then we also have a right pulse, and the memory bank has the property that when the right pulse becomes one, then whatever's on the input bus gets loaded into the selected word, and its value is available on the output bus. So, it's the sequence of registers. Register sort of on each row, except that we use the address to select one of them to work like the register on the previous slide. So, here's the implementation. So for every memory word, in this case there's four words, each with six bits. So, we have w bits going across for each word, and those are just memory bits just as before. Now, over at the left, we have a decoder demux. So, remember if we take the address bits, those address bits and then there is a value that comes in, that's the right enable. So, there's exactly one pair of lines that becomes high. That's what the decoder demux does for us. And all the rest of those lines are zero. That's what we call them selection lines. The address selects which part of the memory is going to be active. In this case, we say right enable is high, so they're both one. If right enable was off, then top one would be zero. But either way only that word, in this case the bitzer one zero or two, is the one that's selected. And then, what we need to do is as we've selected a word we want it's value, but we have to collect the output values, only one of them is going to matter for each bit position, the one for the selected words, so only one of them could possibly be one. And so all we need to do, is collect them together in a big tall or gate, that goes from top to bottom ending the contents of the memory bit with the select line. So that's one hot marks that we've used before, and those things then take the selected word right to the output bus. So, these are all components that we've seen before, and just put together to implement the memory that gives us the behavior that we want. And of course, in TOY-8 this is going to be our implementation of our main memory. So, this example where you can see all the switches is 24 bits. So, for TOY-8 it's bigger, it's 16 8-bit words, so that's 128 different bits. And the decoder demux has 16 different gate, it takes four bits as address, but otherwise it's the same. It's got an input bus, it's got an output bus, it's got an address selector word, and it's got the right control signal. That's our main memory bank for TOY-8. So, again a major component of that TOY-8 computer. And again, if you implemented the circuit for TOY, there would be 256 16-bit words that'd be hard to see at every switch for sure. But wouldn't really add much insight. So, the input bus comes from the register, now the output bus goes to the register in the instruction register, and the address bits come from the PC. And we'll see how the memory connects up to the other components. And again, your computer might have a billion bits, you need a electron microscope to see them all, but the design is the same. So that's starting from the idea of a simple flip flop across coupled nor gates, we get several of the main components of our toy computer. We get the clock that has one flip flop, in it one bit of memory, we get our registers and we get our main memory.