算法状态机

维基百科,自由的百科全书
跳转至: 导航搜索

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

与流程图的区别[编辑]

在外观上,算法状态机图与计算机程序设计流程图使用了相当类似的图形符号,但是二者具有很大的差异。这种差异是软件设计和硬件设计的本质差异带来的:硬件数字电路的状态转移是根据定時器訊號来实现同步的,即每过一个时钟周期“步进”一个状态,因此算法状态机的状态转移隐含着时序的信息,相邻状态的转移所跨越的时间往往精确单个时间脉冲,而软件程序设计则一般不包含时间脉冲信息。[2]:81[1]:518[3]

设计步骤[编辑]

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

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

算法状态机图[编辑]

状态盒
状态决定盒
条件输出盒

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

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

数据路径[编辑]

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

参考文献[编辑]

  1. ^ 1.0 1.1 Stephen Brown, Zvonko Vranesic. Fundamentals of Digital Logic with Verilog Design. McGraw-Hill Education. ISBN 0-07-283878-7. 
  2. ^ 2.0 2.1 Mark Zwolinski. SystemVerilog数字系统设计(原书名:Digital System Design with SystemVerilog). 电子工业出版社. ISBN 978-7-121-12456-3. 
  3. ^ Flowcharts and Algorithmic State Machines (ASM). University of Arizona. [2013-07-12]. 
  4. ^ 4.0 4.1 David Money Harris, Sarah L. Harris. 数字设计与计算机体系结构. 机械工业出版社. ISBN 978-7-111-25459-1. 

相关条目[编辑]

外部链接[编辑]