last modified 5/19/03
Sequential circuits
Combinational vs. Sequential circuits
We've been looking at combinational circuits so far. The
outputs of any of the circuits were determined by the combination
of the inputs. We couldn't have 'loops' with these circuits. By
loops, we refer to the condition of having the output of a circuit
connected to its input (usually indirectly.)
Sequential circuits have loops - these enable circuits to
receive feedback. You may have learned about feedback in other
science classes. A simple example of a system dependent on
feedback is a thermostat. It controls the temperature by receiving
feedback in the form of a temperature reading. A diagram of this
system is:
This system has loops. The output of the temperature changing
functions affects the input of the temperature-checking function.
Its output affects the operation of the temperature changing
function(s).
Now, we can't just use the type of circuit system we've been
using. The reason for this is that in the circuit-systems we've
looked at, we have no control over when the inputs are
read. Before we make an action based on an input value, we want to
make sure that that input value is correct (or valid.) How can the
value be invalid? If the function (or circuit-system) that
computes it hasn't finished its execution yet, the value won't
have the correct value yet.
S-R flip-flop
The S-R flip-flop has two input lines and one output
line. The output, Q, is always whatever value is 'stored' in the
flip-flop. The input lines specify whether a 0 or 1 should be
stored in the flip-flop. If S is 1, the flip-flop is 'set' to 1.
If R is 1, the flip-flop is 'reset' to 0. If S & R are both 0,
the flip-flop should be neither set nor reset, so the bit that is
currently stored in the flip-flop remains there. R and S are not
allowed to both be 1 at the same time. (Logically, it doesn't make
sense to try to both set and reset the flip-flop at the same
time.)
Here is an implementation of an S-R flip-flop: (others
exist)
You can use a truth table to better understand how this circuit
works. However, in addition to the input values of S & R, you
also need to consider the value 'stored' in the flip-flop. (It is
physically stored on that bottom looping wire.) In other words,
you can determine the 'next state' (which corresponds to the
output of a combinational function) by looking at the values of S,
R, and the current state. Here's the associated truth table:
S | R | state | output
----------------------
0 | 0 | 0 | 0 - the output = S OR ((NOT R) AND state)
0 | 0 | 1 | 1 - NOT R AND state => 1, so the output is 1
0 | 1 | 0 | 0 - the input to the AND gate, R, is inverted. 0 AND 0 => 0
0 | 1 | 1 | 0
1 | 0 | 0 | 1
1 | 0 | 1 | 1
1 | 1 | 0 | x - these 2 states are officially undefined, b/c you dont' want
1 | 1 | 1 | x to set and reset at the same time!
Just like with decoders and adders,
you should try to think of flip flops on a higher level than their
gate implementation. A flip-flop stores a bit. That stored bit can
always be read (on the output line.) Depending on the particular
type of flip-flop, the semantics of storing the bit will vary.
the clock
For sequential circuits, we add the control of a clock.
By using a clock, we can ensure that certain events occur in the
correct order. A clock is just an alternating sequence of 0's and
1's that has a set frequency. In the diagram below, you can see
the key aspects of a clock. When the clock is 'high', its value is
1; when it's 'low', its value is 0.
Often, the clock (wire) and the input it controls are combined
with an AND gate. The input will only be activated if the clock
has value 1. A clocked flip-flop is shown below. It works exactly
the same except that SET and RESET only 'work' if the clock has
value 1. Whenever the clock has value 0, the output of both the
AND gates will be 0 and so the input to for both S and R is 0.
Remember that when S and R are both 0, the value stored in the
flip-flop remains unchanged. When you add a clock to a circuit
like this, you have greater control over the system. You can time
events so that they only happen on clock 'ticks' (clock value ==
1).
clocked SR flip flop:
timing diagrams
Timing diagrams are used to better understand the
operation of sequential functions. They are to sequential circuits
what truth tables are to combinational circuits. They show the
values of inputs over time and the resulting output. When the
'line' is raised, it corresponds to a value of 1; when it is flat,
it corresponds to a value of 0. They are read from left to right,
like a time-line. The sequence of each input value is given: in
this case, S & R (and the clock). The output can be computed
based on the values of the inputs.
In this timing diagram, Q has the initial value of 0. During
the first clock 'tick', the value of S is 1, so Q is set to 1. In
this diagram, the transition from 0 to 1 is instantaneous. In
reality, there would be a slight delay. When the clock is 0, the
value of Q remains the same. So, we only need to look at those
points in the diagram at which the clock value is 1. Look at the
top right of the diagram. S is 1 but since the clock is 0, the
value of Q is unaffected. When the clock is 1 but S and R are both
0, Q also remains the same. In this diagram, this happens during
the second and fourth clock 'ticks.' During the second clock tick,
Q stays high (1). During the fourth clock tick, Q stays low (0).
If everything in the above paragraph makes sense, great! Ignore
the blue line & numbers drawn in the middle of the diagram.
They're not a necessary part of the timing diagram. I've put them
in the picture to allow me to give an alternate explanation of how
timing diagrams work. This line is one point in time. At this
moment, the value of S is 0, R is 1, and the clock is 1. (high is
1, low is 0) Based on those inputs to the S-R clocked flip-flop,
the value of the output Q must be 0. So, to determine the answer
to a timing diagram problem (which in this picture is colored
red), you need to determine the value of the output at each point
in time.
D flip flop
A D-type flip-flop uses a S-R flip-flop for its
implementation. The input D controls what is written to the
flip-flop. If the clock is active (value=1), then the flip-flop
will get D's value (0 or 1). A timing diagram is given for a 0-1-1
sequence of D values.
Register
A register is just a sequence of flip flops. In TOY, we
had 16-bit registers. A series of 16 flip-flops can be used to
form one of these registers. The clock (and the extra control of a
load line) is used to ensure that new values are loaded only when
they are supposed to be. Here's how it works. If LOAD has value 0,
all the AND gates have output 0, so neither S nor R (on any of the
flip-flops) has value=1. The register is unchanged, which is what
we want. If LOAD has value 1 and a bit, x, has value 1, then the
AND gate connected to the S input of its flip-flop will have
output 1. So, SET will be activated, and a 1 will be stored in
that register. Alternatively, if bit x has value 0, the AND gate
corresponding to its RESET input will have value 1, and a 0 will
be stored in that flip-flop.
All the values will be set in parallel.
The slide mentions several applications for registers.
Register File
To implement memory, we need to have a control to
handling reading in addition to writing. We also want to be able
to control which flip flop we read. The SELECT control selects the
desired flip-flop using a decoder. By connecting the SELECT lines
to the input of the decoder, we can control which flip-flop we
read.
This slide demonstrates how computers are built up with
components such as decoders and flip-flops. Each time we create a
new 'system,' we can think of it abstractly, as a 'black box.' As
long as we know how many inputs and outputs a circuit has and
understand the function it performs, we can represent this
component of the computer more abstractly. The Memory Bit 'black
box' on the right of this slide is a good example of this.
Think back to what we've already learned to appreciate the
power of this abstraction. It hides a lot of complexity. The
Memory Bit consists of a Decoder and Flip-Flops. Decoders and
Flip-Flops are built up of the primitive gates, like AND/OR/NOT,
and these gates are built from transistors. Attempting to draw
this Memory Bit system out of transistors alone would be extremely
challenging, and it's likely that we would make a mistake. The
idea of abstraction is central to the architecture of computers
(and computer science in general.)