有限状态机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模型，但并不模型，但并不总是一种高效的方法。总是一种高效的方法。如果一味地追求使用如果一味地追求使用FSM来设计时序电路，可能会导来设计时

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

6、M速度要快，满足设计的频率要求；速度要快，满足设计的频率要求；n(3)FSM面积要小，满足设计的面积要求；面积要小，满足设计的面积要求；n(4)FSM设计要清晰、易维护；设计要清晰、易维护；有限状态机（有限状态机（FSM）状态机包含的要素可归纳为状态机包含的要素可归纳为4个：现态、条件、动作、个：现态、条件、动作、次态。次态。“现态现态”和和“条件条件”是因，是因，“动作动作”和和“次态次态”是果。是果。现态：现态：是指当前所处的状态。是指当前所处的状态。条件：条件：又称为又称为“事件事件”。动作：动作：条件满足后执行的动作。条件满足后执行的动作。次态：次态：条件满足后要迁往的新状态。条件满足

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

8、所处的状态，否则仍保留原来的状态；4）在进入不同的状态时刻，对系统的开关阵列做开启或关闭）在进入不同的状态时刻，对系统的开关阵列做开启或关闭的操作。的操作。有限状态机（有限状态机（FSM）n状态机一般包括组合逻辑和寄存器逻辑两部分。寄存器用状态机一般包括组合逻辑和寄存器逻辑两部分。寄存器用于存储状态，组合电路用于状态译码和产生输出信号。于存储状态，组合电路用于状态译码和产生输出信号。n根据输出信号产生方法的不同，状态机可分为根据输出信号产生方法的不同，状态机可分为米里米里(Mealy) 机机和和摩尔摩尔(Moore) 机机。n米里米里(Mealy) 机的机的输出输出是当前状态和输入信号的函数。

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

10、逻态的逻辑辑 F F输出逻辑输出逻辑 G G状态状态寄存器寄存器XXQ0Q0Q1Q1XMAXQ0Q1CLKD0D1当前状态当前状态激励激励输出输出输入输入时钟信号时钟信号下一状态逻辑下一状态逻辑 产生激励信号产生激励信号状态存储器状态存储器输出逻辑输出逻辑例：时钟同步状态机（D触发器）XXQ0Q0Q1Q1XMAXQ0Q1CLKD0D1（1）由电路得到激励方程）由电路得到激励方程 D0 = Q0X + Q0X D1 = Q1X + Q1Q0X + Q1Q0X（2）由电路得到输出方程）由电路得到输出方程MAX = Q1Q0X（3）由激励方程和触发器特征方程）由激励方程和触发器特征方程 得到转移方程

11、（状态方程）得到转移方程（状态方程） D触发器特征方程：触发器特征方程：Qn+1 = D Q0n+1 = Q0X + Q0X Q1n+1= Q1X + Q1Q0X + Q1Q0X（4）由转移方程和输出方程得到状态）由转移方程和输出方程得到状态/输出表输出表001101100101101000000001状态转换表状态转换表 X Q1 Q0 Q1* Q0* MAX0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1Q0n+1 = Q0X + Q0XQ1n+1 = Q1X + Q1Q0X + Q1Q0XMAX = Q1Q0XS0 00 11 01 1X0 100/001

12、/010/011/001/010/011/000/1Q1*Q0*/MAXQ1Q0（5）画状态图）画状态图000/0011/01/10/00/00/0111/0101/0逻辑功能描述：具有使能端逻辑功能描述：具有使能端X的的2位二进制加法计数器位二进制加法计数器电路输出与输入直接相关电路输出与输入直接相关 Mealy机机S0 00 11 01 1X0 100/001/010/011/001/010/011/000/1Q1*Q0*/MAXQ1Q0X（6）画时序图）画时序图ENENQ0Q0Q1Q1XMAXQ0Q1CLKD0D1Mealy机机Moore机机MAXSMAXS=Q1Q0状态机的定时图状态机

13、的定时图例：串行数据例：串行数据1101序列检测器设计序列检测器设计（1） 根据题目要求画出原始状态转换图 设：S0 为没有检测到1的状态， S1为检测到一个1的状态， S2为检测到11的状态， S3为检测到110的状态， S4为检测到1101的状态。所状态图可表示为图1所示：S01/00/01/01/01/10/00/0S1S3S4S20/01/00/0图1 原始状态图状态机设计举例状态机设计举例（2）对原始状态图进行状态化简并进行状态编码 从图1原始状态图中可以看出，不存在等效状态，因此选择000100表示S0S4 五个状态，状态图如图2所示。0001/00/01/01/01/10/00/

