Analysis of Clocked Sequential Circuits
Analysis: Obtaining a table/diagram for the time sequence of
inputs/outputs/internal states.
Examples: State Equations, State Table, State Diagram
1
Analysis of Clocked Sequential Circuits
Example of state equation:
A(t+1) = A(t)x(t) + B(t)x(t)
B(t+1) = A’(t)x(t)
A(t+1)=Ax+Bx
B(t+1)=A’x
y(t)=(A(t)+B(t)).x’(t)
= (A+B)x’
2
Example of state tables
Present state input Next State Output
A B x A B y
0 0 0 0 0 0
0 0 1 0 1 0
0 1 0 0 0 1
0 1 1 1 1 0
1 0 0 0 0 1
1 0 1 1 0 0
1 1 0 0 0 1
1 1 1 1 0 0
State equation:
A(t+1) = A(t)x(t) + B(t)x(t)
B(t+1) = A’(t)x(t)
y(t)=(A(t)+B(t)).x’(t)
3
Example of state tables-2nd form
Present state Next State Output
x=0 x=1 x=0 x=1
AB AB AB y y
00 00 01 0 0
01 00 11 1 0
10 00 10 1 0
11 00 10 1 0
State equation:
A(t+1) = A(t)x(t) + B(t)x(t)
B(t+1) = A’(t)x(t)
y(t)=(A(t)+B(t)).x’(t)
4
Example of state diagram
Present state Next State Output
x=0 x=1 x=0 x=1
AB AB AB y y
00 00 01 0 0
01 00 11 1 0
10 00 10 1 0
11 00 10 1 0
5
Mealy & Moore
Mealy machine: Output depends on both input & present state
Moore machine: Output only depends on present state.
6
Example of Mealy Machine
Present state Next State Output
x=0 x=1 x=0 x=1
AB AB AB y y
00 00 01 0 0
01 00 11 1 0
10 00 10 1 0
11 00 10 1 0
7
Example of Moore Machine
Present state input Next State
A B x A B
0 0 0 0 1
0 0 1 0 0
0 1 0 1 1
0 1 1 1 0
1 0 0 1 1
1 0 1 1 0
1 1 0 0 0
1 1 1 1 1
8
State Reduction and Assignment
Goal: Reduce the number of states while keeping the external input-output
requirements.
2m states need m flip-flops, so reducing the states may reduce flip-flops.
If two states are equal, one can be removed but what are equal states?
9
State Reduction Example
As an example consider the input sequence below:
010101110100 applied and start from state a.
State a a b c d e f f g f g a
input 0 1 0 1 0 1 1 0 1 0 0
output 0 0 0 0 0 1 1 0 1 0 0
10
State Reduction Example
Present State Next State Output
x=0 x=1 x=0 x=1
a a b 0 0
b c d 0 0
c a d 0 0
d e f 0 1
e a f 0 1
f g f 0 1
g a f 0 1
States e and g are equal since for each member of the set of
inputs, they give the same output and send the circuit either to
the same state or an equivalent state.
11
State Reduction Example
Present State Next State Output
x=0 x=1 x=0 x=1
a a b 0 0
b c d 0 0
c a d 0 0
d e f 0 1
e a f 0 1
f e f 0 1
NEW equal states: d and f
Table and state diagram after the first reduction: g is removed and replaced by state e.
12
State Reduction Example
Present State Next State Output
x=0 x=1 x=0 x=1
a a b 0 0
b c d 0 0
c a d 0 0
d e d 0 1
e a d 0 1
If we apply the same sequence
State a a b c d e d d e d e a
input 0 1 0 1 0 1 1 0 1 0 0
output 0 0 0 0 0 1 1 0 1 0 0
Table and state diagram after the second reduction: f is removed and replaced by state d.
13
Design Procedure
First Step: From the word description of the problem derive a state diagram
example:design a circuit to detect three or more consecutive 1’s in a string of bits
coming through an input line.
14
Design steps
[Link] word description, derive state diagram
[Link] the number of states
[Link] binary values to states
[Link] the binary coded state table
[Link] the type of flip-flop used
[Link] the simplified flip-flop input and output equations
[Link] the logic diagram
steps 4 to 7can be implemented by exact algorithms and can be
automated.
The part of the design that is well-defined is referred to as synthesis.
15
State Table for Sequence Decoder
Present State Input Next State Output
A B x A B y
A(t+1)= Σ(3,5,7)
0 0 0 0 0 0
B(t+1)= Σ(1,5,7)
0 0 1 0 1 0
0 1 0 0 0 0 Y(A,B,x)= Σ(6,7)
0 1 1 1 0 0
1 0 0 0 0 0
1 0 1 1 1 0
1 1 0 0 0 1
1 1 1 1 1 1
16
Synthesis Using D Flip-Flops
A(t+1)=DA(A,B,x)= Σ(3,5,7)
B(t+1)=DB(A,B,x)= Σ(1,5,7)
Y(A,B,x)= Σ(6,7)
17
Logic Diagram for a Sequence Detector
DA = Ax + Bx
DB= Ax + B’x
y=AB
18
Excitation Tables
Using flip-flops other than D can be complicated.
Why? Input equations for the circuit must be derived indirectly from the
state table
Excitation tables can help.
Excitation tables give us the flip-flop input for every state transition.
Example : JK- Recall Q(t+1) = JQ’(t) + K’Q(t)
Q(t) Q(t+1) J K
0 0 0 X
0 1 1 X
1 0 X 1
1 1 X 0
19
Excitation Tables- T flip-flop
Example : JK- Recall Q(t+1) = TQ’(t) + T’Q(t) = T XOR Q
Q(t) Q(t+1) T
0 0 0
0 1 1
1 0 1
1 1 0
20
Synthesis Using JK Flip-Flops
Present State Input Next State Flip-Flop Inputs
A B x A B JA KA JB KB
0 0 0 0 0 0 x 0 x
0 0 1 0 1 0 x 1 x
0 1 0 1 0 1 x x 1
0 1 1 0 0 0 x x 0
1 0 0 0 0 x 0 0 x
1 0 1 1 1 x 0 1 x
1 1 0 0 0 x 0 x 0
1 1 1 1 1 x 1 x 1
We also include J, K input conditions, derived from the excitation
table.
21
Synthesis Using JK Flip-Flops
22
Synthesis Using JK Flip-Flops
23
Synthesis Using T Flip-Flops
Example: 3-bit Binary Counter
The counter counts the clock.
Clock does not appear explicitly in the state diagram.
24
Synthesis Using T Flip-Flops
Present State Next State Flip-Flop Inputs
A2 A1 A0 A2 A1 A0 TA2 TA1 TA0
0 0 0 0 0 1 0 0 1
0 0 1 0 1 0 0 1 1
0 1 0 0 1 1 0 0 1
0 1 1 1 0 0 1 1 1
1 0 0 1 0 1 0 0 1
1 0 1 1 1 0 0 1 1
1 1 0 1 1 1 0 0 1
1 1 1 0 0 0 1 1 1
25
Synthesis Using T Flip-Flops
26
Synthesis Using T Flip-Flops
27
Summary
State Reduction, Synthesis
28