第四章有限状态机要点课件.ppt

1、第四章第四章 有限状态机设计大纲4.1 FSM设计方法4.2 FSM设计实例4.3 基于FPGA的数字系统设计原则和技巧4.4小结习题44.1 FSM设计方法设计方法 有限状态机（FSM，Finite State Mechine），顾名思义，就是一系列数量有限的状态组成的一个循环机制。 本章主要介绍有限状态机的特点和设计规则，给出了使用Verilog HDL硬件描述语言设计有限状态机的一般方法。结合Moore机和Mealy机的设计实例，详细分析了具有可综合风格的有限状态机的设计方法和设计过程。最后给出了数字系统设计的一些基本原则和设计技巧。4.1 FSM设计方法设计方法时序电路如图所示：组合逻

2、辑接收电路输入信号并输出结果，时序逻辑将组合逻辑的输出存储并反馈回组合逻辑，以此来形成电路的当前状态(current state)，当前状态和电路输入信号经过组合逻辑作用形成电路的下一状态（next state）传递给时序电路。图 时序电路基本结构4.1 FSM设计方法设计方法 对于同步时序电路，根据输入端情况可分为两种电路结构：一是没有输入端的同步时序电路，比如计数器、分频器等；另外一种是有输入端控制的电路，称之为有限状态机。有限状态机由组合逻辑电路和若干寄存器组成，根据电路的输入和电路当前状态决定电路的输出。4.1 FSM设计方法设计方法v在有限状态机中，根据电路输出是否与电路输入有关，可

3、以将有限状态机分为Mealy机和Moore机两种。图 Mealy机和Moore机示意图4.1 FSM设计方法设计方法vMealy机属于同步输出状态机，它的输出是当前状态和所有输入信号的函数，其输出会在输入变化后立即发生，不依赖于时钟的同步。vMoore机属于异步输出状态机，它的输出仅为当前状态的函数，与当前输入信号无关。当然，当前状态是和上一时刻的输入信号相关的，当前输入的变化必须等待下一时钟到来使状态发生变化时才能导致输出的变化。v因此，Moore机比Mealy机多等待一个时钟周期才会引起输出的变化。4.1.1使用FSM设计数字系统的优点1）有限状态机能够按照输入信号的控制和预先设定的执行顺

4、序在各个状态间顺畅地切换，具有明显的顺序特征，能够很好地执行顺序逻辑；2）有限状态机设计方法非常规范，设计方案相对固定，并能被多数综合工具支持；3）采用有限状态机设计，易于构成性能良好的同步时序逻辑，有利于消除大规模逻辑电路中常见的竞争冒险现象；4）使用Verilog硬件语言进行有限状态机设计，程序层次分明、结构清晰、易读好懂。模块的修改、优化和移植也非常方便；5）在高速运算与控制方面，和CPU相比，状态机具有明显的速度优势。4.1.2设计FSM的基本步骤设计有限状态机的基本步骤如下：1画出状态转移图；2确定状态编码和编码方式；3给出状态方程和输出方程；4编写Verilog代码。4.1.3 设

5、计FSM的基本原则v遵循以下基本指导原则：1）所设计的状态机要安全，不能进入死循环，不能进入非预知状态。即使是由于某种扰动进入非设计状态，也要能很快恢复到正常的状态循环中来；2）状态机的设计要满足设计的面积和速度的要求；3）状态机的设计要清晰易懂，易维护。4.1.4 FSM的Verilog代码编写方法1. 代码分段方法一段式：整个状态机写到一个always模块里，在该模块中既描述状态转移，又描述状态的输入和输出；二段式：用两个always模块来描述状态机，其中一个always模块采用同步时序描述状态转移，另外一个模块采用组合逻辑判断状态转移条件，描述状态转移规律以及输出；4.1.4 FSM的V

6、erilog代码编写方法三段式：在两个always模块描述方法的基础上，使用三个always模块。一个always模块采用同步时序描述状态转移（使用状态寄存器）；另一个always模块采用组合逻辑判断状态转移条件，描述状态转移规律（次态逻辑）；最后一个always模块描述状态输出，输出可以是组合电路输出，也可以是时序电路输出（输出逻辑）。图 三段式状态机设计结构图4.1.4 FSM的Verilog代码编写方法2编码方式 状态机的编码方式可分为顺序编码（sequential encoding，也称为二进制编码）、格雷码（gray encoding）和独热码(one-hot encoding)。状

