Path: utzoo!utgpu!attcan!uunet!lll-winken!ames!ncar!boulder!sunybcs!rutgers!att!whuts!whuxr!ljw
From: ljw@whuxr.ATT.COM (WU)
Newsgroups: sci.electronics
Subject: Optimal State Machine State Assignments
Keywords: FSA, FSM, State Machines, Finite State Automata
Message-ID: <217@whuxr.ATT.COM>
Date: 6 Jan 89 15:08:37 GMT
Organization: AT&T Bell Laboratories, Whippany NJ
Lines: 21


I am in the process of designing a few state machines of reasonable
complexity for eventual ASIC impementation.  Does anyone have a program
that will analyse allowable state transformation and generate an optimal
encoding scheme to minimise the number of product terms?

As an example, I have a state machine with 10 defined states.  I am
currently using a 4-bit machine which utilises something on the order of
60 product terms for my present sub-optimal state mapping. While an
encoding scheme using more bits may reduce the number of product terms,
I have the added restriction that all undefined states must transition
to some known state in one cycle.  Ideally, I would like to be able to
tradeoff both the number of product terms as well as the number of
encoding bits in the search of an optimal area implementation.

I have found several theoretical articles in the literature addressing
this problem, but I do not have the time to implement them.  Any help
with this problem would be appreciated.


				Les J. Wu