第九章 有限状态机

1.1概述有限状态机是指输出取决于过去输入部分和当前输入部分的时序逻辑电路。

有限状态机又可以认为是组合逻辑和寄存器逻辑的一种组合。

状态机特别适合描述那些发生有先后顺序或者有逻辑规律的事情，其实这就是状态机的本质。

状态机就是对具有逻辑顺序或时序规律的事件进行描述的一种方法在实际的应用中根据状态机的输出是否与输入条件相关，可将状态机分为两大类，即摩尔(Moore) 型状态机和米勒(Mealy) 型状态机。

Mealy型状态转移图1.2状态机的描述方法状态机的描述方法多种多样，将整个状态机写到１个always 模块里，在该模块中既描述状态转移，又描述状态的输入和输出，这种写法一般被称为一段式FSM 描述方法；还有一种写法是使用两个always 模块，其中一个always 模块采用同步时序的方式描述状态转移，而另一个模块采用组合逻辑的方式判断状态转移条件，描述状态转移规律，这种写法被称为两段式FSM 描述方法；还有一种写法是在两段式描述方法的基础上发展而来的，这种写法使用3 个always模块，一个always 模块采用同步时序的方式描述状态转移，一个采用组合逻辑的方式判断状态转移条件，描述状态转移规律，第三个always 模块使用同步时序电路描述每个状态的输出，这种写法称为三段式写法。

1.3 FSM的状态编码二进制码（Binary）和格雷码（Gray）属于压缩状态编码，这种编码的优点是使用的状态向量最少，但是需要较多的逻辑资源用来状态译码。

二进制码从一个状态转换到相邻状态时，可能有多个比特位发生变化，易产生中间状态转移问题，状态机的速度也要比采用其它编码方式慢。

格雷码两个相邻的码值仅有一位就可区分，这将会减少电路中相邻物理信号线同时变化的情况，因而可以减少电路中的电噪声。

Johnson码也有同样的特点，但是要用较多的位数。

独热码（One-hot）指对任意给定的状态，状态寄存器中只有l位为1，其余位都为0。

程序设计之有限状态机程序设计之有限状态机状态机？以前听说过，忘了是老师说的，还是老大说得了。

当时的认识也就是字面的意思，无非是和状态以及状态转换有关系。

也许在写过或者读过的一些代码中有遇到过有限状态机的程序，但是当时是一定没有想到这就是状态机吧。

最近在学习一些东西的时候竟然多次遇到，觉得还是有必要写点关于程序设计中有限状态机的东西。

，这里是一篇对状态机从定义到实现都有很好解释的文章，摘录部分如下：*************************************************************** ************************依据状态之间是否有包含关系，分以下两种（1）常规状态机。

状态机中的所有状态是不相交的、互斥的。

（2）层次状态机。

状态机中的状态之间要么是互斥的，要么是真包含的，可以用树性结构来描述这些状态集，包含其它状态的状态称为枝节点，不包含其它状态的状态称为叶节点，为方便单树描述，总是设计一个状态包含所有的状态节点，称为根节点。

状态机的状态只能停留在叶节点，而不能停留在枝节点，每个枝节点需要指定一个子节点为它的默认子节点，以便状态机进入枝节点的时候能够停留到叶节点。

一般都用switch/case if/else方式实现。

在少量状态（3个及其以下）的时候，不需要引入专门的状态机模块。

常规状态机模块实现涉及到的结构由上而下为：顶层结构是状态机：当前状态id，缺省操作，状态表，状态表：状态数组状态结构：状态id，状态名，进入操作，退出操作，缺省操作，状态事件表（数组）状态事件结构：操作，事件，下一状态的id*************************************************************** ************************从代码易读及美观角度来说，建议用switch/case来实现。

从经验来看，在一些稍大的程序设计中一般都会有状态机的实现，特别是在分层实现，协议栈实现，编解码方面。

什么是有限状态机FSM简介有限状态机（以下用FSM指代）是一种算法思想，简单而言，有限状态机由一组状态、一个初始状态、输入和根据输入及现有状态转换为下一个状态的转换函数组成。

在Gof的23种设计模式里的state模式是一种面向对象的状态机思想，可以适应非常复杂的状态管理。

现在，FSM被普遍用于搜索引擎的分词、编译器实现和我们普遍关注的游戏开发中。

游戏开发中，通常用FSM实现NPC控制，如当NPC受到攻击时根据健康、力量等选择逃跑还是反攻的行为，一般是用FSM实现的。

FSM的实现方法有很多种，不能简单地说孰优孰劣，但现代开发中，一般都比较推荐面向对象的实现方式：因为可重用性和健壮性更高，而且当需求变更的时候，也有很好的适应性。