7、态顺序编码格雷码独热编码S000000010000S100100101000S201001100100S301101000010S410011000001表4-1 状态机编码方式表 状态机编码方式4.1.4 FSM的Verilog代码编写方法v状态编码的选择原则设计条件和要求编码方式说明要求面积优先要求面积优先顺序编码顺序编码编码最简单，使用触发器最少，剩余非法编码最简单，使用触发器最少，剩余非法状态最少，但增加了状态译码组合逻辑。状态最少，但增加了状态译码组合逻辑。要求速度优先要求速度优先独热编码独热编码虽然使用了较多触发器，但简化了状态译虽然使用了较多触发器，但简化了状态译码组合逻辑，并且

8、在同一时间只有一个状码组合逻辑，并且在同一时间只有一个状态寄存器发生变化，所以是最快的方式，态寄存器发生变化，所以是最快的方式，而且适用大多数而且适用大多数FPGA。当状态数当状态数5时时顺序编码顺序编码一般是默认的编码方式。一般是默认的编码方式。当状态机后有当状态机后有大型输出译码大型输出译码器时器时顺序编码或顺序编码或格雷码格雷码在这种情况下，虽然必须通过译码决定状在这种情况下，虽然必须通过译码决定状态的值，但仍可能比独热码速度快。态的值，但仍可能比独热码速度快。当触发器资源当触发器资源丰富时丰富时独热码独热码最快的方式，由于简化了状态译码逻辑，最快的方式，由于简化了状态译码逻辑，故提高了

9、状态转换速度。故提高了状态转换速度。4.1.4 FSM的Verilog代码编写方法3非法状态处理办法使用Verilog语言对非法状态的处理有以下两种方法：（1），用“default”语句对未提到的状态做统一处理。当状态转移条件不满足，或者状态发生突变时，通过default能保证系统不会陷入死循环。这是对状态机健壮性的重要要求，也即状态机要具备自恢复功能。（2），使用“full case”的编码方式将所有的状态转移变量的所有向量组合情况都在代码中有相应的说明和处理，大多数综合工具都支持Verilog编码状态机的这种完备状态属性。4.1.4 FSM的Verilog代码编写方法4其他设计技巧1）复位

10、与初始化状态 一个具有较强健壮性的状态机应该具备初始化状态。当芯片加电或者复位后，状态机应该能够自动将所有判断条件复位，并进入初始化状态。2）指定默认输出值 对状态机的所有输出变量指定一个默认的输出值，这样做能防止生成不必要的Latches。另外所有的输出最好使用寄存器打一拍，以获得更好的时序环境和稳定状态。3）状态机输出逻辑复用 如果在状态机中有多个状态都会执行某项操作，则在状态机外部定义这个操作的具体内容，然后在状态机中仅仅调用这个操作的最终输出值即可。4.2 FSM设计实例v1001序列信号检测器设计 1001序列信号检测器是用来检测序列信号“1001”的。电路输入为一位串行数据，当检测

11、到比特流“1001”时，电路输出为1，否则输出为0。图 1001序列信号检测器引脚图4.2 FSM设计实例1画出状态转移图图 1001序列检测器状态转移图4.2 FSM设计实例2给出状态转换表、输出方程和状态方程当前状态下一状态Data_in=0 Data_in=1状态名称当前输出Q当前输入D Q2 Q1 Q0D2 D1 D0D2 D1 D0Start_S000000001First_S001010001Second_S010011001Third_S011000100Last_S100000001Error State101/110/111000000表 1001序列检测器状态转换表2210

12、D =Data_in(Q Q Q )1210D =Data_inQ (QQ )02102110D =Data_in(Q Q Q )+Data_in(Q Q )+(Q Q )210DetectedQ Q Q （）4.2 FSM设计实例3代码实现-14.2 FSM设计实例3代码实现-24.2 FSM设计实例图 fsm1功能仿真图4.2 FSM设计实例v交通灯信号控制器设计交通灯信号控制器设计 某十字路口，在A方向和B方向上各有两组信号灯。每组六盏灯，分别是直行绿（G）、直行黄（Y）、直行红（R）、左弯绿、左弯黄和左弯红。四组信号灯共计24盏灯。另外，设置了四组倒计时显示牌，倒计时显示使用2位的八段

