面向工程化教育的有限状态机教学设计

2013-08-23王建民贺训军田晓华梅金硕曹一江

电气电子教学学报 2013年2期

王建民，贺训军，田晓华，梅金硕，曹一江

(哈尔滨理工大学电子科学与技术系，黑龙江哈尔滨 150080)

0 引言

从广义上讲，有限状态机FSM(Finite State Machine)是一种思想方法，在软件设计、自动控制等领域都得到了广泛的应用。在数字电路设计领域，有限状态机等同于时序逻辑电路。事实上，大部分数字系统都可以划分为控制单元和数据通道两个组成部分。控制单元通常都是采用有限状态机实现，其作用是接受外部信号以及数据通道的状态信息，并据此产生控制信号，协调整个系统的工作，即有限状态机是数字系统的核心部分［1］。因此，有限状态机设计一直都是“硬件描述语言”等数字设计类课程的重要内容，是学习的重点和难点［2，3］。

笔者在我院开设“硬件描述语言”HDL课程的过程中逐渐发现，当前该课程教学无论是教学内容还是教学理念和方法，都无法适应业界对数字设计人员的能力需求，更无法满足当前工程人才培养的要求。一方面，当前有限状态机教学重点关注HDL描述的代码风格、寄存器传输级 RTL(Register Transfer Level)的设计方法和技巧(流水线设计和资源共享等)、状态赋值和电路优化等内容，设计的起点是状态转换图STG(State Transition Graphics)或者算法状态机 ASM(Algorithm State Machine)。另一方面，以状态转换图作为设计起点的数字电路设计任务，已发展到只需作一些机械性工作:设计人员只需选择合适的代码风格(2段式或多段式)对有限状态机进行描述，编写合适设计约束文件，EDA软件一般就能够给出符合设计要求的电路实现。然而，对于实际设计任务而言，其起点往往不是状态转换图，而是用户提出的各类设计任务。设计人员需要经过一系列的理解、消化和逻辑抽象过程，建立描述该设计任务的有限状态机模型，采用合适的方法对模型进行描述。这些内容的学习和训练对于学生分析解决问题的能力以及创新能力的培养都至关重要。但是，这部分内容在目前教学实践中没有受到足够重视，体现不多。

笔者通过拓展教学内容(将教学内容起点扩展至实际的设计任务)，引入算法状态机图对复杂设计进行描述，采用标准HDL模板对有限状态机进行描述等手段，形成了一套完整的问题驱动的有限状态机教学体系，在实践中取得良好教学效果。

1 问题驱动的有限状态机教学

笔者提出的问题驱动的教学体系是一切教学内容的安排以解决实际问题为目标，明确学生的学习目的，并将该思想贯彻教学内容的始终。该教学体系和学生能力培养的关系，如图1所示。

图1 有限状态机教学体系培养

2 有限状态机和算法状态机图

2.1 有限状态机

在现代数字设计中，有限状态机无处不在。例如，按键扫描过程可以采用有限状态机思想描述。一个典型的按键扫描过程可以分为空闲状态、消抖以及等待按键释放三个状态。进一步，一个按键命令解析过程也可以用有限状态机描述。在A状态下，触发一个按键后切换到了B状态，在B状态如果再触发另一个键后切换到C状态，或者返回到A状态，这是最简单的按键状态机例子。类似地，SRAM读写时序也可以抽象成有限个状态，采用有限状态机进行描述。

事实上，有限状态机的本质就是对具有逻辑顺序或时序规律事件的一种描述方法。状态机由各个状态组成，各个状态由状态转移连接在一起。状态是执行某项活动或者等待某个事件的条件。转移是两个状态之间的关系，由某个事件触发，然后执行特定的操作或评估并导致特定的状态结束。此外，状态转移还必须具有某种时序规律。

时序逻辑电路就是有限状态机(在不至于发生混淆的情况，本文将时序逻辑电路直接称为有限状态机)，图2所示为典型的时序逻辑电路结构。电路的每一个状态包含三个要素:当前状态、次态和输出逻辑。次态逻辑是当前状态和输入的函数，是组合逻辑电路。状态寄存器是由多个D触发器组成的寄存器组，用于记录时序逻辑电路的当前状态，寄存器组中的所有D触发器使用相同的时钟信号(同步时序逻辑)。输出逻辑也是组合逻辑电路，用来决定电路的输出。电路的输出可能只有电路的状态决定，这种类型的输出称为摩尔类型的输出。如果电路的输出由电路的输入和电路的状态共同决定则称为米利型的输出。

除了上述三个要素外，时序规律也是有限状态机必须要考虑的要素，有限状态机的状态转移必须按照一定的时序规律进行。例如，时序逻辑电路的状态转移就是在系统时钟的统一控制下完成的，每个时钟周期时序电路都会切换一个状态。

图2 时序逻辑电路典型结构

2.2 算法状态机图

