Fsm design tools

For the legacy code, extracted FSM graphs act as a design specification, allowing better understanding of the RTL code and facilitating its reuse.

The following picture demonstrates the FSM graph extracted by Lint tools:. After FSM extraction, Lint tools apply various structural and functional checks to further verify FSM correctness and its compliance to company standards. Moore FSM are preferable from a timing perspective too, as FSM output timing paths include output decoding logic only. Also, it is a good practice to enforce a specific state encoding type to better fit a design into design requirements.

For example, the one-hot encoding with Moore FSM type is preferable for the high-speed designs, while Gray encoding being preferable for the low-power applications, etc. Lint tools guarantee that proper synthesis-specific attributes accompany the FSM code. For example, a transition such as:. Having the FSM structure extracted, and all transitions verified, Lint tools check that there are no deadlock states in FSM descriptions.

As opposed to the deadlock states, unreachable states do not have input transitions, making FSM impossible to enter either one of these states. In some FSM designs, only the Reset state is allowed to be unreachable in a case that it is never used later on while design is running. In addition to static deadlock, dynamic livelocks may exist in Finite State Machines too. Dynamic livelock represents not the single state, but rather the group of FSM states.

Once entered, the FSM cannot leave this group, continuing to circulate between the group states. The usage of Lint tools is very important for the development of the mission-critical designs. These designs should work flawlessly under any PVT process-voltage-temperature variations, being resistant to excessive radiation levels and aging.

One FSM safety feature is the ability to restore the state machine to a safe state if the state register becomes corrupted.

Lint tools provide such checks as well, making sure that there is always a default statement in the FSM branches description, and all execution branches of the default statement lead to safe state s.

Safety-critical designs are required to be glitch-free. Making Finite State Machines glitch-free is of high importance for such designs, as Finite State Machines usually control significant parts of design logic.

Lint tools help to guarantee the glitch-free operation of designed FSM logic. Designers may configure Lint tools to allow only a glitch-free types of Finite State Machines, for example:. In summary, Lint tools are able to validate deadlock, lovelock, reachability as well as many other FSM-related issues at the earliest design stages, saving verification time and eliminating possible functional and implementation flaws.

For safety-critical designs, Lint tools help to ensure FSM code safety according to safety standard requirements. Mature, low-cost manufacturing and proven reliability spur use in EVs, smart phones, and consumer electronics. For a given combination of input and current state, each cell displays the next state and a list of actions or outputs to be generated at that point. Note that several cells contain only a state transition, since no output is generated.

For instructional purpose, blue type is used to highlight the cells that correspond to a successful input sequence, leading to unlocking the deadbolt. The reason for that is that once the latch is unlocked, the device ends up in the initial state A, as indicated in cell C-1; pressing any key would then allow for relocking the deadbolt.

This exceedingly simple example has very few states and only one output device that can assume two possible values. In more complex applications, each cell could list several actions or outputs to be generated. The next step is to generate the source code that embodies the STT just created.

I'll also discuss optimization of that code. In the hope of making the logic apparent to most programmers, I presented the code in a loosely syntaxed C-like pseudo-language.

It will be left to the object-oriented programmers to figure out how to solve the problem using classes and objects. Note that break statements are implied at the end of each case. This example makes use of a multivariable SWITCH structure dependent on both the State and Input values; this is not normally allowed in C or other programming languages. Also, should changes in the design at a later time require additional states or inputs, the source can be easily edited by inserting more cases with all the new combinations of states and inputs just above the Default statement.

The fifth line of the source code includes the statement IF Debug write Input, State that creates a trace of states and inputs on hard copy or in a file when the Debug flag is set. That sequence of states and inputs reveals a great deal about what happens in the code and should confirm the earlier claim that the FSM paradigm can incorporate an effective debugging tool by just adding that single line of code. The debugging facility could be improved by also listing the last output.

