Algorithmic state machine

The algorithmic state machine (ASM) method is a method for designing finite state machines (FSMs) originally developed by Thomas E. Osborne at the University of California, Berkeley (UCB) since 1960, introduced to and implemented at Hewlett-Packard in 1968, formalized and expanded since 1967 and written about by Christopher R. Clare since 1970. It is used to represent diagrams of digital integrated circuits. The ASM diagram is like a state diagram but more structured and, thus, easier to understand. An ASM chart is a method of describing the sequential operations of a digital system.

ASM method

The ASM method is composed of the following steps:

:''1''. Create an algorithm, using ''pseudocode'', to describe the desired operation of the device.
:''2''. Convert the pseudocode into an ''ASM chart''.
:''3''. Design the ''datapath'' based on the ASM chart.
:''4''. Create a ''detailed ASM chart'' based on the datapath.
:''5''. Design the ''control logic'' based on the detailed ASM chart.

ASM chart

An ASM chart consists of an interconnection of four types of basic elements: state name, state box, condition checks, and conditional outputs. An ASM state, represented as a rectangle, corresponds to one state of a regular state diagram or finite state machine. The Moore type outputs are listed inside the box.

State Name: The name of the state is indicated inside the circle and the circle is placed in the top left corner or the name is placed without the circle.

State Box: The output of the state is indicated inside the rectangle box

Decision Box: A diamond indicates that the stated condition/expression is to be tested and the exit path is to be chosen accordingly. The condition expression contains one or more inputs to the FSM (Finite State Machine). An ASM condition check, indicated by a diamond with one input and two outputs (for true and false), is used to conditionally transfer between two State Boxes, to another Decision Box, or to a Conditional Output Box. The decision box contains the stated condition expression to be tested, the expression contains one or more inputs of the FSM.

Conditional Output Box: An oval denotes the output signals that are of Mealy type. These outputs depend not only on the state but also the inputs to the FSM.

Datapath

Once the desired operation of a circuit has been described using RTL operations, the datapath components may be derived. Every unique variable that is assigned a value in the RTL program can be implemented as a register. Depending on the functional operation performed when assigning a value to a variable, the register for that variable may be implemented as a straightforward register, a shift register, a counter, or a register preceded by a combinational logic block. The combinational logic block associated with a register may implement an adder, subtracter, multiplexer, or some other type of combinational logic function.

Detailed ASM chart

Once the datapath is designed, the ASM chart is converted to a detailed ASM chart. The RTL notation is replaced by signals defined in the datapath.

See also

* Flowchart
* Drakon-chart
* Mealy machine
* Moore machine
* Map-entered variables (MEV)

References

* Sunggu Lee: ''Computer Design: An Example of Advanced Digital Logic Design'', Prentice-Hall 2000, .
* Sunggu Lee: ''Advanced Digital Logic Design: Using VHDL, State Machines, and Synthesis for FPGAs'', Thomson 2006, .
* Stephen D. Brown, Zvonko Vranesic: ''Fundamentals of Digital Logic with VHDL Design''.
** 2nd, McGraw Hill 2004; .
** 3rd, McGraw Hill 2009; .
*
*
*

Further reading

* (7 pages) (NB. This article caused a number of letters to the editor in subsequent issues of the magazine.)
* (1 page) (NB. Osborne's method was later published by Clare.)
* {{cite book , title=Logic Design - A Review of Theory and Practice , chapter=Chapter 4. Interrelationships, D. Logic Design and Switching Theory, 3. The Flow Table as a Point of Departure for Design , author-first=Glen G. , author-last=Langdon, Jr. , location=IBM Corporation, San Jose, California, USA , editor-first=Robert "Bob" Lovett , editor-last=Ashenhurst , editor-link=:d:Q102124175 , date=1974 , edition=1 , series=ACM Monograph Series , publisher=Academic Press, Inc. - A Subsidiary of Harcourt Brace Jovanovich, Publishers , publication-place=New York, USA , isbn=0-12-436550-7 , lccn=73-18988 , issn=0572-4252 , page=149 , chapter-url=https://books.google.com/books?id=sQwE8Gpsj5EC&pg=PA149 , access-date=2021-04-17 , url-status=live , archive-url=https://web.archive.org/web/20210417063924/https://books.google.de/books?id=sQwE8Gpsj5EC&pg=PA149 , archive-date=2021-04-17 , quote-page=149 , quote= €¦An important contribution to the adaptation of theory to practice was made by Schultz 0 he draws upon the designer's basic understanding of the problem and requires him to identify the "infrequent variables." Loosely defined, these variables do not relate to all internal states, i.e., they are not needed to define every state. In essence, the infrequent variables are relevant to only a few (perhaps one or two) states or state transitions. Schultz suggests that the designer first translate the verbal problem to a state transition graph that is reduced. The internal states are encoded and then information regarding infrequent variables is added to the appropriate state transitions. A "first approximation" to flip-flop input equations is made, based only upon the frequent variables. Schultz demonstrates how these equations can subsequently be modified to incorporate transitions controlled by the infrequent variables. In Schultz's examples the infrequent variables are all input signals, but this idea also applies to internal state variable signals that may be considered "infrequent." In this case, for example, an infrequent internal state variable flip-flop might be set by a particular circumstance and reset sometime later. The output of the flip-flop may now be treated as an infrequent input variable. €¦} (ix+1+179+3 pages)

External links

Brief Introduction to ASM Charts

ASM++: a modern Algorithmic State Machine methodology for RTL designs

Computer engineering
Electronic design automation