false

Class Notes
(836,680)

Canada
(509,870)

Simon Fraser University
(12,397)

Computing Science
(225)

CMPT 150
(6)

Anthony Dixon
(6)

Lecture

Unlock Document

Computing Science

CMPT 150

Anthony Dixon

Fall

Description

A.H.Dixon CMPT 150: Week 7 (Oct 16 - 18) 47
24 SEQUENTIAL CIRCUITS
Digital systems are divided into two major groups:
1. Combinational Systems are those that have no \feedback loops" in their schemat-
ics. That is, there is no pathway from the output of a component at level n in the
schematic that is connected to an input of another component at level m, where
m < n. All of the examples up to this point share this property and therefore they
are all examples of combinational systems.
As described previously, to formally de▯ne a combinational system, a behavioral
description must identify two sets and a function, speci▯cally:
▯ The input set, I: This consists of all possible binary sequences that can be
delivered to the digital system. Thus if there are 3 inputs to the entity de▯nition,
there are 2 possible input sequences.
▯ The output set, O: This consists of all \valid" output sequences that can be
output from the system. Each valid output sequence corresponds to an encoding
n
of some meaningful result. With n output ports there are up to 2 possible
output binary sequences, although not all of them may be meaningful.
▯ The output function, f : I ! O: This function de▯nes what output sequence
will be generated by the digital system for each input binary sequence.
2. Sequential Systems are those that possess one or more feedback loops. Because
of the propagation delay introduced by components along any path, feedback loops
enable circuits to be designed that possess memory.
The formal speci▯cation of sequential systems includes the speci▯cation of the input
and output sets and an output function. However an additional set, S, called the
state set must also be de▯ned. Each \state" represents a distinct binary sequence
that can be stored in memory. Digital systems can be designed to provide memory
for storing any number of bits. in a digital system possessing n bits of memory, there
n
are 2 possible binary sequences of length n that can be stored in that digital system.
Digital systems are often referred to as \being in a particular state." This simply
means that the memory of the digital system is currently set to a particular value, that
value being a binary sequence of length n, where n is the number of bits of memory
within the system. The state set therefore represents all valid binary sequences that
can be stored in the digital system. Each meaningful binary sequence that can be
stored de▯nes one state of the system.
The output from a sequential system will depend not only on the input but also
on the value stored in memory. Therefore the output function is a function of two
arguments: the state and the input. That is f : S ▯ I ! O.
An additional function, g, called the state-transition function must also be iden-
ti▯ed to provide a complete behavioral description. The purpose of this function is
to describe how the contents of memory is changed by the digital system. Since any
new value stored in memory (called the \next state") will depend on both the current
state and the input, g is also a function of two arguments; that is, g : S ▯ I ! S.
Therefore when providing a functional speci▯cation of a sequential system, information
about the e▯ect of memory on the outputs must be addressed, along with whether any A.H.Dixon CMPT 150: Week 7 (Oct 16 - 18) 48
change in memory occurs. It is this additional information that is captured by the state
set and state transition function.
In practice, sequential digital systems, like combinational systems, can be formally speci▯ed
by an entity de▯nition and a functional speci▯cation. The functional speci▯cation, however,
must now identify the possible states of the system and provide both the output function
and the state transition function. In many cases these functions will be the same, since the
output from sequential systems is often just the contents of memory, and this is already
identi▯ed by the state-transition function.
A common way to express the functional speci▯cation of a small sequential system (one
with few inputs and few storage bits) is with a characteristic table. This table de▯nes the
state-transition function for the system, that is, the value that is placed in memory when
given the previous value in memory and a particular input sequence.
In this table, the symbol Qi (or Q(i), oi Q ) is often used to denote the current value of
bit i of the set of bits that de▯ne the memory of the system. When there is only one bit
of storage, no \subscript" is required. Since this bit is subject to change, we denote the
\new" value (or \next" value) of bit i by the symbol Qi+.
Example 1: Design a memory circuit with two inputs: S, and R. Depending on the inputs,
either a 0 or a 1 is stored in menory, as follows:
1. If S = 0 and R = 1 then 0 is stored in memory
2. If S = 1 and R = 0 then 1 is stored in memory
3. if S = 0 and R = 0 the value of memory remains unchanged.
Formal Speci▯cation:
1. Input, State, and Output sets: I = f00, 01, 10g, S = f0, 1g, O = f0, 1g
Q S R Q+
0 0 0 0
0 0 1 0
0 1 0 1
2. State Transition Function:0 1 1 X
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 X
NOTE: This tabular representation of the state transition function is called a char-
acteristic table.
3. For many sequential systems, the output function simply delivers the value stored in
memory, as is the case in this example. Therefore, the output function is: A.H.Dixon CMPT 150: Week 7 (Oct 16 - 18) 49
Q S R z
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 X
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 X
Example 2: Design a circuit that counts from 0 to 3 and then repeats as long as a control
input, up is equal to 1.
Formal Speci▯cation:
1. Input, State, and Output sets: i = f0;1g, S = f00;01;10;11g, O = f00;01;10;11g.
In this case, memory is required to remember the current value in the sequence being
output. Since there are four possible values, each value must be able to stored in
memory and this requires binary sequences of length 2 to be stored.
2. Sate Transition Function:
Q1 Q0 up Q1+ Q0+
0 0 0 0 0
0 0 1 0 1
0 1 0 ) 1
0 1 1 1 0
1 0 0 1 0
1 0 1 1 1
1 1 0 1 1
1 1 1 0 0
3. As in the previous example, the output is simply the value stored in memory:
Q1 Q0 up z1 z0
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 1 0
1 0 1 1 1
1 1 0 1 1
1 1 1 0 0
Formal speci▯cations are more often given as an entity de▯nition and a functional speci▯-
cation, just as was the case with combinational circuits described previously.
Example: The SR latch is a sequential system whose behavioral description is giv

More
Less
Related notes for CMPT 150

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.