实践理论从实践中来，也要回到实践中去。

我们现在通过实例来探索一下FSM的实现吧。

首先假设有这样一个世界（World），世界里只有一台永不缺乏动力的汽车（Car），汽车是次世代的，没有油门方向盘之类的落后设备，只有两个互斥的按钮——停止（Stop）和行进（Run），随着时间的流逝，汽车根据驾驶员的操作走走停停。

下面的代码可以实现这种功能：while True:key = get_key() # 按下什么键if key == "stop":stop(car)elif key == "run":go(car)keep(car) # 保持原态完成了功能而且直观、简洁的程序员万岁！但这时候客户（策划或者玩家）觉得走走停停太没意思了，他们想要掉头、左转和右转的功能，我们就要在while 循环里增加更多的if...else分支；他们想要更多的车，我们就要要在每一个分枝里增加循环；他们不仅仅想要Car了，他们还要要玩Truck，这时我们就需要在分枝的循环里判断当前的车是否支持这个操作（如Truck的装卸货物Car 就不支持）；他们……这个while循环终于无限地庞大起来，我们认识到这样的设计的确是有点问题的，所以我们尝试用另一种方法去实现FSM。

第九章状态机状态机的本质就是对具有逻辑顺序或时序规律事件的一种描述方法方法。

状态机的三个基本要素状态机的三个基本要素：：状态状态：：也叫状态变量。

在逻辑设计中，使用状态划分逻辑顺序和时序规律。

比如：设计伪随机码发生器时，可以用移位寄存器序列作为状态；在设计电机控制电路时，可以以电机的不同转速作为状态；在设计通信系统时，可以用信令的状态作为状态变量等。

输出输出：：输出指在某一个状态时特定发生的事件。

如设计电机控制电路中，如果电机转速过高，则输出为转速过高报警，也可以伴随减速指令或降温措施等。

输入输入：：指状态机中进入每个状态的条件。

有的状态机没有输入条件，其中的状态转移较为简单，有的状态机有输入条件，当某个输入条件存在时才能转移到相应的状态一、状态机状态机分为：：状态机分为有限状态机（（Finite State Machine，FSM）√ 有限状态机无限状态机（（Infinite State Machine，ISM） 无限状态机易维护。

FSM设计要清晰易懂设计要清晰易懂、、易维护有限状态机的设计什么是有限状态机（（FSM ） 什么是有限状态机FSM的种类和不同点设计举例什么是有限状态机？什么是有限状态机？-有限状态机是由寄存器组和组合逻辑构成的硬件时序电路；-其状态其状态（（即由寄存器组的1和0的组合状态所构成的有限个状态有限个状态））只能在同一时钟跳变沿的情况下才能从一个状态转向另一个状态；-究竟转向哪一状态不但取决于各个输入值究竟转向哪一状态不但取决于各个输入值，，还取决于当前状态于当前状态。

-状态状态机可用于产生在时钟跳变沿时刻开关的复杂的机可用于产生在时钟跳变沿时刻开关的复杂的控制逻辑控制逻辑，，是数字逻辑的控制核心是数字逻辑的控制核心。

Moore 状态机下一个状态= F(当前状态当前状态，，输入信号)输出信号= G(当前状态)；下一状态的逻辑输出逻辑G状态寄存器输入输出当前状态激励信号时钟同步的状态机结构(Moore 状态机)F时钟信号clk clk输入Moore型状态机Mealy 状态机下一个状态= F(当前状态当前状态，，输入信号)；输出信号= G(当前状态当前状态，，输入信号)；下一状态输出逻辑输入时钟同步的状态机结构(Mealy 状态机)的逻辑FG状态寄存器时钟信号clkclk 输入输出当前状态激励信号Mealy型状态机带流水线输出的Mealy 状态机下一个状态= F(当前状态当前状态，，输入信号)；输出信号= G(当前状态当前状态，，输入信号)；输出输出输输出流带流水线输出的Mealy 状态机下一状态的逻辑F逻辑G 状态寄存器时钟信号clkclk 输入入当前状态激励信号水线寄存器clk 输入有限状态机的Verilog 描述定义模块名和输入输出端口定义模块名和输入输出端口；；定义输入定义输入、、输出变量或寄存器输出变量或寄存器；；定义时钟和复位信号定义时钟和复位信号；；定义状态变量和状态寄存器；定义状态变量和状态寄存器；用时钟沿触发的always 块表示状态转移过程块表示状态转移过程；；在复位信号有效时给状态寄存器赋初始值在复位信号有效时给状态寄存器赋初始值；；描述状态的转换过程描述状态的转换过程：：符合条件符合条件，，从一个状态到另外一个状态一个状态，，否则留在原状态否则留在原状态；；验证状态转移的正确性验证状态转移的正确性，，必须完整和全面必须完整和全面。