In the case of a hard real-time or time-critical application where writing to a printer or a file would unacceptably disturb the timing, one could push the state and input variables into a memory buffer for postmortem viewing. Both improvements will require a bit of additional code that most readers will be able to figure out. A few final points about the overall design process need to be added.

It was indicated earlier that ideally each state transition and associated actions need to take place instantaneously. That means that the state transition and actions have to be atomic, so that no input could occur before the transition to the next state is stable and the output activities have completed.

Otherwise one could end up with unplanned transitions, race conditions, and unexpected behavior. However, in the real world some actions may take a significant amount of time or result in asynchronous events with unpredictable timing just think of a communication system waiting for a response. Here is where the designer needs to apply some careful analysis and possibly consider inserting some transitional states in order to avoid these potential problems and creating an unstable system.

These can be complex issues that are intrinsic and specific to each project and beyond the scope of this article; just let the reader be forewarned. The initial sales pitch indicated that the FSM design method lends itself to group design. If one congregates a team of programmers who have a good understanding of the task at hand, it's possible to brainstorm a state transition table quite effectively using a whiteboard or a computer with a projector and a spreadsheet program.

The design process would start by listing the system's inputs along the left edge and drawing one column for the initial state. The table would be gradually expanded by identifying the various states and adding the corresponding columns until the STT is completed and the system is fully described. The checks and balances provided by several pairs of eyes could ensure a robust design and even contribute to the team's group spirit and cooperation.

Most programmers are familiar with state diagrams or charts, where states are represented by bubbles and transitions are free-form arrows connecting the bubbles. State diagrams are used quite commonly and there are convenient software tools that can expedite their creation.

Here's why. Any chart containing more than a few states and transitions can quickly become overly complex and confusing. This is particularly true if a diagram needs to span over several pages or screenshots. There is no standard drawing order or pattern; some designers start drawing the charts from left to right and top to bottom; others start from the center of the page and fan out in all directions, making it often difficult to find the thread in the logic.

Diagrams may not have a consistent look on different computers because of the dissimilar tools or screen settings used to view them. Graphics are more difficult to edit and maintain than tables, so state diagrams may often fail to keep up with design or code changes throughout the lifecycle of the project and can eventually become useless as either documentation or maintenance tools.

The connection between a state diagram and the corresponding code is not always obvious, whereas a state transition table seems to map directly into the structure of the code, as this paper has attempted to show. I hope that this article will motivate you to use the FSM design method in your next software project. He has over 40 years of experience in designing software for real-time applications and has earned M. In his spare time he plays clarinet and sax in a Jazz band.

You must Sign in or Register to post a comment. This site uses Akismet to reduce spam. Learn how your comment data is processed. You must verify your email address before signing in. Check your email for your verification email, or enter your email address in the form below to resend the email. Please confirm the information below before signing in.

Already have an account? Sign In. The make-multi-fsm-sbb , generate-fsm and generate-dot tasks use the following attributes.

A Java class which will be the super class of the generated state-machine SBB. If set, a fully qualified class name is required. The root directory used to write the generated class file. The package subdirectory structure will be created automatically. Using the fsm-for-multi-per-sbb. Using the dot. The following exception was generated by a modified version of the multifsmsbb example provide in the FSM Tool examples:. To check event parameters, applications typically use input actions.

You can implement this type of parameter checking by defining an input action for the state. For example:. In this example, when the state machine receives an idp on the endpoint capv2 , it:. This transition is unconditional, so will always be executed. If the child FSM needs to communicate a value back to the calling parent FSM after executing its action methods, this can be achieved in two ways:.

Applications need timers when networks might not return a response. For example, the following snippet from a FSM specification contains a state to start, cancel, or handle an timer event:. If the timer expires, the Sbb receives a TimerEvent through its onTimer event handler method. It sets the Timer input and calls the execute method. The FSM Tool installation has an example called multifsmsbb.