14、00010111000100/01/00/0图2 1101序列检测器状态图（3）根据状态图的状态数选择触发器的类型与个数 由图2可知，需要使用3个触发器，本题选用D触发器（4）根据状态图列出次态卡诺图如图3所示0000/0XQ3Q2Q10001000110110000/00000/00011/0/ / 11101001/00000/00010/0/ / / / 1010/01100/1 1010/0图3 1101序列检测器次态卡诺图0001/00/01/01/01/10/00/00010111000100/01/00/0图2 1101序列检测器状态图0XQ3Q2Q100010001101100

15、01110000 0100XQ3Q2Q10001000110110011110001 101nnnQXQQ1213nnnnnnQQQQXXQQ1212312（5）根据次态卡诺图画分解卡诺图，然后求状态方程和输出方程Q3卡诺图Q2卡诺图0000/0XQ3Q2Q10001000110110000/00000/00011/0/ / 11101001/00000/00010/0/ / / / 1010/01100/1 1010/0图3 1101序列检测器次态卡诺图0XQ3Q2Q10001000110110001110000 0100XQ3Q2Q10001000110110011110100 010nn

16、nnnnnnQQXQXQQQQXQ121212311nnnoutQQQXF123Q1卡诺图Fout卡诺图（5）根据次态卡诺图画分解卡诺图，然后求状态方程和输出方程（6）根据状态方程和D触发器的特征方程求驱动方程nnQXQD123nnnnnQQQQXXQD121232nnnnnnnQQXQXQQQQXD12121231nnnoutQQQXF123（7）根据驱动方程、输出方程和D触发器的逻辑符号绘制逻辑电路图如下：（8）仿真波形图如下：CPXCPX0000000008100000101000100009100101002001001101010100100300110000111011100140

17、10000001211000100501010000131101010060110011014111001007011100001511111110（9）检查自启动功能nQ1nQ2nQ312nQ13nQ11nQnQ1nQ2nQ312nQ13nQ11nQoutFoutF 画出全状态转换表，从中可以看出：当3个触发器输出均为1时，电路将进入“死循环”。因此，需要增加1个三输入端的与非门，将Q3、Q2、Q1 与非后送X，使电路自动跳出“死循环”进入有效循环。X=0（10）自启动电路设计有限状态机（有限状态机（FSM）Idle Start Stop Clear !A !Reset /K2=0 K1=0

18、 !Reset / K2=0 K1=0A=1/K2=1 （!Reset |!A ）/ K2=0 K1=1!Reset /K2=0 K1=0 A/K1=0状态机的设计包含两个主要过程：状态机的设计包含两个主要过程： 一是状态机的编码，二是状态机的建模。一是状态机的编码，二是状态机的建模。 同步时钟：同步时钟：clk输入信号：输入信号：reset、A输出信号：输出信号：K1、K2状态转移发生在时钟上升沿触状态转移发生在时钟上升沿触有限状态机（有限状态机（FSM）-编码编码n状态编码又称状态分配。设计时，须综合考虑电路复杂度状态编码又称状态分配。设计时，须综合考虑电路复杂度和电路性能这两个因素，选择

19、编码方法。和电路性能这两个因素，选择编码方法。n二进制编码二进制编码、格雷编码、格雷编码、完整一位热编码完整一位热编码( verbose one-hot) 、简化一位热编码、简化一位热编码( simplified one-hot )二进制编码：二进制编码： Idle = 2b00 Start = 2b01 Stop = 2b10 Clear = 2b11 One-Hot编码：编码： Idle = 4b1000 Start = 4b0100 Stop = 4b0010 Clear = 4b0001有限状态机（有限状态机（FSM）-编码编码二进制编码：使用较少的触发器和较多的组合逻辑；二进制编码：

20、使用较少的触发器和较多的组合逻辑； 适用于适用于CPLD和小型状态机设计；和小型状态机设计；One-Hot编码：使用较多的触发器和较少的组合逻辑；编码：使用较多的触发器和较少的组合逻辑； 适用于适用于FPGA和大型状态机设计；和大型状态机设计； 格雷编码：格雷编码： 在状态转换中在状态转换中, 相邻的状态每次只有一个相邻的状态每次只有一个bit位产位产生变化生变化, 可减少了产生毛刺和一些暂态的可能。可减少了产生毛刺和一些暂态的可能。有限状态机（有限状态机（FSM）-建模建模（1）用三个过程描述：即现态（）用三个过程描述：即现态（CS）、次态（）、次态（NS）、）、 输出逻辑（输出逻辑（OL）