有限状态机设计●有限状态机的概念是一种由状态寄存器和组合逻辑电路按照一定方式组成的、能够根据控制信号按照预先设定的状态进行状态间转移的同步时序逻辑电路模型。

有限状态机模型可用于构建各种同步时序逻辑电路。

●有限状态机的类型及特点根据电路内部组成方式的不同，有三种类型：①MOORE型状态机：状态机的输出信号只是当前状态的函数，与输入信号无关。

输出的变化与当前状态的变化及时钟同步。

②MEALY型状态机：状态机的输出信号是当前状态和输入信号的函数，与输入信号有关。

输出信号的变化不仅随当前状态的改变而改变，而且输入的变化也会立即导致输出信号发生变化。

③带流水线的MEALY型状态机：在MEALY型状态机的输出端加上了一个寄存器,使输出端的信号经寄存后再输出,达到与时钟同步的目的。

输出信号是当前状态和输入信号的函数，且与时钟同步。

三种模型的结构图如下所示：时钟CS NS OLMOORE 型状态机结构图复位MEALY 型状态机结构图时钟复位带流水线的MEALY 型状态机结构图时钟输出寄存器复位有限状态机的功能描述方法状态转换图、状态转换表、流程图例1：一个MOORE 型状态机的状态转换图：时钟和复位信号：reset ，clk输入：in输出：out in=1S0/0S1/1in=1reset=1in=0in=0例2：一个MEALY 型状态机的状态转换图in=1S0S1in=1reset=1in=0in=0in=1/out=1in=0/out=0in=1/out=0in=0/out=1in=0/out=0S0S1in=1/out=0reset=1in=0/out=1in=1/out=1例3：一个带流水线的MEALY 型状态机的状态转换图用硬件描述语言设计有限状态机的步骤：①画状态转换图（表）：确定输入变量、输出变量和状态数，按照命题要求画出状态转换图或状态转换表;②状态化简：合并等价状态;③状态编码：根据状态的个数对状态进行编码;（不需画状态卡诺图及划简状态卡诺图）④用硬件描述语言对状态图（表）进行描述。

有限状态机是由寄存器组和组合逻辑构成的硬件时序电路，其状态（即由寄存器组的1和0的组合状态所构成的有限个状态）只可能在同一时钟跳变沿的情况下才能从一个状态转向另一个状态，究竟转向哪一状态还是留在原状态不但取决于各个输入值，还取决于当前所在状态。

状态机特别适合描述那些有发生有先后顺序，或者有逻辑规律的事情——其实这就是状态机的本质。

状态机的本质就是对具有逻辑顺序或时序规律事件的一种描述方法。

这个论断的最重要的两个词就是“逻辑顺序”和“时序规律”，这两点就是状态机所要描述的核心和强项，换言之，所有具有逻辑顺序和时序规律的事情都适合用状态机描述。

很多初学者不知道何时应用状态机。

这里介绍两种应用思路：第一种思路，从状态变量入手。

如果一个电路具有时序规律或者逻辑顺序，我们就可以自然而然地规划出状态，从这些状态入手，分析每个状态的输入，状态转移和输出，从而完成电路功能；第二种思路是首先明确电路的输出的关系，这些输出相当于状态的输出，回溯规划每个状态，和状态转移条件与状态输入。

无论那种思路，使用状态机的目的都是要控制某部分电路，完成某种具有逻辑顺序或时序规律的电路设计。

其实对于逻辑电路而言，小到一个简单的时序逻辑，大到复杂的微处理器，都适合用状态机方法进行描述。

请读者打开思路，不要仅仅局限于时序逻辑，发现电路的内在规律，确认电路的“状态变量”，大胆使用状态机描述电路模型。

由于状态机不仅仅是一种电路描述工具，它更是一种思想方法，而且状态机的HDL 语言表达方式比较规范，有章可循，所以很多有经验的设计者习惯用状态机思想进行逻辑设计，对各种复杂设计都套用状态机的设计理念，从而提高设计的效率和稳定性。

