Digital Electronics 2 - Sequential Logic with Next

Digital
Electronics 2
Lecture 8
Notes
Andreas
Habegger
Digital Electronics 2
Sequential Logic with Next-State
FSM Types, Design Methods and Examples
Sequential
FSM Types
Design
Examples
Diagram Conversion
Important Rules
BTF4220 - Advanced Electronics
May. 16, 2014
FSM Timing
Timing Relations
Timing Diagram
Mealy vs Moor
FSM Examples
Andreas Habegger
Bern University of Applied Sciences
Rev. 3ce6837
Agenda
–
8.1
Digital
Electronics 2
Notes
Andreas
Habegger
Sequential
FSM Types
Design
Conversion
Examples
Important Rules
Diagram
Sequential
FSM Types
Design
Examples
Diagram Conversion
FSM Timing
Timing Relations
Important Rules
Timing Diagram
FSM Timing
Timing Relations
Timing Diagram
Mealy vs Moor
Mealy vs Moor
FSM Examples
FSM Examples
Rev. 3ce6837
A sequential logic example
−− nested tick generator
tick : process (ClkxCI)
variable tickVari : unsigned(20 downto 0) := (others => ’0’);
begin −− state register
if rising_edge(ClkxCI) then
if tickVari < TICK_CLK_RELATION then
tickVari := tickVari + 1;
TickxS <= ’0’;
else
TickxS <= ’1’;
tickVari := (others => ’0’);
end if;
end if;
8.2
Digital
Electronics 2
Notes
Andreas
Habegger
Nested Tick Generator
−−−−−−−−−−−−−−−−−−−−−−−−−−−−
−− Tick generator
−−−−−−−−−−−−−−−−−−−−−−−−−−−−
−−
−− purpose: tick generator
−− type : sequential
−− inputs : ClkxCI
−− outputs: TickxS
−− descrip: generats a tick corresponding to the relation Clk vs. LedON
−−
–
This circuit
generates a tick
pulse for a certain
frequency relation
Sequential
FSM Types
Design
It is not an obvious
description in
terms of function
blocks
It has a buffered
output
Examples
Diagram Conversion
Important Rules
FSM Timing
Timing Relations
Timing Diagram
Mealy vs Moor
FSM Examples
end process tick;
Rev. 3ce6837
–
8.3
The Block Diagram
Digital
Electronics 2
Notes
Andreas
Habegger
Register
−− nested tick generator
tick : process (ClkxCI)
variable tickVari : unsigned(20 downto 0) := (others => ’0’);
begin −− state register
if rising_edge(ClkxCI) then
Sequential
end if;
end process tick;
FSM Types
Design
Examples
Diagram Conversion
U- and O-Logic
Important Rules
FSM Timing
Timing Relations
if tickVari < TICK_CLK_RELATION then
tickVari := tickVari + 1;
TickxS <= ’0’;
else
TickxS <= ’1’;
tickVari := (others => ’0’);
end if;
Timing Diagram
Mealy vs Moor
FSM Examples
Rev. 3ce6837
–
8.4
The next-state logic is a simple, repetitive pattern hence a
sequential design with combinatorial logic.
A sequential logic example
Enrolled Tick Generator
−−−−−−−−−−−−−−−−−−−−−−−−−−−−
−− Tick generator
−−−−−−−−−−−−−−−−−−−−−−−−−−−−
−−
−− purpose: tick generator
−− type : sequential
−− inputs : ClkxCI
−− outputs: TickxS
−− descrip: generats a tick corresponding to the relation Clk vs. LedON
−−
−− state register
tick : process (ClkxCI)
Digital
Electronics 2
The example
shows a
sequential /
combinatorial tick
pulse generator
The combinatorial
logic is written
concurrent. Only
the register is
written
sequentially
begin −− state register
Notes
Andreas
Habegger
Sequential
FSM Types
Design
Examples
Diagram Conversion
Important Rules
FSM Timing
This is a clear, well
structured, and
simple method
end process tick;
writing VHDL due
−− next state logic
to its clearness
TickNextxD <= (others => ’0’) when TickRegxD = (TICK_CLK_RELATION−1) else
and closeness to
TickRegxD + 1;
function blocks
if rising_edge(ClkxCI) then
TickRegxD <= TickNextxD;
end if;
Timing Relations
Timing Diagram
Mealy vs Moor
FSM Examples
−− output logic
TickxS <= ’1’ when TickRegxD = (TICK_CLK_RELATION−1) else ’0’;
Output is not
buffered
The Block Diagram
Rev. 3ce6837
–
8.5
Digital
Electronics 2
Notes
Andreas
Habegger
Sequential
FSM Types
Update Logic
State Reg
Output Logic
−− next state logic
TickNextxD <= (others => ’0’)
when <CONDITION> else
TickRegxD + 1;
tick : process (ClkxCI)
begin −− state register
if rising_edge(ClkxCI) then
TickRegxD <= TickNextxD;
end if;
end process tick;
TickxS <= ’1’
when <CONDITION> else
’0’;
Design
Examples
Diagram Conversion
Important Rules
FSM Timing
Timing Relations
Timing Diagram
Mealy vs Moor
FSM Examples
The next-state logic is a simple, repetitive pattern hence a
sequential design with combinatorial logic.
Rev. 3ce6837
–
8.6
FSM Basics
Digital
Electronics 2
Notes
Andreas
Habegger
Which main FSM types do you know?
What is the benefit of a FSM implementation?
Sequential
FSM Types
Design
Examples
Diagram Conversion
Important Rules
Exercise
FSM Timing
Draw the Medvedev, Moore, and Meely FSM with the
logic blocks and the state register.
Mealy vs Moor
Timing Relations
Timing Diagram
FSM Examples
Rev. 3ce6837
FSM Basics
–
8.7
Digital
Electronics 2
Notes
Andreas
Habegger
The term FSM means finit state machine (FSM)
Compared to the sequential design a FSM has a certain
randomness in its next-state logic
FSM design is based on (a) a state diagram or (b) an
algorithm state machine (ASM) chart
Sequential
FSM Types
The charts are thought to visualize the interaction between
states
Design
Examples
Diagram Conversion
Important Rules
Never design a FSM without drawn a chart before
FSM Timing
We manly design synchronous FSM, where the state register is
controlled by a single global clock
Mealy vs Moor
Timing Relations
Timing Diagram
FSM Examples
An FSM is specified by five “elements”/“blocks”: symbolic states
, input signals, output signals, next-state function, and output
function
Rev. 3ce6837
FSM Basics
–
8.8
Digital
Electronics 2
Notes
Andreas
Habegger
Sequential
FSM Types
Design
The figure shows a mixed FSM with a Mealy and a Moor output
Examples
Diagram Conversion
Important Rules
We design often a pure Mealy or Moore machine
FSM Timing
Timing Relations
Timing Diagram
As time progresses, the FSM transits from one state to another
Mealy vs Moor
FSM Examples
The figure looks similar to a sequential circuit but the next-state
logic is designed different
The main application of an FSM is to realize operations that are
performed in a sequence of steps and not necessarily
consecutive
Rev. 3ce6837
–
8.9
FSM Design
Digital
Electronics 2
Notes
Andreas
Habegger
IMPORTANT
The design of a FSM starts with an abstract, graphic
description, such as an ASM chart or a state diagram
Sequential
Both descriptions use symbolic state notation
FSM Types
Design
Examples
Writing VHDL code is an easy task the hard work is the chart
There are tools that convert ASM chart or state diagrams into
VHDL code
Diagram Conversion
Important Rules
FSM Timing
Timing Relations
Timing Diagram
Mealy vs Moor
When you draw such a chart you will have to cover all the five
needed information
FSM Examples
symbolic states, input signals, output signals, next-state function,
and output function
Rev. 3ce6837
State Diagram
–
8.10
Digital
Electronics 2
Notes
Andreas
Habegger
State diagram of an example
memory controller
The initialization is indicated
with a rest condition
Sequential
In the bubbles are the Moore
outputs
FSM Types
Design
Examples
Diagram Conversion
A transition is performed on
each clock cycle either to the
current or an other state
On the transition arc are the
Mealy outputs as a
combination of next-state and
input-state
Important Rules
FSM Timing
Timing Relations
Timing Diagram
Mealy vs Moor
FSM Examples
Rev. 3ce6837
ASM Chart
–
8.11
Digital
Electronics 2
The figure shows an
arithmetic state machine
(ASM) chart
An ASM chart contains the
same amount of information
as the state diagram
Such a chart is constructed
out of a network of ASM
blocks
Andreas
Habegger
Sequential
FSM Types
Design
Examples
Diagram Conversion
Important Rules
FSM Timing
An ASM block consists of
one state box an optional
network of decision boxes
and conditional output boxes
Timing Relations
Timing Diagram
Mealy vs Moor
FSM Examples
This method of FSM design
is the simplest do convert to
VHDL, later
Rev. 3ce6837
–
8.12
Notes
The Memory Ctrl
Digital
Electronics 2
Notes
Andreas
Habegger
Sequential
FSM Types
Design
Examples
Diagram Conversion
Draw the function blocks, first
Important Rules
FSM Timing
Draw the connections to realize the Mealy (ME) and Moore (MO)
outputs
Timing Relations
Timing Diagram
Mealy vs Moor
FSM Examples
Write the VHDL code based on the state diagram mentioned
before
Rev. 3ce6837
The Memory Ctrl
–
8.13
Digital
Electronics 2
Notes
Andreas
Habegger
Sequential
Memory Ctrl Interface
FSM Types
Design
library ieee;
use ieee.std_logic_1164.all;
entity memCtrl is
port (
EnaMemxSI
: in std_logic;
−− enable memory ctrl
RwxSI
: in std_logic;
−− read or write −> read := 1, write := 0
BurstxSI
: in std_logic;
−− burst mode
ClkxCI, RstxRI : in std_logic;
−− Clock and Reset
WeMexSO
: out std_logic;
−− Mealy output write
WeMoxSO
: out std_logic;
−− Moore output write
OexSI
: out std_logic);
−− Output enable
end memCtrl;
Examples
Diagram Conversion
Start with a clear interface
Important Rules
FSM Timing
BurstxSI has no impact
on Mealy output hence no
feed-forward
Timing Relations
Timing Diagram
Mealy vs Moor
FSM Examples
We use a reset to bring
the “Mem Ctrl” to a
defined initial condition
Rev. 3ce6837
The Memory Ctrl
–
8.14
Digital
Electronics 2
Andreas
Habegger
State Type - Enumeration
architecture fsmMealyMoore of memCtrl is
type memCtrlType is (idle, write, read1, read2,
read3, read4);
signal StateRegxD, StateNextxD : memCtrlType;
begin −− fsmMealyMoore
...
end fsmMealyMoore;
State Register
stateReg : process (ClkxCI, RstxRI)
begin −− process stateReg
if RstxRI = ’1’ then
StateRegxD <= idle;
elsif rising_edge(ClkxCI) then
StateRegxD <= StateNextxD;
end if;
end process stateReg;
Snipped NS Logic
nextStateLogic : process (StateRegxD, EnaMemxSI,
RwxSI, BurstxSI)
begin −− process nextStateLogic
case StateRegxD is
when idle =>
when write =>
StateNextxD <= idle;
when read1 =>
...
when read2 =>
...
when read3 =>
...
when read4 =>
...
when others =>
null; −− error handling
end case;
end process nextStateLogic;
Sequential
FSM Types
Design
Examples
Diagram Conversion
Important Rules
FSM Timing
Timing Relations
Timing Diagram
Mealy vs Moor
FSM Examples
Rev. 3ce6837
–
8.15
Notes
The Memory Ctrl
Digital
Electronics 2
Notes
Andreas
Habegger
Moore Outputs
outMoore : process (StateRegxD)
begin −− process outMoore
−− default values
WeMoxSO <= ’0’;
OexSI <= ’0’;
case StateRegxD is
when idle =>
when write =>
WeMoxSO <= ’1’;
when read1 =>
OexSI <= ’1’;
when read2 =>
OexSI <= ’1’;
when read3 =>
OexSI <= ’1’;
when read4 =>
OexSI <= ’1’;
when others => null;
end case;
end process outMoore;
Mealy Outputs
outMealy : process (StateRegxD, EnaMemxSI, RwxSI)
begin −− process outMealy
WeMexSO <= ’0’;
Sequential
case StateRegxD is
when idle =>
FSM Types
if (EnaMemxSI = ’1’) and (RwxSI = ’1’) then
Design
WeMexSO <= ’1’;
Examples
end if;
Diagram Conversion
Important Rules
when write => null;
when read1 => null;
FSM
Timing
when read2 => null;
Timing Relations
when read3 => null;
Timing Diagram
when read4 => null;
when others => null;
Mealy vs Moor
end case;
FSM Examples
end process outMealy;
Rev. 3ce6837
State Diagram to ASM Conversion
–
8.16
Digital
Electronics 2
Notes
Andreas
Habegger
Sequential
FSM Types
Design
Examples
Diagram Conversion
Important Rules
This control circuit is toggling between S0 and S1 – on
consecutive clock edges.
On state S0 the output y is set to logical one, hold on logical
zero, otherwise.
FSM Timing
Timing Relations
Timing Diagram
Mealy vs Moor
FSM Examples
Each bubble on the state-diagram results in a corresponding
ASM box
To transform an state-diagram into a ASM chart we transform
the output into corresponding output box – Moore or Mealy
State Diagram to ASM Conversion
Rev. 3ce6837
–
8.17
Digital
Electronics 2
Andreas
Habegger
Sequential
FSM Types
Design
Examples
Diagram Conversion
Important Rules
FSM Timing
This FSM stays in state S0 until input A becomes logical one.
When A chances to one a state transaction event is going to be
performed to S1. After one clock pulse a back transaction from
S1 to S0 happens
Timing Relations
Timing Diagram
Mealy vs Moor
FSM Examples
On the transaction S0 → S1 output y0 is set to one. In state S1
output y1 is hold at logical one, others are zero. This results in a
transaction pulse of y0 and in an one clock-cycle long pulse on
y1
Rev. 3ce6837
–
8.18
Notes
State Diagram to ASM Conversion
Digital
Electronics 2
Notes
Andreas
Habegger
Sequential
FSM Types
Design
Examples
Diagram Conversion
Important Rules
FSM Timing
Timing Relations
Timing Diagram
Transform bubbles into ASM boxes and put output logic into
corresponding boxes – Moore and Mealy
Mealy vs Moor
FSM Examples
Convert the transaction logic into a Boolean expression
Draw the decisions arrow network – if a certain ASM box has no
Boolean expression it results in an one clock delay
Rev. 3ce6837
State Diagram to ASM Conversion
–
8.19
Digital
Electronics 2
Notes
Andreas
Habegger
Exercise
Describe in your own words the function of the state
diagram, first. Convert the state diagram into an ASM
chart, afterwards.
Sequential
FSM Types
Design
Examples
Diagram Conversion
Important Rules
FSM Timing
Timing Relations
Timing Diagram
Mealy vs Moor
FSM Examples
Rev. 3ce6837
State Diagram to ASM Conversion
–
8.20
Digital
Electronics 2
Andreas
Habegger
Sequential
FSM Types
Design
Examples
Diagram Conversion
Important Rules
FSM Timing
Timing Relations
Timing Diagram
Mealy vs Moor
FSM Examples
Rev. 3ce6837
–
8.21
Notes
State Diagram to ASM Conversion
Digital
Electronics 2
Notes
Andreas
Habegger
Exercise
Describe in your own words the function of the circuit
described by the ASM chart, first. Convert the ASM chart
into a state diagram, afterwards.
Sequential
FSM Types
Design
Examples
Diagram Conversion
Important Rules
FSM Timing
Timing Relations
Timing Diagram
Mealy vs Moor
FSM Examples
Rev. 3ce6837
State Diagram to ASM Conversion
–
8.22
Digital
Electronics 2
Notes
Andreas
Habegger
Sequential
FSM Types
Design
Examples
Diagram Conversion
Important Rules
FSM Timing
Timing Relations
Timing Diagram
Mealy vs Moor
FSM Examples
Rev. 3ce6837
ASM Chart Rules
–
8.23
Digital
Electronics 2
Andreas
Habegger
1. For a given input
combination, there is one
unique exit path from the
current ASM block
Sequential
FSM Types
Design
2. The exit path of an ASM
block must always lead to a
state box. The state box can
be the state box of the
current or of another ASM
block.
Examples
Diagram Conversion
Important Rules
FSM Timing
Timing Relations
Timing Diagram
Mealy vs Moor
FSM Examples
Rev. 3ce6837
–
8.24
Notes
ASM Pitfalls
Digital
Electronics 2
Notes
Andreas
Habegger
Sequential
FSM Types
Design
Examples
Diagram Conversion
The first ASM chart violates the first rule – there are two exit
paths if A and B are both true.
Important Rules
FSM Timing
Timing Relations
Timing Diagram
The second ASM chart violates the first rule – since there is no
exit path when the condition of the decision box is false.
The third ASM chart violates the second rule – because the exit
path of bottom ASM block dose not enter the top of an ASM
block. The second rule essentially states that the decision boxes
and conditional output boxes are associated with a single ASM
block and they cannot be shared by other blocks.
Timing Relations
Mealy vs Moor
FSM Examples
Rev. 3ce6837
–
8.25
Digital
Electronics 2
Notes
Andreas
Habegger
When an FSM is synthesized, the physical components
introduce propagation delays
Tcq , Tsetup , Thold : The clock-to-q delay, the setup and hold time
of the state register
Tnext : The maximal propagation delay of next-state logic
Sequential
FSM Types
Design
ToutMo : The maximal propagation delay of Moore output logic
Examples
Diagram Conversion
Important Rules
ToutMe : The maximal propagation delay of Mealy output logic
FSM Timing
Timing Relations
Timing Diagram
Mealy vs Moor
Clock to output delay
Shortest Clock Period
allowed
FSM Examples
Tco(mo) = Tcq + ToutMo
Tco(me) = Tcq + ToutMe
Tc = Tcq + Tnext + Tsetup
Rev. 3ce6837
FSM Timing Diagram
–
8.26
Digital
Electronics 2
Andreas
Habegger
Clk
Input
S0
StateReg
StateNext
S0
S1
S1
S0
S1
S0
OutMe
Sequential
FSM Types
Design
Examples
OutMo
Diagram Conversion
Important Rules
FSM Timing
What dose during the Tcq phase happen (red)? What does the
delay Tcq represent?
Timing Relations
Timing Diagram
Mealy vs Moor
FSM Examples
When does a state transaction happen and why?
Which output is a Mealy and which a Moore output? And why?
Which phase represents which delay?
Rev. 3ce6837
–
8.27
Notes
FSM Timing Diagram
Digital
Electronics 2
Notes
Andreas
Habegger
In computer science a Moore and a Mealy FSM have similar
computation capability
In general a Mealy machine accomplishes the same task with
fewer states
When the FSM is used as a control circuit, the control signals
generated by a Moor machine and a Mealy machine have
different timing characteristics
Understanding the difference in timing is important for
correctness and efficiency of a control circuit
Sequential
FSM Types
Design
Examples
Diagram Conversion
Important Rules
FSM Timing
Timing Relations
Timing Diagram
Mealy vs Moor
Let’s discuss the difference by an example – positive edge
detector circuit
FSM Examples
Rev. 3ce6837
Edge Detector
How does an edge detector work? When do we use such
a circuit?
–
8.28
Digital
Electronics 2
Notes
Andreas
Habegger
We assume that a synchronous system is connected to a slow
varying signal “strobe”
The signal “strobe” can be asserted to ’1’ much longer than a
clock period
Sequential
FSM Types
Design
Examples
For detecting a rising or falling edge an edge-detector circuit will
be used
Diagram Conversion
Important Rules
FSM Timing
Timing Relations
The pulse is about or less than a clock period
Timing Diagram
Mealy vs Moor
The duration of this pulse depends on the implementation hence
on the machine used (Mealy or Moore)
FSM Examples
The interface signals are
IN : clock, strobe
OUT : posPulse
Rev. 3ce6837
Edge Detector
–
8.29
Digital
Electronics 2
Andreas
Habegger
Sequential
FSM Types
Design
Examples
Diagram Conversion
Important Rules
FSM Timing
Timing Relations
1. The first machine represents a Moore machine. In addition to
the one and zero states a delay state is needed
Timing Diagram
Mealy vs Moor
FSM Examples
2. The second machine represents a Mealy machine. The p2
(positive edge 2) is asserted on the transition zero → one and
dis-asserted otherwise
3. The third machine is a Mealy implementation of Moore behavior.
Since the p3 is asserted on every transition arc in the delay state
we can move the assertion into the bubble that results in a
Moore machine
Rev. 3ce6837
–
8.30
Notes
Edge Detector
Digital
Electronics 2
Notes
Andreas
Habegger
Sequential
FSM Types
Design
Examples
Diagram Conversion
Important Rules
FSM Timing
Timing Relations
The differences between Moore and Mealy
The Mealy machine uses fewer states than the Moore machine.
This is due to the fact that the output states are a function of
state and external input
Timing Diagram
Mealy vs Moor
FSM Examples
The Mealy machine can generate a fast response
The third difference involves the control of the width and timing
of the output signal. A level-sensitive control signal means that a
signal has to be asserted for a certain amount of time
Describe the FSMs
Exercise
Rev. 3ce6837
–
8.31
Digital
Electronics 2
Notes
Andreas
Habegger
Write the VHDL code for both the Moore and Mealy
implementation of the positive edge-detector. Test it with
ModleSim can you verify the signal flow graph shown
above?
Sequential
FSM Types
Step-by-Step guide
Design
Examples
Diagram Conversion
1. Write the entity first. Call that file “posEdgeDetector-entity.vhdl”
Important Rules
FSM Timing
2. Write the Moore machine implementation call the file
“posEdgeDetector-behavior_moore.vhdl”
Timing Relations
Timing Diagram
Mealy vs Moor
FSM Examples
3. Write the Mealy machine implementation call the file
“posEdgeDetector-behavior_mealy.vhdl”
4. Use explicit processes for realizing the function blocks :
state-register, update-logic, output or transition logic
Rev. 3ce6837
–
8.32
Notes

Download Report