《CPLD FPGA设计与应用基础教程》课件第七章

第七章有限状态机设计LOREMIPSUMDOLOR目录CONCENT7.1有限状态机的基本概念7.2有限状态机的算法描述7.3有限状态机描述的基本语法7.4状态初始化7.5状态编码7.6FullCase与ParallelCase7.7实例7.1有限状态机的基本概念GRADUATIONTHESIS7.1有限状态机的基本概念数字世界主要由组合逻辑电路和时序逻辑电路组成。而时序逻辑电路区别于组合逻辑电路关键在于时序性以及电路的记忆功能。通常，时序逻辑电路的基本单元都是D触发器。有限状态机则是在时钟信号的控制下，结合组合逻辑电路和时序逻辑电路而形成的一种的电路描述行为。在时钟信号有效边沿的作用下，有限状态机电路会进行顺序的跳动——时序中的每一步就称之为状态。有限状态机不仅仅只是一个时序逻辑系统，而且还包含有组合逻辑电路。其行为是在时钟边沿的作用下按照时钟间隔顺序发生。其行为的跳转可能是有条件的，也可能是无条件的。比如在交通灯系统设计中，由黄变红是无条件的，而由红变绿则是有条件的。7.1有限状态机的基本概念7.1有限状态机的基本概念通过SynplifyPro综合后生成的逻辑电路图如下：7.1有限状态机的基本概念7.1.1Mearly型状态机1951年，G.H.Mearly提出了一种并以他名字命名的新型状态机——Mearly型状态机。其状态跳转图如图7-1所示。它的输出不仅与当前状态有关，而且与输入信号相关，因而在状态跳转图中的每条转移边需要包含输入和输出的信息。由于Mearly型状态机的输出与输入信号有关，而输入信号可能在一个时钟周期内任何时刻发生变化，所以Mearly型状态机对输入的响应会比Moore型状态机早一个周期，并且输入信号的噪声会直接影响到输出信号的质量。7.1.2Moore型状态机Moore型状态机由EdwardF.Moore提出，和Mearly型状态机最大的不同在于，其输出只与当前状态有关，与输入信号无关。在状态跳转图中，每条转移边只包含输入信息，而在每个状态内，不仅会包含当前状态信息，而且还会包含输出信息。Mearly型状态机都可以转化为一个等价的Moore型状态机7.1有限状态机的基本概念Moore型状态机把当前状态存储在触发器中，并把当前状态解码成输出。Moore型状态机的输出会在时钟脉冲的有效边沿后的有限个门延后达到稳定值。7.2有限状态机的算法描述GRADUATIONTHESIS7.2有限状态机的算法描述有限状态机就可以抽象为关于关于图中的变量的函数：FSM=f(X,Z,S,C,R)X——有限状态机的输入信号集合；Z——有限状态机的输出信号集合；S——包含初始状态的状态集合，S0∈S。如图7-1中，S={00，01，10，11},初始状S0=00；δ——状态跳转函数：XxS→S。如卡诺图中N_State[1:0]和State[1:0]之间的关系λ——输出函数：λMearly：XxS→Z，λMoore：S→Z。C——时钟信号R——复位信号。一旦该信号有效，有限状态机立即进入初始状态。7.3有限状态机描述的基本语法GRADUATIONTHESIS7.3有限状态机描述的基本语法【例7-1】采用SystemVerilog实现图7-1的有限状态机逻辑7.3有限状态机描述的基本语法moduleFSM(inputlogicclk,inputlogicrst_l,inputlogicx,outputlogicz);enumlogic[1:0]{S0,S1,S2,S3}state;always_ff@(posedgeclk,negedgerst_l)if(!rst_l)state<=S0;elsecase(state)

S0:state<=(x)?S1:S0;

S1:state<=(~x)?S2:S1;

S2:state<=(~x)?S3:S2;

S3:state<=(x)?S0:S1;

default:state<=S0;endcasealways_combbeginz=1'b0;if(state==S2)z=~x;

elsez=x;endmodule7.3有限状态机描述的基本语法7.3有限状态机描述的基本语法例7-1采用SystemVerilog所设计的一个可综合的有限状态机。从该例可以看出，对于有限状态机的描述，其基本语法会涉及到如下几部分：(1)变量声明(2)状态编码(3)状态跳转语句(4)组合逻辑语句(5)条件判断语句(6)多分支语句在复杂的有限状态机设计中，状态输出数量较多或者组合逻辑输出较多时，会影响到代码的可读性，一般可以采用任务和函数来进行封装，从而提高代码的可读性。

