有限状态机FSM

1、第八章第八章 有限状态机有限状态机 （FSM-Finite State Machine） n学习内容：学习内容： q什么是有限状态机什么是有限状态机 q有限状态机的设计规则有限状态机的设计规则 q基于基于verilog状态机设计的三种方式状态机设计的三种方式 q有限状态机的小结有限状态机的小结 状态机的生活实例状态机的生活实例 n 一个学生，为了不耽误第一节课，每个工作日早上一个学生，为了不耽误第一节课，每个工作日早上 六点起床。可是到了周末，可能想睡觉，不用早起。六点起床。可是到了周末，可能想睡觉，不用早起。 当你还在睡觉，闹钟却在六点响了，并且把你吵醒了。当你还在睡觉，闹钟却在六点响了，并

2、且把你吵醒了。 如果是工作日，关掉闹钟，起床，为新的一天做准备。如果是工作日，关掉闹钟，起床，为新的一天做准备。 然而，若是周末，你忘记了调整闹钟，则到时候你可然而，若是周末，你忘记了调整闹钟，则到时候你可 能会生气的关掉闹钟（丢掉房子的一边，仍到厕所里能会生气的关掉闹钟（丢掉房子的一边，仍到厕所里 冲走，或者把它报废），然后继续睡觉。冲走，或者把它报废），然后继续睡觉。 n 我们可以用图我们可以用图1所示的有限状态机来模拟这一连串所示的有限状态机来模拟这一连串 的事件。的事件。 简化的状态机的例子（续）简化的状态机的例子（续） 实际上，这个状态机就是你自己。你可能处于下列三个状态实际上，这个

3、状态机就是你自己。你可能处于下列三个状态 之一：睡眠中，醒了但还在床上，或起床。你接受两个输入：之一：睡眠中，醒了但还在床上，或起床。你接受两个输入： 唤你醒来的闹钟和当天是否是工作日，后者决定你对闹钟的反唤你醒来的闹钟和当天是否是工作日，后者决定你对闹钟的反 映态度。在这个例子中，唯一的输出就是关掉闹钟。映态度。在这个例子中，唯一的输出就是关掉闹钟。 状态状态 状态机状态机 闹钟闹钟关掉闹钟关掉闹钟 图图1 1状态机模型：（状态机模型：（b b）闹钟系统）闹钟系统 工作日工作日 为什么要使用状态机为什么要使用状态机 有限状态机克服了纯硬件数字系统顺序方式控制不灵活的有限状态机克服了纯硬件数字

4、系统顺序方式控制不灵活的 缺点缺点 状态机的结构模式相对简单，层次分明、易读易懂易排错状态机的结构模式相对简单，层次分明、易读易懂易排错 状态机容易构成性能良好的同步时序逻辑模块状态机容易构成性能良好的同步时序逻辑模块 状态机的状态机的verilog表述丰富多样，综合器易于优化表述丰富多样，综合器易于优化 利用同步时序和全局时钟线可实现高速有限状态机利用同步时序和全局时钟线可实现高速有限状态机 可靠性高，非法状态易控制可靠性高，非法状态易控制 5 理论上，任何时序电路都可以建立理论上，任何时序电路都可以建立FSM模型，但并不模型，但并不 总是一种高效的方法。总是一种高效的方法。 如果一味地追求

5、使用如果一味地追求使用FSM来设计时序电路，可能会导来设计时序电路，可能会导 致代码冗长和容易出错致代码冗长和容易出错。 例如，任务简单的寄存器就不必使用例如，任务简单的寄存器就不必使用FSM方式实现。方式实现。 又例如，又例如，虽然任务与顺序很明确，但任务数目太多或虽然任务与顺序很明确，但任务数目太多或 者性能要求较高时，者性能要求较高时，也不宜用也不宜用FSM方式实现。方式实现。 FSM是为时序电路设计而创建的特殊模型技术，是为时序电路设计而创建的特殊模型技术，在针对在针对 任务顺序非常明确任务顺序非常明确的电路（如交通灯控制器）是非常实用的电路（如交通灯控制器）是非常实用。 RTL级FS

