JavaFSM

by Karola Krönert and Ulrich Dallmann

ENGLISH translation by Holger Rehmeier
IPCT, PUCRS, BRASIL (more tools)


The written version of our pre-theses in Postscript-Format (German only) is located here.

Introduction and motivation:

Through the increasing complexity and integration in chip-design, more complex course-controls are necessary. Therefore, finite processors gain more importance in modelling in this area. Nevertheless, there is still a lack of suitable graphic devolpment tools, especially in the area of public domain software.

Furthermore, the aim originated in the work-area TECH of the university of Hamburg is to make technical computer science more clear to the student of basic informatics through practical examples. So, the idea originated to develop a program that fulfills both requests. JavaFSM is therefore for students for introduction, as well as for developers for practical use.

As programming language, the new, object-oriented language Java of Sun Microsystems was chosen. Java offers several advantages compared to conventional programming languages:
 
Java is platform-independent. A Java-program is translated by a compiler in platform-independent byte-code, that is then executed to the term of a Interpreter, the Java Virtual Machine. The Virtual Machine is implemented for all current systems in the meantime. 

Java is object-oriented. With the object-bearings, the data and their manipulation stand in the foreground, not the procedures. Objects can transmit their qualities to other objects or can be supplemented with more options. 

Java offers extensive class-libraries, that cover beside standard-functions also new areas, as network- and data base-access. Since the libraries come already with the client in the Java-interpreter, these don't have to be loaded from the network. 

Beside Standalone-Applikationen, Java offers the possibility to embed programs in HTML-pages. These so-called applets are executed then by the virtual machine integrated in the browser. Therefore Java-appletses are accessible through the World-Wide-Web. Another advantage of applets is that no installation is necessary. Also updates can be done through a simple exchange of the classes on the WWW-Server.

Through the platform-independence from Java and the possibility that applets can be embeded in HTML-pages, Java is especially suitable for the use in education, since a great number of  people can be reached.

Reference-platform of  Java is the Java Developers Kit (JDK) of Sun company.

The JDK offers the possibility with the command javadoc, to generate a documentation of the classes in HTML-format from the sourcecode and the comments automatically. The Javadoc-Dokumentation to JavaFSM is located here.

Introductory literature to the topic Java and interesting Java-links are located at http://tech-www.informatik.uni-hamburg.de/Students/2kroene/java/java/javalinks.html.

Program-construction:

JavaFSM can be started as an applet, as well as an application.

JavaFSM consists of three windows: in the first, the control mechanism-model can be seen with the in- and outputs. Here, an machine-name can be given and the type of network is defined. Furthermore, the in- and outputs can be added, altered and deleted. After defining the machine, it can be simulated here. Therefore you find a bar for clock and reset. In the delta-network, the machine is displayed. The current sate and the transition activated under the momentary conditions is marked red.

The machine is designed in the editor-window. Here, states, transitions, transition- and output-functions are defined. Additionally, it is possible to provide a vending machine with comments. The editor works modus orientated. Using buttons, you can change to the referring mode. There are six different modes.

Conditions can be moved in the move-mode ("Move"). Furthermore, transitions and states can be selected, to change their options (name, function, etc) in the parameter-field,, (see also selection-algorithm). Whether a Moore- or Mealy-machine is edited, the parameter-field of the states changes. While each output at Moore has solid output-values, a function can be defined with Mealy (using inputs). The Lambda-network can be "simulated" this way, even without a correct state-definition.

The state-mode ("State") inserts states per mouse-click. In the transition-mode ("Transition"), two conditions are connected by a transition clicking on each state. The transitions are displayed as arrows between two states. The algorithm to draw the arrows was taken from the program JavaFIG in [He97]. Components can be removed by clicking to the delete-mode ("Delete"). You fix the start-state in the start-state-mode ("Start-state"). In the comment-mode ("Comment"), comments can be inserted. Since the machine may not be changed during the simulation, the editor-window is closed automatically when starting a simulation.

The third window with the impulse-diagram offers the possibility to display the simulation-results. For a better differentiation, the inputs are blue and the outputs red in different color-gradations.

problem occured with the impulse-diagram with Mealy-machines. Here, the output-values can change also between the clock, if the input-values change. Here, we have introduced "inter-clock". Each alteration of the output-values generates such an "inter-clock". Additionally, a vector "clock-series" inserted into the class FSM that contains a "true" for each real clock and for each "inter-clock" a "false". Only with Mealy-machines both types are displayed.

FSM:

The class FSM was drafted for presenting and processing of finite state machines. All data of the machine are summarized here. Furthermore, the class provides all basic-functions for processing.