(1)任务task——当状态跳转频繁时，可以采用task来进行封装;

(2)函数function——当状态机内有大量重复使用的组合逻辑输出或者功能时，可以采用function来进行封装，这样整个代码会显得更为简洁;如例7.2所示7.3有限状态机描述的基本语法【例7-2】采用function进行有限状态机设计示例//IDLESTATEfunctions{IDLE,4'b0_0_?_0}:next_state={IDLE,1'b0,1'b0,1'b0};{IDLE,4'b1_0_?_0}:next_state={WAIT,1'b0,1'b1,1'b1};{IDLE,4'b0_1_?_0}:next_state={WAIT,1'b0,1'b1,1'b0};{IDLE,4'b1_1_?_0}:next_state={WAIT,1'b0,1'b1,1'b1};//WAITSTATEfunctions{WAIT,4'b0_0_?_0}:next_state={WAIT,1'b0,1'b0,1'b0};{WAIT,4'b0_?_0_0}:next_state={WAIT,1'b0,1'b0,1'b0};{WAIT,4'b0_1_1_0}:next_state={DONE,1'b0,1'b1,1'b0};{WAIT,4'b1_0_?_0}:next_state={WAIT,1'b0,1'b0,1'b1};{WAIT,4'b1_?_0_0}:next_state={WAIT,1'b0,1'b0,1'b1};{WAIT,4'b1_?_0_0}:next_state={WAIT,1'b0,1'b0,1'b1};{WAIT,4'b1_1_1_0}:next_state={DONE,1'b0,1'b1,1'b1};//DONESTATEfunctions{DONE,4'b?_?_0_0}:next_state={DONE,1'b0,1'b0,1'b1};{DONE,4'b?_?_0_0}:next_state={DONE,1'b0,1'b0,1'b1};{DONE,4'b?_?_1_0}:next_state={IDLE,1'b1,1'b0,1'b1};7.4状态机初始化GRADUATIONTHESIS7.4状态机初始化1.初始化的必要