与状态转换图STG一样，算法状态机图ASM也是一种有限状态机的图形化的表示方法，对于相对复杂的设计，算法状态机图比状态转换图更具优势，因而在工程实践中应用广泛［4，5］。在国外，“硬件描述语言”课程中较多采用算法状态机图作为基本工具，而在国内教学中，算法状态机图还未得到足够的重视。本节介绍算法状态机图的画法和应用。

算法状态机图类似于软件设计中的流程图，但两者存在本质区别。ASM图由若干ASM块组成。每个ASM块包含一个状态框以及一个可选的条件判断框和条件输出框，典型的ASM块如图3所示。

图3 典型算法状态机ASM块

状态框表示有限状态机FSM的状态，用矩形表示。摩尔类型的输出直接列于状态框内部，状态名一般标注在状态框的左上角。通常情况下，ASM图中只标出不等于默认值的输出信号取值，如果在某个状态下没有明确指明输出的取值，表示在该状态下输出信号取默认值。

条件判断框用菱形表示，其包含关于输入信号的逻辑表达式(状态转换条件)，逻辑表达式取值确定FSM离开该ASM块的路径。条件判断框可以包含复杂程度不同的状态转换条件，根据状态转换表达式取值不同，FSM按照true路径或者false路径切换至相应的次态(另一个ASM块)。

条件输出框用圆角矩形表示，其内部只列出非默认取值的输出信号。需要强调的是，条件输出框只能放在条件判断框之后，表示当条件判断框中的逻辑表达式为真时，相应的输出信号才会有效。因为条件判断框的逻辑表达式是关于输入信号的，说明输出依赖于当前状态和输入信号。通常也只有在输出信号置位时，才会将其列入条件输出框。如果没有条件输出框，表示输出信号取默认值。

算法状态机图由多个ASM块组成，每个ASM块代表有限状态机的一个状态，根据条件判断结果，在时钟控制下，实现在不同状态之间的转移。图4给出一个典型的算法状态机图，为了对比同时给出其对应的状态转换图。

图4 算法状态机图及其对应的状态转换图

3 有限状态机的结构和描述方式

3.1 模板式的HDL描述

有限状态机的HDL代码描述风格至关重要，良好的代码风格有助于提高代码的可读性和可维护性，更有助于综合软件给出符合设计意图的综合结果。相反，不良的代码风格可能导致综合软件给出复杂的甚至是不正确的综合结果。

因此，笔者建议在教学实践中，采用模板式的代码描述方式对表示成状态转换图或算法状态机图的有限状态机进行描述，具体的描述方式如图5所示。

图5 有限状态机的模板式Verilog HDL描述

此外，以Verilog HDL为例，如果采用VHDL也有类似的描述方式。模板式HDL描述方式的关键是将组合逻辑和时序逻辑分开，并分别采用always块对次态逻辑、输出逻辑和状态寄存器进行描述。因此，这种描述方式也称为多段式描述方式［4，5］。

除了图5给出的多段式描述方式外，2段式也是常用的描述方法。这种描述方法与多段式类似，同样需要将状态寄存器和组合逻辑分开描述，其区别在于多段式描述将次态逻辑和输出逻辑独立采用always块实现，2段式描述将次态逻辑、输出逻辑统一采用一个always块描述，对于某些不是特别复杂的设计，2段式描述能有效减少代码量。教学中，我们应尽量避免采用1段式描述。

3.2 状态赋值和未用状态的处理

状态赋值也称为状态编码，状态编码类型对有限状态机有显著的影响，状态编码方案选取得当，有限状态机状态译码电路会很简单;反之，可能会产生过于复杂的译码逻辑，导致消耗过多的逻辑资源。目前，常用的状态编码方式有二进制编码、格雷编码和独热编码(one-hot coding)等。

随着综合理论和技术的进步，采用HDL描述有限状态机时，笔者建议直接使用符号常量。综合软件会自动根据设计约束选择合适的状态赋值方案(一般会从前面介绍的几种状态赋值方案中选择1种)，以得到满足设计约束的最优电路。

采用符号常量表示状态时，通常会存在某些状态未被使用的情况。对于未被使用的状态一般会有两种处理方式:①将未用状态处理成“错误状态”，一旦进入“错误状态”，状态机采用统一的错误处理机制进行处理。②将未用状态处理为“don't care”，认为有限状态机不会进入这些状态，按照面积或速度最优原则进行优化。然而，一旦由于某种干扰或者其它情况，有限状态机进入了这些未用状态，就会导致整个系统无法正常工作。

3.3 “面积”和“速度”的折衷

“面积”和“速度”的折衷与平衡是数字系统设计的永恒话题，在数字电路设计的各个层次存在不同的方法和策略对二者进行平衡。“硬件描述语言”课程的教学中，主要强调在电路结构层次如何影响电路“面积”和“速度”。核心的教学内容包括:流水线设计思想(通过提高或者降低电路的并行性改进电路的“面积”或者“速度”优势)、复位电路设计等内容［4］。