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 Assignments  (Second Posting -- Sorry)
Keywords: State Machines
Message-ID: <218@whuxr.ATT.COM>
Date: 6 Jan 89 15:21:48 GMT
Organization: AT&T Bell Laboratories, Whippany NJ
Lines: 29

[sorry for the second posting, but my signature was missing!]

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
-----------------------------------------------------------------------------
Les J. Wu					AT&T Bell Laboratories
(UUCP) att!whuxr!ljw				One Whippany Road
(arpa) ljw!whuxr@research.att.com		WH 2F-316
						Whippany, NJ 07981
*** STANDARD DISCLAIMERS APPLY ***		Tel: (201)386-3409
-----------------------------------------------------------------------------