CS641 Class 18

Note hw5, due next Mon: questions?

Last time: Start on states handout linked from syllabus

Sequential Circuits

We take the basic D edge-triggered flip-flop as “given”

If interested, follow this link to see 6 gates needed to make an edge-triggered D flip-flop (from Wikipedia page on flip-flops)

http://en.wikipedia.org/wiki/File:Edge_triggered_D_flip-flop.png

So be happy we don’t need to understand this!

The D flip-flop is a one-bit register  By itself, it is represented by a rectangle as follows:

http://en.wikipedia.org/wiki/File:D-Type_Flip-flop.svg

This has D and CLK inputs, Q and not-Q outputs.  Also two special inputs: R for reset and S for set. The not-Q is not that important, so we often drop it.  The reset and set are important now and then, but not in most operations, so the core operational signals are D, Q,  and CLK.

So the simpler representation has D and CLK inputs and Q output, as this picture of a register and its D FF’s from the State Element handout:

 

Here all the CLK inputs are driven by one input to the group. They all sample their input at the same moment.

We can add the R input on the left hand side of each FF above, and connect them all together to make a “Reset” input for the whole register, as shown in the next diagram.  When R is “not asserted”, the FF is in “normal operation”, as we have described.  When R is asserted, the FF’s bit is cleared at the clock edge, regardless of the D input. More on this below.

Note that there are negative-edge-triggered FFs/registers and positive-edge-triggered FFs/registers.  Our first example, last time, (pg. 2 of handout) involved a negative-edge-triggered register.

The timing diagram on pg. 3 shows the operation of a positive-edge-triggered FF. Now we mark the rising edges of the clock instead of the falling edges, and see the D input sampled, and a little later the Q output following it. 

See the next diagram with more detailed markup.  It shows that the input data needs to be stable for a little period of time called the hold time that starts from the clock edge. This needs to be significantly less than the clock period. 

Also we see that after the hold time and a little more time, the output becomes stable. The period from the clock edge to this point is the “clk-to-q” delay. This also needs to be significantly less than the clock period. 

 

     S_i-1

 

 

 

 

 

 More accurate timing diagram, with positive-edge-triggered register:

 

To see this better:

1.       Mark the clock rising edges

2.       Drop dotted lines down from there

3.       We see that the X’s are supplied just after the clock edges, coming in from elsewhere, probably from another sequential circuit

4.       Consider the summing: it ignores the clock, just follows the Si-1 and Xi inputs, with the little delay shown.  You can mark bars of stable input value on these inputs, and the corresponding interval (by intersection of the two input intervals) on the Si-1 output.

5.       So Si is determined, and sampled just after the clock by the register, and the register gives its output after the delay shown: that’s Si-1. You can mark the sample time as a very short bar or fat dot on Si’s waveform, with a curvy arrow up to where Si-1 is determined by it.

 

Here is an example of a  timing diagram with a curvy arrow (the arrow shows how the transition in one signal is causing something to happen in other signals)

It’s still not clear how Si-1 = 0 near the start, but we see a reset input now on the register.  It is connected to all the internal D FF’s on their R input that hasn’t been shown on the diagrams.

Here is a timing diagram with the reset input, and new markup for areas where the sum is not as marked by the simple analysis because the inputs to the adder are not coming in exactly together, i.e., the bars you marked for the two inputs are not quite the same in time. Luckily this gray area is away from the critical point where the signal is sampled for the register.

 

 

The reset line is normally low during register operation, but when the reset action is wanted, it is put to high across a clock rising edge.  When the register sees reset high at its sample time, it ignores the ordinary inputs and just clears its internal bits (D FF’s) using their R inputs.

Pipelining to improve performance

Adding and shifting can be done by cascading two combinational blocks, like this:

Now the gate delays of the two combinational blocks add up, and may be too long for the desired T.  We don’t want to increase T and slow everything down, so instead we can put a register in between the combinational blocks:

This can tolerate a faster clock than the first version.

Finite State Machines Introduction

If you’re new to this, see the Wikipedia article on FSMs

Their first example. Consider a door. It can be open or closed, i.e., it has two states.  Put each in a balloon. Then the action “open_door” causes a transition from state “open” to state “closed”, and action “close_door” causes a transition the other way.

What about trying to do open_door on an open door?  There are two ways to go here, say it’s an error or say it’s OK but a no-op.  Note that there is no “error state” in most FSMs. The system can fail transitions they don’t like, leaving the system in its old state.  The door system is left in open state after this unnecessary open_door event happens, so we can put a little curlicue on the balloon to show that the open_door action on the open door has not caused a change in state.

The transitions are marked with event/outcome notation on the arrow between the balloons.  So doing open_door on a closed door  has an arrow from state closed to state open with notation open_door/OK.

Doing an open_door action on an open door is represented by the curlicue back to open state, with notation open_door/OK or open_door/ERROR depending on which model we have adopted about this case.

For sequential circuits, the events causing transitions are incoming digital signals.  The outcomes are outputs from the circuit. It’s understood that the inputs are sampled by the clock, so the transitions follow those clock times.  Thus we see:

 

Try out a simple circuit (this example not in handout): two D FFs in series: output of first connected to D input of second.

Four states of the system, four balloons, one input (D of first FF), one output (Q of second FF). 

Work out the transitions: Suppose start in 00 state, where Q=0. Then if D=0, stay in 00 state.  If D=1, transition to 10 state, with Q=0 still.

From 10 state: D=0 yields 01 state while D=1 yields  11 state, with Q=1 either way.

And so on.  End up with 4 balloons variously connected by arrows.  Sorry, no picture.

 

Finite State Machine Example from Handout: 3 ones…

To do this, the system must be able to count ones up to 3, then start over.  But it only needs memory for counts up to 2, because it can handle the last instance “on the fly”.  So it only needs 3 states, S0, S1, S2 for how many ones already seen, and if in state S2 and sees another 1, report output=1.

Note fix from handout!  S2 --> S0 on input = 1.