有限状态机设计与化简(第5节)

1通用有限状态机设计过程(1)定义输入和输出(2)定义状态机可能的状态状态化简(3)用二进制对状态和输出进行编码状态分配或状态编码输出编码可能的输入编码(4)选择适当的逻辑实现状态和输出组合逻辑的实现和优化步骤2和3对最终的逻辑将产生很大的影响2自动售货机FSMNDResetClockOpen硬币传感器商品释放机制例：简单的自动售货机自动售货机在收到15美分之后就会给出一件商品，这台机器具有能够接收5美分和1角硬币的单个投币口，每次投入一枚硬币，其中机械传感器用来指示插入投币口是5美分还是1角，控制器的输出导致一件商品交到顾客手中两个假设简化设计：不找零在每次使用前，机器都会复位1、理解问题假设：投入5美分，在单个周期内N为真；投入1角，在单个周期内D为真；在上一次复位之后，若收到15美分或更多，则状态机Open为真，并保持一个周期3例：简单的自动售货机2、有限状态机抽象表达列出最终能给出商品的输入顺序:3个5美分：N，N，N2个5美分，再1角：N，N，D1角，5分：D，N5分，1角：N，D2个1角：D，D画状态图:输入:N,D,reset,clk输出商品:open假设:假设信号N和D从来不会同时为真省略了自环N=D=0(nocoin)只将open信号为真时列出S0ResetS2DS6[open]DS4[open]DS1NS3NS5[open]NS8[open]DS7[open]N4例：简单的自动售货机3、状态最简化：状态S4～S8具有等价，可合并成一个状态若每个状态表示接受到钱的数量最简化的符号状态转换表presentinputsnextoutputstateDNstateopen0¢000¢0015¢01010¢011––5¢005¢00110¢01015¢011––10¢0010¢00115¢01015¢011––15¢––15¢10¢[0]Reset5¢[0]NNN+D10¢[0]D15¢[open]D状态图状态转换表5当前状态输入次态输出tQ1Q0DNN1N0open0000000010101010011–––0100010011001011011–––1000100011101011011–––11––111例：简单的自动售货机4、进行状态分配4个状态，采用2位状态编码：0¢（00）、5¢（01）、10¢（10）、15¢（11）状态分配后的状态转换表6D1=Q1+D+Q0ND0=Q0’N+Q0N’+Q1N+Q1DOPEN=Q1Q0例：简单的自动售货机逻辑电路00110111XX1X1111Q1D1Q0ND01101011XX1X0111Q1D0Q0ND00100010XX1X0010Q1OpenQ0ND5、实现7简单的自动售货机(verilog)moduleautosell(clk,reset,D,N,open);inputclk,reset,D,N;outputopen;parametercell0=2'b00，cell5=2'b01,cell10=2'b10,cell15=2'b11;reg[1:0]state;reg[1:0]next_state;always@(posedgeclk)if(reset)state=cell0;elsestate=next_state;always@(NorDorstate)case(state)cell0:beginif(N)next_state=cell5;elseif(D)next_state=cell10;elsenext_state=cell0;endcell5:beginif(N)next_state=cell10;elseif(D)next_state=cell15;elsenext_state=cell5;endcell10:beginif(N)next_state=cell15;elseif(D)next_state=cell15;elsenext_state=cell10;endcell15:next_state=cell15;endcaseassignopen=(state==cell15);endmodule8有限输入串的识别器设计要求：有限输入串的识别器一个输入端(X)和一个输出端(Z)如果上次复位之后输入没有观察到…100…序列，那么只要在输入端检测到…010…的输入序列，输出端即为1步骤1:理解说明最好写出一些输入样本和输出行为:X:00101010010…Z:00010101000…X:11011010010…Z:00000001000…9有限输入串的识别器步骤2:画状态图假设用摩尔机实现先画出其必须识别的串010和100只有一个输入，则每个状态应该有两个分支S1[0]S2[0]01S3[1]0S4[0]10or1S5[0]00S6[0]S0[0]reset10有限输入串的识别器离开状态S3条件:已经识别到…010序列如果下一位输入为0，那么状态机已经接收到…100(终止)，到状态S6，即终止循环状态如果下一位输入为1，则状态机接收序列为…0101，…01(状态S2)状态S1条件:S1表示在接收到1之前的…0序列只要输入为0就会在此循环状态S4条件:S4描述连1序列的状态只要输入为1就会在此循环1...01...010...100S4[0]S1[0]S0[0]S2[0]101reset0or1S3[1]0S5[0]00S6[0]...1...01011有限输入串的识别器S2和S5仍然是不完整的条件S2=…01;如果下一个输入为1,就不再是010序列的前缀而成为终止序列的前缀(01)1(00)S4就是代表这种情况S5=…10;如果下一个输入为1,则接收机的序列为101，可能为序列010的前缀，S2就是代表这种情况尽可能复用状态寻找相同的意思最小的状态使代表状态的位数可以尽可能少一旦所有状态有完整的条件转换，意味着是一个最终状态图1...01...010...100S4[0]S1[0]S0[0]S2[0]101reset0or1S3[1]0S5[0]00S6[0]...1...010...101112有限输入串的识别器包括状态分配（或状态编码）的Verilog描述modulestring1(clk,X,rst,Z);inputclk,X,rst;outputZ;parameterS0=3'b000,S1=3'b001,S2=3'b010,S3=3'b011,S4=3'b100,S5=3'b101,S6=3'b110;reg[2:0]state;reg[2:0]next_state;always@(posedgeclk)if(rst)state=S0;elsestate=next_state;assignZ=(state==S3);always@(stateorX)case(state)S0:if(X)next_state=S4;elsenext_state=S1;S1:if(X)next_state=S2;elsenext_state=S1;S2:if(X)next_state=S4;elsenext_state=S3;S3:if(X)next_state=S2;elsenext_state=S6;S4:if(X)next_state=S4;elsenext_state=S5;S5:if(X)next_state=S2;elsenext_state=S6;S6:next_state=S6;default:next_state=S0;endcaseendmodule注意：模块名最好与文件名一致13有限输入串的识别器（测试程序）`timescale1ns/1ns`include./string1.vmodulestring1_tb;regclk,rst;reg[10:0]data;wirez,x;assignx=data[10];always#10clk=~clk;always@(posedgeclk)data={data[9:0],data[10]};initialbeginclk=0;rst=0;#2rst=1;#30rst=0;data='b1010_1001_00;#500$stop;endstring1m(clk,x,rst,z);endmodule14设计要求：有限输入串的识别器一个输入端(X)和一个输出端(Z)，只要在输入端检测到10010的输入序列，输出端即为1.modulestring10010(clk,X,rst,Z);inputclk,X,rst;outputZ;ParameterS0=3'b000,S1=3'b001,S2=3'b010,S4=3'b011,S5=3'b100;reg[2:0]state;reg[2:0]next_state;always@(posedgeclk)if(rst)state=S0;elsestate=next_state;assignZ=(state==S5);15always@(stateorX)case(state)S0:if(X)next_state=S1;elsenext_state=S0;S1:if(X)next_state=S1;elsenext_state=S2;S2:if(X)next_state=S1;elsenext_state=S3;S3:if(X)next_state=S4;elsenext_state=S0;S4:if(X)next_state=S1;elsenext_state=S5;S5:if(X)next_state=S1;elsenext_state=S3;defaultnext_state=S0;endcaseendmodule164比特序列检查器初始状态图该状态机具有单一输入X和输出Z，如果每次接收的4比特输入为0110或1010中的一个，则输出为1。状态机每次接收４比特输入后回到复位状态。假设用米利型机实现：只有在之前的４比特输入匹配指定串中的任意一个，输出才为１,状态机只在每４位比特一组输入后才决定是否输出１原始状态图17状态简化的等价状态等价状态:设Si、Sj为两个原始状态，当它们满足以下条件时等效。对于所有的输入组合①输出相同②它们的次态属于下列情况之一A．次态相同。Si、Sj的次态均为SkB．次态交错或为各自的现态。交错：Si的次态为Sj，Sj的次态为Si。为各自的现态：或Si的次态为Si，Sj的次态为Sj。等效类：由若干等效状态构成的集合。等效类中任意两个状态均等效。若存在关系，(S1，S2)，(S2，S3)→(S1，S3)，则S1、S2、S3属于同一等效类。记作(S1，S2)，(S2，S3)→|S1、S2、S3|。最大等效类：一个等效类不是其他等效类的子集，则该等效类为最大等效类。状态简化：对原始状态表进行简化，消去多余状态，求得最小化状态表。状态简化目标–识别和结合有等价行为的状态18状态化简方法行匹配法：一种良好的人工推导方法，但并不是总能得到最简状态表蕴含表法：容易用软件实现，并确实能找到可能的最优解可同时应用这两种方法：行匹配法能快速化简，减少状态数目。接下来用蕴含表法，由于只针对更少的状态，因此能迅速找到行匹配法遗漏的等价状态19行匹配算法概述算法概述（由状态转换表开始对状态进行化简）1.对状态进行分组，每组中的状态在相同的输入条件下具有相同的输出2.检查转换表，查看各组中的状态是否对于所有的输入组合都进入等价的次态，若等价可将它们合并成一个状态，并重新命名。3.然后将所有的状态转换过程都指向这些新状态4.重复以上过程，直到再也没有状态可以合并20状态表和行匹配法状态表：每个状态对应一行，每列对应不同的输入组合时的次态和输出21行匹配法检查状态转换表中的每一行，寻找在相同输入条件下具有相同次态和输出的状态S10和S12具有相同次态和输出的状态，可以合并成新状态名S10’