Browse Prior Art Database

Choosing State Assignments to Minimize State Machine Logic

IP.com Disclosure Number: IPCOM000112671D
Original Publication Date: 1994-Jun-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 4 page(s) / 104K

Publishing Venue

IBM

Related People

Itskin, R: AUTHOR

Abstract

This procedure is a simple guideline to determine the state assignments for each state, when minimum combinatorial logic that sets and resets the state machine logic is desired. The procedure is particularly useful after a state diagram has been drawn.

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

Choosing State Assignments to Minimize State Machine Logic

      This procedure is a simple guideline to determine the state
assignments for each state, when minimum combinatorial logic that
sets and resets the state machine logic is desired.  The procedure is
particularly useful after a state diagram has been drawn.

      A state diagram consists of a set of circles, one for each
state.  Arcs are used to determine how to get from the present state
to the next state, and are usually labeled with the condition that
causes the transition.

      The Figure is an example of a diagram with three states (A, B,
and C) and six arcs.  This state machine will require two state
machine latches, and each state can occupy one of the decodes of the
two latches, "00", "01", "10", or "11".

      To minimize the combinational logic, examine the state diagram
and find the state that has the most arcs going to it.  This includes
the arc that feeds back into the same state, if applicable.  For this
state, maximize the 0's in the state assignment.  For example, in the
Figure state C has the most arcs going into it and should be assigned
to the decode of "00".  Continue to the state with the next highest
number of arcs going to it and try to maximize the number of 0's in
its state assignment until all states have been assigned.

      To understand how this procedure works, examine the logic that
sets and resets the state machine latches.  Feeding each latch will
be an OR function gathering all the conditions that set and reset the
latch.  The number of conditions equal the number of arcs in the
state diagram.  In the Figure, the number of conditions equal six.
Each condition is an AND function of the present state latch values,
the transition condition on the arc, and the value of the next state
latch.  It is the value of the next state for each latch that
determines how much combinatorial logic is required.

      The table lists the conditions that correspond with the Figure
and with the following state assignments.

        State C is assigned to "00" since it has the most arcs into
it.

        State A is assigned to "01".

        State B is assigned to "10".

PS(0:1) stands for Present State of latches 0 and 1.  NS(0:1) stands
for the next state.

      Examine the condition that feeds NS(0) under the X column of
the table.  This condition covers the arc that goes from state A back
onto itself in the Figure.  Recall that state A assignment is "01"
which determines the present state

values PS(0)*PS(1).  X is the condition on the arc.  "0" is the
value for latch 0's next state.

      Since anything ANDed with "0" returns "0", most of the
conditions in the Table retu...