The basis-components of a finite state machine are states, transitions, inputs and outputs. Their options are displayed in the following table:
 
State Transition Input Output
  • Name
  • Position
  • Output-function
  • Start-state?
  • Initial-state
  • Goal-state
  • Transition-condition
  • Name 
  • Initialvalue
  • Current value
  • Value-sequence of the simulation
  • Name
  • Current value
  • Value-sequence of the simulation
The dynamic values of the simulation are saved in each case directly with the corresponding object, i.e.

"Just-in-time-parsing"

The calculation of transition-tables for the finite state machine necessitates exponential calculation-expenditure and additional memory. With an alteration of the machine, the tables must at least be calculated at the start of a simulation. The used alternative in JavaFSM is the "Just-in-time"-parsing of the required functions during the simulation. Only transitions, that start from the current state, are taken into account.

For the calculation of the transition-conditions and the output-functions in the states, the class Parser is used, that receives the respective function as string.

Bigger calculation-expenditure (exponentially) happen only during the checking of machines ("FSM testen"-button in the editor) and exporting to KISS, because all functions with all possibilities must be calculated here.

Method to check a defined machine

The editor contains a function, that  allows to check the  machine for syntax errors.

The "FSM-test" checks first, if conditions and transitions are existing, and if one of the states was defined as start-state. It calculates all possibilities then and determines, whether in each case exactly one transition is activated. In a dialogue-window, errors are displayed.

Selection-algorithm in the editor:

The selection of conditions simply takes place through the calculation of the distance between state-center and click-point (see illustration). In order to select transitions, the distance of the click-point to the line (plumb) should actually be calculated. A simpler possibility consists of the comparison of the distance of both states with the sum of the distances of the states to the click-point. If this is not really longer, the transition has been selected:
 
Condition-selection Transitionsselektion

Load and save

JavaFSM offers the possibility to save designed machines and to load them again.

For this you use "File - Load/Save".

In the applet, a name and a password is entered in a dialogue-window and is saved with the machine under this name on the server.

A FSM-Datei has the following construction:
 