有限状态机在执行时必须初始化，否则将无法正确执行有限状态机的跳转动作，或者初始化不完整时会导致死锁的现象。2.初始化方法在SystemVerilog或者VerilogHDL语言中，通常采用异步复位电路来实现状态机的初始化——也就是说，当异步复位信号有效时，不管时钟信号的边沿是否有效，有限状态机将无条件进入其初始状态。3.初始化的关键在状态初始化过程中，需要防止出现伪初始化或者不完整初始化的情况，特别是针对采用一段式状态机——把状态跳转和组合逻辑写在一起的状态机——来说，这个尤为重要。7.4状态机初始化【例7-2】不完整初始化的有限状态机示例moduleex_FSM(inputlogicclk,inputlogiccs,inputlogicframe,inputlogicrst_,inputlogicrw,outputlogicad_decode,outputlogicreg_type_dir,outputlogicrst_timer,outputlogictrdy);enumlogic[1:0]{CY_TYPE=2'b00,

IDLE=2'b01,

START=2'b10}state;

always_ff@(posedgeclk,negedgerst_)if(!rst_)

state<=IDLE;//异步状态复位elsecase(state)

CY_TYPE:begin

ad_decode<=1'b0;

rst_timer<=1'b0;

reg_type_dir<=1'b1;

if(!frame)begin

state<=IDLE;

trdy<=1'b1;

end

elsebegin

state<=CY_TYPE;

trdy<=1'b0;

end

end

7.4状态机初始化【例7-2】不完整初始化的有限状态机示例（续）IDLE:begin

rst_timer<=1'b0;

reg_type_dir<=1'b0;

if(frame&&cs)

state<=START;

elsestate<=IDLE;end

START:begin

ad_decode<=1'b1;

rst_timer<=1'b1;

reg_type_dir<=1'b0;

if(!frame)

state<=IDLE;

elseif(rw)

begin

state<=CY_TYPE;

reg_type_dir<=1'b1;

end

elsestate<=START;endendcaseendmodule7.4状态机初始化【例7-2】不完整初始化的有限状态机示例（续）例7-2为典型的一段式状态机，在该程序中，既有状态跳转，也有状态的逻辑输出，很容易生产死锁。程序主体一开始就针对状态机进行异步复位，状态机马上跳转至IDLE状态，但没有对所有的输出信号进行初始化，因此，当状态机跳转至IDLE状态时，ad_decode和trdy两信号没有被初始化，因而是未定状态。解决此问题的最好方式，就是针对状态机内的所有状态和输出信号进行初始化。同时，需要注意的是，本例没有采用default关键字，因此，如果出现状态为2’b11时，状态机无法正常跳转，因此出现死锁的情况。正确的解决方式是增加一个default状态，或者才用unique和priority关键词来对case进行限定。7.4状态机初始化always_ff@(posedgeclk,negedgerst_)if(!rst_)begin//状态异步复位和输出复位

state<=IDLE;

ad_decode<=1'b0;rst_timer<=1'b0;

reg_type_dir<=1'b1;

trdy<=1'b0;

endelse

uniquecase(state)

CY_TYPE:begin

ad_decode<=1'b0;

rst_timer<=1'b0;

reg_type_dir<=1'b1;

if(!frame)begin

state<=IDLE;

trdy<=1'b1;

end

elsebeginstate<=CY_TYPE;trdy<=1'b0;endend在if语句中针对所有的输出信号和状态进行初始化，同时在case语句前增加unique关键字，这样就可以避免死锁或者未完全初始化的情况。当然，本例还有更多更好的方式进行有限状态机设计，后续章节将陆续讲述。7.5状态编码GRADUATIONTHESIS7.5状态编码状态编码:

有限状态机最重要的特征之一是状态编码。所谓的状态编码，就是对有限状态机的所有状态进行数字标识，并采用文本助记符与数字标识意义对应。不同的状态编码会导致不同的面积与速度。状态编码种类：在数字逻辑系统设计中，一般常见的数字编码方式有：二进制码（Binary码）格雷码（Gray码）独热码（One-hot码）独冷码（One-cold码）二-十进制码（BCD码）等。7.5状态编码定义方式：VerilogHDL一般采用参数进行状态编码，也可以采用`define宏定义的方式进行编码——但一般不推荐此方式。参数编码的方式如下：parameter//theseparametersrepresentstatenamesIDLE=3’b000,DECISION=3’b001,READ1=3’b010,READ2=3’b011,READ3=3’b100,READ4=3’b101,WRITE=3’b110;7.5状态编码

SystemVerilog也可以采用参数和宏定义的方式进行状态编码。但一般推荐采用枚举类型进行状态编码，如把上述的参数编码修改为枚举类型的编码方式，如下：enum{IDLE,DECISION,READ1,READ2,READ3,READ4,WRITE}state;枚举类型不仅列出了每一种状态，同时也列出了枚举变量名称，状态编码可以显式声明，也可以省略，因此更加容易对应。但需要注意的是，枚举变量默认为int类型——32位，如果没有显式进行位宽限制，则在综合时会出现面积浪费的现象，从而出现告警。因此，在采用枚举类型进行状态编码时，需要限定枚举变量位宽，如：enumlogic[2:0]{IDLE=3’b000,DECISION=3’b001,READ1=3’b010,READ2=3’b011,READ3=3’b100,READ4=3’b101,WRITE=3’b110}state;7.5状态编码7.5.1二进制码（Binary码）

二进制码也叫顺序码（Sequential码），是最简单也是最常用的状态编码方式。它的编码是顺序的，相邻两个状态之间相差为1。状态数量和编码所需的位之间的关系是：其中，N代表编码所需要的比特位，M表示状态数量。在该状态中，总计有7种状态，因此只需要三个比特位就可以实现状态编码。优点：所占的FPGA/CPLD面积最小缺点：由于相邻状态进行转换时的状态位翻转的数量不确定7.5状态编码7.5.2格雷码（Gray码）格雷码，也称之为循环码，也是一种压缩编码，格雷码也是一种二-十进制编码，但它是一种无权码，采用绝对编码的方式。由于格雷码只改变一位，因而可以降低数字电路的尖峰电流脉冲格雷码一般应用于对面积和速度都有一定要求的数字系统设计中。7.5状态编码格雷码的声明：采用SystemVerilog进行格雷码编码声明如下：enumlogic[2:0]{IDLE=3’b000,DECISION=3’b001,READ1=3’b011,READ2=3’b010,READ3=3’b110,READ4=3’b111,WRITE=3’b101}state;二进制码和格雷码之间可以相互转换：（1）二进制码转换为格雷码：其中，G表示格雷码，B表示二进制码，i表示位号。7.5状态编码（2）格雷码转换为二进制码：其中，G表示格雷码，B表示二进制码，i表示位号。7.5状态编码7.5.3独热码（one-hot码）和独冷码（one-cold码）

独热码和独冷码是相对的编码方式，也是一种特殊的二进制编码方式，属于非压缩编码。独热码是每个状态有且仅有一个1，而独冷码是每个状态有且仅有一个0。因此采用独热码或者独冷码进行状态编码所需要的比特位和有限状态机的状态数量一一对应。这种方式最大的缺点是:占用的FPGA/CPLD面积最大。优点为：采用这种方式进行编码，其译码简单，状态机的运行速度会很快。因此，特别适合含有丰富触发器的FPGA设计。7.5状态编码采用SystemVerilog进行独热码和独冷码编码声明如下：独热码：enumlogic[6:0]{IDLE=7’b000_0001,DECISION=7’b000_0010,READ1=7’b000_0100,READ2=7’b000_1000,READ3=7’b001_0000,READ4=7’b010_0000,WRITE=7’b100_0000}state;独冷码：enumlogic[6:0]{IDLE=7’b111_1110,DECISION=7’b111_1101,READ1=7’b111_1011,READ2=7’b111_0111,READ3=7’b110_1111,READ4=7’b101_1111,WRITE=7’b011_1111}state;7.5状态编码7.5.4状态编码原则和编译指导

通常来说，状态编码基本原则是：（1）有足够的触发器逻辑，但需要满足速度要求，则优先采用独热码、独冷码或者格雷码进行编码（2）对面积和速度都有要求，则优先考虑格雷码进行编码（3）对速度没有要求，但逻辑资源紧张，则优先考虑格雷码和二进制码进行编码7.6FullCase与ParallelCaseGRADUATIONTHESIS7.6FullCase与ParallelCase【例7-4】状态跳转图如图所示，采用VerilogHDL语言设计此有限状态机，并使用fullcase指导SynplifyPro综合软件进行综合。本例中有三个状态，分别是A、B和C，对其采用格雷码编码：parameterA=2’b00,B=2’b01,C=2’b11;而2’b10状态为未定态。7.6FullCase与ParallelCase部分代码如下：moduleFSM_full_case(inputclk,inputRESET,inputx,outputreg[1:0]z);parameterA=2'b00,B=2'b01,C=2'b11;reg[1:0]statealways@(posedgeclk,posedgeRESET)if(RESET)

begin

state<=A;

z<=2'b01;

endelsecase(state)/*synthesisfull_case*/

A:begin

z<=2'b01;

if(x)

state<=C;

else

state<=B;endB:begin

z<=2'b10;

state<=x?C:B;endC:begin

z<=2'b10;

state<=x?C:A;endendcaseendmodule7.6FullCase与ParallelCase例7-4并没有default语句来表示其他状态如何执行状态跳转，换句话说，当状态跳转至2’b10时，状态机就出现了死锁的状态，这是设计不能出现的状况。但在本例中采用了fullcase的注释，指导SynplifyPro软件忽略掉2’b10状态，因而不会生成锁存器，具体可以从图7-9综合后生成的逻辑电路看出7.6FullCase与ParallelCase【例7-5】针对例7-4所采用的状态跳转图，采用VerilogHDL语言设计此有限状态机，并使用parallelcase指导SynplifyPro综合软件进行综合。elsecasez(state)/*synthesisparallel_case*/

A:begin

z<=2'b01;

if(x)

state<=C;

else

state<=B;

end

B:begin

z<=2'b10;

state<=x?C:B;

end

C:begin

z<=2'b10;

state<=x?C:A;endendcase7.6FullCase与ParallelCaseparallelcase指导SynplifyPro生成的逻辑电路图会根据具体的硬件功能进行优化，其具体的逻辑电路如下7.7状态机的描述GRADUATIONTHESIS7.7状态机的描述

状态机由各种描述方式，可以深入到门级逻辑设计，也可以采用行为级描述。通常最常用的有三种描述方式：(1)一段式状态机(2)两段式状态机(3)三段式状态机。这三种方式各有特点，在不同的场合有不同的应用。7.7状态机的描述7.7.1一段式状态机概念：一段式状态机是最原始的状态机，在该状态机内，仅仅只有一个always或者always_ff语句块，该语句块内不仅含有状态跳转，还包含有组合逻辑的输入输出。特点：一段式状态机混合了时序逻辑和组合逻辑，代码冗长，不利于代码的维护和修改，也不利于时序约束，因此不推荐采用一段式状态机进行有限状态机设计。7.7状态机的描述【例7-6】采用一段式状态机对图7-11的状态跳转图进行有限状态机设计7.7状态机的描述代码采用uniquecase，表示忽略没有枚举的状态。代码中的每一个状态，既有状态跳转，也有逻辑输出。程序很容易产生锁存器。经过SynplifyPro软件综合后生成的逻辑电路如下7.7状态机的描述7.7.2两段式状态机概念：两段式状态机把时序逻辑和组合逻辑分开设计，其中时序逻辑采用always_ff负责状态初始化和状态跳转，而组合逻辑则采用always_comb负责输出信号的初始化和输出逻辑设计。特点：这样的设计不仅符合代码的风格，同时也提高了代码的可读性，容易维护。7.7状态机的描述【例7-7】采用两段式状态机对图7-11的状态跳转图进行有限状态机设计

程序含有两个always语句块，其中always_ff语句用于有限状态机的异步复位和状态跳转，不涉及任何的输出信号逻辑。7.7状态机的描述

两段式状态机还有两种额外的设计方式。一种方式是把状态机分为三部分进行：状态更新、下一个状态逻辑以及输出逻辑。因此，与例7-7不同在于，该状态机设计中需要定义两个枚举类型：现态和次态。具体设计如例7-8所示。【例7-8】采用两段式状态机对图7-11的状态跳转图进行有限状态机设计//状态更新逻辑always_ff@(posedgeclk,posedgeR)if(R)state<=SA;//状态初始化elsestate<=next_state;

always_combbeginuniquecase(state)//次态更新逻辑SA:next_state=Start?SB:SA;SB:next_state=Read?SC:SD;SC:next_state=memDataAvail?SA:SC;SD:next_state=dataValid?SA:SD;endcaseendalways_combbegin//输出信号逻辑ld_AddrUp=1'b0;ld_AddrLo=1'b0;dv=1'b0;en_Data=1'b0;ld_Data=1'b0;//输出信号初始化if(state==SA)ld_AddrUp=Start?1'b1:ld_AddrUp;if(state==SB)ld_AddrLo=1'b1;if(state==SC)begindv=1'b1;en_Data=1'b1;endif(state==SD)ld_Data=1'b1;end7.7状态机的描述另外的一类变体是采用一个always_comb语句把次态更新逻辑和输出逻辑放在一起，这样所有的基于状态的组合逻辑都集中在一起，在代码设计中经常会用到此种方式。【例7-9】采用两段式状态机对图7-11的状态跳转图进行有限状态机设计//状态更新逻辑always_ff@(posedgeclk,posedgeR)if(R)state<=SA;//状态初始化elsestate<=next_state;always_combbegin//基于状态的组合逻辑输出ld_AddrUp=1'b0;ld_AddrLo=1'b0;dv=1'b0;en_Data=1'b0;ld_Data=1'b0;//输出信号初始化uniquecase(state)SA:beginnext_state=Start?SB:SA;ld_AddrUp=Start?1'b1:ld_AddrUp;endSB:beginnext_state=Read?SC:SD;ld_AddrLo=1'b1;endSC:beginnext_state=memDataAvail?SA:SC;dv=1'b1;en_Data=1'b1;endSD:beginnext_state=dataValid?SA:SD;ld_Data=1'b1;endendcase7.7状态机的描述7.7.3三段式状态机

严格意义上来说，不存在三段式状态机。三段式状态机主要是为了解决两段式状态机采用组合逻辑输出所产生的毛刺问题，同时增加一级寄存器也可以有效地进行时序计算和约束。对于总线来说，容易使得总线数据对其，从而减小总线数据之间的偏斜，减小接收端数据采样出错的频率。描述方式;三段式状态机采用三个always语句块，分别是采用always_ff语句块实现状态更新逻辑、采用always_comb语句块实现组合逻辑，以及采用always_ff语句块实现同步输出。7.7状态机的描述【例7-10】采用三段式状态机对图7-11的状态跳转图进行有限状态机设计//状态更新逻辑always_ff@(posedgeclk,posedgeR)if(R)state<=SA;//状态初始化elsestate<=next_state;

always_combbeginuniquecase(state)//次态更新逻辑SA:next_state=Start?SB:SA;SB:next_state