martin@csc2.essex.ac.uk (Colley M) (06/13/91)
Hi I am looking for a compiler/translator (public domain) that will take a description of a state machine and produce the equivalent logical equations. I have previously used CUPL for this purpose but that requires the state machine to fit into one of the PALs that CUPL knows about. The state machine I am currently working on is too large to take this route. Does anybody have or know about such a program. Thanks in advance Martin Colley email: martin@uk.ac.essex
pixley@mowog.cad.mcc.com (Carl Pixley) (06/15/91)
In response to Martin Colley to whom my reply bounced.
I am looking for a compiler/translator (public domain) that will take
a description of a state machine and produce the equivalent logical
equations. ....
Any gate level synthesis tool performs the task you require, at least
implicitly. Given a state machine, an encoding must be specified or,
often, the tool figures out an encoding for you. A one-hot encoding
assigns a different storage element to each state of the state
diagram.
Given the encoding and the specification, logic functions for the
inputs to flip-flops and outputs of the designs are derived
automatically. In state-of-the-art synthesis tools (like Synopsys)
these functions are often represented as Binary Decision Diagrams
which can easily be printed out as logic formulas. I suspect that
this is true of the BOLD system from the University of Colorado or the
MIS system from Berkeley.
You might contact Fabio Somenzi at Colorado for some information.
fabio@duke.Colorado.EDU
Carl
(pixley@mcc.com)
@ MCC VLSI CAD Program [512] 338-3734
P.O. Box 200195, Austin, TX 78720
ARPA: pixley@mcc.com
UUCP: {ihnp4,seismo,harvard,gatech,pyramid}!ut-sally!im4u!milano!bell!pixleymiyazaki@taichung (Takeshi Miyazaki) (06/16/91)
Related question: Is there any state assignment program which can reduce finite state machine? (reduce the number of states and generate equivalent FSM) I tried NOVA, JEDI, and Mustang, but they don't seems to change the number of states. (when applied to ex3, ex5... of MCNC benchmarks) Thanks in advance. Takeshi Miyazaki miyazaki@ee.princeton.edu
luciano@canuck.Berkeley.EDU (Luciano Lavagno) (06/17/91)
stamina, a program written by June Rho at the University of Colorado, Boulder, does state machine minimization. Send mail to rho@boulder.colorado.edu for more information. It's very good, even though it can take a long time to complete on large FSM's. It can do exact minimization of incompletely specified FSM's. Bye ! Luciano -- +----------------------------+------------------------------------+ |Luciano Lavagno | E-mail: luciano@ic.Berkeley.EDU | |Dept of EECS, Rm. 550B2-69 | | |UC Berkeley | Phone: (415) 642-5012 | |Berkeley, CA 94720 (USA) | | +----------------------------+------------------------------------+
mshute@cs.man.ac.uk (Malcolm Shute) (06/18/91)
In article <10809@idunno.Princeton.EDU> miyazaki@taichung (Takeshi Miyazaki) writes: >Is there any state assignment program which can reduce finite state machine? >(reduce the number of states and generate equivalent FSM) It's probably not what you were asking for (since it was only a 'toy' research package): but does anyone know if anything commercially usable came out of an M.Sc. thesis by Simon Finn (1983) of the Programming Research Group (Oxford University)... he used Mary Sheeran's HDL (called uFP) to describe a simple Minsky machine, going through the same sort of process as Mead and Conway (1980) did in section 6.2 of their book (An Introduction to VLSI Systems)... i.e. Starting with the processor described as a single, massive FSM, it was mathematically decomposed into a network of much smaller FSMs (e.g. the PC, and PSW could be broken off from the main loop, and then the register bank, etc). -- Malcolm SHUTE. (The AM Mollusc: v_@_ ) Disclaimer: all
fernand@imag.imag.fr (Jean-Claude Fernandez) (06/20/91)
In article <10809@idunno.Princeton.EDU> miyazaki@taichung (Takeshi Miyazaki) writes: > >Is there any ... program which can reduce finite state machine? >(reduce the number of states and generate equivalent FSM) > >Takeshi Miyazaki >miyazaki@ee.princeton.edu I've done such a tool of minimization of finite transition systems. This tool was done in a very different context : @ARTICLE{fernandez90, AUTHOR = {J.C. Fernandez}, TITLE = {An Implementation of an Efficient Algorithm for Bisimulation Equivalence}, JOURNAL = {Science of Computer Programming}, VOLUME = {13}, NUMBER = {2-3}, MONTH = {\may\ }, YEAR = {1990} } But I'm ready to try some other examples, the field of VLSI seems interesting. Interested reader would have to send me their exemple files and a syntax of the description. J.Cl. Fernandez -- Jean-Claude Fernandez (fernand@imag.fr fernand@imag.UUCP uunet.uu.net!imag!fernand)