Browse Prior Art Database

Random Finite State Machines

IP.com Disclosure Number: IPCOM000111621D
Original Publication Date: 1994-Mar-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 2 page(s) / 95K

Publishing Venue

IBM

Related People

Schlipf, T: AUTHOR

Abstract

The Finite State Machines (FSM) of today's VLSI chips implement very complex protocols. Some of the state transitions of these FSMs are very difficult to exercise since they may depend on input sequences which are hard to activate, especially in a system in which several VLSI chips communicate with each other. These sequences may lead to errors which are only detected late in the verification process. The protocols used for communication are composed of fixed sequences and variable sequences. A fixed sequence is usually triggered by some external condition, after which for several cycles the protocol is strictly defined. In a variable sequence the number of cycles between two states is either not defined or defined within a range (e.g., after a signal S1 the signal S2 becomes active after 2 to 6 cycles).

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Random Finite State Machines

      The Finite State Machines (FSM) of today's VLSI chips implement
very complex protocols.  Some of the state transitions of these FSMs
are very difficult to exercise since they may depend on input
sequences which are hard to activate, especially in a system in which
several VLSI chips communicate with each other.  These sequences may
lead to errors which are only detected late in the verification
process.  The protocols used for communication are composed of fixed
sequences and variable sequences.  A fixed sequence is usually
triggered by some external condition, after which for several cycles
the protocol is strictly defined.  In a variable sequence the number
of cycles between two states is either not defined or defined within
a range (e.g., after a signal S1 the signal S2 becomes active after 2
to 6 cycles).  To generate all conditions which explore all
possibilities of such a range is a cumbersome process.  Therefore a
hardware structure is disclosed which allows the exercise in a random
way of a variable sequence.

      In the state of the art, finite state machines are used to
describe a protocol.  These FSMs require unique state-input pairs for
each transition, i.e., a unique combination of the state of the FSM
and the input signal.  So-called non-deterministic FSMs which could
have state-input pairs that activate more than one transition are
merely of theoretical interest.  These non-deterministic FSMs are not
in a single state, but can be described as being in a set of states.
All of the states in a non-deterministic FSM are concurrently active
and able to activate further transitions.

      Disclosed in this article is a method which uses the
descriptive method of the non-deterministic FSMs to implement a
random FSM.  The basic structure of a FSM is shown in Fig. 1.  A
state register 10 holds the current state of the FSM.  The current
state and the external inputs 30 are used by the combinational logic
20 to compute the outputs 35 and the next state.  The computed next
state is loaded in the next clock cycle into the state register 10.

      The structure derived for a random FSM is shown in Fig. 2.
Besides the external inputs 30, a random input vector (Random_Input)
40 is fed to the combinational logic 20.  All other connections to
the combinational logic 20 are the same as for a "classical" FSM, as
shown in Fig. 1.  The random input vector 40 is provided by a random
array 50 which is addressed by the external inputs 30 and the current
state.  The addre...