第四章有限状态机要点课件.ppt
第四章,第四章 有限状态机设计,大纲,4.1 FSM设计方法4.2 FSM设计实例4.3 基于FPGA的数字系统设计原则和技巧4.4小结习题4,4.1 FSM设计方法,有限状态机（FSM，Finite State Mechine），顾名思义，就是一系列数量有限的状态组成的一个循环机制。 本章主要介绍有限状态机的特点和设计规则，给出了使用Verilog HDL硬件描述语言设计有限状态机的一般方法。结合Moore机和Mealy机的设计实例，详细分析了具有可综合风格的有限状态机的设计方法和设计过程。最后给出了数字系统设计的一些基本原则和设计技巧。,4.1 FSM设计方法,时序电路如图所示：组合逻辑接收电路输入信号并输出结果，时序逻辑将组合逻辑的输出存储并反馈回组合逻辑，以此来形成电路的当前状态(current state)，当前状态和电路输入信号经过组合逻辑作用形成电路的下一状态（next state）传递给时序电路。,图 时序电路基本结构,4.1 FSM设计方法,对于同步时序电路，根据输入端情况可分为两种电路结构：一是没有输入端的同步时序电路，比如计数器、分频器等；另外一种是有输入端控制的电路，称之为有限状态机。有限状态机由组合逻辑电路和若干寄存器组成，根据电路的输入和电路当前状态决定电路的输出。,4.1 FSM设计方法,在有限状态机中，根据电路输出是否与电路输入有关，可以将有限状态机分为Mealy机和Moore机两种。,图 Mealy机和Moore机示意图,4.1 FSM设计方法,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.4 FSM的Verilog代码编写方法,代码分段方法一段式：整个状态机写到一个always模块里，在该模块中既描述状态转移，又描述状态的输入和输出；二段式：用两个always模块来描述状态机，其中一个always模块采用同步时序描述状态转移，另外一个模块采用组合逻辑判断状态转移条件，描述状态转移规律以及输出；,4.1.4 FSM的Verilog代码编写方法,三段式：在两个always模块描述方法的基础上，使用三个always模块。一个always模块采用同步时序描述状态转移（使用状态寄存器）；另一个always模块采用组合逻辑判断状态转移条件，描述状态转移规律（次态逻辑）；最后一个always模块描述状态输出，输出可以是组合电路输出，也可以是时序电路输出（输出逻辑）。,图 三段式状态机设计结构图,4.1.4 FSM的Verilog代码编写方法,2编码方式 状态机的编码方式可分为顺序编码（sequential encoding，也称为二进制编码）、格雷码（gray encoding）和独热码(one-hot encoding)。,表4-1 状态机编码方式,表 状态机编码方式,4.1.4 FSM的Verilog代码编写方法,状态编码的选择原则,4.1.4 FSM的Verilog代码编写方法,3非法状态处理办法使用Verilog语言对非法状态的处理有以下两种方法：（1），用“default”语句对未提到的状态做统一处理。当状态转移条件不满足，或者状态发生突变时，通过default能保证系统不会陷入死循环。这是对状态机健壮性的重要要求，也即状态机要具备自恢复功能。（2），使用“full case”的编码方式将所有的状态转移变量的所有向量组合情况都在代码中有相应的说明和处理，大多数综合工具都支持Verilog编码状态机的这种完备状态属性。,4.1.4 FSM的Verilog代码编写方法,4其他设计技巧1）复位与初始化状态 一个具有较强健壮性的状态机应该具备初始化状态。当芯片加电或者复位后，状态机应该能够自动将所有判断条件复位，并进入初始化状态。2）指定默认输出值 对状态机的所有输出变量指定一个默认的输出值，这样做能防止生成不必要的Latches。另外所有的输出最好使用寄存器打一拍，以获得更好的时序环境和稳定状态。3）状态机输出逻辑复用 如果在状态机中有多个状态都会执行某项操作，则在状态机外部定义这个操作的具体内容，然后在状态机中仅仅调用这个操作的最终输出值即可。,4.2 FSM设计实例,1001序列信号检测器设计 1001序列信号检测器是用来检测序列信号“1001”的。电路输入为一位串行数据，当检测到比特流“1001”时，电路输出为1，否则输出为0。,图 1001序列信号检测器引脚图,4.2 FSM设计实例,1画出状态转移图,图 1001序列检测器状态转移图,4.2 FSM设计实例,2给出状态转换表、输出方程和状态方程,表 1001序列检测器状态转换表,4.2 FSM设计实例,3代码实现-1,4.2 FSM设计实例,3代码实现-2,4.2 FSM设计实例,图 fsm1功能仿真图,4.2 FSM设计实例,交通灯信号控制器设计 某十字路口，在A方向和B方向上各有两组信号灯。每组六盏灯，分别是直行绿（G）、直行黄（Y）、直行红（R）、左弯绿、左弯黄和左弯红。四组信号灯共计24盏灯。另外，设置了四组倒计时显示牌，倒计时显示使用2位的八段码实现。A方向上的两组信号灯显示情况一样，同样B方向上的两组信号灯显示情况一样。,图 交通信号灯控制示意图,图 交通信号灯控制器引脚图,4.2 FSM设计实例,图 交通信号灯A、B方向时间匹配图,4.2 FSM设计实例,同一方向的信号灯亮灭相关性如下所示: 1）直行绿灯亮时必有左转红灯亮； 2）直行黄灯亮必有左转黄灯亮； 3）直行红灯亮则必有左转绿灯亮或者左转红灯亮。 交叉方向的信号灯亮灭相关性如表所示：,表 交叉方向信号灯亮灭相关性对应表,4.2 FSM设计实例,图 交通灯信号控制器A方向状态转移图,4.2 FSM设计实例,功能仿真图,4.2 FSM设计实例,图 设计在FPGA中的资源占用情况,4.3 基于FPGA的数字系统设计原则和技巧,4.3.1基本原则1面积和速度的折衷考虑,图 速度换面积之功能模块时分复用,图 面积换速度之逻辑复用,4.3 基于FPGA的数字系统设计原则和技巧,2写代码时考虑硬件结构1）在编写代码进行硬件设计时一定要具备硬件设计思想，勾画出硬件情况，然后使用语言描述出来，这样综合工具才能快速有效地综合出最优结构。2）评价Verilog代码的优劣不在于代码段的整洁简短，而在于代码是否能由综合工具流畅合理地转换成速度快和面积小的硬件形式。,4.3 基于FPGA的数字系统设计原则和技巧,3最好使用同步设计 电路设计可以是异步设计也可以是同步设计，但是异步设计的时序正确性完全取决于每个逻辑元件和布线的延迟情况，非常容易产生毛刺现象和亚稳态等，且难于处理。而使用由时钟沿驱动的同步设计可以很好地避免毛刺情况，使系统稳定性和可靠性更好。,4.3 基于FPGA的数字系统设计原则和技巧,4分模块设计方法,图 分模块设计示意图,4.3 基于FPGA的数字系统设计原则和技巧,在分模块设计时，需要注意：（1）顶层模块主要完成对子模块的组织和调用，最好不要有复杂的逻辑功能。一般顶层模块包括有这几部分：输入输出管脚说明、模块调用、时钟与置位/复位、三态缓冲和简单组合逻辑。（2）子模块的划分一定要合理，要综合考虑功能、时序、复杂度等等因素。（3）为增加设计可读性和可维护性，尽量不要在深层次的模块间建立接口，也不要跨层次建立接口。,4.3 基于FPGA的数字系统设计原则和技巧,4.3.2设计技巧1串并、并串转换技巧2流水线设计技巧,图 三步骤流水线设计结构图,图 三步骤流水线设计时序图,4.3 基于FPGA的数字系统设计原则和技巧,3乒乓操作技巧,图 乒乓操作原理图,图 乒乓操作实现低速模块处理高速数据,4.4小结,本章讨论了有限状态机的基本原理和两种不同类型的有限状态机：Moore机和Mealy机。给出了设计FSM的基本步骤和指导原则。通过两个典型实例阐述了FSM设计的一般方法和设计过程。最后给出了基于FPGA的数字系统设计时的一些通用原则和设计技巧。,习 题 4,1.什么是有限状态机？Moore机和Mealy机的各自特点和区别？2.请使用本章介绍的有限状态机设计方法设计同步FIFO和异步FIFO。3.充分体会基于FPGA的数字系统设计的基本原则和设计技巧，掌握一些常用的可综合风格代码写法。,
