第四章有限状态机

第四章第四章有限状态机设计大纲4.1FSM设计方法4.2FSM设计实例4.3基于FPGA的数字系统设计原则和技巧4.4小结习题44.1FSM设计方法有限状态机（FSM，FiniteStateMechine），顾名思义，就是一系列数量有限的状态组成的一个循环机制。本章主要介绍有限状态机的特点和设计规则，给出了使用VerilogHDL硬件描述语言设计有限状态机的一般方法。结合Moore机和Mealy机的设计实例，详细分析了具有可综合风格的有限状态机的设计方法和设计过程。最后给出了数字系统设计的一些基本原则和设计技巧。4.1FSM设计方法时序电路如图所示：组合逻辑接收电路输入信号并输出结果，时序逻辑将组合逻辑的输出存储并反馈回组合逻辑，以此来形成电路的当前状态(currentstate)，当前状态和电路输入信号经过组合逻辑作用形成电路的下一状态（nextstate）传递给时序电路。图时序电路基本结构组合逻辑时序逻辑（寄存器）输入输出当前状态下一状态4.1FSM设计方法对于同步时序电路，根据输入端情况可分为两种电路结构：一是没有输入端的同步时序电路，比如计数器、分频器等；另外一种是有输入端控制的电路，称之为有限状态机。有限状态机由组合逻辑电路和若干寄存器组成，根据电路的输入和电路当前状态决定电路的输出。4.1FSM设计方法在有限状态机中，根据电路输出是否与电路输入有关，可以将有限状态机分为Mealy机和Moore机两种。组合逻辑状态寄存器组合逻辑输入输出时钟Moore机组合逻辑状态寄存器组合逻辑输入输出时钟Mealy机图Mealy机和Moore机示意图4.1FSM设计方法Mealy机属于同步输出状态机，它的输出是当前状态和所有输入信号的函数，其输出会在输入变化后立即发生，不依赖于时钟的同步。Moore机属于异步输出状态机，它的输出仅为当前状态的函数，与当前输入信号无关。当然，当前状态是和上一时刻的输入信号相关的，当前输入的变化必须等待下一时钟到来使状态发生变化时才能导致输出的变化。因此，Moore机比Mealy机多等待一个时钟周期才会引起输出的变化。4.1.1使用FSM设计数字系统的优点1）有限状态机能够按照输入信号的控制和预先设定的执行顺序在各个状态间顺畅地切换，具有明显的顺序特征，能够很好地执行顺序逻辑；2）有限状态机设计方法非常规范，设计方案相对固定，并能被多数综合工具支持；3）采用有限状态机设计，易于构成性能良好的同步时序逻辑，有利于消除大规模逻辑电路中常见的竞争冒险现象；4）使用Verilog硬件语言进行有限状态机设计，程序层次分明、结构清晰、易读好懂。模块的修改、优化和移植也非常方便；5）在高速运算与控制方面，和CPU相比，状态机具有明显的速度优势。4.1.2设计FSM的基本步骤设计有限状态机的基本步骤如下：1．画出状态转移图；2．确定状态编码和编码方式；3．给出状态方程和输出方程；4．编写Verilog代码。4.1.3设计FSM的基本原则遵循以下基本指导原则：1）所设计的状态机要安全，不能进入死循环，不能进入非预知状态。即使是由于某种扰动进入非设计状态，也要能很快恢复到正常的状态循环中来；2）状态机的设计要满足设计的面积和速度的要求；3）状态机的设计要清晰易懂，易维护。4.1.4FSM的Verilog代码编写方法1.代码分段方法一段式：整个状态机写到一个always模块里，在该模块中既描述状态转移，又描述状态的输入和输出；二段式：用两个always模块来描述状态机，其中一个always模块采用同步时序描述状态转移，另外一个模块采用组合逻辑判断状态转移条件，描述状态转移规律以及输出；4.1.4FSM的Verilog代码编写方法三段式：在两个always模块描述方法的基础上，使用三个always模块。一个always模块采用同步时序描述状态转移（使用状态寄存器）；另一个always模块采用组合逻辑判断状态转移条件，描述状态转移规律（次态逻辑）；最后一个always模块描述状态输出，输出可以是组合电路输出，也可以是时序电路输出（输出逻辑）。输入现态&使能输出逻辑状态寄存器次态次态逻辑输出现态反馈图三段式状态机设计结构图4.1.4FSM的Verilog代码编写方法2．编码方式状态机的编码方式可分为顺序编码（sequentialencoding，也称为二进制编码）、格雷码（grayencoding）和独热码(one-hotencoding)。状态顺序编码格雷码独热编码S000000010000S100100101000S201001100100S301101000010S410011000001表4-1状态机编码方式表状态机编码方式4.1.4FSM的Verilog代码编写方法状态编码的选择原则设计条件和要求编码方式说明要求面积优先顺序编码编码最简单，使用触发器最少，剩余非法状态最少，但增加了状态译码组合逻辑。要求速度优先独热编码虽然使用了较多触发器，但简化了状态译码组合逻辑，并且在同一时间只有一个状态寄存器发生变化，所以是最快的方式，而且适用大多数FPGA。当状态数5时顺序编码一般是默认的编码方式。当状态机后有大型输出译码器时顺序编码或格雷码在这种情况下，虽然必须通过译码决定状态的值，但仍可能比独热码速度快。当触发器资源丰富时独热码最快的方式，由于简化了状态译码逻辑，故提高了状态转换速度。4.1.4FSM的Verilog代码编写方法3．非法状态处理办法使用Verilog语言对非法状态的处理有以下两种方法：（1），用“default”语句对未提到的状态做统一处理。当状态转移条件不满足，或者状态发生突变时，通过default能保证系统不会陷入死循环。这是对状态机健壮性的重要要求，也即状态机要具备自恢复功能。（2），使用“fullcase”的编码方式将所有的状态转移变量的所有向量组合情况都在代码中有相应的说明和处理，大多数综合工具都支持Verilog编码状态机的这种完备状态属性。4.1.4FSM的Verilog代码编写方法4．其他设计技巧1）复位与初始化状态一个具有较强健壮性的状态机应该具备初始化状态。当芯片加电或者复位后，状态机应该能够自动将所有判断条件复位，并进入初始化状态。2）指定默认输出值对状态机的所有输出变量指定一个默认的输出值，这样做能防止生成不必要的Latches。另外所有的输出最好使用寄存器打一拍，以获得更好的时序环境和稳定状态。3）状态机输出逻辑复用如果在状态机中有多个状态都会执行某项操作，则在状态机外部定义这个操作的具体内容，然后在状态机中仅仅调用这个操作的最终输出值即可。4.2FSM设计实例1001序列信号检测器设计1001序列信号检测器是用来检测序列信号“1001”的。电路输入为一位串行数据，当检测到比特流“1001”时，电路输出为1，否则输出为0。1001序列检测器Data_inDetectedClockReset图1001序列信号检测器引脚图4.2FSM设计实例1．画出状态转移图起始状态第一状态第二状态第三状态最后状态000010110010101图1001序列检测器状态转移图4.2FSM设计实例2．给出状态转换表、输出方程和状态方程当前状态下一状态Data_in=0Data_in=1状态名称当前输出Q当前输入DQ2Q1Q0D2D1D0D2D1D0Start_S000000001First_S001010001Second_S010011001Third_S011000100Last_S100000001ErrorState101/110/111000000表1001序列检测器状态转换表2210D=Data_in(QQQ)1210D=Data_inQ(QQ)02102110D=Data_in(QQQ)+Data_in((QQ)+(QQ))210DetectedQQQ（）4.2FSM设计实例3．代码实现-14.2FSM设计实例3．代码实现-24.2FSM设计实例图fsm1功能仿真图4.2FSM设计实例交通灯信号控制器设计某十字路口，在A方向和B方向上各有两组信号灯。每组六盏灯，分别是直行绿（G）、直行黄（Y）、直行红（R）、左弯绿、左弯黄和左弯红。四组信号灯共计24盏灯。另外，设置了四组倒计时显示牌，倒计时显示使用2位的八段码实现。A方向上的两组信号灯显示情况一样，同样B方向上的两组信号灯显示情况一样。RGYRGYRGYRGYLAMPB1LAMPA1LAMPB2LAMPA2图交通信号灯控制示意图交通灯控制逻辑ClockResetACOUNT1[7:0]LAMPA1[5:0]ACOUNT2[7:0]LAMPA2[5:0]BCOUNT1[7:0]LAMPB1[5:0]BCOUNT2[7:0]LAMPB2[5:0]图交通信号灯控制器引脚图4.2FSM设计实例T(s)040456065120006595100115120T(s)A向T(s)B向直行等待左转等待禁行禁行直行等待左转等待图交通信号灯A、B方向时间匹配图4.2FSM设计实例方向A方向B直行红灯亮要么直行绿灯亮，要么直行黄灯亮，要么直行红灯亮&左转绿灯亮直行绿灯亮直行红灯亮直行红灯亮&左转绿灯亮直行红灯亮直行黄灯亮直行红灯亮同一方向的信号灯亮灭相关性如下所示:1）直行绿灯亮时必有左转红灯亮；2）直行黄灯亮必有左转黄灯亮；3）直行红灯亮则必有左转绿灯亮或者左转红灯亮。交叉方向的信号灯亮灭相关性如表所示：表交叉方向信号灯亮灭相关性对应表4.2FSM设计实例图交通灯信号控制器A方向状态转移图Reset=1State_A=000LAMP_A=001001temp_A=0State_A=001LAMP_A=010010State_A=010LAMP_A=100100State_A=011LAMP_A=010010State_A=100LAMP_A=100001temp_A=0temp_A=0temp_A=0temp_A=0temp_A=1temp_A=1temp_A=1temp_A=1temp_A=14.2FSM设计实例功能仿真图4.2FSM设计实例图设计在FPGA中的资源占用情况4.3基于FPGA的数字系统设计原则和技巧4.3.1基本原则1．面积和速度的折衷考虑功能模块-1功能模块-2功能模块（两倍时钟频率）面积大，频率低面积小，频率高DFFBufferDFFDFF面积小，延时大面积大，延时小图速度换面积之功能模块时分复用图面积换速度之逻辑复用4.3基于FPGA的数字系统设计原则和技巧2．写代码时考虑硬件结构1）在编写代码进行硬件设计时一定要具备硬件设计思想，勾画出硬件情况，然后使用语言描述出来，这样综合工具才能快速有效地综合出最优结构。2）评价Verilog代码的优劣不在于代码段的整洁简短，而在于代码是否能由综合工具流畅合理地转换成速度快和面积小的硬件形式。4.3基于FPGA的数字系统设计原则和技巧3．最好使用同步设计电路设计可以是异步设计也可以是同步设计，但是异步设计的时序正确性完全取决于每个逻辑元件和布线的延迟情况，非常容易产生毛刺现象和亚稳态等，且难于处理。而使用由时钟沿驱动的同步设计可以很好地避免毛刺情况，使系统稳定性和可靠性更好。4.3基于FPGA的数字系统设计原则和技巧4．分模块设计方法TopModuleModuleBModuleAModuleCA1A2B1B2C1C2C3图分模块设计示意图4.3基于FPGA的数字系统设计原则和技巧在分模块设计时，需要注意：（1）顶层模块主要完成对子模块的组织和调用，最好不要有复杂的逻辑功能。一般顶层模块包括有这几部分：输入输出管脚说明、模块调用、时钟与置位/复位、三态缓冲和简单组合逻辑。（2）子模块的划分一定要合理，要综合考虑功能、时序、复杂度等等因素。（3）为增加设计可读性和可维护性，尽量不要在深层次的模块间建立接口，也不要跨层次建立接口。4.3基于FPGA的数字系统设计原则和技巧4.3.2设计技巧1．串并、并串转换技巧2．流水线设计技巧Step1Step2Step3图