[sci.electronics] Optimal State Machine State Assignments

ljw@whuxr.ATT.COM (WU) (01/06/89)

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