6 Finite-State Machines and Automata

6.1 FSM Stability

The term Stability is of central importance for the treatment of finite state machines. The FSM stability depends on the intended mode of operation, i.e. a distinction has to be made in asynchronous and synchronous operation.

Similar to what has been seen in the treatment of Flip-Flops, an asynchronous FSM will be in a stable state when the following is valid for all feedbacks:

Obviously this criteria defines stability as the state in which no signal changes are occurring in the feedback path.

Using the function table and the state transition diagram these conditions can be clarifies:

Inputs				Outputs					Sequence
x₁	x₂	z₁	z₂	v₁	v₂	y₁	y₂	y₃
0	0	0	0	1	0	1	1	1	→	1
0	0	0	1	0	1	1	0	0				3
0	0	1	0	0	1	0	1	1			2
:		:		:		:

						stable state

Figure 6.2: Asynchronous Finite State Machine.
Function Table (above) and State Diagram (right).
The last column in the table shows the path to the stable state (3).

Function Table and State Diagram show that the stable state will only be reached after passing a sequence:
With constant inputs x₁ = x₂ = 0 the asynchronous FSM will first switch into the state

v₁, v₂ = 1,0 = z₁, z₂ .

After the gate propagation delay times have passed both feedback lines will change their values:

v₁: '1' '0' and v₂: '0' '1' .

Only with these feedback values the outputs of the combinational circuit will assume stable values.

Hint:

The stable values are valid relative to the constant external inputs. In the example state '01' is stable relative to input '00'. The states '00' and '01' however are unstable relative to the input '00'.
In the sequence described here it is assumed that all values at the feedback outputs will change simultaneously.

In the synchronous Finite State Machine the prerequisite for stability is always given; the subsequent state will always be assumed with the next clock signal.

But the triggering edge may only occur after all output signals have assumed stable values.

Inputs				Outputs					State
x₁	x₂	z₁	z₂	v₁	v₂	y₁	y₂	y₃
0	0	0	0	1	0	1	1	1	→	t_i
0	0	0	1	0	1	1	0	0		t_i+2
0	0	1	0	0	1	0	1	1		t_i+1
:		:		:		:

Figure 6.3: Synchronous Finite State Machine.
Function Table (above) and State Diagram (right).

In a synchronous finite state machine all states are stable.

Synchronous FSMs are more "good-natured" than asynchronous ones, because it is determined externally when the next state will be assumed. In asynchronous FSMs the signal changes at the feedback inputs depend on the gate delay times.

Synchronous finite state machines can be designed fail safe, but in general they are running more slowly than the asynchronous ones.

Contents

Previous Chapter

Next Chapter