COMP3222/9222 Digital Circuits & Systems
6. Synchronous Sequential Circuits
Objectives
• Learn design techniques for circuits that use flip-flops
• Understand the concept of states and their
implementation with flip-flops
• Learn about the synchronous control of circuits using a
clock signal
• Learn how to design synchronous sequential circuits
• Learn how to specify synchronous sequential circuits
using VHDL
• Understand the techniques CAD tools use to synthesize
synchronous sequential circuits
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S2
Synchronous sequential circuits
• So far…
– Looked at combinational circuits, whose outputs are complete-
ly determined by their inputs, and
– Flip-flops, whose outputs depend upon their current state
• Now:
– Consider a general class of circuits, known as sequential
circuits, whose outputs depend upon past inputs and state, as
well as present input values
– A clock signal is commonly used to control the operation of a
sequential circuit; these circuits are therefore known as
synchronous sequential circuits (we won’t consider the design
of asynchronous sequential circuits in this course)
– Synchronous sequential circuits are designed using
combinational logic together with one or more flip-flops
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S3
• Circuit has primary inputs W and primary outputs Z
• The outputs of the FFs are referred to as the state, Q, of the circuit.
– In order to simplify analysis, the state should only change once per
clock cycle; FFs should therefore be edge-triggered
– Changes in state depend upon both the current inputs and the present
(current) outputs of the FFs, Q
• Outputs of the circuit depend upon the current state, and may also
depend upon the current inputs, though this is not required
B&V3, Figure 8.1
Combinational
circuit
Flip-flops
Clock
Q
W Z
Combinational
circuit
General form of a sequential circuit
May, or may not be present
next
state
present
state
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S4
• When the outputs Z only depend upon the current state Q, the
circuit is said to be of Moore type
• Alternatively, when the outputs Z depend upon the current state,
Q, and the inputs W, the circuit is said to be of Mealy type
– Mealy circuits may require less states than Moore circuits for similar
behaviour and are more responsive to changes in the inputs
• Because the functional behaviour of the circuit can be
represented using a finite number of states, sequential circuits
are also called finite state machines
B&V3, Figure 8.1
Combinational
circuit
Flip-flops
Clock
Q W Z Combinational
circuit
General form of a sequential circuit
20T3 COMP3222/9222 Synchronous Sequential Circuits
current
state
L06/S5
Basic design steps
• Consider the design of a simple circuit meeting the
following specifications:
1. The circuit has one input, w, and one output, z
2. z = 1 if during two immediately preceding clock cycles/periods
the input w was equal to 1. Otherwise, z = 0
3. All changes in the circuit occur on the positive edge of a clock
signal
• Input/output behaviour of the circuit:
Clock cycle: t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10
w : 0 1 0 1 1 0 1 1 1 0 1
z : 0 0 0 0 0 1 0 0 1 1 0
B&V3, Figure 8.2
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S6
Input/output behaviour of the circuit
• Consider the design of a simple circuit meeting the
following specifications:
1. The circuit has one input, w, and one output, z
2. z = 1 if during two immediately preceding clock cycles/periods
the input w was equal to 1. Otherwise, z = 0
3. All changes in the circuit occur on the positive edge of a clock
signal
• The circuit detects two or more consecutive 1s. Circuits
that detect the occurrence of a particular input pattern
are referred to as sequence detectors
• Clearly, the output doesn’t only depend on the present
value of w…easily seen if we consider the desired
input/output behaviour of the circuit
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S7
• The different outputs during cycles t4 and t8 or t2 and t5
illustrate that the output must be determined by some
state of the circuit rather than by the current input value
• The first step in designing a finite state machine is to
determine how many states are needed and which
“transitions” are possible from one state to another
Clock cycle: t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10
w : 0 1 0 1 1 0 1 1 1 0 1
z : 0 0 0 0 0 1 0 0 1 1 0
Input/output behaviour of the circuit
B&V3, Figure 8.2
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S8
Behaviour of state machine
• There is no set procedure for determining the number of states
• In our example:
– Select a starting state that the circuit should enter when first powered
on or when a reset signal is applied; call it state A
– While w = 0, the circuit need not do anything, and so each active clock
edge results in the circuit remaining in state A
– When w = 1, the machine should recognize this and move to a new
state, B, say. The transition takes place on the next active clock edge
after w = 1.
– In both states A and B, the output z = 0 as the machine has not yet
seen w = 1 for 2 consecutive clock cycles.
– When in state B, if w = 0 at the next active clock edge, the circuit should
return to state A. However, if w = 1 is seen in state B, the circuit should
change to a third state called C and generate an output z = 1.
– The circuit should remain in state C and output z = 1 as long as w = 1.
When w becomes 0, the machine should return to state A.
• As all possible values for w have been considered in all possible
states, we can conclude that 3 states are enough.
A
B
C
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S9
State diagram
• The behaviour of a sequen-
tial circuit can be described
in several ways.
• The conceptually easiest is to use a
pictorial representation in the form of a
state diagram, which is a directed graph
that depicts states of the circuit as nodes
and transitions between states as
directed edges.
• The state diagram corresponding to our
specification is as shown to the right.
• It should be noted that any labels instead
of letters could be used for the states,
and that the transition that is taken is the
one associated with the input present
when the active clock edge arrives.
20T3 COMP3222/9222 Synchronous Sequential Circuits
⁄ ⁄
B&V3, Figure 8.3
C z 1 = ⁄
Reset
B z 0 = A z 0 = w 0 =
w 1 =
w 1 =
w 0 =
w 0 = w 1 =
L06/S10
Present Next state Output
state w = 0 w = 1 z
A A B 0
B A C 0
C A C 1
State table
• While a state diagram is easy to understand, for implementation it
is more convenient to translate the diagram into tabular form
• A state table indicates all transitions from each present state to
the next state for different input signal values
• For our design, the state table is as shown:
– Note that here the output is listed with respect to the present state only
B&V3, Figure 8.4
20T3 COMP3222/9222 Synchronous Sequential Circuits
C z 1 = ⁄
Reset
B z 0 = ⁄ A z 0 = ⁄ w 0 =
w 1 =
w 1 =
w 0 =
w 0 = w 1 =
State table:
L06/S11
State assignment
• The state table of the previous slide defines 3 states in
terms of letters A, B and C
• When implemented in a logic circuit, each state is
represented by a particular valuation of state variables
• Each state variable is implemented in the form of a flip-flop
– In our example, with three states to represent, at least two state
variables are required
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S12
Moore sequential circuit with two state flip-flops
• Upper case Y1 and Y2 are called the next-state variables
• Lower case y1 and y2 are called the present-state variables
• Next, we need to determine what type of flip-flop to use and design
the combinational circuit blocks
Combinational
circuit
Combinational
circuit
Clock
y2
z
w
y1Y1
Y2
B&V3, Figure 8.5
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S13
Present
Next state
state w = 0 w = 1 Output
y 2 y 1 Y 2 Y 1 Y 2 Y 1
z
A 00 00 01 0
B 01 00 10 0
C 10 00 10 1
11 dd dd d
State-assigned table
• We therefore need to produce a truth table that defines the
function of the combinational circuits.
• More importantly, this requires us to assign a specific valuation of
the state variables to each state, resulting in a so-called state-
assigned table for the circuit
B&V3, Figure 8.6
20T3 COMP3222/9222 Synchronous Sequential Circuits
Present Next state Output
state w = 0 w = 1 z
A A B 0
B A C 0
C A C 1
State assigned table:State table:
L06/S14
• Depends on flip-flop type used for the implementation
– D-type is most straightforward
Derivation of logic expressions
B&V3, Figure 8.7
20T3 COMP3222/9222 Synchronous Sequential Circuits
w 00 01 11 10
0
1
0
1 0
y 2 y 1
w
00 01 11 10
0
1
0 d
1 d
y
2
y
1
d
d
0
0
0
0
0
0
1
0 1
0
1
0
d
y
1
0
1
y
2
Y
1
wy2 y 1 =
Y
2
wy
2
y 1 wy2 y 1
+ =
z y 2 y 1
=
Ignoring don’t cares Using don’t cares
Y
1
wy2 y 1 =
Y
2
wy
1
wy
2
+ =
z y
2
=
w y 1 y 2 +
( ) =
Present Next state
state w = 0 w = 1 Output
y 2 y 1 Y 2 Y 1 Y 2 Y 1
z
00 00 01 0
01 00 10 0
10 00 10 1
11 dd dd d
State assigned table:
L06/S15
D Q
Q
D Q
Q
Y 2
Y 1
w
Clo ck
z
y 1
y 2
R esetn
Final implementation
B&V3, Figure 8.8
20T3 COMP3222/9222 Synchronous Sequential Circuits
z y 2 = Y 2 wy1 wy2 + =
w y
1
y
2
+ ( ) =
Y
1
wy2 y 1 =
Resetn
Next state
logic
L06/S16
Timing diagram of the
circuit
t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10
1
0
1
0
1
0
1
0
Clock
w
y 1
y 2
1
0
z
B&V3, Figure 8.9
D Q
Q
D Q
Q
Y 2
Y 1
w
Clo ck
z
y 1
y 2
R esetn
20T3 COMP3222/9222 Synchronous Sequential Circuits
Resetn
L06/S17
Summary of design steps
1. Obtain the specification of the desired circuit
2. Derive the states for the machine and create a state diagram.
Given a starting state, consider the behaviour in response to
all possible inputs and identify new states as required. Repeat
for all added states until all possible inputs have been
considered for all states. When finished, the state diagram
shows all states and the conditions under which the circuit
moves from one state to another.
3. Create a state table from the state diagram.
4. Determine the number of state variables required to represent all
the states and perform a state assignment.
5. Given the type of flip-flops to be used, derive the next-state logic
expressions to control the FF inputs and to produce the desired
output.
6. Implement the circuit.
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S18
State-assignment problem
• In the example we’ve just considered, we have seen
straightforward implementations following from the
state assignment we chose
• Is it possible to obtain better implementations for
different assignments?
YES, it is!
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S19
Present Next state
state w = 0 w = 1 Output
y 2 y 1 Y 2 Y 1 Y 2 Y 1
z
A 00 00 01 0
B 01 00 11 0
C 11 00 11 1
10 dd dd d
Improved state assignment for Ex 1
• Choosing C = 11 rather than C = 10, as we previously did, and
choosing to implement the circuit using D-type flip-flops results in
the next-state and output expressions:
Y1 = D1 = w
Y2 = D2 = wy1
z = y2
B&V3, Figure 8.16
20T3 COMP3222/9222 Synchronous Sequential Circuits
C z 1 = ⁄
Reset
B z 0 = ⁄ A z 0 = ⁄ w 0 =
w 1 =
w 1 =
w 0 =
w 0 = w 1 =
L06/S20
Circuit for improved state assignment
D Q
Q
D Q
Q
Y 2
Y 1
w
Clo ck
z
y 1
y 2
R esetn
Previous circuit
20T3 COMP3222/9222 Synchronous Sequential Circuits
t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10
1
0
1
0
1
0
1
0
Clock
w
y 1
y 2
1
0
z
D Q
Q
D Q
Q
Y 2
Y 1
w
Clock
z
y 1
y 2
Resetn
B&V3, Figure
8.17
L06/S21
Mealy state machines
• In contrast to Moore state machines, in which the output is purely
a function of the present state of the circuit, in Mealy machines,
the output is also a function of the circuit’s current inputs
• Mealy machines thereby provide additional flexibility and
responsiveness in the design of sequential circuits
• In our first example, the output was required to become 1 in the
cycle after two consecutive 1s on the input had been detected.
• Suppose instead that the output should become 1 in the clock cycle
during which a second or further consecutive 1 is detected.
• The input/output sequence should then look as follows:
Clock cycle: t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10
w : 0 1 0 1 1 0 1 1 1 0 1
z : 0 0 0 0 1 0 0 1 1 0 0
B&V3, Figure 8.22
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S22
• Note that now only two states are needed because we
allow the output value to depend upon the present value
of the input as well as the present state of the machine
• The FSM is implemented by following the design steps
previously outlined
State diagram for revised example 1
A
w 0 = z 0 = ⁄
w 1 = z 1 = ⁄ B w 0 = z 0 = ⁄
Reset
w 1 = z 0 = ⁄
B&V3, Figure 8.23
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S23
Present Next state Output z
state w = 0 w = 1 w = 0 w = 1
A A B 0 0
B A B 0 1
State table for the revised example 1
• Note that the output value is now dependent upon the
present state as well as the input value
B&V3, Figure 8.24
A
w 0 = z 0 = ⁄
w 1 = z 1 = ⁄ B w 0 = z 0 = ⁄
Reset
w 1 = z 0 = ⁄
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S24
Present Next state Output
state w = 0 w = 1 w = 0 w = 1
y Y Y z z
A 0 0 1 0 0
B 1 0 1 0 1
State-assigned table for revised example 1
• Assuming D-type flip-flops are selected to be used in the
implementation of the machine, the next-state and output
expressions are:
Y = D = w
z = wy
B&V3, Figure 8.25
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S25
Clock
Resetn
D Q
Q
w
z
t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10
1
0
1
0
1
0
1
0
Clock
y
w
z
y
Implementation of revised example 1
B&V3, Figure 8.26
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S26
Using CAD tools to design FSMs
• Manually designing FSMs is tedious and error-prone
– One could use structural VHDL to input a manually derived
design before simulation and implementation
– But CAD tools offer a better alternative, namely, to enter the
state diagram and to derive the design automatically
• Graphical tools exist for this purpose
• More commonly, behavioural HDL is used to capture the diagram
• Let’s take a look at this approach with our “two-1s”
recognizer
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S27
Reminder: FSM of Example 1
C z 1 = ⁄
Reset
B z 0 = ⁄ A z 0 = ⁄ w 0 =
w 1 =
w 1 =
w 0 =
w 0 = w 1 =
Observe that state diagrams for Moore machines associate
output values with the state nodes and only list the inputs
that lead to each state transition.
A single ‘1’ has
just been seen
Two successive ‘1’s
have just been seen
Initial state – just
seen a ‘0’
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S28
10 BEGIN
11 PROCESS ( Resetn, Clock )
12 BEGIN
13 IF Resetn = ‘0’ THEN
14 y <= A ;
15 ELSIF (Clock'EVENT AND Clock = '1') THEN
16 CASE y IS
17 WHEN A => — each state needs a WHEN
18 IF w = ‘0’ THEN — input determines
19 y <= A ; -- next state
20 ELSE
21 y <= B ;
22 END IF ;
23 WHEN B => — when in state B
24 IF w = ‘0’ THEN
25 y <= A ;
26 ELSE
27 y <= C ;
28 END IF ;
29 WHEN C => — state C
30 IF w = ‘0’ THEN
31 y <= A ;
32 ELSE
33 y <= C ;
34 END IF ;
35 END CASE ;
36 END IF ;
37 END PROCESS ;
38 z <= '1' WHEN y = C ELSE '0' ; -- output depends on state
39 END Behavior ;
VHDL code for the Moore-type FSM of Ex 1
• There is no standard way
of describing FSMs
• Using VHDL syntax, there
are a few different ways of
describing FSMs
– Note user-defined signal type
[an enumerated type] (line 8)
– The compiler chooses the
number of state flip-flops and
the state assignment
– Changes in state occur on
positive clock edges
B&V3, Figure 8.29
1 LIBRARY ieee ;
2 USE ieee.std_logic_1164.all ;
3 ENTITY simple IS
4 PORT (Clock, Resetn, w : IN STD_LOGIC ;
z : OUT STD_LOGIC ) ;
5 END simple ;
7 ARCHITECTURE Behavior OF simple IS
8 TYPE State_type IS (A, B, C) ;
9 SIGNAL y : State_type ;
C z 1 = ⁄
Reset
B z 0 = ⁄ A z 0 = ⁄ w 0 =
w 1 =
w 1 =
w 0 =
w 0 = w 1 =
• For this simple FSM it is easy to check its correctness
• For more complex FSMs, there may be a large number
of possible states and inputs, so the designer needs to
plan sequences of input patterns and corresponding
acceptance tests carefully
Simulation results for the implemented circuit
B&V3, Figure 8.32
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S30
• Note the explicit reference to
the present and next state here
• First process implements the
combinational logic to the left
of the FFs, which determines
the next state in L06/S13
• Second process implements
the state FFs by giving effect
to the state transition
PROCESS (Clock, Resetn)
BEGIN
IF Resetn = '0' THEN
y_present <= A ;
ELSIF (Clock'EVENT AND Clock = '1') THEN
y_present <= y_next ;
END IF ;
END PROCESS ;
z <= '1' WHEN y_present = C ELSE '0' ;
END Behavior ;
Common alternate style of VHDL code for the
Moore-type FSM of Example 1
B&V3, Figure 8.33
ARCHITECTURE Behavior OF simple IS
TYPE State_type IS (A, B, C) ;
SIGNAL y_present, y_next : State_type ;
BEGIN
PROCESS ( w, y_present )
BEGIN
CASE y_present IS
WHEN A =>
IF w = ‘0’ THEN
y_next <= A ;
ELSE
y_next <= B ;
END IF ;
WHEN B =>
IF w = ‘0’ THEN
y_next <= A ;
ELSE
y_next <= C ;
END IF ;
WHEN C =>
IF w = ‘0’ THEN
y_next <= A ;
ELSE
y_next <= C ;
END IF ;
END CASE ;
END PROCESS ;
C z 1 = ⁄
Reset
B z 0 = ⁄ A z 0 = ⁄ w 0 =
w 1 =
w 1 =
w 0 =
w 0 = w 1 =
N
ex
t-s
ta
te
lo
gi
c
State flip-flops
Output logic
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S31
• It is possible for the user to manually specify a desired
state assignment, but there is no standardized
approach for doing so
• In Quartus, this is done as follows:
• But note that this should not normally be necessary
ARCHITECTURE Behavior OF simple IS
TYPE State_TYPE IS (A, B, C) ;
ATTRIBUTE ENUM_ENCODING : STRING ;
ATTRIBUTE ENUM_ENCODING OF State_type : TYPE IS "00 01 11" ;
SIGNAL y_present, y_next : State_type ;
BEGIN
.
.
.
User-defined state assignment
B&V3, Figure 8.34
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S32
BEGIN
PROCESS ( w, y_present )
BEGIN
CASE y_present IS
WHEN A =>
IF w = ‘0’ THEN y_next <= A ;
ELSE y_next <= B ;
END IF ;
WHEN B =>
IF w = ‘0’ THEN y_next <= A ;
ELSE y_next <= C ;
END IF ;
WHEN C =>
IF w = ‘0’ THEN y_next <= A ;
ELSE y_next <= C ;
END IF ;
WHEN OTHERS =>
y_next <= A ;
END CASE ;
END PROCESS ;
PROCESS ( Clock, Resetn )
BEGIN
IF Resetn = '0' THEN
y_present <= A ;
ELSIF (Clock'EVENT AND Clock = '1') THEN
y_present <= y_next ;
END IF ;
END PROCESS ;
z <= '1' WHEN y_present = C ELSE '0' ;
END Behavior ;
Using constants for manual state assign-
ment – works with all VHDL compilers
• Note the need for a WHEN
OTHERS clause in the
next_state logic as there is no
enumerated state_type;
y_present is simply a
STD_LOGIC_VECTOR
B&V3, Figure 8.35
LIBRARY ieee ;
USE ieee.std_logic_1164.all ;
ENTITY simple IS
PORT ( Clock, Resetn, w : IN STD_LOGIC ;
z : OUT STD_LOGIC ) ;
END simple ;
ARCHITECTURE Behavior OF simple IS
SIGNAL y_present, y_next : STD_LOGIC_VECTOR(1 DOWNTO 0);
CONSTANT A : STD_LOGIC_VECTOR(1 DOWNTO 0) := "00" ;
CONSTANT B : STD_LOGIC_VECTOR(1 DOWNTO 0) := "01" ;
CONSTANT C : STD_LOGIC_VECTOR(1 DOWNTO 0) := "11" ;
Reminder: Mealy-type FSM for Ex 1
A
w 0 = z 0 = ⁄
w 1 = z 1 = ⁄ B w 0 = z 0 = ⁄
Reset
w 1 = z 0 = ⁄
B&V3, Figure 8.23
Observe that state diagrams for Mealy machines list the
output values together with the input that leads to each
state transition.
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S34
VHDL code for the Mealy-type FSM of Ex 1
• Note use of second process to
determine output independently
of the state transition logic
• It is also common to separate the
next-state logic from the state
transition logic, as we saw in
slide L06/S31, in which case,
there would be 3 processes for
the Mealy machine
B&V3, Figure 8.36
LIBRARY ieee ;
USE ieee.std_logic_1164.all ;
ENTITY mealy IS
PORT ( Clock, Resetn, w : IN STD_LOGIC ;
z : OUT STD_LOGIC ) ;
END mealy ;
ARCHITECTURE Behavior OF mealy IS
TYPE State_type IS (A, B) ;
SIGNAL y : State_type ;
BEGIN
PROCESS ( Resetn, Clock )
BEGIN
IF Resetn = '0' THEN
y <= A ;
ELSIF (Clock'EVENT AND Clock = '1') THEN
CASE y IS
WHEN A =>
IF w = ‘0’ THEN y <= A ;
ELSE y <= B ;
END IF ;
WHEN B =>
IF w = ‘0’ THEN y <= A ;
ELSE y <= B ;
END IF ;
END CASE ;
END IF ;
END PROCESS ;
PROCESS ( y, w )
BEGIN
CASE y IS
WHEN A =>
z <= '0' ; WHEN B =>
z <= w ;
END CASE ;
END PROCESS ;
END Behavior ;
O
ut
pu
t l
og
ic
20T3 COMP3222/9222 Synchronous Sequential Circuits
A
w 0 = z 0 = ⁄
w 1 = z 1 = ⁄
B
w 0 = z 0 = ⁄
Reset
w 1 = z 0 = ⁄
L06/S35
Simulation results for the Mealy machine
B&V3, Figure 8.37
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S36
Potential problem with asynchronous inputs
to the Mealy machine
• Here changes in w occur after negative clock edges
• z should not be asserted until after w is asserted for 1 clock period
– If z is input to another circuit that is not controlled by the same clock, we
could get big problems (downstream errors)
– On the other hand, a downstream circuit controlled by the same clock
should ignore the erroneous pulse
B&V3, Figure 8.38
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S37
Example 2: Design a control circuit for a
bus-based register swap
• Consider the control required to swap the contents of R1
and R2 via a bus using R3 for temporary storage
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S38
Details for connecting registers to a bus
• Consider two 2-bit registers
– 3-state buffers used to avoid “tying” outputs together
Synchronous Sequential Circuits20T3 COMP3222/9222
i o
c c o
0 Z = high impedance (open circuit)
1 i
3-state buffer:
Tri-state® buffer:
0
1
L06/S39
Control circuit design
• Consider the control required to swap the contents of
R1 and R2 using R3 for temporary storage
– What register transfers are required to effect the swap?
– Which control signals need to be asserted for each transfer?
– When & how should the control signals be sequenced?
20T3 COMP3222/9222
In successive steps:
1. R3 <= R2
2. R2 <= R1
3. R1 <= R3
: R3in <= ‘1’; R2out <= ‘1’
: R2in <= ‘1’; R1out <= ‘1’
: R1in <= ‘1’; R3out <= ‘1’
Control
circuit
w
Clock
Done
R 1 out
R 2 out
R 1 in
R 2 in
R 3 out
R 3 in
Signals needed by control circuit
B&V3, Figure 8.10
20T3 COMP3222/9222 Synchronous Sequential Circuits
(Start signal)
L06/S41
w 0 =
D R 3 out 1 = R 1 in 1 = Done 1 = , , ⁄
w 0 =
w 1 =
B R 2 out 1 = R 3 in 1 = , ⁄
w 1 =
A No⁄
C R 1 out 1 = R 2 in 1 = , ⁄
w 0 =
w 1 =
transfer
w 0 =
w 1 =
Reset
Moore state diagram for example 2
B&V3, Figure 8.11
20T3 COMP3222/9222 Synchronous Sequential Circuits
In successive steps:
1. R3 <= R2
2. R2 <= R1
3. R1 <= R3
L06/S42
Present Next state Outputs
state
A A B 0 0 0 0 0 0 0
B C C 0 0 1 0 0 1 0
C D D 1 0 0 1 0 0 0
D A A 0 1 0 0 1 0 1
w = 0 w = 1
State table
for example 2
B&V3, Figure 8.12
D R 3 out 1 = R 1 in 1 = Done 1 = , , ⁄
w 0 =
w 1 =
C R 1 out 1 = R 2 in 1 = , ⁄
B R 2 out 1 = R 3 in 1 = , ⁄
w 1 =
A No⁄
w 0 =
w 1 =
transfer
w 0 =
w 1 =
Reset
w 0 =
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S43
Present Next state
state Outputs
A 00 00 0 1 0 0 0 0 0 0 0
B 01 10 1 0 0 0 1 0 0 1 0
C 10 11 1 1 1 0 0 1 0 0 0
D 11 00 0 0 0 1 0 0 1 0 1
State-assigned table, next-state and output
expressions for example 2 using D-type FFs
B&V3, Figure 8.13
R2out = R3in = y2y1
R1out = R2in = y2y1
R1in = R3out = Done = y2y1
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S44
Y1 = wy1 + y2y1 Y2 = y2y1 + y2y1
B&V3, Figure 8.14
Final implementation of example 2
B&V3, Figure 8.15
D Q
Q
D Q
Q
Done
w
Clock
Y
2
Y
1
y
2
y
1
y 2
y 1
R 1
in
R 3
out
R 1
out
R 2
in
R 2
out
R 3
in
20T3 COMP3222/9222 Synchronous Sequential Circuits
Y1 = wy1 + y2y1
Y2 = y2y1 + y2y1
R2out = R3in = y2y1
R1out = R2in = y2y1
R1in = R3out = Done = y2y1 Cost: 6x 2-input gates + 2 FFs
L06/S45
R2out = R3in = y2y1
R1out = R2in = y2y1
R1in = R3out = Done = y2y1
Improved state assignment for Ex 2
• Swapping the assignments for states C and D…
B&V3, Figure 8.18
w 00 01 11 10
0
1
1
1 1
y 2 y 1
Y 1 wy2 y 1 y 2 + =
w
00 01 11 10
0
1
1 1
1 1
y 2 y 1
Y 2 y 1 = B&V3, Figure 8.19
Present Next state
state Outputs
A 00 00 0 1 0 0 0 0 0 0 0
B 01 11 1 1 0 0 1 0 0 1 0
C 11 10 1 0 1 0 0 1 0 0 0
D 10 00 0 0 0 1 0 0 1 0 1
20T3 COMP3222/9222 Synchronous Sequential Circuits
Cost: 5x 2-input gates + 2 FFs
L06/S46
Y1 = wy2 + y2y1 Y2 = y1
Present Next state
state Outputs
A 0 001 0001 0010 0 0 0 0 0 0 0
B 0 010 0100 0100 0 0 1 0 0 1 0
C 0 100 1000 1000 1 0 0 1 0 0 0
D 1 000 0001 0001 0 1 0 0 1 0 1
One-hot encoding of example 2
• Treating the remaining 12 valuations of the state variables as don’t
cares results in:
Y1 = wy1 + y4, Y2 = wy1, Y3 = y2 and Y4 = y3
• The output expressions are just the outputs of the flip-flops:
R2out = R3in = y2, R1out = R2in = y3 and R1in = R3out = Done = y4
• These expressions are simpler than previously seen, but 4 FFs are
needed
• Simpler expressions, as often result from one-hot encodings, may
lead to faster circuits
B&V3, Figure 8.21
Synchronous Sequential Circuits L06/S47
R3out 1= R1in 1= Done 1=, ,
w 0=
w 1=
R1out 1= R2in 1=,
w 1= R⁄ 2out 1= R3in 1=,
A
w 0=
w 1=
Reset
w 0=
B
C
Mealy-type FSM for swapping two registers
• While the Mealy
implementation only re-
quires 3 states, this does
not necessarily imply a
simpler circuit since we still
need 2 FFs.
• The most important difference
with the Moore version is the
timing of the output signals,
which are generated one clock
cycle sooner.
• Note also that the entire swap
only takes 3 clock cycles for
the Mealy-type FSM, whereas
it takes 4 clock cycles to
complete for the Moore
machine.
B&V3, Figure 8.28
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S48
Sum A B + =
Shift register
Shift register
Adder
FSM Shift register
B
A
ai
bi
si
Clock
Complete design example:
serial addition
• We’ve looked at several addition schemes that added two n-bit
numbers in parallel (e.g., ripple-carry, carry-lookahead)
• In these schemes, the speed of the adder is important, but fast
adders are more complex and thus more expensive
• If speed is not important, then a more cost-effective option is to use
a serial adder in which bits are added a pair at a time
B&V3, Figure 8.39
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S49
Serial addition
• Let A = an-1an-2…a0 and B = bn-1bn-2…b0 be two
unsigned numbers that have to be added to produce
S = sn-1sn-2…s0
• Our task is to design a circuit that will perform the serial
addition, dealing with a pair of bits in one clock cycle
• Having loaded a pair of numbers in parallel, the process
starts by adding a0 and b0 and shifting the result, s0, into
the sum register. In the next clock cycle, bits a1 and b1
are added, including a possible carry from bit-position 0.
• Assume we are to use positive edge-triggered D-type
flip-flops in the design
20T3 COMP3222/9222 Synchronous Sequential Circuits
Sum A B + =
Shift register
Shift register
Adder
FSM Shift register
B
A
ai
bi
si
Clock
L06/S50
State diagram for the serial adder FSM
• An FSM is needed since the sum bit produced differs
depending upon the carry produced in the previous
cycle
• We therefore need two states depending upon the value
of the carry-in bit
carry-in 0 =
carry-in 1 =
G:
H:
G
00 1 ⁄
11 1 ⁄
10 0 ⁄
01 0 ⁄
H
10 1 ⁄
01 1 ⁄
00 0 ⁄
Reset
11 0 ⁄
ab s ⁄ ( )
B&V3, Figure 8.40
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S51
Present Next state Outputs
state ab=00 01 10 11 00 01 10 11
G G G G H 0 1 1 0
H G H H H 1 0 0 1
State table for the serial adder FSM
• The state table is readily obtained from the state
diagram
B&V3, Figure 8.41
G
00 1 ⁄
11 1 ⁄
10 0 ⁄
01 0 ⁄
H
10 1 ⁄
01 1 ⁄
00 0 ⁄
Reset
11 0 ⁄
ab s ⁄ ( )
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S52
Present
Next state Output
state ab=00 01 10 11 00 01 10 11
y Y s
0 0 0 0 1 0 1 1 0
1 0 1 1 1 1 0 0 1
State-assigned table for serial adder FSM
• A simple state assignment leads to the following next-
state and output equations:
• These are the same as for a full-adder with
carry-in y, carry-out Y, and sum s
B&V3, Figure 8.42
Y = ab + ay + by
s = a Å b Å y
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S53
Full
adder
a
b
s
D Q
Q
carry-out
Clock
Reset
Y y
Circuit for the serial adder FSM
B&V3, Figure 8.43
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S54
H 1 s 1 = ⁄
Reset
H 0 s 0 = ⁄
01
1011
11
01
10
G 1 s 1 = ⁄
G 0 s 0 = ⁄
01
10 00
01
00
10
11
00
00
11
State diagram for a Moore-type
serial adder FSM
• Now let’s consider the design of the equivalent Moore-type FSM
– We then need a separate state, i.e. two states, for each output we
found in the state diagram of the Mealy machine (slide L06/S51)
B&V3, Figure 8.44
G
00 1 ⁄
11 1 ⁄
10 0 ⁄
01 0 ⁄
H
10 1 ⁄
01 1 ⁄
00 0 ⁄
Reset
11 0 ⁄
ab s ⁄ ( )
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S55
Present Next state Output
state ab=00 01 10 11 s
G 0 G 0 G 1 G 1 H 0 0
G 1 G 0 G 1 G 1 H 0 1
H 0 G 1 H 0 H 0 H 1 0
H 1 G 1 H 0 H 0 H 1 1
State table for the Moore-type serial adder FSM
B&V3, Figure 8.45
20T3 COMP3222/9222 Synchronous Sequential Circuits
H 1 s 1 = ⁄
Reset
H 0 s 0 = ⁄
01
1011
11
01
10
G 1 s 1 = ⁄
G 0 s 0 = ⁄
01
10 00
01
00
10
11
00
00
11
L06/S56
Present
state ab=00 01 10 11 Output
y 2 y 1 Y 2 Y 1
s
00 0 0 01 0 1 10 0
01 0 0 01 0 1 10 1
10 0 1 10 1 0 11 0
11 0 1 10 1 0 11 1
State-assigned table for the Moore-type
serial adder FSM
• The next-state and output equations are:
Y1 = a Å b Å y2
Y2 = ab + ay2 + by2
s = y1
• The expressions for Y1 and Y2 correspond to the sum
and carry-out expressions in the full-adder circuit
B&V3, Figure 8.46
20T3 COMP3222/9222 Synchronous Sequential Circuits
Next state
L06/S57
Full
adder
a
b
D Q
Q
Carry-out
Clock
Reset
D Q
Q
s
Y 2
Y 1 Sum bit
y 2
y 1
Circuit for the Moore-type
serial adder FSM
• Referring back to the Mealy circuit of L06/S54, the output s is now
passed through an extra flip-flop and thus delayed by one clock cycle
B&V3, Figure 8.47
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S58
How do we build the serial adder?
How do we control its operation?
Synchronous Sequential Circuits20T3 COMP3222/9222
Sum A B + =
Shift register
Shift register
Adder
FSM Shift register
B
A
a
b
s
Clock
L06/S59
Q 3 Q 2 Q 1 Q 0
Clock
Parallel input
Parallel output
Shift/LoadSerialinput
D Q
Q
D Q
Q
D Q
Q
D Q
Q
Recall: Parallel-access shift register
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S60
Code for a left-to-right shift register
with an enable input
B&V3, Figure 8.48
LIBRARY ieee ;
USE ieee.std_logic_1164.all ;
-- left-to-right shift register with parallel load and enable
ENTITY shiftrne IS
GENERIC ( N : INTEGER := 4 ) ;
PORT ( R : IN STD_LOGIC_VECTOR(N-1 DOWNTO 0) ;
L, E, w : IN STD_LOGIC ;
Clock : IN STD_LOGIC ;
Q : BUFFER STD_LOGIC_VECTOR(N-1 DOWNTO 0) ) ;
END shiftrne ;
ARCHITECTURE Behavior OF shiftrne IS
BEGIN
PROCESS
BEGIN
WAIT UNTIL Clock'EVENT AND Clock = '1' ;
IF E = '1' THEN -- if enabled
IF L = '1' THEN -- depending upon the load signal
Q <= R ; -- either load a new word in parallel
ELSE
Genbits: FOR i IN 0 TO N-2 LOOP -- or shift the word to right
Q(i) <= Q(i+1) ;
END LOOP ;
Q(N-1) <= w ;
END IF ;
END IF ;
END PROCESS ;
END Behavior ; Synchronous Sequential Circuits L06/S61
VHDL code for the serial adder (part A)
B&V3, Figure 8.49
1 LIBRARY ieee ;
2 USE ieee.std_logic_1164.all ;
3 ENTITY serial IS
4 GENERIC ( length : INTEGER := 8 ) ;
5 PORT ( Clock : IN STD_LOGIC ;
6 Reset : IN STD_LOGIC ;
7 A, B : IN STD_LOGIC_VECTOR(length-1 DOWNTO 0) ;
8 Sum : BUFFER STD_LOGIC_VECTOR(length-1 DOWNTO 0) );
9 END serial ;
10 ARCHITECTURE Behavior OF serial IS
11 COMPONENT shiftrne -- include the parallel load shift register as a component
12 GENERIC ( N : INTEGER := 4 ) ;
13 PORT ( R : IN STD_LOGIC_VECTOR(N-1 DOWNTO 0) ;
14 L, E, w : IN STD_LOGIC ; -- load, enable, shift-in
15 Clock : IN STD_LOGIC ;
16 Q : BUFFER STD_LOGIC_VECTOR(N-1 DOWNTO 0) ) ;
17 END COMPONENT ;
18 SIGNAL QA, QB, Null_in : STD_LOGIC_VECTOR(length-1 DOWNTO 0) ;
19 SIGNAL s, Low, High, Run : STD_LOGIC ;
20 SIGNAL Count : INTEGER RANGE 0 TO length ;
21 TYPE State_type IS (G, H) ; -- our Mealy machine
22 SIGNAL y : State_type ;
… continued in Part b
Sum A B + =
Shift register
Shift register
Adder
FSM Shift register
B
A
a
b
s
Clock
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S62
VHDL code for the serial adder (part B)
B&V3, Figure 8.49
23 BEGIN
24 Low <= '0' ; High <= '1' ;
25 ShiftA: shiftrne GENERIC MAP (N => length)
26 PORT MAP ( A, Reset, High, Low, Clock, QA ) ;
27 ShiftB: shiftrne GENERIC MAP (N => length)
28 PORT MAP ( B, Reset, High, Low, Clock, QB ) ;
29 AdderFSM: PROCESS ( Reset, Clock )
30 BEGIN
31 IF Reset = ‘1’ THEN
32 y <= G ;
33 ELSIF Clock'EVENT AND Clock = '1' THEN
34 CASE y IS
35 WHEN G =>
36 IF QA(0) = ‘1’ AND QB(0) = ‘1’ THEN
y <= H ;
37 ELSE y <= G ;
38 END IF ;
39 WHEN H =>
40 IF QA(0) = ‘0’ AND QB(0) = ‘0’ THEN
y <= G ;
41 ELSE y <= H ;
42 END IF ;
43 END CASE ;
44 END IF ;
45 END PROCESS AdderFSM ;
46 WITH y SELECT
47 s <= QA(0) XOR QB(0) WHEN G,
48 NOT ( QA(0) XOR QB(0) ) WHEN H ;
49 Null_in <= (OTHERS => ‘0’) ;
50 ShiftSum: shiftrne GENERIC MAP ( N => length )
51 PORT MAP ( Null_in, Reset, Run, s,
Clock, Sum ) ;
52 Stop: PROCESS — shift in the result until the shift register is full
53 BEGIN
54 WAIT UNTIL (Clock’EVENT AND Clock = ‘1’) ;
55 IF Reset = ‘1’ THEN
56 Count <= length ;
57 ELSIF Run = '1' THEN
58 Count <= Count -1 ;
59 END IF ;
60 END PROCESS ;
61 Run <= '0' WHEN Count = 0 ELSE '1' ; -- stops counter and ShiftSum
62 END Behavior ;
G
00 1 ⁄
11 1 ⁄
10 0 ⁄
01 0 ⁄
H
10 1 ⁄
01 1 ⁄
00 0 ⁄
Reset
11 0 ⁄
ab s ⁄ ( )
Sum A B + =
Shift register
Shift register
Adder
FSM Shift register
B
A
a
b
s
Clock
load, enable, shift-in
load, enable
FSM state
transitions
FSM
output
L06/S6320T3 COMP3222/9222 Synchronous Sequential Circuits
shift-in
Counter counts down
from length to 0 and
deasserts Run signal
when it reaches 0
Synthesized serial adder
B&V3, Figure 8.50
Adder
FSM
Clock
E
w
L
E
w
L
b 7 b 0
a 7 a 0
E
w
L
E
L
Q 3 Q 2 Q 1 Q 0
D 3 D 2 D 1 D 0
1 0 0 0
Counter
0 0
Reset
Sum 7 Sum 0
0
1
0
1
Run
20T3 COMP3222/9222 Synchronous Sequential Circuits
0010 1101
1010 0101
Count Run State Sum
~R 8 1 G 0000 0000 (00)
↑Clk 7 1 H 0000 0000 (00)
↑Clk 6 1 G 1000 0000 (80)
↑Clk 5 1 H 0100 0000 (40)
↑Clk 4 1 H 0010 0000 (20)
↑Clk 3 1 G 1001 0000 (90)
↑Clk 2 1 H 0100 1000 (48)
↑Clk 1 1 G 1010 0100 (A4)
↑Clk 0 0 G 1101 0010 (D2)
8 7 6 5 4 3 2 1 0
a0 b0
1 1
0 0
1 1
1 0
0 0
1 1
0 0
0 1
L06/S64
New Question:State minimization
• How do we know the state diagram we have constructed
is as simple as can be – has as few states as possible?
• Minimizing the number of states:
Þpossibly fewer flip-flops needed to represent states
Þcomplexity of the FSM’s combinational logic may be reduced
• To reduce the number of states in a state diagram, some
states must be equivalent to others in terms of their
contribution to the overall behaviour of the FSM
• Definition: Two states Si and Sj are said to be
equivalent if and only if for every possible input
sequence the same output sequence will be produced
regardless of whether Si or Sj is the initial state
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S65
State minimization procedure
• It is possible to define an exhaustive minimization
procedure, as used in CAD tools, but it is tedious
• We’ll look at a more efficient but limited method to get
the general idea
• We exploit the idea that it is easy to show that some
states are definitely not equivalent and partition the set
of states into equivalent sets of states on that basis:
– First, partition the states into different sets on the basis of the
different output values they produce
– Next, consider the members of each set and determine whether
or not they all have next states that belong to the same sets, i.e.
refine the partitioning until all states within each set have the
same next state set for each possible input value
– When the partitioning cannot be further refined, replace each set
with a single state – a minimal number of states has been found
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S66
Present Next state Output
state w = 0 w = 1 z
A B C 1
B D F 1
C F E 0
D B G 1
E F C 0
F E D 0
G F G 0
State minimization Example 8.5
• Here, the initial partitioning P1 = (A B C D E F G)
• The different output values lead to a partitioning into two sets
P2 = (A B D)(C E F G)
• The first set has a next state in the first set when w = 0 and in the
second set when w = 1.
• However, state F differs from the other members of the second set
in that it has a next state in the first set when w = 1
B&V3, Figure 8.51
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S67
Present Next state Output
state w = 0 w = 1 z
A B C 1
B D F 1
C F E 0
D B G 1
E F C 0
F E D 0
G F G 0
State minimization Example 8.5 (cont)
• We therefore have P3 = (A B D)(C E G)(F)
• As state B has next state F when w = 1, we need to further partition
the first set to obtain P4 = (A D)(B)(C E G)(F)
• Checking all successor states for each set under each input we note
no further partitioning is necessary, thus 4 states suffice for this
example and we can label them A = (A D), B = (B), C = (C E G) and
F = (F)
B&V3, Figure 8.51
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S68
Present Nextstate Output
state w = 0 w = 1 z
A B C 1
B A F 1
C F C 0
F C A 0
Minimized state table for Example 8.5
• Thus the following minimized state table can be derived
• This functionally equivalent FSM only requires two state
flip-flops
B&V3, Figure 8.52
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S69
Vending machine (Example 8.6)
• Suppose we need to design the FSM for a vending
machine with the following requirements:
– The machine accepts nickels (5¢) and dimes (10¢)
– It takes 15¢ for an item to be dispensed from the machine
– If 20¢ is deposited, the machine will not provide change, but it
will credit the buyer with 5¢ and wait for the buyer to make a
second purchase
• All electronic signals are synchronized to the positive
edge of the clock signal
• A mechanical coin receptor generates a very slow sense
signal, and these trigger a single pulse corresponding to
the type of coin deposited
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S70
D Q
Q
sense N D Q
Q Clock
N
sense N
sense D
Clock
N
D
(a) Timing diagram
(b) Circuit that generates N
Signals for the vending machine
B&V3, Figure 8.53
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S71
S1 0 ⁄
S7 1 ⁄
DN
D N
S3 0 ⁄
S6 0 ⁄
S9 1 ⁄ S8 1 ⁄
S2 0 ⁄
S5 1 ⁄
S4 1 ⁄
DNDN
DNDN
DN
DN
DN
D
D N
D N
DN
N
Reset
State diagram for Example 8.6
B&V3, Figure 8.54
0¢
10¢
15¢
20¢
20¢
15¢
15¢5¢
10¢
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S72
Present Next state Output
state DN= 00 01 10 11 z
S1 S1 S3 S2 0
S2 S2 S4 S5 0
S3 S3 S6 S7 0
S4 S1 1
S5 S3 1
S6 S6 S8 S9 0
S7 S1 1
S8 S1 1
S9 S3 1
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
State table for Example 8.6
B&V3, Figure 8.55
Can this state table be minimized?
S1 0 ⁄
S7 1 ⁄
DN
D N
S3 0 ⁄
S6 0 ⁄
S9 1 ⁄ S8 1 ⁄
S2 0 ⁄
S5 1 ⁄
S4 1 ⁄
DNDN
DN
DN
DN
DN
DN
D
D N
D N
DN
N
Reset
(S1 S2 S3 S6)(S4 S5 S7 S8 S9)
S S S S
S O S O
S O O O
(S1)(S2 S6)(S3)(S4 S7 S8)(S5 S9)
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S73
Partition states based on output:
Refine sets based on next state:
Halt, since no further refinement
possible
Present Next state Output
state DN =00 01 10 11 z
S1 S1 S3 S2 0
S2 S2 S4 S5 0
S3 S3 S2 S4 0
S4 S1 1
S5 S3 1
–
–
–
– – –
– – –
Minimized state table for Example 8.6
B&V3, Figure 8.56
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S74
Minimized state diagram for Example 8.6
B&V3, Figure 8.57
S1 0 ⁄
S5 1 ⁄
DNDN
DN
DN
DN
D
D
D
N
N
N
S3 0 ⁄
S2 ⁄ 0
S4 1 ⁄
0¢
5¢
10¢
20¢
15¢
20T3 COMP3222/9222 Synchronous Sequential Circuits
Present Next state Output
state DN =00 01 10 11 z
S1 S1 S3 S2 0
S2 S2 S4 S5 0
S3 S3 S2 S4 0
S4 S1 1
S5 S3 1
–
–
–
– – –
– – –
L06/S75
S3
S2
D 0 ⁄
S1
D 1 ⁄
D 1 ⁄
N 1 ⁄
N 0 ⁄
N 0 ⁄
DN 0 ⁄
DN 0 ⁄
DN 0 ⁄
Mealy-type FSM for Example 8.6
B&V3, Figure 8.58
S1 0 ⁄
S5 1 ⁄
DNDN
DN
DN
DN
D
D
D
N
N
N
S3 0 ⁄
S2 ⁄ 0
S4 1 ⁄
Can you derive a VHDL output
expression for each graph?
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S76
Present Next state Output z
state w = 0 w = 1 w = 0 w = 1
A B C 0 0
B D 0
C F E 0 1
D B G 0 0
E F C 0 1
F E D 0 1
G F 0
–
–
–
–
Incompletely specified state table
• We have already applied the minimization procedure to some
incompletely specified tables
• In general, the procedure becomes more difficult to apply since all
possible output and next-state values need to be considered to
determine which design uses the least number of states
B&V3, Figure 8.59
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S77
Present Next state Output z
state w = 0 w = 1 w = 0 w = 1
A B C 0 0
B D 0
C F E 0 1
D B G 0 0
E F C 0 1
F E D 0 1
G F 0
–
–
–
–
Incompletely specified state table
• In this case, if the unspecified outputs are both assumed to be 0, the
partitioning P = (A)(B)(D)(G)(CE)(F) is arrived at
• On the other hand, if they are considered to be 1, then
P = (AD)(B)(CEG)(F) is obtained
• In general, a good state assignment is more important than
state minimization in obtaining a low cost implementation
B&V3, Figure 8.59
Can you find a partitioning with fewer states?
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S78
Analysis of synchronous sequential circuits
• Designers must be able to analyze the behaviour of
existing circuits – this is much easier than synthesizing
them
– To analyze a circuit, simply reverse the steps of the synthesis
process
1. FF outputs represent the present state variables
2. Their inputs determine the next state the circuit will enter
3. From this information we can construct the state-assigned table
4. Which leads to the state table, and ultimately, the state diagram
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S79
• What is the function of this circuit?
Y1 = wy2 + wy1
Y2 = wy2 + wy1
z = y2y1
Analysis example 8.8
B&V3, Figure 8.80
Q
D Q
D Q
Q
Clock
Resetn
y 2
y 1
Y 2
Y 1
w
z
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S80
Present Next State
state w = 0 w = 1 Output
y 2 y 1 Y 2 Y 1 Y 2 Y 1 z
0 0 0 0 01 0
0 1 0 0 10 0
1 0 0 0 11 0
1 1 0 0 11 1
(a) State-assigned table
Present Next state Output
state w = 0 w = 1 z
A A B 0
B A C 0
C A D 0
D A D 1
(b) State table
Tables for the circuit in Example 8.8
B&V3, Figure 8.81
Y1 = wy2 + wy1
Y2 = wy2 + wy1
z = y2y1
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S81
J Q
Q
Clock
Resetn
y2
y1
J2
J1
w z
K
J Q
QK
K2
K1
Example 8.9 using JK flip-flops
B&V3, Figure 8.82
J1 = w
K1 = w + y2
J2 = wy1
K2 = w
z = y2y1
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S82
Present Flip-flop inputs
state w = 0 w = 1 Output
y
2
y
1 J 2 K 2 J 1 K 1 J 2 K 2 J 1 K 1 z
00 01 0 1 0 0 1 1 0
01 01 0 1 1 0 1 1 0
10 01 0 1 0 0 1 0 0
11 01 0 1 1 0 1 0 1
The excitation table for the circuit in L06/S82
B&V3, Figure 8.83
J1 = w
K1 = w + y2
J2 = wy1
K2 = w
z = y2y1
Present Next State
state w = 0 w = 1 Output
y 2 y 1 Y 2 Y 1 Y 2 Y 1 z
0 0 0 0 01 0
0 1 0 0 10 0
1 0 0 0 11 0
1 1 0 0 11 1
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S83
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
A/0 B/1 C/2 D/3
E/4F/5G/6H/7
Design of a counter using the sequential circuit
approach
• Say we are to design a 0 – 7 up counter with enable
B&V3, Figure 8.60
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S84
Present Next state Output
state w = 0 w = 1
A A B 0
B B C 1
C C D 2
D D E 3
E E F 4
F F G 5
G G H 6
H H A 7
State table for the counter
B&V3, Figure 8.61
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S85
Present Next state
state w = 0 w = 1 Count
y 2 y 1 y 0 Y 2 Y 1 Y 0 Y 2 Y 1 Y 0
z 2 z 1 z 0
A 000 000 001 000
B 001 001 010 001
C 010 010 011 010
D 011 011 100 011
E 100 100 101 100
F 101 101 110 101
G 110 110 111 110
H 111 111 000 111
State-assigned table for the counter
B&V3, Figure 8.62
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S86
00 01 11 10
00
01
0
1 1
0
1
0
1
0
0
1 1
0
1
0
1
0 11
10
y 2 y 1
y w0 00 01 11 10
00
01
1
0 1
1
1
0
0
0
0
0 1
0
1
1
0
1 11
10
00 01 11 10
00
01
0
0 0
1
1
1
1
0
1
0 0
0
1
1
1
0 11
10
Y 2 y w2 y 2 y 0 y 2 y 1 + + + y 2 y 1 y w 0 =
Y 0 y w0 y w0 + = Y 1 y w1 y 1 y 0 y1 y w 0 + + =
K-maps for D flip-flops for the counter
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S87
= y 0 ⊕w
y 2 y 1
y w0
y 2 y 1
y w0
= y 1 ⊕ y w0
= y 2 ⊕ y y w1 0
Circuit diagram for the counter implemented with D FFs
B&V3, Figure 8.64
D Q
Q
D Q
Q
Clock
y 0
w
y 1
y 2
Y 0
Y 1
Y 2
Resetn
D Q
Q
L06/S88
Recall: four-bit counter with D FFs
Clock
Enable D Q
Q
D Q
Q
D Q
Q
D Q
Q
Q0
Q1
Q2
Q3
Output
carry
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S89
Design Exercise:
Parity generator for serial communication
• Design an even parity generator to produce parity bit p
to replace b7 = 0 of each ASCII byte B that is to be
serially transmitted by the system below
20T3 COMP3222/9222 Synchronous Sequential Circuits L06/S90