University of Basrah

College of Engineering
Computer Engineering Department

Digital System Design (CoE233)

Course 2023-2024

Analysis
of
Sequential Circuits
Digital System Design CoE233 2nd Class
Sequential Circuits
• A Sequential circuit consists of:
1. Combinational circuit
 It computes the Outputs of the circuit.
- Outputs depend on Inputs and Current State.
 It computes the Next State of the circuit.
- Next State also depends on the Inputs and the Present State.
2. Memory elements:
 Latches or Flip-Flops.
 Store the Present State.

Inputs Combinational Outputs

Circuit

Present State Memory Next State

Elements
• There are two types of Sequential Circuits.
1. Synchronous Sequential Circuit
 Uses a clock signal as an additional input.
 Changes in the memory elements are controlled by the clock.
 Changes happen at discrete instances of time.
2. Asynchronous Sequential Circuit
 No clock signal.
 Changes in the memory elements can happen at any instance of time.
• Synchronous Sequential Circuits
 Synchronous sequential circuits use a clock signal.
 The clock signal is an input to the memory elements.
 The clock determines when the memory should be updated.
 The present state = output value of memory (stored).
 The next state = input value to memory (not stored yet).
• There are two ways to analysis and design a clocked sequential circuit:
1. Mealy Machine: Outputs depend on both the present state of the flip-flops and on the value of the
inputs.
2. Moore Machine: Outputs depend only on the present state of the flip-flops.

Page | 2 Prepared by: Dr. Dunia S.

Digital System Design CoE233 2nd Class
• The clock
 Clock is a periodic signal = Train of pulses (1's and 0's).
 The same clock cycle repeats indefinitely over time.
 Positive Pulse: when the level of the clock is 1.
 Negative Pulse: when the level of the clock is 0.
 Rising Edge: when the clock goes from 0 to 1.
 Falling Edge: when the clock goes from 1 down to 0.

Page | 3 Prepared by: Dr. Dunia S.

Digital System Design CoE233 2nd Class
Analysis of Clocked Sequential Circuits
• Analysis is describing what a given circuit will do.
• The behavioral of a clocked (synchronous) sequential circuit is determined from the
➢ inputs
➢ outputs
➢ states of flip-flop
1. Analysis of Clocked Sequential Circuits using State Tables and state graphs
The following method can be used to construct the state table:
1. Determine the flip-flop input equations and the output equations from the circuit.
2. Derive the next-state equation for each flip-flop from its input equations, using one of the following
relations:
D flip-flop Q+ = D
T flip-flop Q+ = T ⊕ Q
S-R flip-flop Q+ = S + R′Q
J-K flip-flop Q+ = JQ′ + K′Q
3. Plot a next-state map for each flip-flop.
4. Combine these maps to form the transition table. Such a state table, which gives the next state of the
flip-flops as a function of their present state and the circuit inputs, is referred to as a transition table.
Example 1: Derive the state table and the state graph for the following logic circuit:

Solution:
Step 1: The flip-flop input equations and output equation are:

Step 2: Using the characteristic equation: Q+ = D to give the next state equations:

Page | 4 Prepared by: Dr. Dunia S.

Digital System Design CoE233 2nd Class
Step 3: The corresponding K-maps are:
X X
AB 0 1 AB 0 1
00 00
01 01
11 11
10 10
A+ B+

Step 4: The state table

Present State Next State A+ B+ Output

A B X=0 X=1 Z
0 0
0 1
1 1
1 0

To convert a transition table to a state table.

Assume that the states S0, S1, S2, S3 equal to 00, 01 10, and 11, respectively.
Present State Next State A+ B+ Output
A B X=0 X=1 Z
S0
S1
S3
S2

Step 5: The state graph

Page | 5 Prepared by: Dr. Dunia S.

Digital System Design CoE233 2nd Class
Example 2: Derive the state table and the state graph for the following logic circuit:

Solution:
Step 1: The flip-flop input equations and output equation are:

Step 2: Using the characteristic equation: Q+ = JQ′ + K′Q to give the next state equations:

Step 3: The corresponding K-maps are:

X X X
AB 0 1 AB 0 1 AB 0 1
00 00 00
01 01 01
11 11 11
10 10 10
A+ B+ Z

Step 4: The state table

Present State Next State A+ B+ Output (Z)

