12-11-2012, 04:44 PM
A New Paradigm for Synchronous State Machine Design in Verilog
[attachment=39129]
Introduction
Synchronous State Machines are one of the most common building blocks in modern digital systems. They
handle everything from communications handshaking protocols to microprocessor bus wait state insertion.
State machines operate at hardware speeds where software cannot compete. All too often engineers take an
ad-hoc approach to state machine design. Subtle and frustrating problems can arise from poorly designed
state machines which typically manifest themselves as intermittent operation or lockup. Other problems
such as glitches may appear in the outputs causing headaches for customers and service personnel long after
a product is in production.
This article will first describe the basic architectures for synchronous state machines, then describe a method
of State Machine implementation which leads to glitchless, minimum-delay operation. The Verilog Hardware
Description Language will be utilized.
State Machine Architectures
There are two generally accepted architectures for Synchronous State Machines. The first type considered is
a state machine in which the outputs depend only on the current state. This is commonly known as a Moore
machine. In the second type, the outputs depend on both the current state and the input variables. This is
known as a Mealy Machine.
Moore Machine
This is the simplest of the two state machine types. The outputs are combinatorial signals based solely on the
current state. Unfortunately, this can lead to glitches on the output signals which can cause erratic operation
of circuitry driven by the state machine.
The glitches are due to unequal delays in the Clock to Q path of the flip-flops which make up the state bits as
well as unequal propagation delays in the combinatorial logic which derives the output from the state bits.
Moore machine implementations are generally simpler than Mealy machines and may allow somewhat
higher clock rates than a Mealy machine.
State Diagram
A state diagram allows the designer to describe the desired state machine operation graphically. This helps
him or her visualize the operation of the state machine prior to implementation. The diagram contains a
wealth of information.
First, the diagram shows state transitions. The circles and arrows describe how the state machine moves
from one state to another. The circles represent a particular value of the state variable. The arrowed lines
describe how the state machine transitions from one state to the next state. The arrowed lines contain a boolean
expression which shows the criteria for a transition from one state to another. If the boolean expression
is TRUE and the current state is the state at the source of the arrowed line, the state machine will transition
to the destination state on the next clock.
The diagram also shows the values of the output variables during each state. In a Moore Machine, the outputs
are only a function of the current state; inputs have no effect after the clock. This makes the Moore
Machine an ideal candidate for a fully synchronous design. Outputs of a Moore Machine have reasonably
predictable timing and are always referenced to the clock. On the other hand, Mealy Machine outputs can be
dependent on the value of inputs to the state machine which may be transitioning at less predictable times. It
is for this reason, that Moore Machines generally provide for a smoother implementation in FPGA and Gate
Array designs.
Input Variables
ALL Input variables MUST be synchronous to the state machine clock. If they are not, strange things will
begin to happen to the state machine in actual operation. Illegal states will be mysteriously entered. Total
state machine lockup can result. Inevitably, the design will fail intermittently in the field. Why?
The reason lies in the fact that a physical state machine implementation uses physical gates which have a
non-zero propagation delay. An input signal progagating through gates to the D input of one state flip flop
will be slightly faster or slower than that same input signal travelling through a different set of gates to
another flip flop’s D input. If the input signal changes at just the wrong time, the fast path will see the
change, but the slow one won’t. The clock comes along and one of the flip-flops will now have an incorrect
logic level. The overall state machine just made an illegal state transition; the circuit has failed. This type of
design error generally goes unnoticed because the faulty behavior shows up only a small percentage of the
time. Bewareof the asynchronous input!
The cure for the asynchronous input is a synchronizer. Generally a 2 stage synchronizer is adequate to prevent
illegal state entry. It should be noted that there is a statistical probability, albeit very low, that an asynchronous
input may still be able to propagate through a synchronizer. For each stage of synchronization
employed, the probability is reduced considerably. Some space/military designs require the use of a 3 stage
synchronizer, but 2 stages is generally considered the standard for commercial and industrial grade designs.
To minimize latency, use the falling edge of the clock for the first stage and the rising edge as the second
stage.
Output Variables
Remember that in a Moore state machine, the value of output variables are solely a function of the current
state. One of the valuable things about a Moore design is that the timing of the state transitions/outputs is
dependent only upon the clock. But, we start to lose that timing simplicity when combinatorial logic is used
to generate outputs which are functions of the state bits. Depending on the complexity of this “back-end”
logic, the actual timing of the outputs can be seriously degraded.
Another problem with this popular approach is that narrow glitches can appear on these combinatorial outputs
during state transitions. Due to clock skew, unequal clock to Q prop delay and unequal combinatorial
logic prop delay, glitches will invariably occur. These glitches may be very narrow, and may not be visible at
all on most logic analyzers and some scopes. You can be assured that sensitive edge based circuits which are
driven by these outputs will see them and again circuit failure can result.
[attachment=39129]
Introduction
Synchronous State Machines are one of the most common building blocks in modern digital systems. They
handle everything from communications handshaking protocols to microprocessor bus wait state insertion.
State machines operate at hardware speeds where software cannot compete. All too often engineers take an
ad-hoc approach to state machine design. Subtle and frustrating problems can arise from poorly designed
state machines which typically manifest themselves as intermittent operation or lockup. Other problems
such as glitches may appear in the outputs causing headaches for customers and service personnel long after
a product is in production.
This article will first describe the basic architectures for synchronous state machines, then describe a method
of State Machine implementation which leads to glitchless, minimum-delay operation. The Verilog Hardware
Description Language will be utilized.
State Machine Architectures
There are two generally accepted architectures for Synchronous State Machines. The first type considered is
a state machine in which the outputs depend only on the current state. This is commonly known as a Moore
machine. In the second type, the outputs depend on both the current state and the input variables. This is
known as a Mealy Machine.
Moore Machine
This is the simplest of the two state machine types. The outputs are combinatorial signals based solely on the
current state. Unfortunately, this can lead to glitches on the output signals which can cause erratic operation
of circuitry driven by the state machine.
The glitches are due to unequal delays in the Clock to Q path of the flip-flops which make up the state bits as
well as unequal propagation delays in the combinatorial logic which derives the output from the state bits.
Moore machine implementations are generally simpler than Mealy machines and may allow somewhat
higher clock rates than a Mealy machine.
State Diagram
A state diagram allows the designer to describe the desired state machine operation graphically. This helps
him or her visualize the operation of the state machine prior to implementation. The diagram contains a
wealth of information.
First, the diagram shows state transitions. The circles and arrows describe how the state machine moves
from one state to another. The circles represent a particular value of the state variable. The arrowed lines
describe how the state machine transitions from one state to the next state. The arrowed lines contain a boolean
expression which shows the criteria for a transition from one state to another. If the boolean expression
is TRUE and the current state is the state at the source of the arrowed line, the state machine will transition
to the destination state on the next clock.
The diagram also shows the values of the output variables during each state. In a Moore Machine, the outputs
are only a function of the current state; inputs have no effect after the clock. This makes the Moore
Machine an ideal candidate for a fully synchronous design. Outputs of a Moore Machine have reasonably
predictable timing and are always referenced to the clock. On the other hand, Mealy Machine outputs can be
dependent on the value of inputs to the state machine which may be transitioning at less predictable times. It
is for this reason, that Moore Machines generally provide for a smoother implementation in FPGA and Gate
Array designs.
Input Variables
ALL Input variables MUST be synchronous to the state machine clock. If they are not, strange things will
begin to happen to the state machine in actual operation. Illegal states will be mysteriously entered. Total
state machine lockup can result. Inevitably, the design will fail intermittently in the field. Why?
The reason lies in the fact that a physical state machine implementation uses physical gates which have a
non-zero propagation delay. An input signal progagating through gates to the D input of one state flip flop
will be slightly faster or slower than that same input signal travelling through a different set of gates to
another flip flop’s D input. If the input signal changes at just the wrong time, the fast path will see the
change, but the slow one won’t. The clock comes along and one of the flip-flops will now have an incorrect
logic level. The overall state machine just made an illegal state transition; the circuit has failed. This type of
design error generally goes unnoticed because the faulty behavior shows up only a small percentage of the
time. Bewareof the asynchronous input!
The cure for the asynchronous input is a synchronizer. Generally a 2 stage synchronizer is adequate to prevent
illegal state entry. It should be noted that there is a statistical probability, albeit very low, that an asynchronous
input may still be able to propagate through a synchronizer. For each stage of synchronization
employed, the probability is reduced considerably. Some space/military designs require the use of a 3 stage
synchronizer, but 2 stages is generally considered the standard for commercial and industrial grade designs.
To minimize latency, use the falling edge of the clock for the first stage and the rising edge as the second
stage.
Output Variables
Remember that in a Moore state machine, the value of output variables are solely a function of the current
state. One of the valuable things about a Moore design is that the timing of the state transitions/outputs is
dependent only upon the clock. But, we start to lose that timing simplicity when combinatorial logic is used
to generate outputs which are functions of the state bits. Depending on the complexity of this “back-end”
logic, the actual timing of the outputs can be seriously degraded.
Another problem with this popular approach is that narrow glitches can appear on these combinatorial outputs
during state transitions. Due to clock skew, unequal clock to Q prop delay and unequal combinatorial
logic prop delay, glitches will invariably occur. These glitches may be very narrow, and may not be visible at
all on most logic analyzers and some scopes. You can be assured that sensitive edge based circuits which are
driven by these outputs will see them and again circuit failure can result.