[科普中国]-算法状态机图

简介

ASM图是一种用来描述数字系统算法的流程图，从结构和形式上看，类似于传统的计算机流程图。ASM图在寄存器传输级(RTL)描述系统的状态变化，侧重于描述寄存器中信息的传输和处理，包括复位、预置、计数和移位等功能。对于一个数字系统，设计者应首先在RTL画出它的ASM图，正如编程人员在编写软件时需要画出算法流程图一样。

数字系统的控制和数据处理两部分都可以在ASM图中表示出来。画ASM图时，设计者只要考虑RTL信号的传输和处理，对具体底层硬件可以不加理会。对状态的设定可以“宁多勿少”，多余的状态可以借助EDA软件消除。另外，把信号都看成寄存器型信号，无须细分信号是组合信号还是时序信号。

ASM图表面上与通常的软件流程图非常相似。但ASM图表示事件的精确时间间隔序列I而一般软件流程图只表事件序列，没有时间概念，这是两者的根本差别。

ASM图的基本元素组成ASM图的基本元素是状态框、判断框、条件输出框和输入、输出路径。输入、输出路径就是连接各种方框的有向箭头；状态框表示ASM的一个状态，判断框表示状态分支，条件输出框表示ASM图的条件输出，它总是位于满足状态分支条件的路径上。它们的形状和操作如图1所示。

状态框数字系统控制序列中的状态用一个矩形框表示，称为状态框。框内标出在此状态下实现的寄存器传输操作和输出，状态的名称置于状态框左上角，分配给状态的二进制代码位于状态框的右上角，图2为状态框实例。状态框的名称是S1，其代码是010，框内规定的寄存器的操作是BA，输出信号是Z。图2中的箭头表示系统状态的流向，在时钟脉冲触发沿的触发下，系统进入状态S1，在下一个时钟脉冲触发沿的触发下，系统离开状态S1，因此一个状态框占用一个时钟脉冲周期。由此看出，ASM图内蕴涵着事件序列特性。

控制器的控制命令由控制算法决定，为表示这些输出命令，将其放入相应状态框内，在该状态框内的动作都应在相应该状态时钟结束时或结束以前完成。在该状态期间可以根据需要定义其它输出信号。

判断框当控制算法存在分支时，次态不仅决定于现态，还与现态时的外输入有关，因此需要有表示分支的方法。表示分支的符号以菱形或矩形加菱形边框表示。判断框表示状态变量对控制器工作的影响，如图1所示。它有一个入口和多个出口，框内填判断条件，如果条件是真，选择一个出口，若条件是假，选择另一个出口。判断框不占用时间。

条件输出框控制器某些状态只有在一定条件下才能输出。为与一般的状态输出相区别，用椭圆框表示条件输出。条件输出框如图3(a)所示，条件框的入口必定与判断框的输出相连。列在条件框内的寄存器操作或输出是在给定的状态下，满足判断条件才发生的。在图3(b)的例子中，当系统处于状态S1时，若条件X=1，则寄存器R被清零，否则R保持不变；不论X为何值系统的下一个状态都是S2。

ASM图示例下面通过一个例子说明ASM图的构造方法。假设十字路口交通灯控制器的技术指标为：红灯显示45s，黄灯显示5s，绿灯显示40s。A、B两路的显示数字分别用寄存器信号LEDA、LEDB表示，A路和B路的指示灯用寄存器信号Light表示，Light包括RA(A红)、YA(A黄)、GA(A绿)和RB(B红)、YB(B黄)和GB(B绿)。采用ASM图描述该控制系统的框图如图4所示。

ASM图一共设置了8个状态框S0～S7，按照自然二进制编码方式编码，当然也可以采用1位热位编码(One-hot)。S0、S2、S4和S6状态框完成初始值的预置，其余状态框都是执行减1计数功能，这是按照交通灯时间显示要求来设定的。指示灯寄存器信号Light预置的数值是十进制数，转换为二进制数就可以发现，S0的预置数33对应于A路红灯、B路绿灯；S2预置的数值34对应A路红灯、B路黄灯；S4预置的12对应A路绿灯、B路红灯；S6预置的20对应A路黄灯、B路红灯。1