Algorithmic state machine

Not to be confused with Abstract state machine.

The algorithmic state machine (ASM) is a method for designing finite state machines (FSMs) originally developed by Thomas E. Osborne at the University of California, Berkeley (UCB) since 1960,^[1] introduced to and implemented at Hewlett-Packard in 1968, formalized and expanded since 1967 and written about by Christopher R. Clare since 1970.^[2][3][4] 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, decision box, and conditional outputs box. 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

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

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

 

Decision box used in an ASM chart

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

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

1. Osborne, Thomas "Tom" E. (2004-11-11) [1994]. "Tom Osborne's Story in His Own Words". Steve Leibson's HP9825 page (Letter to Barney Oliver). from the original on 2021-02-24. Retrieved 2021-02-24.
2. Clare, Christopher "Chris" R. (February 1971) [November 1970]. Logic Design of Algorithmic State Machines. Hewlett-Packard Laboratories, USA: Hewlett-Packard. CHM Catalog Number 102650285. (110 pages) (NB. Several internal revisions existed in 1970 and 1971. This was later published by McGraw-Hill.^[A])
3. Clare, Christopher "Chris" R. (1973) [November 1972]. Designing Logic Systems Using State Machines. Osborne, Thomas "Tom" E. (initial contributions) (1 ed.). Electronics Research Laboratory, Hewlett-Packard Laboratories: McGraw-Hill, Inc. ISBN 0-07011120-0. S2CID 60509061. SBN 07-011120-0. ISBN 978-0-07011120-2. ark:/13960/t9383kw8n. 79876543. Retrieved 2021-02-14. (vii+114+3 pages) [2] (NB. This book is based on a 1970 Hewlett-Packard in-house document.^[B])
4. House, Charles "Chuck" H. (2012-12-24). "A Paradigm Shift Was Happening All Around Us" (PDF). IEEE Solid-State Circuits Magazine. Vol. 4, no. 4. Stanford University: Institute of Electrical and Electronics Engineers. pp. 32–35. doi:10.1109/MSSC.2012.2215759. eISSN 1943-0590. ISSN 1943-0582. (PDF) from the original on 2013-01-20. Retrieved 2023-06-30. pp. 2–3: The second annual IEEE Workshop on Microprocessors (now called the Asilomar Microcomputer Workshop, or AMW) was held Wednesday–Friday, April 28–30, 1976, near Monterey, California […] My Wednesday evening talk described tools that enabled a very different design methodology—Algorithmic State Machine design (ASM)—using Lyapunov state-variable mathematics, and derivative techniques pioneered at HP by Chris Clare and Dave Cochran for the spectacularly successful handheld scientific calculators (e.g., HP 35) […] My point: circuit design was no longer an element-by-element issue, but a question of "state flow" at lots of nodes—the sequential "words" of registers rather than the voltages of device pins. In effect, it argued that electronic voltages, whether analogic or switched, would "lose out" to software instructions, and "data states." Systems would be designed and analyzed for proper state sequencing rather than analogic signal distortion or digital switching times. […] I'd already seen the power of pre-publication books. Clare's insightful ASM methodology text, Designing Logic Systems Using State Machines, swept through the HPdesign community […] Stanford's electrical engineering department was not so sanguine, however, canceling Clare's course in 1974, saying that "it is a little bit too unconventional" […] Stanford preferred Quine–McCluskey minimization techniques. Fittingly, Mead's Caltech colleague Ivan Sutherland prepared a Scientific American article (1977) […] about the challenge microelectronics posed to computing theory and practice, noting that since most of a chip's surface was occupied by "wires" (conducting pathways) rather than "components" (transistors), decades of minimization theory in logic design had become irrelevant […] (4 pages)

• Lee, Sunggu (1999). Design of Computers and Other Complex Digital Devices. Pearson. ISBN 0-47129285-0. ISBN 978-0-13040267-7. (418 pages)
• Lee, Sunggu (2000). Computer Design: An Example of Advanced Digital Logic Design. Prentice-Hall. ISBN 0-13-040267-2.
• Lee, Sunggu (2006). Advanced Digital Logic Design: Using VHDL, State Machines, and Synthesis for FPGAs. Thomson. ISBN 0-534-46602-8.
• Brown, Stephen D.; Vranesic, Zvonko. Fundamentals of Digital Logic with VHDL Design (1 ed.).
  • Brown, Stephen D.; Vranesic, Zvonko (2004). Fundamentals of Digital Logic with VHDL Design (2 ed.). McGraw Hill. ISBN 978-0-07-249938-4.
  • Brown, Stephen D.; Vranesic, Zvonko (2009). Fundamentals of Digital Logic with VHDL Design (3 ed.). McGraw Hill. ISBN 978-0-07-352953-0.