[JavaFSM V1.0] Header with version-number
[Machine Type MEALY or MOORE
[Name] Marks the namen-block
Name The name of the machine 
[Inputs quantity] Marks the input-block, with the number of inputs
name,initial Name and start-value of an input (each line contains exactly one input) 
[Outputs quantity] Marks the output-block, with the number of outputs 
name Name of an output (each line contains exactly one output) 
[Zustaende quantity] Marks the states-block, with the number of states
name,xpos,ypos,isStart,output1_fkt... Name, position, isStart (boolean) and for each output the output-function 
[Transitions quantity] Marks the transitions-block, with the number of transitions
name1,name2,fkt Names of the two states connected and the transition-function 
[Kommentare quantity] Marks the comment-block, with the number of comments
xpos, ypos, text Position and comment-text (this can contain "%10" for a new line) 
[ENDE] The End

Example:

[JavaFSM V1.0]  
[MOORE]  
[Name]  
Example machine  
[Inputs 2]  
a,0  
b,1  
[Outputs 3]  
x  
y  
Z  
[Zustaende 2]  
state 1,58,129,true,0,1,0  
state 2,229,222,false,1,0,1  
[Transitions 4]  
state 2,state 1,b  
state 1 state 1,*  
state 1,state 2,a  
state 2,state 2,*  
[Kommentare 1]  
10,10,this is an example machine  
[ENDE]

Load and save with CGI

A Java Applet cannot access the filesystem of the lokal computer (security). A possibility to the save machines consists of to pass out text in a window and to store this by means of Copy&Paste. This way, we have done with the convertibility of the  machine to VHDL / KISS, so that the user can process the data directly.

Sending an e-mail with the data to the user represents another possibility to save data. This however does not solve the problem of saving of machines yet.

The solution, that we have chosen to save and load machines, is a network-connection to the host. Instead of implementing an own server in Java, the application of the existing WWW-Servers offeres itself. A WWW-Server offers the possibility with the CGI (Commin Gateway interface), to start programs, [He96]. These CGI-Programmes are executed over a certain URL. You can generate HTML-Seiten for example dynamically (like search-engines).

The communcation between browser, server and CGI-Programm: the browser sends an inquiry to the server and waits for an answer. The server starts the aquired CGI-Programm, which processes the inquiry, that generates the aquired answer and sends it from the server to the browser.

In the Hypertext-Transfer-Protokol (HTTP) there are two commands for browser-inquiries: with the GET-kommand, data can be send only directly to the URL. Since a URL is limited in its length, this is not enough all the time. All big data can be sent with the POST-kommand.

JavaFSM uses separate CGI-programmes to save and load. When loading, the applet sends the machinename and a password as parameters. The CGI-programm looks for that machine and checks the affiliated password.  If no errors appear,  the data of the vending machine is sent to the applet. To save a machine, the applet also sends name and password, followed from the data. Provided the name is not forgiven yet, as well as the password is correct, the CGI-Programm writes password and data into a File. The answer to the applet consists of a confirmation or a error message.

The password is mainly used for the protection of accidantally overwriting an existing file through other users. So, the designer of the machine can access the file only.

With applet-parameter, existing machines can be implemented into the menu as examples and be loaded from there.

More literature:

Parser

The Parser is needed to calculate logical expressions of the transition-conditions and output-functions (only with Mealy).

Basic-units of an expression are the operators AND (&), OR (|) and NOT (!), the names of the inputs as variables and the values 0 and 1, as well as brackets. The grammar of the parsers is:

program:
END
expression END
expression:
expression | term
term
term:
term & primary
primary
primary:
number (0,1)
name (inputs)
(expression)
! primary
The syntax-analysis is done in the manner of the rekursiven descent(top down). Each prozess-rule of the grammar corresponds to a function, the executes other function. Terminale symbols (0, 1, names of the inputs) get recognized by the syntax-analysis-functions expr(), term() and prim(). As soon as both operands of a (sub-)expression are known, it is appraised.

The Parser uses a function get_token () for reading the input. This reads the next basis-unit of the expression and saves them in a global variable. Before executing a parser-funktion the next token of get_token is determined. If get_token reads a name, it is searched in the vector of the inputs with the function look() and the current value is determined.

With the call of the parsers, the expression is extended with a return, which is used for the recognition of the end. If Get_token()  finds this sign, the evaluation-process is finished and the truth-value of the expression is reruned. If an error occurs during the evaluation-process, a BadExpressionException is done, which ends the Parser appruptly.
 

Export of machines to VHDL / KISS

In order to process defined machines more further, JavaFSM offers the possibility, to convert these into the formats VHDL and KISS. The edition of the VHDL- / KISS-codes is exported into a text-field, from where you can copy & paste it.

VHDL

VHDL is a hardware-description-language accepted world-wide meanwhile. It was originally developed for the documentation of circuits: the from outside visible behavior is defined in form of (legible) behavior-descriptions. High-level-language-struktures like IF-THEN-ELSE or CASE are used within. In circuit-design, so-called synthese-tools generate complete networks in form of gate-network-listings from it. These can be optimized on different goals (time, space,...).

Since VHDL is supported by numerous tools, it is also used for data exchange. Front-End tools generate compiler-specific VHDL-Codes, that can be processed by other tools    .

To be able to use generated machines with JavaFSM it is possibe to export them to VHDL.

KISS / PLA design format

KISS is mainly used witch programmable logic. It is a technology-independent format, which is based on truth-talbes. Beside miscellaneous features like "don't cares", "subsets" etc it supports also finite state machines. A Design-File consists of a header with basic-information and a Body with the actual logic-tables. The table used by JavaFSM is described here:
 
# Commentary-line
.design name Name of the design
.inputnames name_1, [name_2...] Here, all inputs are defined (incl. clock- and reset-Signal). In this sequence, they are listed in the value-table. 
.outputnames name_1, [name_2...] All outputs are defined here. In this sequence, they are listed in the value-table. 
.clock signal sense One of the inputs is defined as Clock-Signal here
  • signal: Name of the input 
  • sense: can assume the values "of rising_edge" or "falling_edge" (Flip-Flop is activated with rising or falling edge of the clock-signal) 
async_reset signal sense state One of the inputs is defined here as Reset-Signal 
  • signal: Name of the input
  • sense: can assume the values "of rising_edge" or "falling_edge"  (s.o.) 
  • state: state, that should be assumed after a reset, (start-state) 
010 z1 z2 01  a line of the value-table: 
  • input-value
  • sate regarded in this line
  • state, in to the machine changes with this configuration, 
  • output-value with this configuaration
01 - z1 z2 01 a "-" in the input-value marks a "don't care". 

In JavaFSM it is abstracted by a concrete condition-coding. If a certain coding is required (for example as direct edition), you can define it in KISS later:
 
.encoding state-coding
state_name encoding
  • state_name: state
  • encoding: numerical value:
 
2#1010 binary
10#10 decimal
16#A hexadezimal 
 


JavaFSMTECHUlrich DallmannKarola Krönert