6、M的判断标准 n(1)FSM要安全、稳定性高；要安全、稳定性高； n(2)FSM速度要快，满足设计的频率要求；速度要快，满足设计的频率要求； n(3)FSM面积要小，满足设计的面积要求；面积要小，满足设计的面积要求； n(4)FSM设计要清晰、易维护；设计要清晰、易维护； 有限状态机（有限状态机（FSM） 状态机包含的要素可归纳为状态机包含的要素可归纳为4个：现态、条件、动作、个：现态、条件、动作、 次态。次态。 “现态现态”和和“条件条件”是因，是因，“动作动作”和和“次态次态”是果。是果。 现态：现态：是指当前所处的状态。是指当前所处的状态。 条件：条件：又称为又称为“事件事件”。 动作：

7、动作：条件满足后执行的动作。条件满足后执行的动作。 次态：次态：条件满足后要迁往的新状态。条件满足后要迁往的新状态。“次态次态”是相对于是相对于 “现态现态”而言而言 有限状态机（有限状态机（FSM） 感冒感冒 健康健康 康复中康复中 休息 淋雨 吃药 有限状态机（有限状态机（FSM） 设计这样一个电路（特点）：设计这样一个电路（特点）： 1）能记住自己目前所处的状态）能记住自己目前所处的状态 ； 2）状态的变化只可能在同一个时钟的跳变沿时刻发生，而不）状态的变化只可能在同一个时钟的跳变沿时刻发生，而不 可能发生在任意时刻；可能发生在任意时刻； 3）在时钟跳变沿时刻，如输入条件满足，则进入下一

8、状态，）在时钟跳变沿时刻，如输入条件满足，则进入下一状态， 并记住自己目前所处的状态，否则仍保留原来的状态；并记住自己目前所处的状态，否则仍保留原来的状态； 4）在进入不同的状态时刻，对系统的开关阵列做开启或关闭）在进入不同的状态时刻，对系统的开关阵列做开启或关闭 的操作。的操作。 有限状态机（有限状态机（FSM） n状态机一般包括组合逻辑和寄存器逻辑两部分。寄存器用状态机一般包括组合逻辑和寄存器逻辑两部分。寄存器用 于存储状态，组合电路用于状态译码和产生输出信号。于存储状态，组合电路用于状态译码和产生输出信号。 n根据输出信号产生方法的不同，状态机可分为根据输出信号产生方法的不同，状态机可分

9、为米里米里(Mealy) 机机和和摩尔摩尔(Moore) 机机。 n米里米里(Mealy) 机的机的输出输出是当前状态和输入信号的函数。是当前状态和输入信号的函数。 n摩尔摩尔(Moore) 机的机的输出输出仅是当前状态的函数。仅是当前状态的函数。 n在硬件设计时在硬件设计时,需自行决定采用哪种状态机。需自行决定采用哪种状态机。 Mealy 状态机状态机 下一状态下一状态 的逻辑的逻辑 F F 输出逻辑输出逻辑 G G 状态状态 寄存器寄存器 clk 输入 下一个状态下一个状态 = F(当前状态，输入信号当前状态，输入信号)； 输出信号输出信号 = G(当前状态，输入信号当前状态，输入信号)；

10、 Moor 状态机状态机 下一个状态下一个状态 = F(当前状态，输入信号当前状态，输入信号) 输出信号输出信号 = G(当前状态当前状态)； 下一状下一状 态的逻态的逻 辑辑 F F 输出逻辑输出逻辑 G G 状态状态 寄存器寄存器 X X Q0 Q0 Q1 Q1 X MAX Q0 Q1 CLK D0 D1 当前状态当前状态 激励激励 输出输出 输入输入 时钟信号时钟信号 下一状态逻辑下一状态逻辑 产生激励信号产生激励信号状态存储器状态存储器 输出逻辑输出逻辑 例：时钟同步状态机（D触发器） X X Q0 Q0 Q1 Q1 X MAX Q0 Q1 CLK D0 D1 （1）由电路得到激励方程