• Bjørner, Dines (December 1970) [1970-05-04, 1970-04-07, 1970-02-04]. "Flowchart Machines". BIT Numerical Mathematics. IBM Research Laboratory, San Jose, California. 10 (4): 415–442. doi:10.1007/BF01935563. S2CID 189767592. RJ-685 (No. 13346).
• Lee, Samuel C. (1976). Digital Circuits and Logic Design. Englewood Cliffs, New Jersey, USA: Prentice-Hall.
• Santrakul, Krayim (1983). Multi Values LSI/VLSI Logic Design (PDF) (PhD thesis). The University of Oklahoma. (PDF) from the original on 2016-08-17. Retrieved 2021-02-17.

Further reading

• Schultz, G. W. (March 1969). Written at Central Data Systems, Inc., Sunnyvale, California, USA. "An Algorithm for the Synthesis of Complex Sequential Networks". Computer Design. Vol. 8, no. 3. Concord, Massachusetts, USA: Computer Design Publishing Corporation. pp. 49–55. ISSN 0010-4566. OCLC 828863003. Retrieved 2021-02-22. (7 pages) (NB. This article caused a number of letters to the editor in subsequent issues of the magazine.)
• Schultz, G. W. (1969). Written at Central Data Systems, Inc., Sunnyvale, California, USA. "To the Editor". Letters to the editor. Computer Design. Vol. 8, no. 5–12?. Concord, Massachusetts, USA: Computer Design Publishing Corporation. p. 10. ISSN 0010-4566. OCLC 828863003. p. 10: […] In your April issue you published a letter by R. L. Dineley describing a simple method for treating product-of-sums logical expressions. […] An even simpler method is taught by D. A. Huffman. This method is based on recognizing that the Boolean expression will be zero when any of the factors in the product-of-sums form is zero. Plotting zeroes of factors on a Veitch diagram or Karnaugh map is as easy as locating ones for a sum-of-products expression. […] To illustrate, using Dineley's example (A+BC)(A+C): […] The zeroes resulting from A+BC will be located wherever both A and BC are zero. Therefore we locate on the map the expression A*BC (which is equal to A*B + A*C). Similarly the zeroes of A+C are located and plotted at A*C. With all zeroes located, the rest of the map can be filled with ones. One can be a little more formal and work out algebraically the logical complement of the expression under consideration and then plot zeroes for that resulting expression. In a simple product-of-sums representation, however, the complementary terms can be written by inspection; or the zeroes can be plotted by inspection without writing the complete expression […] "Classical Reduction Involving Infrequently Used Variables" October 11, 1968. University of Santa Clara […] Mr. Osborne's work draws close similarity to that I presented in this article and thus, would certainly be of interest to those readers seeking further information. I understand he has done work to apply the technique of infrequent variables to the design of sequential networks constructed from Read Only Memory. Since he has not yet published anything on this area, if readers would like additional information, they can write Mr. Osborne at: […] Thomas E. Osborne […] Building 1U […] 1501 Page Mill Road […] Palo Alto, California […] Thank you for the opportunity to publish with you. […] G. W. Schultz […] Central Data Systems, Inc. […] Sunnyvale, Calif. (1 page) (NB. Osborne's method was later published by Clare.^[B])
• Langdon, Jr., Glen G. (1974). "Chapter 4. Interrelationships, D. Logic Design and Switching Theory, 3. The Flow Table as a Point of Departure for Design". Written at IBM Corporation, San Jose, California, USA. In Ashenhurst, Robert "Bob" Lovett [at Wikidata] (ed.). Logic Design - A Review of Theory and Practice. ACM Monograph Series (1 ed.). New York, USA: Academic Press, Inc. - A Subsidiary of Harcourt Brace Jovanovich, Publishers. p. 149. ISBN 0-12-436550-7. ISSN 0572-4252. LCCN 73-18988. from the original on 2021-04-17. Retrieved 2021-04-17. p. 149: […] An important contribution to the adaptation of theory to practice was made by Schultz [20]; 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