1、第5章 同步有限状态机设计 5.1 同步有限状态机引例 5.2 状态机的基本概念 5.3 状态机的编码方法 5.4 复杂状态机的编写方法 5.5 采用状态机来实现程序算法 5.6 小结5.1 同步有限状态机引例同步有限状态机引例【例5-1】 设计一个串行数据检测器。电路的输入信号A是与时钟脉冲同步的串行数据，其时序关系如图所示。输出信号为Y；要求电路在信号输入A出现110序列时，输出信号Y为1，否则为0。5.1 同步有限状态机引例同步有限状态机引例 由给定的逻由给定的逻辑功能建立辑功能建立原始状态图原始状态图和原始状态和原始状态表表 状态状态 化简化简 状态状态 分配分配 选择选择 触发触发器
2、类器类型型 确定激励确定激励方程组方程组 和和 输出输出 方程组方程组 画出画出 逻辑图逻辑图并检查并检查自启动自启动能力能力 图5-2 时序逻辑电路设计过程5.1 同步有限状态机引例同步有限状态机引例第一步：理解题意，由给定的逻辑功能建立原始状态图，如图5-3所示 a d c b 0/0 1/0 0/0 1/0 0/0 1/0 0/1 1/0 初始状态初始状态 S A/Y 图5-3 原始状态图图中，S表示状态，A/Y中横线上面的为输入，横线下面的为输出。5.1 同步有限状态机引例同步有限状态机引例第二步：状态化简，合并等价状态 abc0/01/00/01/01/00/1图5-4 化简后的状态
3、图5.1 同步有限状态机引例同步有限状态机引例第三步：状态编码 0/0 1/0 0/1 1/0 1/0 0/0 00 11 01 图5-5 编码后的状态图5.1 同步有限状态机引例同步有限状态机引例第四步：选择触发器的个数和类型触发器个数可根据状态数确定，要求满足2n-1M2n，式中M为状态数，n为触发器的个数。对于本例，已知M为3，所以可求出触发器的个数为2个。 触发器可以选择D触发器、JK触发器等等，本例选用D触发器。5.1 同步有限状态机引例同步有限状态机引例第五步：求出电路的激励方程和输出方程 0 0 1 0 1 0 D1 A Q1 n Q0 n 0 1 1 0 1 0 D0 A Q1
4、 n Q0 n 0 0 0 0 0 1 Y A Q1 n Q0 n 5.1 同步有限状态机引例同步有限状态机引例第六步：画出逻辑图并检查自启动能力 DclkQDclkQD:dff1comb0Y0clkAYD:dff05.1 同步有限状态机引例同步有限状态机引例【例5-2】 对应于步骤六的层次建模方法module fsm_1(clk,A,Y);input clk,A;output Y;wire q0,q1;assign Y= q1 & (A);mydff_2 dff0(.D(A),.Q(q0),.clk(clk), dff1(.D(A&q0), .Q(q1), .clk(clk);endmodu
5、le/以下实现被调用模块mydff_2module mydff_2(D,Q,clk);input D,clk;output reg Q;always (posedge clk) Q=D;endmoduleDclkQDclkQmydff_2:dff0mydff_2:dff1comb0Y0AYclk5.1 同步有限状态机引例同步有限状态机引例【例5-3】 对例5-2的改进消除毛刺module fsm_1(clk,A,Y);input clk,A;output reg Y;wire q0,q1;mydff_2 dff0(.D(A),.Q(q0),.clk(clk), dff1(.D(A&q0), .
6、Q(q1), .clk(clk);always (posedge clk) Y= q1 & (A);endmodule DclkQDclkQDENAQPRECLRmydff_2:dff1comb0Y0Yreg0clkAYmydff_2:dff05.1 同步有限状态机引例同步有限状态机引例【例5-4】 对应于步骤五的Verilog建模module fsm_2(clk,A,Y);input clk,A;output reg Y;reg q0,q1;always (posedge clk) beginq0 = A;q1 JK触发器的激励J和Kmodule D_JK(d,q,j,k); input d
7、,q;output reg j,k;always (d,q)case(d,q)2b00,2b11: begin j=0; k=0; end 2b01,2b10: begin j=1; k=1; endendcaseendmoduledqjkdqjkclkjkqclkjkqDENAQPRECLRD_JK:d_jk0D_JK:d_jk1JK:jk0JK:jk1Y0Yreg0clkAYtemp05.1 同步有限状态机引例同步有限状态机引例/顶层模块，实现例5-2的功能module fsm_3(clk,A,Y);input clk,A;output reg Y;wire q0,q1,j0,k0,j1,
8、k1,temp;assign temp=q0&A;D_JK d_jk0(A,q0,j0,k0);D_JK d_jk1(temp,q1,j1,k1);JK jk0(clk,j0,k0,q0);JK jk1(clk,j1,k1,q1);always (posedge clk) Y= q1 & (A);endmodule /JK触发器实现-JK全1翻转,全0不变,其它为Jmodule JK(clk,j,k,q);input clk,j,k;output reg q;always (posedge clk)case(j,k)2b11: q=q;2b10: q=1;2b01: q=0;2b00: q=q
9、;default: ;endcaseendmodule5.1 同步有限状态机引例同步有限状态机引例【例5-6】 对应于步骤一、步骤二和步骤三的同步状态机module fsm_3(clk,A,Y); input clk,A;output reg Y;reg1:0 state;parameter s0=2b00, /状态编码为顺序编码方式 s1=2b01, s2=2b11;always (posedge clk) case(state) s0: begin if(A) state=s1; else state=s0; Y=0; end s1: begin if(A) state=s2; else
10、state=s0; Y=0;end s2: begin if(A) beginstate=s2;Y=0;end else beginstate=s0;Y=1;end end default: state=s0;endcaseendmodule5.2 状态机的基本概念状态机的基本概念1 状态机的基本描述方式2 状态机的基本要素及分类3 同步状态机和异步状态机4 单进程、双进程和多进程状态机 状态机的基本描述方式状态机的基本描述方式有3种：状态转移图状态转移列表HDL语言描述 状态机的基本要素及分类状态机的基本要素有3 个：状态输出输入 同步状态机和异步状态机异步状态机是没有确定时钟的状态机，它的
11、状态转移不是由唯一的时钟跳变沿所触发。目前多数综合器不能综合采用Verilog HDL描述的异步状态机。因此，应尽量不要使用综合工具来设计异步状态机。 如果一定要设计异步状态机，我们建议采用原理图输入或实例引用的方法，而不要用Verilog HDL输入的方法。为了能综合出有效的电路，用Verilog HDL描述的状态机应明确地由唯一时钟触发，这种状态机我们称为同步状态机。同步有限状态机是设计复杂时序逻辑电路最有效最常用的方法之一。 单进程、双进程和多进程状态机 一个有限状态机总是可以被分成次态译码、状态寄存器、输出一个有限状态机总是可以被分成次态译码、状态寄存器、输出译码三个模块，可以有五种不
12、同的方式将这些模块分配到进程语译码三个模块，可以有五种不同的方式将这些模块分配到进程语句，以实现对状态机的描述。句，以实现对状态机的描述。 三个模块用一个进程实现，也就是说3个模块均在1个always块内，这种状态机描述称为单进程有限状态机。 每一个模块分别用一个进程实现，也就是说3个模块对应着3个always块，这种状态机描述称为三进程有限状态机。 其他其他3种为双进程状态机种为双进程状态机: 次态译码、输出译码分配在一个进程中，状态寄存器用另一个进程描述； 次态译码、状态寄存器分配在一个进程中，输出译码用另一个进程描述； 次态译码用一个进程描述，状态寄存器、输出译码分配在另一个进程中。 5
13、.3 状态机的编码方法状态机的编码方法状态顺序编码 独热编码 直接输出型编码1直接输出型编码2S0000010000001S1010100010010S2101000100100S3-1001100独热编码【例5-9】状态机设计独热码表示状态 module fsm_2(clk,A,Y); input clk,A;output reg Y;reg2:0 state;parameter s0=3b001, s1=3b010, s2=3b100;always (posedge clk) case(state) s0: begin if(A) state=s1; else state=s0; Y=0;
14、 end s1: begin if(A) state=s2; else state=s0; Y=0; end s2: begin if(A) beginstate=s2;Y=0;end else beginstate=s0;Y=1;end end default: state=s0;endcaseendmodule直接输出型编码【例5-10】状态机设计状态编码包含输出信息module fsm_1(clk,A,Y); input clk,A;output Y;reg3:0 state;parameter s0=4b0001, s1=4b0010, s2=4b0100, s3=4b1100;ass
15、ign Y=state3;always (posedge clk) case(state) s0: if(A) state=s1; else state=s0; s1: if(A) state=s2; else state=s0; s2: if(A) state=s2; else state=s3; s3: if(A) state=s1; else state=s0; default: state=s0;endcaseendmodule 非法状态的处理处理的方法有两种：（1）在语句中对每一个非法状态都作出明确的状态转换指示，如在原来的case语句中增加诸如以下语句：case(state)N1:
16、 state=s0;N2: state=s0;（2）如例5-6、例5-9和例5-10中那样，利用default语句对未提到的状态作统一处理。case(state) s0: if(A) state=s1; else state=s0; default: state=s0;endcase由于剩余状态的次态不一定都指向状态s0，所以可以使用方法一来分别处理每一个剩余状态的转向。 5.4 复杂状态机的编写方法复杂状态机的编写方法【例5-11】状态机设计状态和输出使用单独进程module fsm_0(clk,A,Y); input clk,A;output reg Y;reg2:0 current_st
17、ate,next_state;parameter s0=3b001, s1=3b010, s2=3b100;always (posedge clk) /状态寄存器current_state=next_state;always (current_state,A) /产生下一个状态状态的组合逻辑 case(current_state) s0: if(A) next_state=s1; else next_state=s0; s1: if(A) next_state=s2; else next_state=s0; s2: if(A) next_state=s2; else next_state=s0
18、; default: next_state=s0;endcasealways (posedge clk) /产生输出的时序逻辑 case(current_state) s0: Y=0; s1: Y=0; s2: if(A) Y=0; else Y=1; default: Y= y_i) 4: x=x_i; 5: y=y_i; else 6: x=y_i; 7: y=x_i; 8: while (y != 0) 9: r = x % y;10: x = y; 11: y = r; 12: d_o = x; 求两数最大公约数的实现 图图5-18 状态图转换模板状态图转换模板求两数最大公约数的实现
19、图图5-19 求最大公约数的状态图（左）及化简后的状态图（右）求最大公约数的状态图（左）及化简后的状态图（右）求两数最大公约数的实现 【例【例5-13】求最大公约数的】求最大公约数的Verilog代码代码module gcd(clk,x_i,y_i,go_i,d_o);parameter N=6; /用于定义输入数的范围用于定义输入数的范围,最大为最大为2*N-1inputN-1:0 x_i,y_i; input clk,go_i;output regN-1:0 d_o;parameter s0=3b111,s1=3b001,s2=3b010, s3=3b011,s4=3b100,s5=3b1
20、01,s6=3b110;reg2:0 current_state,next_state;regN-1:0 x,y,r; always (posedge clk) /状态寄存器状态寄存器 current_state=next_state;求两数最大公约数的实现 always (current_state,x_i,y_i,go_i,x,y,r) /产生下一个状态的组合逻辑产生下一个状态的组合逻辑case(current_state)s0: if(go_i) next_state=s1; else next_state=y_i) next_state=s2; else next_state=s3;s
21、2: begin next_state=s4;ends3: begin next_state0) next_state=s5; else next_state=s6; s5: begin next_state=s4;ends6: begin next_state=s0;enddefault: next_state=s0; endcasealways (negedge clk) /产生输出和中间变量的组合逻辑产生输出和中间变量的组合逻辑case(current_state)s2: begin x=x_i;y=y_i;ends3: begin x=y_i;y=x_i;ends5: begin r=
22、x%y;x=y;y=r; ends6: begin d_o=x; enddefault: ; endcaseendmodule5.6 小结小结在本章，我们讨论了以下知识点：有限状态机设计的一般步骤： 第一步：理解题意，由给定的逻辑功能建立原始状态图； 第二步：状态化简； 第三步：状态编码； 第四步：选择触发器的个数和类型； 第五步：求出电路的激励方程和输出方程； 第六步：画出逻辑图并检查自启动能力。用Verilog HDL来描述有限状态机，可以充分发挥硬件描述语言的抽象建模能力，使用always块语句和case选择语句（或if条件语句）及赋值语句即可方便实现。具体的逻辑化简、逻辑电路到触发器映
23、射均可由计算机自动完成，也就是说，上述第四步、第五步和第六步不再需要过多的人为干预，使电路设计工作得到简化，效率也有很大提高。5.6 小结小结等价状态是指两个或多个状态，它们在相同的输入下转换到同一个状态去，并得到一样的输出。显然等价状态是重复的，可以合并为一个。电路的状态数越少，存储电路也就越简单。状态化简的目的就在于将等价状态尽可能地合并，以得到最简的状态转换图。这一步，不管是手工完成设计，还是利用计算机自动设计，都是很重要的。但对于FPGA等可编程逻辑设计，由于可用逻辑资源比较丰富，而且状态编码要考虑设计的稳定性，安全性等因素，所以通常不进行状态化简。编码方法有很多，编码方案选择得当，设
24、计的电路可以简单，反之，选得不好，则设计的电路就会复杂许多。在实际设计时，须综合考虑电路复杂度与电路性能之间的折衷。在触发器资源丰富的FPGA设计中，采用独热编码既可以使电路性能得到保证又可充分利用其触发器数量多的优势，也可以采取输出编码的状态指定来简化电路结构，以提高状态机的运行速度。触发器个数可根据状态数确定，要求满足2n-1M2n，式中M为状态数，n为触发器的个数。触发器可选为D触发器，事实上D触发器、JK触发器、T触发器等等，其等价电路图很容易实现。对于任何程序算法，均可采用状态机理论将其转换为纯硬件实现，本章介绍了将程序转化为硬件实现的一种实用的方法。 P128 T1、2、3、4、 5、 6、 7、8作业作业
