View source for Algorithmic state machine

{{more footnotes|date=October 2024}}
{{Distinguish|Abstract state machine}}
{{Use dmy dates|date=February 2021|cs1-dates=y}}
{{Use list-defined references|date=January 2022}}

The '''algorithmic state machine''' ('''ASM''') is a method for designing [[finite-state machine]]s (FSMs) originally developed by [[Tom Osborne (engineer)|Thomas E. Osborne]] at the [[University of California, Berkeley]] (UCB) since 1960,<ref name="Osborne_2004"/> introduced to and implemented at [[Hewlett-Packard]] in 1968, formalized and expanded since 1967 and written about by Christopher R. Clare since 1970.<ref name="Clare_1970"/><ref name="Clare_1973"/><ref name="House_2012"/> It is used to represent diagrams of digital [[integrated circuit]]s. 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 machine|Moore]] type outputs are listed inside the box.
[[File:ASM State Name.svg|thumb|right|100px|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.
[[File:ASM Chart State Box.svg|thumb|left|124px|State box]]
'''State Box:''' The output of the state is indicated inside the rectangle box

[[File:ASM Chart Decision Box.svg|thumb|left|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.  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.

[[File:ASM Chart Conditional Output Box.svg|thumb|right|100px|Conditional output box]]
'''Conditional Output Box''': An oval denotes the output signals that are of [[Mealy machine|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 [[register transfer level|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, subtractor, 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 [[register transfer level|RTL]] notation is replaced by signals defined in the datapath.

== See also ==
* [[Flowchart]]
* [[DRAKON|Drakon-chart]]
* [[Mealy machine]]
* [[Moore machine]]
* [[Map-entered variables]] (MEV)

== References ==
{{reflist|refs=
<ref name="Clare_1970">{{cite book |title=Logic Design of Algorithmic State Machines |author-first=Christopher "Chris" R. |author-last=Clare |publisher=[[Hewlett-Packard]] |location=Hewlett-Packard Laboratories, USA |date=February 1971 |orig-date=November 1970 |id={{CHMID|102650285}}}} (110 pages) [https://web.archive.org/web/20210217095629/https://www.computerhistory.org/collections/catalog/102650285] (NB. Several internal revisions existed in 1970 and 1971. This was later published by McGraw-Hill.{{citeref|Clare|1973|A}})</ref>
<ref name="Clare_1973">{{cite book |title=Designing Logic Systems Using State Machines |author-first=Christopher "Chris" R. |author-last=Clare |others=[[Tom Osborne (engineer)|Osborne, Thomas "Tom" E.]] (initial contributions) |location=Electronics Research Laboratory, Hewlett-Packard Laboratories |publisher=[[McGraw-Hill, Inc.]] |date=1973 |orig-date=November 1972 |edition=1 |isbn=0-07011120-0 |s2cid=60509061 |id={{ISBN|978-0-07011120-2}}. ark:/13960/t9383kw8n.<!-- archive.org: designinglogicsystemsusingstatemachines --> 79876543 |sbn=07-011120-0 |url=https://archive.org/details/designinglogicsystemsusingstatemachines |access-date=2021-02-14}} (vii+114+3 pages) [https://archive.org/details/designinglogicsystemsusingstatemachines][https://web.archive.org/web/20230702154806/http://bitsavers.trailing-edge.com/pdf/hp/tutorial/Clare_-_Designing_Logic_Systems_Using_State_Machines_1973.pdf] (NB. This book is based on a 1970 Hewlett-Packard in-house document.{{citeref|Clare|1971|B}})</ref>
<ref name="Osborne_2004">{{cite web |title=Tom Osborne's Story in His Own Words |author-first=Thomas "Tom" E. |author-last=Osborne |author-link=Tom Osborne (engineer) |date=2004-11-11 |orig-date=1994 |work=Steve Leibson's HP9825 page |type=Letter to Barney Oliver |url=http://www.hp9825.com/html/osborne_s_story.html |access-date=2021-02-24 |url-status=live |archive-url=https://web.archive.org/web/20210224114433/http://www.hp9825.com/html/osborne_s_story.html |archive-date=2021-02-24}}</ref>
<ref name="House_2012">{{cite magazine |title=A Paradigm Shift Was Happening All Around Us |author-first=Charles "Chuck" H. |author-last=House |date=2012-12-24 |magazine=IEEE Solid-State Circuits Magazine |issn=1943-0582 |eissn=1943-0590 |publisher=[[Institute of Electrical and Electronics Engineers]] |volume=4 |issue=4 |pages=32–35 |doi=10.1109/MSSC.2012.2215759 |location=Stanford University |url=http://ai.eecs.umich.edu/people/conway/Memoirs/VLSI/Commentaries/A_Paradigm_Shift_Was_Happening_by_Chuck_House.pdf |access-date=2023-06-30 |url-status=live |archive-url=https://web.archive.org/web/20130120035602/http://ai.eecs.umich.edu/people/conway/Memoirs/VLSI/Commentaries/A_Paradigm_Shift_Was_Happening_by_Chuck_House.pdf |archive-date=2013-01-20 |quote-pages=2-3 |quote=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 [[Alexey Lyapunov|Lyapunov]] state-variable mathematics, and derivative techniques pioneered at [[Hewlett Packard|HP]] by Chris Clare and [[David S. Cochran|Dave Cochran]] for the spectacularly successful handheld [[scientific calculator]]s (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 book]]s. 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 technique]]s. Fittingly, [[Carver Mead|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)</ref>
}}

==Further reading==
* {{cite book |title=Design of Computers and Other Complex Digital Devices |author-first=Sunggu |author-last=Lee |date=2000 |orig-date=1999 |edition=1 |publisher=[[Prentice-Hall, Inc.]] |publication-place=Upper Saddle River, New Jersey, USA |isbn=0-13-040267-2 |id={{ISBN|978-0-13040267-7}} |lccn=99-049967}} (xiv+418 pages)
* {{cite book |title=Computer Design: An Example of Advanced Digital Logic Design |author-first=Sunggu |author-last=Lee |edition= |publisher=[[Prentice-Hall]] |date=2000 |isbn=}}
* {{cite book |title=Advanced Digital Logic Design: Using VHDL, State Machines, and Synthesis for FPGAs |author-first=Sunggu |author-last=Lee |publisher=Thomson |date=2006 |isbn=0-534-46602-8}}
* {{cite book |title=Fundamentals of Digital Logic with VHDL Design |author-first1=Stephen D. |author-last1=Brown |author-first2=Zvonko |author-last2=Vranesic |author-link2=Zvonko Vranesic |edition=1 |publisher= |isbn=}}
** {{cite book |title=Fundamentals of Digital Logic with VHDL Design |author-first1=Stephen D. |author-last1=Brown |author-first2=Zvonko |author-last2=Vranesic |author-link2=Zvonko Vranesic |edition=2 |date=2004 |publisher=McGraw Hill |isbn=978-0-07-249938-4}}
** {{cite book |title=Fundamentals of Digital Logic with VHDL Design |author-first1=Stephen D. |author-last1=Brown |author-first2=Zvonko |author-last2=Vranesic |author-link2=Zvonko Vranesic |edition=3 |date=2009 |publisher=McGraw Hill |isbn=978-0-07-352953-0}}
* {{cite journal |title=Flowchart Machines |author-last=Bjørner |author-first=Dines |author-link=Dines Bjørner |journal=[[BIT Numerical Mathematics]] |volume=10 |location=IBM Research Laboratory, San Jose, California |doi=10.1007/BF01935563 |s2cid=189767592 |id=RJ-685 (No. 13346) |date=December 1970 |issue=4 |orig-date=1970-05-04, 1970-04-07, 1970-02-04 |pages=415–442 |url=https://link.springer.com/article/10.1007%2FBF01935563|url-access=subscription }}
* {{cite book |title=Digital Circuits and Logic Design |author-last=Lee |author-first=Samuel C. |publication-place=Englewood Cliffs, New Jersey, USA |publisher=[[Prentice-Hall]] |date=1976}}
* {{cite thesis |degree=PhD |author-last=Santrakul |author-first=Krayim |title=Multi Values LSI/VLSI Logic Design |publisher=The University of Oklahoma |date=1983 |url=https://shareok.org/bitstream/handle/11244/5200/8404568.PDF?sequence=1 |access-date=2021-02-17 |url-status=live |archive-url=https://web.archive.org/web/20160817085356/https://shareok.org/bitstream/handle/11244/5200/8404568.PDF?sequence=1 |archive-date=2016-08-17}}
* {{anchor|Schultz-1969-1}}{{cite magazine |title=An Algorithm for the Synthesis of Complex Sequential Networks |author-first=G. W. |author-last=Schultz |magazine=Computer Design |issn=0010-4566 |oclc=828863003 |publisher=Computer Design Publishing Corporation |publication-place=Concord, Massachusetts, USA |location=Central Data Systems, Inc., Sunnyvale, California, USA |volume=8 |issue=3 |date=March 1969 |pages=49–55 |url=https://books.google.com/books?id=Uy4-AQAAIAAJ&q=%22An+Algorithm+for+the+Synthesis+of+Complex+Sequential+Networks%22 |access-date=2021-02-22}} (7 pages) (NB. This article caused a number of letters to the editor in [[#Schultz-1969-2|subsequent issues]] of the magazine.)
* {{anchor|Schultz-1969-2}}{{cite magazine |title=To the Editor |department=Letters to the editor |author-first=G. W. |author-last=Schultz |magazine=Computer Design |issn=0010-4566 |oclc=828863003 |publisher=Computer Design Publishing Corporation |publication-place=Concord, Massachusetts, USA |location=Central Data Systems, Inc., Sunnyvale, California, USA |volume=8 |issue=5–12?<!-- must be in one of these --> |date=<!-- May or later? --> 1969 |page=10 |url=https://books.google.com/books?id=Uy4-AQAAIAAJ&q=In+your+April+issue+you |quote-page=10 |quote=[…] 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 [[David A. Huffman|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 <span style="text-decoration:overline">A</span>*<span style="text-decoration:overline">BC</span> (which is equal to <span style="text-decoration:overline">A</span>*<span style="text-decoration:overline">B</span> + <span style="text-decoration:overline">A</span>*<span style="text-decoration:overline">C</span>). Similarly the zeroes of A+C are located and plotted at <span style="text-decoration:overline">A</span>*<span style="text-decoration:overline">C</span>. 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. [[Tom Osborne (engineer)|Osborne]]'s work draws close similarity to that I presented in [[#Schultz-1969-1|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 network]]s 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.{{citeref|Clare|1971|B}})
* {{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 [[#Schultz-1969-1|[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 (electronics)|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 ==
* [http://buzbox1.hartford.edu/kmhill/suppnotes/AsmChart/index.html Brief Introduction to ASM Charts]
* [http://www.epyme.uva.es/asm++ ASM++: a modern Algorithmic State Machine methodology for RTL designs]

[[Category:Computer engineering]]
[[Category:Electronic design automation]]