This example has two FSMs:. To correctly generate the code:. To make it work, you must:. For example, if the declared input is message and received on endpoint tcp , the service calls the getMessageFSM.

If you need to set more than one input before executing the state machine, simply add more getMessageFSM. It is accessed using getTimerFSM. Each action defined in the state machine specification renders into a method declaration in an actions interface , which is declared as an inner interface of the state-machine POJO class.

In this case TimerFSM. TimerFSMActions :. The action interfaces are typically implemented in POJO classes, and an instance must be registered with the state machine execution class best to do this in the setSbbContext method. For example, the following code snippet shows the method implementation for the setTimer action, defined in the multifsmsbb example:.

See the multifsmsbb service in the examples. The description element describes the FSM, using the description keyword followed by the text in quotes which can span multiple lines :.

You define a state with the state keyword, followed by the name of the state, and then the state body see below. You define initial and final states using the initial and final modifiers. For example, for an initial state:. The state body has the following elements, defined by keywords and other variables, and declared in the following order:.

The first line in this example evaluates the conditional expression tcp. The second line evaluates the conditional expression tcp. The second line evaluates the conditional expression capv2. This example shows an unconditional transition. The state machine will never wait for input in this state as this transition will be performed. Only one unconditional transition should be declared and always last. Any transitions declared after it will be unreachable and never checked or performed.

For multiple transitions with conditions evaluating to true, the first transition declared will take precedence and will be the only transition to execute. The inputdictionary must declare all inputs used in the state body elements.

You define an inputdictionary element with the inputdictionary keyword, followed by the inputdictionary body. The inputdictionary body declares 0 or more inputs. Each input can either be an external input received through an endpoint or a local input internal to the current FSM. External inputs are declared by the name of the endpoint on which they are received, followed by a.

Used to specify the behaviour of an action. The actiondictionary must declare all entry, exit and input actions used in state body elements. An actiondictionary element is defined with the actiondictionary keyword, followed by the actiondictionary body.

In the example, tcp. Quick Start. FSM Tool Procedures. A finite state machine FSM is a behavioural model that consists of:. Example: opening and closing a door The Wikipedia FSM entry gives the following example of an elevator door opening and closing:. The states are Opened and Closed. The actions are open door and close door. While Moore machines are often simpler, Mealy machines often have fewer states. A declared set of actions used in the FSM states' input, exit, and entry actions.

Boolean algebraic conditional expression. The FSM evaluates any possible transitions. Otherwise, the FSM selects the first transition for which the condition evaluates to true. It executes exit actions for the source state. The FSM executes entry actions for the sink state. The tool does not automatically unset durable inputs. Using FSM Tool , generated code can be as efficient as handwritten. Support for Moore and Mealy machines Developers who have experience in Moore and Mealy machines can use FSM Tool to support both machine styles by limiting the use to specific features:.

The perils of hand-coding. The benefits of using a tool. Some state machine tools, such as UML state charts and SCXML, have complex specifications that include features such as composite states that represent embedded state machines, include conditional logic and provide embedded programming features.

Instead, it focuses on the formal specification of state machine behaviour. Check your prerequisites. To use FSM tool you need:. Unpack the downloaded. Try the "Hello World" example. To review the sample application, please explore the following:. The "Hello World" state machine includes:. When the machine detects the hello input received on the tcp endpoint in state startState , it transitions to state stopState , whereupon it executes entry action helloWorld.

How the sample state machine is defined You define FSM Tool state machines using a simple, easy-to-understand and modify , text-based, domain-specific language DSL. Build and deploy First build and deploy the service, using the following commands:.

Start a command window or shell. Enter telnet localhost Type hello , and press Return. Hello World. Digging deeper. Extending the "Hello World" example Now that you have successfully run the "Hello World" example you can extend the state-machine definition to implement more complex state-machine behaviour, as follows:. Installing the extended HelloWorld example First build and deploy the service, using the following commands:. Starting Again.

Run telnet localhost Type hello , and press Return.