13、码实现。A方向上的两组信号灯显示情况一样，同样B方向上的两组信号灯显示情况一样。图 交通信号灯控制示意图图 交通信号灯控制器引脚图4.2 FSM设计实例图 交通信号灯A、B方向时间匹配图4.2 FSM设计实例方向A方向B直行红灯亮直行红灯亮要么直行绿灯亮，要么直行黄灯亮，要么直行绿灯亮，要么直行黄灯亮，要么直行红灯亮要么直行红灯亮&左转绿灯亮左转绿灯亮直行绿灯亮直行绿灯亮直行红灯亮直行红灯亮直行红灯亮直行红灯亮&左转绿灯左转绿灯亮亮 直行红灯亮直行红灯亮直行黄灯亮直行黄灯亮直行红灯亮直行红灯亮同一方向的信号灯亮灭相关性如下所示同一方向的信号灯亮灭相关性如下所示: 1）直行绿灯亮时必有左转红灯亮

14、；）直行绿灯亮时必有左转红灯亮； 2）直行黄灯亮必有左转黄灯亮；）直行黄灯亮必有左转黄灯亮； 3）直行红灯亮则必有左转绿灯亮或者左转红灯亮。）直行红灯亮则必有左转绿灯亮或者左转红灯亮。 交叉方向的信号灯亮灭相关性如表所示：交叉方向的信号灯亮灭相关性如表所示：表表 交叉方向信号灯亮灭相关性对应表交叉方向信号灯亮灭相关性对应表4.2 FSM设计实例 图 交通灯信号控制器A方向状态转移图4.2 FSM设计实例功能仿真图4.2 FSM设计实例图 设计在FPGA中的资源占用情况4.3 基于FPGA的数字系统设计原则和技巧4.3.1基本原则1面积和速度的折衷考虑图 速度换面积之功能模块时分复用图 面积换速

15、度之逻辑复用4.3 基于FPGA的数字系统设计原则和技巧2写代码时考虑硬件结构1）在编写代码进行硬件设计时一定要具备硬件设计思想，勾画出硬件情况，然后使用语言描述出来，这样综合工具才能快速有效地综合出最优结构。2）评价Verilog代码的优劣不在于代码段的整洁简短，而在于代码是否能由综合工具流畅合理地转换成速度快和面积小的硬件形式。4.3 基于FPGA的数字系统设计原则和技巧3最好使用同步设计 电路设计可以是异步设计也可以是同步设计，但是异步设计的时序正确性完全取决于每个逻辑元件和布线的延迟情况，非常容易产生毛刺现象和亚稳态等，且难于处理。而使用由时钟沿驱动的同步设计可以很好地避免毛刺情况，使

16、系统稳定性和可靠性更好。4.3 基于FPGA的数字系统设计原则和技巧4分模块设计方法图 分模块设计示意图4.3 基于FPGA的数字系统设计原则和技巧在分模块设计时，需要注意：（1）顶层模块主要完成对子模块的组织和调用，最好不要有复杂的逻辑功能。一般顶层模块包括有这几部分：输入输出管脚说明、模块调用、时钟与置位/复位、三态缓冲和简单组合逻辑。（2）子模块的划分一定要合理，要综合考虑功能、时序、复杂度等等因素。（3）为增加设计可读性和可维护性，尽量不要在深层次的模块间建立接口，也不要跨层次建立接口。4.3 基于FPGA的数字系统设计原则和技巧4.3.2设计技巧1串并、并串转换技巧2流水线设计技巧图

17、 三步骤流水线设计结构图图 三步骤流水线设计时序图4.3 基于FPGA的数字系统设计原则和技巧3乒乓操作技巧图 乒乓操作原理图图 乒乓操作实现低速模块处理高速数据4.4小结 本章讨论了有限状态机的基本原理和两种不同类型的有限状态机：Moore机和Mealy机。给出了设计FSM的基本步骤和指导原则。通过两个典型实例阐述了FSM设计的一般方法和设计过程。最后给出了基于FPGA的数字系统设计时的一些通用原则和设计技巧。习 题 41.什么是有限状态机？Moore机和Mealy机的各自特点和区别？2.请使用本章介绍的有限状态机设计方法设计同步FIFO和异步FIFO。3.充分体会基于FPGA的数字系统设计的基本原则和设计技巧，掌握一些常用的可综合风格代码写法。