ljw@whuxr.ATT.COM (WU) (01/21/89)
Recently, I posted a message asking for assistence (preferably automatic) in the optimal assignment of states for a Finite State Machine. I received several email responses and phone calls and thank all those who took the time to lend advice. While ad hoc hints and tips were available, there doesn't seem to be a turnkey approach to this problem. I suspect that I will apply these tips to produce a brute force, sub-optimal implementation. A summary of tips follows: *** Original Problem Statement *** 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 transformations and generate an optimal encoding scheme to minimise the number of product terms? ... 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. Tom Merrick Replies: > *DO NOT HAVE ANY UNASSIGNED STATES* This is easy to do and reduces > logic. Use an "x" in a binary state assignment and that uses up two > possible state assignments. In addition it is easier to decode. Two > x's would use up 4 possible codes. It is helpful to examine your states > to see which ones would benefit from ease of decoding. I initially used ABEL v2.00b to develop and to simulate my state machines. I recently talked to Data I/O and they basically say to not use don't cares, or X's in the state assignments. It is not entirely clear whether or not this is going to be resolved in v3.1 which they claim will be out shortly. Further, they state that they will support a higher level of reduction/optimisation in v3.1. It sounds like they will be able [no pun intended] to support equivalent states, but I am not certain. Unfortunately, I cannot justify the high cost of buying their support to obtain the 3.1 upgrade. > I know of no good program for doing state assignment, but in your case > exhaustive search is possible. Before doing that take a look at > symmetry. For example, if two branches of your machine have the same > structure, make their assignments differ by the same bit. From: sun!tc.fluke.COM!witters (John Witters) > I use Data I/O's ABEL program to create and reduce the logic equations > of a state machine. With ABEL I can try several different state > sequences fairly quickly since ABEL takes care of converting the state > machine into reduced logic equations. I also use ABEL v2.00b in a similar manner. (See the above comment on reduction in v3.1) > I suppose you could automate this to try all possible state sequences. > However, with ten states there are about 3.6 million possible sequences, > and it's not practical to try them all out unless you have a CRAY 2 (or > a lot of time). You can try a few though, and you may stumble upon a > good one. I'd suggest starting with a grey code sequence. Grey code is often recommended, but is not always practical. (A Cray might be nice to have, but is a pain to use!) > ... you may find using a[n ABEL] truth table will work better than using > a state diagram. The state diagram will force all unspecified states to > transition to state 0, which may not be what you want. You can work > around this by specifying transitions for unspecified states, but it may > be less cumbersome to use a truth table instead. The truth table for a > state machine would look something like this: A potentually useful idea. I haven't gotten around to test this though. ========================== And finally, a collection of references on the subject: ti Sequential machines and automata theory. au Booth, T.L. pu Wiley. 1967. 592p. ti Introduction to the theory of finite state machines. au Gill, A. pu McGraw-Hill. 1962. 207p. ti Finite state models for logical machines. au Hennie, F.C. pu Wiley. 1968. 466p. ti Logic design of digital systems. 2d ed. au Dietmeyer, D.L. pu Allyn & Bacon 1978. 851p. ti Introduction to automata theory, languages, and computation. au Hopcroft, J.E. au Ullman, J.D. pu Addison. 1979. 418p. > From: asuvax.asu.edu!asuvax:sullivan (G. Allen Sullivan) > I offer the Myhill-Nyrode theorem on page 65 of Introduction to > Automata Theory, Languages, and Computation ti Algebraic structure theory of sequential machines. au Hartmanis, J. au Stearns, R.E. pu Prentice-Hall. 1966. 211p. Articles: Treseler, "PLD State Machines Cut Controller Design Time" in Electronic Design, 27 Oct 1988, pp 129-133. Karp, R. M., "Some Techniques of State Assignment for Synchronous Sequential Machines." IEEE Trans EC-13 Oct 1964, pp 507-518. Hartmanis, J. "On the State Assignment Problem for Sequential Machines I," IRE Trans EC-10, pp 157-165, Jun 1961. Sterns, R. E. and Hartmanis, J. "On the State Assignment Problem for Sequential Machines II," IRE Trans EC-10, pp 593-603, Dec 1961. Mealy, G. H. "A Method for Synthesizing Sequential Circuits." BSTJ v34 Sept 1955, pp 1045-1079. ----------------------------------------------------------------------------- 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 -----------------------------------------------------------------------------