11、）由电路得到激励方程 D0 = Q0X + Q0X D1 = Q1X + Q1Q0X + Q1Q0X （2）由电路得到输出方程）由电路得到输出方程 MAX = Q1Q0X （3）由激励方程和触发器特征方程）由激励方程和触发器特征方程 得到转移方程（状态方程）得到转移方程（状态方程） D触发器特征方程：触发器特征方程：Qn+1 = D Q0n+1 = Q0X + Q0X Q1n+1= Q1X + Q1Q0X + Q1Q0X （4）由转移方程和输出方程得到状态）由转移方程和输出方程得到状态/输出表输出表 0 0 1 1 0 1 1 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 1

12、 状态转换表状态转换表 X Q1 Q0 Q1* Q0* MAX 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Q0n+1 = Q0X + Q0X Q1n+1 = Q1X + Q1Q0X + Q1Q0X MAX = Q1Q0X S 0 0 0 1 1 0 1 1 X 0 1 00/0 01/0 10/0 11/0 01/0 10/0 11/0 00/1 Q1*Q0*/MAXQ1Q0 （5）画状态图）画状态图 00 0/0 01 1/0 1/1 0/0 0/0 0/0 11 1/0 10 1/0 逻辑功能描述：具有使能端逻辑功能描述：具有使能端X的

13、的2位二进制加法计数器位二进制加法计数器 电路输出与输入直接相关电路输出与输入直接相关 Mealy机机 S 0 0 0 1 1 0 1 1 X 0 1 00/0 01/0 10/0 11/0 01/0 10/0 11/0 00/1 Q1*Q0*/MAXQ1Q0 X （6）画时序图）画时序图 EN EN Q0 Q0 Q1 Q1 X MAX Q0 Q1 CLK D0 D1 Mealy机机Moore机机 MAXS MAXS =Q1Q0 状态机的定时图状态机的定时图 例：串行数据例：串行数据1101序列检测器设计序列检测器设计 （1） 根据题目要求画出原始状态转换图 设：S0 为没有检测到1的状态，

14、S1为检测到一个1的状态， S2为检测到11的状态， S3为检测到110的状态， S4为检 测到1101的状态。所状态图可表示为图1所示： S0 1/0 0/0 1/0 1/0 1/1 0/0 0/0 S1 S3S4S2 0/0 1/0 0/0 图1 原始状态图 状态机设计举例状态机设计举例 （2）对原始状态图进行状态化简并进行状态编码 从图1原始状态图中可以看出，不存在等效状态，因此 选择000100表示S0S4 五个状态，状态图如图2所示。 000 1/0 0/0 1/0 1/0 1/1 0/0 0/0 001 011100010 0/0 1/0 0/0 图2 1101序列检测器状态图 （

15、3）根据状态图的状态数选择触发器的类型与个数 由图2可知，需要使用3个触发器，本题选用D触发器 （4）根据状态图列出次态卡诺图如图3所示 0000/0 XQ3 Q2Q1 00 01 00011011 0000/00000/00011/0 / / 11 10 1001/0 0000/0 0010/0/ / / / 1010/01100/1 1010/0 图3 1101序列检测器次态卡诺图 000 1/0 0/0 1/0 1/0 1/1 0/0 0/0 001 011100010 0/0 1/0 0/0 图2 1101序列检测器状态图 0 XQ3 Q2Q1 00 01 00011011 000 1

