Browse Prior Art Database

Method for Finite State Table Compaction

IP.com Disclosure Number: IPCOM000099715D
Original Publication Date: 1990-Feb-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 2 page(s) / 59K

Publishing Venue

IBM

Related People

Slane, AA: AUTHOR

Abstract

A method to compact state tables into efficient structures using mapping arrays is described. This addresses problems associated with finite state tables using large data areas due to a large number of inputs and possible states associated with the state table.

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

Method for Finite State Table Compaction

       A method to compact state tables into efficient
structures using mapping arrays is described.  This addresses
problems associated with finite state tables using large data areas
due to a large number of inputs and possible states associated with
the state table.

      Redundant rows in a state table are compacted by remapping the
rows of common inputs into a single row of a finite state machine.
This is done with the use of a mapping array.  An example is
explained below.

      In Fig. 1, a state table is shown with twelve rows and ten
columns. Rows C, D, F, and L are identical.  Rows H, I, and J are
also identical. These seven rows are compacted into two unique rows,
thus saving five rows in the state table.  This is shown in Fig. 2.

      The second state table in Fig. 2 is the same as the first
except the redundant rows are compacted into two unique rows.  The
remaining problem is how to map the original inputs from the first
table into the new inputs of the second table.  A mapping array is
used to accomplish this task.  Before accessing the state table, the
row that is desired to be used is looked up.  The following examples
show the difference between an original access method and a new
access method.  The name of the mapping array is MAP.
      Initial final state machine method:
           Next_State := State_Table(Input, Current_State)
      New Method:
        ...