21、各用一个）各用一个always过程描述。过程描述。（2）双过程描述（）双过程描述（CS+NS、OL双过程描述）双过程描述）（3）双过程描述（）双过程描述（CS、NS+OL双过程描述）双过程描述） （4）单过程描述）单过程描述(CS+NS+OL）有限状态机的几种描述方式有限状态机的几种描述方式有限状态机（有限状态机（FSM）-建模建模有限状态机（有限状态机（FSM）Idle Start Stop Clear !A !Reset /K2=0 K1=0 !Reset / K2=0 K1=0A=1/K2=1 （!Reset |!A ）/ K2=0 K1=1!Reset /K2=0 K1=0 A/K1=

22、0同步时钟：同步时钟：clk输入信号：输入信号：reset、A输出信号：输出信号：K1、K2状态转移发生在时钟上升沿触状态转移发生在时钟上升沿触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; /定义

23、输出控制信号的寄存器定义输出控制信号的寄存器regreg 1:0 state ; 1:0 state ; / /定义状态寄存器定义状态寄存器parameter Idle = 2parameter Idle = 2b00, Start = 2b00, Start = 2b01, /b01, /定义状态变量参数值定义状态变量参数值 Stop = 2Stop = 2b10, Clear = 2b10, Clear = 2b11b11；always (always (posedgeposedge Clock) Clock) if (!Reset) if (!Reset) begin / begin /

24、定义复位后的初始状态和输出值定义复位后的初始状态和输出值 state = Idle; K2=0; K1=0; state = Idle; K2=0; K1=0; end endelseelse case (state) case (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:

25、 begin Start: begin if (!A) state = Stop; if (!A) state = Stop; else state = Start; else state = Start; end endStop: 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 endClear: begin Clear: begin if (!A) begin if

26、 (!A) begin state = Idle; state = Idle; K2=0; K1=1; K2=0; K1=1; end end else state = Clear; else state = Clear; end end endcaseendcaseendmoduleendmodule 建模方法之一（二进制编码）建模方法之一（二进制编码）module module fsmfsm (Clock, Reset, A, K2, K1); (Clock, Reset, A, K2, K1);input Clock, Reset, A;input Clock, Reset, A;out

27、put K2, K1;output K2, K1;regreg K2, K1; K2, K1;regreg 3:0 state ; 3:0 state ; parameter Idle = 4parameter 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

28、begin state = Idle; K2=0; K1=0; state = Idle; K2=0; K1=0; end end else else case (state) case (state) 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个个alw

29、ays）endendmodule建模方法之三（建模方法之三（2个个always）建模方法之四（多个建模方法之四（多个always）建模方法之四（多个建模方法之四（多个always）建模方法之四（多个建模方法之四（多个always）ResetAclkStopClear010010always20always30K10K20ClockResetAK2K1stateIdleStartStopresetClear 有限状态机（有限状态机（FSM）-总结总结 n 有限状态机（有限状态机（FSM）-扩展扩展 有限状态机有限状态机-扩展扩展隐式状态机隐式状态机FSM 不需要声明状态寄存器不需要声明状态寄存器

30、 仿真效率高仿真效率高 只适合于线性的状态改变只适合于线性的状态改变 大多数综合工具不能处理大多数综合工具不能处理显式显式FSM： 利于结构化利于结构化 易于处理缺省条件易于处理缺省条件 能处理复杂的状态改变能处理复杂的状态改变 所有综合工具都支持所有综合工具都支持 有限状态机有限状态机问题：问题： 什么是什么是FSM？ Mealy机和机和moor机的区别？机的区别？回答：回答： 有限状态机，有向的状态转移图。有限状态机，有向的状态转移图。 前者输出由当前输入和当前状态决定。后者输出仅由当前前者输出由当前输入和当前状态决定。后者输出仅由当前输入决定。输入决定。历史视角：有限状态机和微处理器历史

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

32、的控制单元本质上是一个有限状态机。指令和标微处理器的控制单元本质上是一个有限状态机。指令和标志值是状态机的输入，控制信号是状态机的输出。志值是状态机的输入，控制信号是状态机的输出。n设计集成电路时设计集成电路时,通常可将整个系统划分为数据单元和通常可将整个系统划分为数据单元和控制单元。其中控制单元的主体通常是一个有限状态控制单元。其中控制单元的主体通常是一个有限状态机机,它接收外部信号和数据单元产生的状态信息它接收外部信号和数据单元产生的状态信息, 产生产生控制信号序列。控制信号序列。历史视角：有限状态机和微处理器历史视角：有限状态机和微处理器“101”序列检测器的序列检测器的Verilog描

33、述（三个过程）描述（三个过程） 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为起始状态为起始状态else state=next_st