//1-paragraph method to decribe FSM//Describe state transition, state output, state input condition in only 1 always block //Westor Wang, Dec. 2006//Verilog Training -- How to write FSM bettermodule state1 ( nrst,clk,i1,i2,o1,o2,err);input nrst,clk;input i1,i2;output o1,o2,err;reg o1,o2,err;reg [2:0] NS; //NextStateparameter [2:0] //one hot with zero idleIDLE = 3'b000,S1 = 3'b001,S2 = 3'b010,ERROR = 3'b100;//1 always block to describe state transition, state output, state input condition always @ (posedge clk or negedge nrst)if (!nrst)beginNS <= IDLE;{o1,o2,err} <= 3'b000;endelsebeginNS <= 3'bx;{o1,o2,err} <= 3'b000;case (NS)IDLE: beginif (~i1) begin{o1,o2,err}<=3'b000;NS <= IDLE; endif (i1 && i2) begin{o1,o2,err}<=3'b100;NS <= S1; endif (i1 && ~i2) begin{o1,o2,err}<=3'b111;NS <= ERROR;endendS1: beginif (~i2) begin{o1,o2,err}<=3'b100;NS <= S1; endif (i2 && i1) begin{o1,o2,err}<=3'b010;NS <= S2; endif (i2 && (~i1)) begin{o1,o2,err}<=3'b111;NS <= ERROR;endendS2: beginif (i2) begin{o1,o2,err}<=3'b010;NS <= S2; endif (~i2 && i1) begin{o1,o2,err}<=3'b000;NS <= IDLE; endif (~i2 && (~i1))begin{o1,o2,err}<=3'b111;NS <= ERROR;end endERROR: beginif (i1) begin{o1,o2,err}<=3'b111;NS <= ERROR;endif (~i1) begin{o1,o2,err}<=3'b000;NS <= IDLE; endendendcaseendendmodule//2-paragraph method to describe FSM//Describe sequential state transition in 1 sequential always block//State transition conditions in the other combinational always block//Package state output by task. Then register the output//Westor Wang, Dec. 2006//Verilog Training -- How to write FSM bettermodule state2 ( nrst,clk,i1,i2,o1,o2,err);input nrst,clk;input i1,i2;output o1,o2,err;reg o1,o2,err;reg [2:0] NS,CS;parameter [2:0] //one hot with zero idleIDLE = 3'b000,S1 = 3'b001,S2 = 3'b010,ERROR = 3'b100;//sequential state transitionalways @ (posedge clk or negedge nrst)if (!nrst)CS <= IDLE;elseCS <=NS;//combinational condition judgmentalways @ (nrst or CS or i1 or i2)beginNS = 3'bx;ERROR_out;case (CS)IDLE: beginIDLE_out;if (~i1) NS = IDLE;if (i1 && i2) NS = S1;if (i1 && ~i2) NS = ERROR; endS1: beginS1_out;if (~i2) NS = S1;if (i2 && i1) NS = S2;if (i2 && (~i1)) NS = ERROR; endS2: beginS2_out;if (i2) NS = S2;if (~i2 && i1) NS = IDLE;if (~i2 && (~i1)) NS = ERROR; endERROR: beginERROR_out;if (i1) NS = ERROR;if (~i1) NS = IDLE;endendcaseend//output tasktask IDLE_out;{o1,o2,err} = 3'b000;endtasktask S1_out;{o1,o2,err} = 3'b100;endtasktask S2_out;{o1,o2,err} = 3'b010;endtasktask ERROR_out;{o1,o2,err} = 3'b111;endtaskendmodule//3-paragraph method to describe FSM//Describe sequential state transition in the 1st sequential always block //State transition conditions in the 2nd combinational always block//Describe the FSM out in the 3rd sequential always block//Westor Wang, Dec. 2006//Verilog Training -- How to write FSM bettermodule state3 ( nrst,clk,i1,i2,o1,o2,err);input nrst,clk;input i1,i2;output o1,o2,err;reg o1,o2,err;reg [2:0] NS,CS;parameter [2:0] //one hot with zero idleIDLE = 3'b000,S1 = 3'b001,S2 = 3'b010,ERROR = 3'b100;//1st always block, sequential state transitionalways @ (posedge clk or negedge nrst)if (!nrst)CS <= IDLE;elseCS <=NS;//2nd always block, combinational condition judgment always @ (nrst or CS or i1 or i2)beginNS = 3'bx;case (CS)IDLE: beginif (~i1) NS = IDLE;if (i1 && i2) NS = S1;if (i1 && ~i2) NS = ERROR; endS1: beginif (~i2) NS = S1;if (i2 && i1) NS = S2;if (i2 && (~i1)) NS = ERROR; endS2: beginif (i2) NS = S2;if (~i2 && i1) NS = IDLE;if (~i2 && (~i1)) NS = ERROR; endERROR: beginif (i1) NS = ERROR;if (~i1) NS = IDLE;endendcaseend//3rd always block, the sequential FSM outputalways @ (posedge clk or negedge nrst)if (!nrst){o1,o2,err} <= 3'b000;elsebegin{o1,o2,err} <= 3'b000;case (NS)IDLE: {o1,o2,err}<=3'b000;S1: {o1,o2,err}<=3'b100;S2: {o1,o2,err}<=3'b010;ERROR: {o1,o2,err}<=3'b111;endcase endendmodule。