A B X=0 X=1 X=0 X=1
0 0
0 1
1 1
1 0

Page | 6 Prepared by: Dr. Dunia S.

Digital System Design CoE233 2nd Class
To convert a transition table to a state table.
Assume that the states S0, S1, S2, S3 equal to 00, 01 10, and 11, respectively.

Present State Next State A+ B+ Output (Z)

A B X=0 X=1 X=0 X=1
S0
S1
S3
S2

Step 5: The state graph

Page | 7 Prepared by: Dr. Dunia S.

Digital System Design CoE233 2nd Class
Example 3: Construct a state table and graph for the following logic circuit:

Solution:
Step 1: The flip-flop input equations and output equation are:

Step 2: Using the characteristic equation: Q+ = D to give the next state equations:

Step 3: The corresponding K-maps are:

X1X2 X1X2
Q1 Q2 00 01 11 10 Q1 Q2 00 01 11 10
00 00
01 01
11 11
10 10
Q1+ Q2+

Step 4: The state table

Present State Next State Q1+Q2+ O/P

Q1 Q2 X 1 X2 : 00 01 11 10 Z
0 0
0 1
1 1
1 0

Page | 8 Prepared by: Dr. Dunia S.

Digital System Design CoE233 2nd Class
To convert a transition table to a state table.
Assume that the states S0, S1, S2, S3 equal to 00, 01 10, and 11, respectively.
Present State Next State Q1+Q2+ O/P
Q1 Q2 X 1 X2 : 00 01 11 10 Z
S0
S1
S3
S2

Step 5: The state graph

Page | 9 Prepared by: Dr. Dunia S.

Digital System Design CoE233 2nd Class
Example 4: Construct a state table and graph for the following logic circuit:

Solution:
Step 1: The flip-flop input equations and output equation are:

Step 2: Using the characteristic equations: Q+ = D and Q+ = JQ′ + K′Q to give the next state equations:

Step 3: The corresponding K-maps are:

X X X
AB 0 1 AB 0 1 AB 0 1
00 00 00
01 01 01
11 11 11
10 10 10
A+ B+ Z

Step 4: The state table

Present State Next State A+ B+ Output (Z)

A B X=0 X=1 X=0 X=1
0 0
0 1
1 1
1 0
Page | 10 Prepared by: Dr. Dunia S.
Digital System Design CoE233 2nd Class
To convert a transition table to a state table.
Assume that the states S0, S1, S2, S3 equal to 00, 01 10, and 11, respectively.
Present State Next State A+ B+ Output (Z)
A B X=0 X=1 X=0 X=1
S0
S1
S3
S2

Step 5: State graph

Page | 11 Prepared by: Dr. Dunia S.

Digital System Design CoE233 2nd Class
2. Analysis of Clocked Sequential Circuits using Signal Tracing and Timing Charts
The basic procedure to analyze finite state machines to find the output sequence resulting from a given input
sequence by tracing 0 and 1 signals through the circuit is as follows:

1. Assume an initial state of the flip-flops (all flip-flops reset to 0 unless otherwise specified).
2. For the first input in the given sequence, determine the circuit output(s) and flip-flop inputs.
3. Determine the new set of flip-flop states after the next active clock edge.
4. Determine the output(s) that corresponds to the new states.
5. Repeat 2, 3, and 4 for each input in the given sequence.

Example 1: Determine the timing chart for the following circuit using the input sequence: X=01101 (signal
tracing). In this circuit, the initial state is A = B = 0, and all state changes occur after the rising edge of the
clock.

I/P Present State Next State O/P

X A B DA A+ DB B+ Z
0
1
1
0
1

Timing chart
Page | 12 Prepared by: Dr. Dunia S.
Digital System Design CoE233 2nd Class
Example 2: Determine the timing chart for the following circuit using the input sequence: X=10101010…
(signal tracing). In this circuit, the initial state is A = B = 0, and all state changes occur after the falling edge
of the clock.

I/P Present State Next State O/P

X A B JA KA A+ JB KB B+ Z
1
0
1
0
1

Timing chart

Page | 13 Prepared by: Dr. Dunia S.

