Sequential Synchronous Circuit Analysis
General Model
• Current State at time (t) is stored in an array of flip-flops.
• Next State at time (t+1) is a Boolean function of State and
Inputs.
• Outputs at time (t) are a Boolean function of State(t) and
(sometimes) Inputs (t).
Inputs Outputs
Combina-
tional
Storage Logic
Elements
Next
State State
CLK
Example 1
Input: x(t)
Output: y(t) x
D Q A
State: (A(t), B(t))
C Q
A
What is the Output Function?
What is the Next State Function?
D Q B
CP C Q B
y
Example 1
Boolean equations
for the functions:
• A(t+1) = A(t)x(t) + B(t)x(t)
x
D Q A
• B(t+1) = A(t)x(t) C Q A
• y(t) = x(t)(B(t) + A(t)) Next State
D Q B
CP C Q' B
Output
State Table Characteristics
State table – a multiple variable table with the
following four sections:
• Present State – the values of the state variables for
each allowed state.
• Input – the input combinations allowed.
• Next-state – the value of the state at time (t+1) based
on the present state and the input.
• Output – the value of the output as a function of the
present state and (sometimes) the input.
From the viewpoint of a truth table:
• the inputs are Input, Present State
• and the outputs are Output, Next State
Example 1: State Table
The state table can be filled in using the next
state and output equations:
A(t+1) = A(t)x(t)+B(t)x(t) B(t+1) =A (t)x(t)
y(t) =x (t)(B(t) + A(t))
Present State Input Next State Output
A(t) B(t) x(t) A(t+1) B(t+1) y(t)
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
Example 1: Alternate State Table
2-dimensional table that matches well to a K-map.
Present state rows in Gray code order.
• A(t+1) = A(t) x(t) + B(t) x(t)
• B(t+1) =A(t) x(t)
• y(t) =x(t) (B(t) + A(t))
Present Next State Output
State x(t)=0 x(t)=1 x(t)=0 x(t)=1
A(t) B(t) A(t+1)B(t+1) A(t+1)B(t+1) y(t) y(t)
0 0 0 0 0 1 0 0
0 1 0 0 1 1 1 0
1 1 0 0 1 0 1 0
1 0 0 0 1 0 1 0
State Diagrams
The sequential circuit function can be represented
in graphical form as a state diagram with the
following components:
• A circle with the state name in it for each state
• A directed arc from the Present State to the Next
State for each state transition
• A label on each directed arc with the Input values which
causes the state transition, and
• A label:
On each circle with the output value produced, or
On each directed arc with the output value produced.
State Diagrams
Label form:
• On circle with output included:
state/output
Moore type output depends only on state
• On directed arc with the output included:
input/output
Mealy type output depends on state and input
Example 1: State Diagram
x=0/y=0 x=0/y=1 x=1/y=0
Which type?
Diagram gets AB
confusing for 00 10
large circuits x=0/y=1
For small circuits, x=1/y=0
usually easier to
understand than x=1/y=0
the state table x=0/y=1
01 11
x=1/y=0
Equivalent State Definitions
Two states are equivalent if their response for
each possible input sequence is an identical output
sequence.
Alternatively, two states are equivalent if their
outputs produced for each input symbol is
identical and their next states for each input
symbol are the same or equivalent.
Equivalent State Example 1
0 1
For states S3 and S2,
• the output for input S0/0 S1
0 is 1 and input 1 is 0, 0/1
and
• the next state for input 0/1
0/1 1/0
0 is S0 and for input
1 is S2.
• states S3 and S2 are
S2
1/0
S3
equivalent.
1/0
Equivalent State Example
0/0
Replacing S3 and S2 1/0
by a single state gives
state diagram: S0 S1
0/1
Examining the new diagram,
states S1 and S2 are equivalent
since 0/1 1/0
• their outputs for input
0 is 1 and input 1 is 0,
and
• their next state for input
S2
0 is S0 and for input
1/0
1 is S2,
0/0 1/0
Replacing S1 and S2 by a
single state gives state S0 S1
diagram: 0/1
1/0
Moore and Mealy Models
Sequential Circuits or Sequential Machines are also called
Finite State Machines (FSMs). Two formal models exist:
Moore Model Mealy Model
• Named after E.F. Moore • Named after G. Mealy
• Outputs are a function • Outputs are a function
ONLY of states of inputs AND states
• Usually specified on the • Usually specified on the
states. state transition arcs.
Moore and Mealy Example Diagrams
Mealy Model State Diagram
maps inputs and state to outputs x=1/y=0
x=0/y=0
0 1
x=0/y=0 x=1/y=1
x=0
Moore Model State Diagram
maps states to outputs
0/0
x=0
x=1 x=1
x=0
1/0 2/1
x=1
Moore and Mealy Example Tables
Moore Model state table maps state to outputs
Present Next State Output
State x=0 x=1
0 0 1 0
1 0 2 0
2 0 2 1
Mealy Model state table maps inputs and state to outputs
Present Next State Output
State x=0 x=1 x=0 x=1
0 0 1 0 0
1 0 1 0 1
Mixed Moore and Mealy Outputs
In real designs, some outputs may be Moore type
and other outputs may be Mealy type.
Example: Figure can be modified to illustrate this
• State 00: Moore
• States 01, 10, 0 1
and 11: Mealy
00/0 01
Simplifies output 0/1
specification
0/1
0/1 1/0
1/0
10 11
1/0
Example 2: Sequential Circuit Analysis
A
Logic Diagram: D Q Z
C RQ
B
D Q
C RQ
C
D Q
Clock CRQ
Reset
Example 2: Flip-Flop Input Equations
Variables
• Inputs: None
• Outputs: Z
• State Variables: A, B, C
Initialization: Reset to (0,0,0)
Equations
• A(t+1) = BC Z= A
• B(t+1) = B’C+BC’
• C(t+1) = A’C’
Example 2: State Table
X’ = X(t+1) ABC A’B’C’ Z
0 0 0 0 0 1 0
0 0 1 0 1 0 0
0 1 0 0 1 1 0
0 1 1 1 00 0
1 0 0 000 1
1 0 1 010 1
1 1 0 010 1
1 1 1 100 1
Example 2: State Diagram
Reset ABC
000
111 100 001
011 010 101
Which states are used?
What is the function of 110
the circuit?
Sequential Asynchronous Circuit Analysis
Register chip
74164
Memory Design with D Flip Flops
Require separate data
in and out lines