16、1 10 0 0 0 010 0 XQ3 Q2Q1 00 01 00011011 001 11 10 0 0 1 101 nnn QXQQ 12 1 3 nnnnnn QQQQXXQQ 12123 1 2 （5）根据次态卡诺图画分解卡诺图，然后求状态方程和 输出方程 Q3卡诺图Q2卡诺图 0000/0 XQ3 Q2Q1 00 01 00011011 0000/00000/00011/0 / / 11 10 1001/0 0000/0 0010/0/ / / / 1010/01100/1 1010/0 图3 1101序列检测器次态卡诺图 0 XQ3 Q2Q1 00 01 00011011 000

17、 11 10 0 0 0 010 0 XQ3 Q2Q1 00 01 00011011 001 11 10 1 0 0 010 nnnnnnnn QQXQXQQQQXQ 1212123 1 1 nnn out QQQXF 123 Q1卡诺图Fout卡诺图 （5）根据次态卡诺图画分解卡诺图，然后求状态方程和 输出方程 （6）根据状态方程和D触发器的特征方程求驱动方程 nnQ XQD 123 nnnnn QQQQXXQD 121232 nnnnnnn QQXQXQQQQXD 12121231 nnn out QQQXF 123 （7）根据驱动方程、输出方程和D触发器的逻辑符号绘 制逻辑电路图如下：

18、（8）仿真波形图如下： CPXCPX 000000000810000010 100010000910010100 2001001101010100100 3001100001110111001 4010000001211000100 5010100001311010100 6011001101411100100 7011100001511111110 （9）检查自启动功能 n Q1 n Q2 n Q3 1 2 n Q 1 3 n Q 1 1 n Q n Q1 n Q2 n Q3 1 2 n Q 1 3 n Q 1 1 n Q out F out F 画出全状态转换表，从中可以看出：当3个触发器

19、输出均 为1时，电路将进入“死循环”。因此，需要增加1个三输入 端的与非门，将Q3、Q2、Q1 与非后送X，使电路自动跳出 “死循环”进入有效循环。 X=0 （10）自启动电路设计 有限状态机（有限状态机（FSM） Idle Start Stop Clear !A !Reset /K2=0 K1=0 !Reset / K2=0 K1=0 A=1/K2=1 （!Reset |!A ）/ K2=0 K1=1 !Reset /K2=0 K1=0 A/K1=0 状态机的设计包含两个主要过程：状态机的设计包含两个主要过程： 一是状态机的编码，二是状态机的建模。一是状态机的编码，二是状态机的建模。 同步时

20、钟：同步时钟：clk 输入信号：输入信号：reset、A 输出信号：输出信号：K1、K2 状态转移发生在时钟上升沿触状态转移发生在时钟上升沿触 有限状态机（有限状态机（FSM）-编码编码 n状态编码又称状态分配。设计时，须综合考虑电路复杂度状态编码又称状态分配。设计时，须综合考虑电路复杂度 和电路性能这两个因素，选择编码方法。和电路性能这两个因素，选择编码方法。 n二进制编码二进制编码、格雷编码、格雷编码、完整一位热编码完整一位热编码( verbose one- hot) 、简化一位热编码、简化一位热编码( simplified one-hot ) 二进制编码：二进制编码： Idle = 2b

21、00 Start = 2b01 Stop = 2b10 Clear = 2b11 One-Hot编码：编码： Idle = 4b1000 Start = 4b0100 Stop = 4b0010 Clear = 4b0001 有限状态机（有限状态机（FSM）-编码编码 二进制编码：使用较少的触发器和较多的组合逻辑；二进制编码：使用较少的触发器和较多的组合逻辑； 适用于适用于CPLD和小型状态机设计；和小型状态机设计； One-Hot编码：使用较多的触发器和较少的组合逻辑；编码：使用较多的触发器和较少的组合逻辑； 适用于适用于FPGA和大型状态机设计；和大型状态机设计； 格雷编码：格雷编码： 在