Digital System Design CoE233 2nd Class
General Models for Finite State Machines (Sequential Circuits)
A sequential circuit can be divided conveniently into two parts:
1. The flip-flops which serve as memory for the circuit.
2. The combinational logic which realizes the input functions for the flip-flops and the output
functions.
The combinational logic may be implemented with gates, with a ROM, or with a PLA.
For general model of Mealy circuit, the combinational subcircuit realizes the n output functions and the k
next-state functions, which serve as inputs to the D flip-flops: (see figure 3)

When a set of inputs is applied to the circuit, the combinational subcircuit generates the outputs (Z1, Z2, . .
. , Zn) and the flip-flop inputs (D1, D2, . . . , Dk). Then, a clock pulse is applied and the flip-flops change to
the proper next state. This process is repeated for each set of inputs.

Figure 3 General Model for Mealy Circuit Using Clocked D Flip-Flops

Page | 14 Prepared by: Dr. Dunia S.

Digital System Design CoE233 2nd Class
The general model for the clocked Moore circuit (see figure 4) is similar to the clocked Mealy circuit. The
output subcircuit is drawn separately for the Moore circuit because the output is only a function of the
present state of the flip-flops and not a function of the circuit inputs. Operation of the Moore circuit is
similar to that of the Mealy except when a set of inputs is applied to the Moore circuit, the resulting outputs
do not appear until after the clock causes the flip-flops to change state.

Figure 4 General Model for Moore Circuit Using Clocked D Flip-Flops

Page | 15 Prepared by: Dr. Dunia S.

Digital System Design CoE233 2nd Class
Example:
A sequential circuit of the form shown in figure below is constructed using a ROM and two D flip-flops.
The contents of the ROM are given in the table. Construct a transition table and state graph for the circuit.
Q1 Q2 X1 X2 D1 D2 Z1 Z2
0 0 0 0 0 0 1 0
0 0 0 1 0 0 1 0
0 0 1 0 0 1 1 0
0 0 1 1 0 1 1 0
0 1 0 0 1 1 0 0
0 1 0 1 1 1 1 0
0 1 1 0 1 0 0 1
0 1 1 1 1 0 1 1
1 0 0 0 1 1 0 0
1 0 0 1 0 0 0 0
1 0 1 0 1 1 0 1
1 0 1 1 0 0 0 1
1 1 0 0 1 0 0 0
1 1 0 1 0 1 0 0
1 1 1 0 1 0 0 0
1 1 1 1 0 1 0 0

D1 = Q1+= Σ

D2 = Q2+= Σ

Z1= Σ
Z2= Σ

Page | 16 Prepared by: Dr. Dunia S.

Digital System Design CoE233 2nd Class
The K-maps:
Q1Q2 Q1Q2
X1 X2 00 01 11 10 X1 X2 00 01 11 10
00 00
01 01
11 11
10 10
Q1+ Q2+
Q1Q2 Q1Q2
X1 X2 00 01 11 10 X1 X2 00 01 11 10
00 00
01 01
11 11
10 10
Z1 Z2
The state table:
P. S. Next State Q1+Q2+ O/P (Z1Z2)
Q1 Q2 X1X2: 00 01 11 10 X1X2: 00 01 11 10
0 0
0 1
1 1
1 0

P. S. Next State Q1+Q2+ O/P (Z1Z2)

Q1 Q2 X1X2: 00 01 11 10 X1X2: 00 01 11 10
S0
S1
S3
S2

The state graph:

Page | 17 Prepared by: Dr. Dunia S.

Digital System Design CoE233 2nd Class
Problems
1. Analyze the following clocked synchronous sequential circuit by performing the following steps:
(a) Write the equations for the flip-flop inputs and the output equation.
(b) Construct the state table.
(c) Construct the state graph.

2. Construct a state table and graph for the following logic circuit.

3. Construct a state table and graph for the following logic circuit.

Page | 18 Prepared by: Dr. Dunia S.

Digital System Design CoE233 2nd Class
4. Consider the circuit shown.
a. Construct a transition table and state graph for the following circuit. Is the circuit a
Mealy or Moore circuit? Does the circuit have any unused states?
b. Draw a timing diagram for the input sequence X = 01100. Assume the initial state
Q1 = Q2 = 0, and all state changes occur after the falling edge of the clock.
c. What is the output sequence for the input sequence?

5. For the following sequential circuit, the table gives the contents of the PLA. (All PLA
outputs are 0 for input combinations not listed in the table.) Construct a transition table and
draw a state graph.

Page | 19 Prepared by: Dr. Dunia S.