算法状态机

算法状态机（英語：Algorithmic State Machine，縮寫：ASM）方法是设计有限状态机的一种方法。在数字电路设计中，算法状态机图是对时序逻辑状态转移的一种图形描述。在功能上，算法状态机图与状态图类似。^[1]:516

與流程圖的區别

参见：流程圖

在外觀上，算法狀態機圖與計算機程序設計的流程圖使用了相當類似的圖形符號，但是二者具有很大的差異。這種差異是軟體設計和硬體設計的本質差異導致的：硬體數位電路的狀態轉移是根據定時器訊號來實現同步的，即每過一個時脈“步進”一個狀態，因此算法狀態機的狀態轉移包含著時脈的訊號，相鄰狀態的轉移所跨越的時間往往精確單個時間脈衝，而軟體程式設計則一般不包含時間脈衝訊號。^{[2]:81[1]:518[3]}

设计步骤

利用算法状态机方法来设计有限状态机，需要依次完成以下步骤：

1. 根据需要完成的状态跳转功能，创建一组对应的算法，可以使用伪代码来描述电路模块的所需工作流程；
2. 将伪代码转换到算法状态机图（ASM图）；
3. 根据算法状态机图设计数据路径；
4. 在数据路径的基础上完成算法状态机图的其他细节；
5. 为算法状态机的各个状态之间的转移设计控制逻辑单元。

算法状态机图

状态盒

状态决定盒

条件输出盒

算法状态机图（ASM图）由四中基本元素：状态名称、状态盒、状态决定盒和条件输出盒，后三者之间用箭头连接起来。由于摩尔型有限状态机的输出只与当前的状态有关，因此其输出情况被标注在状态盒内部，而米利型有限状态机的状态块中不会标注输出情况。^[2]:82

• 状态名：有限状态机各个状态的名称被标注在一个状态块的左上角，有时还可以标注上该状态所分配到的状态码。
• 状态盒：其外形为一个长方形方块，摩尔型有限状态机的输出由状态盒表示（输出只与当前状态有关^[4]:82）。
• 状态决定盒：其外形为一个菱形块，这个方块会标注上即将被测试的表达式，然后对应不同的测试结果，给出不同的处理路径。算法状态机的状态决定盒一般具有一个输入路径和两个输出路径（分别对应条件满足和条件不满足）。状态决定盒的选择条件表达式是两个输入变量的函数。
• 条件输出盒：其外形为一个圆角方形块，米利型有限状态机的输出由条件输出盒表示（输出与当前状态和输入信号同时有关^[4]:82）。

数据路径

当有限状态机的时序逻辑电路用寄存器传输级硬件描述语言代码描述之后，综合工具会自动生成一系列数据路径部件。过程代码块中被赋值的变量在实际的硬件电路中可以通过硬件寄存器来实现数据的储存。根据不同赋值操作实现的功能，这样的硬件寄存器可以是单纯的寄存器、移位寄存器、计数器或其他含有组合逻辑网络的触发器电路（组合逻辑网络可以是加法器、减法器、数据选择器的各种组合方式）。

参考文献

1. Stephen Brown, Zvonko Vranesic. Fundamentals of Digital Logic with Verilog Design. McGraw-Hill Education. 2002. ISBN 0-07-283878-7.
2. Mark Zwolinski. SystemVerilog数字系统设计（原书名：Digital System Design with SystemVerilog）. 电子工业出版社. ISBN 978-7-121-12456-3.
3. Flowcharts and Algorithmic State Machines (ASM) (PDF). University of Arizona. [2013-07-12]. （原始内容 (PDF)存档于2014-02-11）.
4. David Money Harris, Sarah L. Harris. 数字设计与计算机体系结构. 机械工业出版社. ISBN 978-7-111-25459-1.

相关条目

• 有限状态机（摩尔型、米利型）
• 状态图、流程图

外部链接

• Background of the Algorithmic State Machine (ASM) Notation （页面存档备份，存于互联网档案馆）
• Brief Introduction to ASM Charts （页面存档备份，存于互联网档案馆）
• ASM++: a modern Algorithmic State Machine methodology for RTL designs （页面存档备份，存于互联网档案馆）