22、状态转换中在状态转换中, 相邻的状态每次只有一个相邻的状态每次只有一个bit位产位产 生变化生变化, 可减少了产生毛刺和一些暂态的可能。可减少了产生毛刺和一些暂态的可能。 有限状态机（有限状态机（FSM）-建模建模 （1）用三个过程描述：即现态（）用三个过程描述：即现态（CS）、次态（）、次态（NS）、）、 输出逻辑（输出逻辑（OL）各用一个）各用一个always过程描述。过程描述。 （2）双过程描述（）双过程描述（CS+NS、OL双过程描述）双过程描述） （3）双过程描述（）双过程描述（CS、NS+OL双过程描述）双过程描述） （4）单过程描述）单过程描述(CS+NS+OL） 有限状态机的几

23、种描述方式有限状态机的几种描述方式 有限状态机（有限状态机（FSM）-建模建模 有限状态机（有限状态机（FSM） Idle Start Stop Clear !A !Reset /K2=0 K1=0 !Reset / K2=0 K1=0 A=1/K2=1 （!Reset |!A ）/ K2=0 K1=1 !Reset /K2=0 K1=0 A/K1=0 同步时钟：同步时钟：clk 输入信号：输入信号：reset、A 输出信号：输出信号：K1、K2 状态转移发生在时钟上升沿触状态转移发生在时钟上升沿触 module module fsmfsm (Clock, Reset, A, K2, K1);

24、 (Clock, Reset, A, K2, K1); input Clock, Reset, A; /input Clock, Reset, A; /定义时钟、复位和输入信号定义时钟、复位和输入信号 output K2, K1; /output K2, K1; /定义输出控制信号的端口定义输出控制信号的端口 regreg K2, K1; / K2, K1; /定义输出控制信号的寄存器定义输出控制信号的寄存器 regreg 1:0 state ; 1:0 state ; / /定义状态寄存器定义状态寄存器 parameter Idle = 2parameter Idle = 2b00, Sta

25、rt = 2b00, Start = 2b01, /b01, /定义状态变量参数值定义状态变量参数值 Stop = 2Stop = 2b10, Clear = 2b10, Clear = 2b11b11； always (always (posedgeposedge Clock) Clock) if (!Reset) if (!Reset) begin / begin /定义复位后的初始状态和输出值定义复位后的初始状态和输出值 state = Idle; K2=0; K1=0; state = Idle; K2=0; K1=0; end end elseelse case (state) ca

26、se (state) Idle: begin Idle: begin if (A) begin if (A) begin state = Start; state = Start; K1=0; K1=0; end end else state = Idle; else state = Idle; end end 建模方法之一（二进制编码）建模方法之一（二进制编码） Start: begin Start: begin if (!A) state = Stop; if (!A) state = Stop; else state = Start; else state = Start; end en

27、d Stop: begin Stop: begin if (A) begin if (A) begin state = Clear; state = Clear; K2= 1; K2= 1; end end else state = Stop; else state = Stop; end end Clear: begin Clear: begin if (!A) begin if (!A) begin state = Idle; state = Idle; K2=0; K1=1; K2=0; K1=1; end end else state = Clear; else state = Cle

28、ar; end end endcaseendcase endmoduleendmodule 建模方法之一（二进制编码）建模方法之一（二进制编码） module module fsmfsm (Clock, Reset, A, K2, K1); (Clock, Reset, A, K2, K1); input Clock, Reset, A;input Clock, Reset, A; output K2, K1;output K2, K1; regreg K2, K1; K2, K1; regreg 3:0 state ; 3:0 state ; parameter Idle = 4parame

29、ter Idle = 4b1000, b1000, Start = 4 Start = 4b0100, b0100, Stop = 4 Stop = 4b0010, b0010, Clear = 4 Clear = 4b0001;b0001; always ( always (posedgeposedge clock) clock) if (!Reset) if (!Reset) begin begin state = Idle; K2=0; K1=0; state = Idle; K2=0; K1=0; end end else else case (state) case (state)

30、Idle: if (A) begin Idle: if (A) begin state = Start; state = Start; K1=0; K1=0; end end else state = Idle; else state = Idle; 建模方法之二（一位热编码）建模方法之二（一位热编码） 建模方法之二（一位热编码）建模方法之二（一位热编码） 建模方法之三（建模方法之三（2个个always） end endmodule 建模方法之三（建模方法之三（2个个always） 建模方法之四（多个建模方法之四（多个always） 建模方法之四（多个建模方法之四（多个always） 建模方法

31、之四（多个建模方法之四（多个always） Reset A clk Stop Clear 0 10 0 10 always20 always30 K10 K20 Clock Reset A K2 K1 state IdleStartStop reset Clear 有限状态机（有限状态机（FSM）-总结总结 n 有限状态机（有限状态机（FSM）-扩展扩展 有限状态机有限状态机-扩展扩展 隐式状态机隐式状态机FSM 不需要声明状态寄存器不需要声明状态寄存器 仿真效率高仿真效率高 只适合于线性的状态改变只适合于线性的状态改变 大多数综合工具不能处理大多数综合工具不能处理 显式显式FSM： 利于结构

32、化利于结构化 易于处理缺省条件易于处理缺省条件 能处理复杂的状态改变能处理复杂的状态改变 所有综合工具都支持所有综合工具都支持 有限状态机有限状态机 问题：问题： 什么是什么是FSM？ Mealy机和机和moor机的区别？机的区别？ 回答：回答： 有限状态机，有向的状态转移图。有限状态机，有向的状态转移图。 前者输出由当前输入和当前状态决定。后者输出仅由当前前者输出由当前输入和当前状态决定。后者输出仅由当前 输入决定。输入决定。 历史视角：有限状态机和微处理器历史视角：有限状态机和微处理器 微处理器有三个主要部分：寄存器，算术逻辑单元和控微处理器有三个主要部分：寄存器，算术逻辑单元和控 制单元

33、。控制单元输入将被执行的指令和其他的信息，如制单元。控制单元输入将被执行的指令和其他的信息，如 标志寄存器的值。控制单元输出控制信号以便加载和修改标志寄存器的值。控制单元输出控制信号以便加载和修改 寄存器的内容，执行算术逻辑功能，存取存储器和输入寄存器的内容，执行算术逻辑功能，存取存储器和输入/ /输输 出设备。它按照适当的顺序输出这些信号，以便微处理器出设备。它按照适当的顺序输出这些信号，以便微处理器 正确读取，译码和执行每条指令。正确读取，译码和执行每条指令。 微处理器的控制单元本质上是一个有限状态机。指令和标微处理器的控制单元本质上是一个有限状态机。指令和标 志值是状态机的输入，控制信号

34、是状态机的输出。志值是状态机的输入，控制信号是状态机的输出。 n设计集成电路时设计集成电路时,通常可将整个系统划分为数据单元和通常可将整个系统划分为数据单元和 控制单元。其中控制单元的主体通常是一个有限状态控制单元。其中控制单元的主体通常是一个有限状态 机机,它接收外部信号和数据单元产生的状态信息它接收外部信号和数据单元产生的状态信息, 产生产生 控制信号序列。控制信号序列。 历史视角：有限状态机和微处理器历史视角：有限状态机和微处理器 “101”序列检测器的序列检测器的Verilog描述（三个过程）描述（三个过程） module fsm1_seq101(clk,clr,x,z); input clk,clr,x; output reg z; reg1:0 state,next_state; parameter S0=2b00,S1=2b01,S2=2b11,S3=2b10; /*状态编码，采用格雷（状态编码，采用格雷（Gray）编码方式）编码方式*/ always (posedge clk or posedge clr) /*该过程定义当前状态该过程定义当前状态*/ beginif(clr) state=S0; /异步复位，异步复位，s0为起始状态为起始状态 e