状态机说课材料.ppt

状态机2022/11/2022.2.摩尔（摩尔（MooreMoore）机）机摩尔（Moore）机的结构如图11-3所示。由图11-3可见，摩尔（Moore）机的下一状态取决于当前状态和当前输入，但其输出仅取决于当前状态。8.3 有限状态机常用的描述、开发方法有限状态机常用的描述、开发方法n n状态转移图（状态转移图（State Transition GraphState Transition Graph，STGSTG）是）是一种有向图，图中带有标记的节点或顶点与时序一种有向图，图中带有标记的节点或顶点与时序状态机的状态一一对应。当系统处于弧线起点的状态机的状态一一对应。当系统处于弧线起点的状态时，用有向边或弧线表示在输入信号的作用状态时，用有向边或弧线表示在输入信号的作用下可能发生的状态转移。米利机下可能发生的状态转移。米利机STGSTG的顶点用状态的顶点用状态进行标记，状态转移图的有向边有下面两种标记进行标记，状态转移图的有向边有下面两种标记方法：方法：n n（1 1）用能够导致状态向指定的下一状态转移的输）用能够导致状态向指定的下一状态转移的输入信号来标记。入信号来标记。n n（2 2）在当前状态下，用由输入信号确定的输出来）在当前状态下，用由输入信号确定的输出来进行标记。进行标记。n n有限状态机可以借助时序图、状态表、状态图以及有限状态机可以借助时序图、状态表、状态图以及ASMASM图进行系统的描述与设计。时序图可用于说明系图进行系统的描述与设计。时序图可用于说明系统中及系统与周围环境的接口中信号的有效输入与统中及系统与周围环境的接口中信号的有效输入与状态转移之间的关系。例如，静态随机访问内存的状态转移之间的关系。例如，静态随机访问内存的写周期可以用一个时序图加以说明，该时序图表明写周期可以用一个时序图加以说明，该时序图表明存储单元的地址必须在写使能信号有效之前就已经存储单元的地址必须在写使能信号有效之前就已经被确定。在面向综合的设计方法中，设计的时序指被确定。在面向综合的设计方法中，设计的时序指标构成了对必须由设计工具实现的电路的限制。标构成了对必须由设计工具实现的电路的限制。n n状态表或状态转移表以表格的形式表示在当前状态状态表或状态转移表以表格的形式表示在当前状态和输入的各种组合下状态机的下一状态和输出。和输入的各种组合下状态机的下一状态和输出。摩尔机的状态转移图与米利机相类似，但它的输出摩尔机的状态转移图与米利机相类似，但它的输出是由各状态的顶点来表示的，而不是在弧线上表示。算是由各状态的顶点来表示的，而不是在弧线上表示。算法状态机（法状态机（ASMASM）图是时序状态机功能的一种抽象，是）图是时序状态机功能的一种抽象，是模拟其行为特性的关键工具。它类似于软件流程图，但模拟其行为特性的关键工具。它类似于软件流程图，但显示的是计算动作（如寄存器操作）的时间顺序，以及显示的是计算动作（如寄存器操作）的时间顺序，以及在状态机输入影响下发生的时序步骤。在状态机输入影响下发生的时序步骤。ASMASM图描述的是图描述的是状态机的行为动作，而不是存储组件所存储的内容。有状态机的行为动作，而不是存储组件所存储的内容。有时候用机器工作期间的行为动作来描述状态机的状态，时候用机器工作期间的行为动作来描述状态机的状态，比起用状态机产生的数据进行描述更为方便也更重要。比起用状态机产生的数据进行描述更为方便也更重要。例如，我们可以用例如，我们可以用1616位的计数器内容来描述计数器本身，位的计数器内容来描述计数器本身，我们也可以将它视为一个数据信道单元来描述它的动作我们也可以将它视为一个数据信道单元来描述它的动作（如计数、等待等）。在描述时序状态机的行为方面，（如计数、等待等）。在描述时序状态机的行为方面，以及设计状态机来控制数据信道方面，以及设计状态机来控制数据信道方面，ASMASM图是非常有图是非常有帮助的。帮助的。n nASMDASMD图是图是ASMASM图的扩展。状态机的一个重要应用就是控制时图的扩展。状态机的一个重要应用就是控制时序状态机数据信道上的寄存器操作，而该时序状态机已被划序状态机数据信道上的寄存器操作，而该时序状态机已被划分为控制器和数据信道。控制器可以用分为控制器和数据信道。控制器可以用ASMASM图来描述，我们图来描述，我们修改修改ASMASM图的目的是把它连接到状态机所控制的数据信道上。图的目的是把它连接到状态机所控制的数据信道上。当控制器的状态沿着通道发生转移时，通过标注每个数据信当控制器的状态沿着通道发生转移时，通过标注每个数据信道来指出那些在相关数据信道单元中所发生的寄存器操作。道来指出那些在相关数据信道单元中所发生的寄存器操作。以这种方式连接到数据信道的以这种方式连接到数据信道的ASMASM图被称为算法状态机和数图被称为算法状态机和数据信道（据信道（ASMDASMD）图。在把时序状态机数据信道的设计从控制）图。在把时序状态机数据信道的设计从控制器的设计中分离出来，并在两个单元之间保持清晰联系的情器的设计中分离出来，并在两个单元之间保持清晰联系的情况下，况下，ASMDASMD图有助于阐明这样的时序状态机设计方法。与状图有助于阐明这样的时序状态机设计方法。与状态转移并行发生的寄存器操作是在图的通道上标注的，而不态转移并行发生的寄存器操作是在图的通道上标注的，而不是在通道上的条件框或状态框中标注的，因为这些寄存器不是在通道上的条件框或状态框中标注的，因为这些寄存器不是控制器的一部分。由控制器产生的输出是那些控制数据信是控制器的一部分。由控制器产生的输出是那些控制数据信道寄存器的信号，以及引发道寄存器的信号，以及引发 ASMASM图上标注的寄存器操作的信图上标注的寄存器操作的信号。号。8.4基于状态转移图（基于状态转移图（STG）的设计）的设计1.设计要点设计要点n n对于一个同步时序状态机的给定对于一个同步时序状态机的给定STGSTG，设计的任务就是确定下，设计的任务就是确定下一状态和输出逻辑。如果用一个二进制代码来表示时序状态一状态和输出逻辑。如果用一个二进制代码来表示时序状态机的状态，那么其值可以存储在触发器中。在时钟的各个有机的状态，那么其值可以存储在触发器中。在时钟的各个有效沿处，状态保持触发器的输入变成下一个时钟周期的状态。效沿处，状态保持触发器的输入变成下一个时钟周期的状态。同步时序状态机的设计就是要根据机器的状态和外部输入来同步时序状态机的设计就是要根据机器的状态和外部输入来确定能形成触发器输入的逻辑，该逻辑为组合逻辑，并且应确定能形成触发器输入的逻辑，该逻辑为组合逻辑，并且应该是最简逻辑。对于有效的该是最简逻辑。对于有效的STGSTG而言，其每个顶点必须表示一而言，其每个顶点必须表示一个唯一的状态；每个弧线则表示在指定输入信号的作用下，个唯一的状态；每个弧线则表示在指定输入信号的作用下，从给定状态到下一个状态的转移，并且从一个节点出发的各从给定状态到下一个状态的转移，并且从一个节点出发的各弧线必须对应一个唯一的输入。通常，与从一个节点出发的弧线必须对应一个唯一的输入。通常，与从一个节点出发的一组弧线有关的布尔条件必须满足和为一组弧线有关的布尔条件必须满足和为1 1（即状态转移图必须（即状态转移图必须考虑到从一个节点出发的所有可能的状态转移），并且在给考虑到从一个节点出发的所有可能的状态转移），并且在给定状态下与输入变量判定有关的每个分支条件必须对应于一定状态下与输入变量判定有关的每个分支条件必须对应于一条唯一的弧线（实时序状态机仅可以由一个节点经过一条弧条唯一的弧线（实时序状态机仅可以由一个节点经过一条弧线转移到下一个状态）。根据时钟到来之前的状态值和当前线转移到下一个状态）。根据时钟到来之前的状态值和当前输入值，由同步时序状态机的输入值，由同步时序状态机的STGSTG所表示的状态转移将在时钟所表示的状态转移将在时钟信号的有效沿处发生。信号的有效沿处发生。有限状态机的系统设计方法通常包有限状态机的系统设计方法通常包括以下几个步骤括以下几个步骤 n n（1）构建状态机的STG。n n（2）消去等价状态。n n（3）选取状态码（如二进制代码）。n n（4）编写状态表。n n（5）推出描述保持状态位的D触发器的输入布尔方程。n n（6）利用卡诺图优化布尔方程。【例例1】设设计计一一个个串串行行数数据据检检测测器器，在在连连续续输输入入4个个或或4个以上的个以上的1时输出时输出1,否则输出否则输出0。解解:(串行数据输入方向为：串行数据输入方向为：从左至右。从左至右。)逻辑抽象逻辑抽象 输入输入X(串行数据串行数据)Sn电路现态电路现态 输出输出Z(检测结果检测结果)Sn+1电路次态电路次态定义：定义：S0没有输入没有输入1;0 S1输入输入1个个1;1 S2连续输入连续输入2个个1;11 S3连续输入连续输入3个个1;111 S4连续输入连续输入4个或个或4个以上个个以上个1;1111状态转移表：状态转移表：状态简化状态简化：简化简化两个状态如果两个状态如果“等价等价”，则这，则这两个状态可以合并为一个状态。两个状态可以合并为一个状态。两个状态等价的条件是：两个状态等价的条件是：(1)在所有输入条件下，两在所有输入条件下，两个状态对应输出完全相同；个状态对应输出完全相同；(2)在所有输入条件下，两在所有输入条件下，两个状态转移效果完全相同。个状态转移效果完全相同。状态分配状态分配M=4(状态状态)选选n=2，定定义义:S000、S101、S211、S310选定选定FF 由状态转换表有由状态转换表有:选定选定FF 由状态转换表有由状态转换表有:选选JK触发器触发器由驱动方程和输出方程画逻辑电路图由驱动方程和输出方程画逻辑电路图检查自启动检查自启动 该电路没有无效状态，不用检查自启动。该电路没有无效状态，不用检查自启动。程序程序module stat(x,z,clk,rst);input x,clk,rst;output z;reg 1:0 state;/wire z;parameter idle=b00,a=b01,b=b10,c=b11,d=b100;assign z=(state=d&x=1)?1:0;always(posedge clk or negedge rst)if(!rst)begin state=idle;end else case(state)idle:if(x=1)begin state=a;end else begin state=idle;end a:if(x=1)begin state=b;end else begin state=idle;end b:if(x=1)begin state=c;end else begin state=idle;end c:if(x=1)begin state=d;end else begin state=idle;end default:state=idle;endcase endmodule总结：时序逻辑电路设计总结：时序逻辑电路设计主要有主要有4个过程：个过程：1.确定原始状态转移图和原始状态表。确定原始状态转移图和原始状态表。2.状态简化；状态简化；3.状态编码；状态编码；4.存储电路类型的选择。存储电路类型的选择。【例例6-6】设计模设计模6 6同步计数器同步计数器6.3.2 采用采用SSI设计同步计数器设计同步计数器 定义：定义：S0=000 S1=001 S2=011 S3=111 S4=110 S5=100CPCP QQ3 3n nQQ2 2n nQQ1 1n nQQ3 3n+1n+1QQ2 2n+1n+1QQ1 1n+1n+1Z Z0 00 00 00 00 00 01 10 01 10 00 01 10 01 11 10 02 20 01 11 11 11 11 10 03 31 11 11 11 11 10 00 04 41 11 10 01 10 00 00 05 51 10 00 00 00 00 01 10137642.建模实例建模实例n n利用利用STGSTG构建一个构建一个BCDBCD码到余码到余3 3码的转换器码的转换器n n一个串行发送的一个串行发送的BCDBCD码码BinBin被转换成为一个余被转换成为一个余3 3码串行比特码串行比特流流BoutBout是这样得到的：给是这样得到的：给BCDBCD码对应的十进制数加上码对应的十进制数加上310310，并将其转换为等价的二进制数就得到了该十进制数的余，并将其转换为等价的二进制数就得到了该十进制数的余3 3码，表码，表11-111-1给出了十进制数及其相应的给出了十进制数及其相应的4 4位位BCDBCD码和余码和余3 3码。码。余余3 3码是自补码，即余码是自补码，即余3 3码的码的9 9补，在硬件上可以通过对码补，在硬件上可以通过对码字逐位取反得到（即取码字的二进制反码）。例如字逐位取反得到（即取码字的二进制反码）。例如610610的的余余3 3码为码为1001210012，逐位取反后为，逐位取反后为0110201102，这就是，这就是310310的余的余3 3码。码。余余3 3码的这一特性使得计算以码的这一特性使得计算以BCDBCD形式编码的基数减形式编码的基数减1 1的反的反码变得很容易，这类似于减去带符号二进制数可以通过给码变得很容易，这类似于减去带符号二进制数可以通过给减数加上被减数的二进制补码实现，二进制补码可由被减减数加上被减数的二进制补码实现，二进制补码可由被减数的二进制反码加数的二进制反码加1 1得到。于是，得到。于是，610610的十进制补码可由的十进制补码可由610610的余的余3 3码码1001210012逐位取反后再加逐位取反后再加1 1得到，得到，01102+00012=0111201102+00012=01112，即，即410410的余的余3 3码。码。表表11-1 BCD码与余码与余3码码十进制数字8421码（BCD码）余3码000000011100010100200100101300110110401000111501011000601101001701111010810001011910011100n n串行比特流的串行比特流的BCDBCD码到余码到余3 3码转换器可以用米利型码转换器可以用米利型FSMFSM实现。图实现。图11-411-4给出了输入该转换器的串行比特给出了输入该转换器的串行比特流流BinBin，以及转换器输出的相应余，以及转换器输出的相应余3 3码的串行比特码的串行比特流。应注意流。应注意BinBin是先从最低位是先从最低位LSBLSB（Least Significant Least Significant BitBit）开始按顺序发送的，因此要对）开始按顺序发送的，因此要对BinBin和和BoutBout进行进行正确译码应该多加小心。波形中各位的顺序是随正确译码应该多加小心。波形中各位的顺序是随时间时间t t的增加从左向右行进的，左边是最低位的增加从左向右行进的，左边是最低位LSBLSB，右边是最高位，右边是最高位MSBMSB（Most Significant BitMost Significant Bit）。在这）。在这种转换器中，波形的位顺序必须反转，如图种转换器中，波形的位顺序必须反转，如图11-411-4所示，从而形成发送和接收码字的二进制数值。所示，从而形成发送和接收码字的二进制数值。如图如图11-4所示，从而形成发送和接收所示，从而形成发送和接收码字的二进制数值。码字的二进制数值。n n实现表实现表11-111-1中的串行转换器的中的串行转换器的STGSTG如图如图11-511-5所示，所示，其异步复位信号与时钟无关，一旦该信号有效，其异步复位信号与时钟无关，一旦该信号有效，状态机就会转移到状态机就会转移到S_0S_0状态，复位后状态机在第一状态，复位后状态机在第一个时钟沿从个时钟沿从S_0S_0状态开始动作，并对输入位流的连状态开始动作，并对输入位流的连续续4 4位字段重复进行加位字段重复进行加0011200112的操作。码字的的操作。码字的LSBLSB是是输入样值序列的第一位，也是所产生的输出码字输入样值序列的第一位，也是所产生的输出码字的第一位。表的第一位。表11-211-2的状态表以表格的形式给出了的状态表以表格的形式给出了与状态转移图相同的信息。符号与状态转移图相同的信息。符号-/-/-表示某种不表示某种不确定的或不可能的条件。确定的或不可能的条件。n n表表11-2 11-2 用米利型用米利型FSMFSM实现的实现的BCDBCD码到余码到余3 3码串行转码串行转换器状态表换器状态表下一状态/输出表状 态下一状态/输出输 入01S_0S_1/1S_2/0S_1S_3/1S_4/0S_2S_4/0S_4/1S_3S_5/0S_5/1S_4S_5/1S_6/0S_5S_0/0S_0/1S_6S_0/1-/-n n一般而言，用于表示状态机状态的触发器数目必一般而言，用于表示状态机状态的触发器数目必须足够多，以满足状态的二进制表示，如具有须足够多，以满足状态的二进制表示，如具有1212个状态的时序状态机至少需要个状态的时序状态机至少需要4 4个触发器。对于一个触发器。对于一组给定的触发器，需要为各个状态指定唯一的二组给定的触发器，需要为各个状态指定唯一的二进制代码字，而且所用码字的数量在给各状态指进制代码字，而且所用码字的数量在给各状态指定二进制代码的过程中将随着触发器的数目呈指定二进制代码的过程中将随着触发器的数目呈指数增长，如何选定也将直接影响到实现状态机所数增长，如何选定也将直接影响到实现状态机所需逻辑的复杂度。本例中为各状态分配的码字如需逻辑的复杂度。本例中为各状态分配的码字如表表11-311-3所示，采用简单的（顺序的）所示，采用简单的（顺序的）3 3位二进制代位二进制代码为状态机的码为状态机的7 7个状态进行编码，表个状态进行编码，表11-411-4则给出了则给出了下一状态编码和输出表。下一状态编码和输出表。表表11-3 状态分配表状态分配表状态分配表q2q1q0状 态000S_0001S_1010S_6011S_4100101S_2110S_5111S_3表11-4 下一状态编码与输出表下一状态编码/输出表状 态下一状态输 出q2q1q0q2+q1+q0+输 入输 入0101S_000000110110S_100111101110S_210101101101S_311111011001S_401111001010S_511000000001S_60100001100n n下一步将研究状态编码的每个位以及作为当前状态位和输入（Bin）函数的输出卡诺图，这些卡诺图及其相应的布尔方程如图11-6所示，表中的不确定输入可作为任意项处理。各方程已分别进行了化简，尽管这样做未必会得到逻辑的最优（逻辑与面积之比）实现。modulemealy_fsm1(clk,Bin,Bout);inputclk,Bin;outputBout;regq0,q1,q2;always(posedgeclk)begin q0=q1_bar;q1=q0;q2=(q1_bar&q0_bar&Bin)&(q2_bar&q0&(Bin)&(q2&q1&q0);end wireq0_bar=q0;wireq1_bar=q1;wireq2_bar=q2;assignBout=(q2_bar&(Bin)&(q2&Bin);endmodulen n通过上例可以看到，基于布尔方程的状态机建模需要通过卡诺图进行化简。如果状态机逻辑比较复杂，用卡诺图化简就变得十分困难。因此，在实际应用中的状态机通常采用行为级建模。例如，上例的BCD码转余3码可以用下面的行为级语句建模。modulemealy_fsm2(clk,rst,Bin,Bout);parameterS_0=3b000,S_1=3b001,S_2=3b010,S_3=3b011,S_4=3b100,S_5=3b101,S_6=3b110;inputclk,rst,Bin;outputBout;regBout;reg2:0current_state,next_state;always(posedgeclk)begin if(rst)current_state=S_0;elsecurrent_state=next_state;end always(*)case(current_state)S_0:if(Bin)begin next_state=S_2;Bout=0;end elsebegin next_state=S_1;Bout=1;end S_1:if(Bin)begin next_state=S_4;Bout=0;end elsebegin next_state=S_3;Bout=1;end S_2:if(Bin)begin next_state=S_4;Bout=1;end elsebegin next_state=S_4;Bout=0;end S_3:if(Bin)begin next_state=S_5;Bout=1;end elsebegin next_state=S_5;Bout=0;end S_4:if(Bin)begin next_state=S_6;Bout=0;end elsebegin next_state=S_5;Bout=1;end S_5:if(Bin)begin next_state=S_0;Bout=1;end elsebegin next_state=S_0;Bout=0;end S_6:if(!Bin)begin next_state=S_0;Bout=1;end endcase endmodulen n通过上例可知，基于行为级的状态机建模提高了程序代码的编程效率、可读性和可维护性。但是，采用化简后的布尔方程描述的状态机则占用最小的硬件资源 11.1.4 基于算法状态机（基于算法状态机（ASM）图的）图的设计设计n n1.1.算法状态机图算法状态机图n n算法状态机图是时序状态机功能的一种抽象，是算法状态机图是时序状态机功能的一种抽象，是模拟其行为的关键工具，类似于软件流程图。但模拟其行为的关键工具，类似于软件流程图。但是显示的是计算动作的时间顺序，以及在状态机是显示的是计算动作的时间顺序，以及在状态机输入影响下发生的时序步骤。输入影响下发生的时序步骤。ASMASM图描述的是状图描述的是状态机的行为动作，而不是存储组件所存储的内容。态机的行为动作，而不是存储组件所存储的内容。n n在描述时序状态机的行为方面，以及设计状态机在描述时序状态机的行为方面，以及设计状态机来控制数据信道方面，来控制数据信道方面，ASMASM图是非常有用的。图是非常有用的。ASMASM图由如图图由如图11-911-9所示的基本元素组成：状态框、所示的基本元素组成：状态框、条件输出或寄存器操作框及判决框。条件输出或寄存器操作框及判决框。ASM图的基本单元是ASM块，如图11-10所示。它包含一个状态框、一个可选的判决框和在分支信道上放置的条件框。ASM块图等同于状态机的时序。对一个给定的ASM图，用状态转移图也可以表示同样的信息。两种类型的状态机（米利型和摩尔型）都可以用ASM图表示。摩尔型状态机的输出常常在状态框中列出。条件输出放置在条件框中，条件框中还可以表示状态转移时的寄存器操作。在数据信道中的判决框隐含了优先权解碼。n n状态机具有同步复位到空闲状态S_IDLE功能，一旦En信号有效则状态机从S_IDLE状态转到S_1状态，同时将数据加载到移位寄存器P1，P0中。在下一个时钟周期，状态机进入S_FULL状态。然后等待Load信号，一旦有效则将输入数据加载到移位寄存器中，同时状态机转到S_1状态。moduledecimator(clk,rst,En,Load,Data,Dout);parameterS_IDLE=2b00,S_1=2b01,S_FULL=2b10,S_WAIT=2b11;inputclk,rst,En,Load;input7:0Data;output7:0Dout;reg7:0P0,P1,Dout;reg1:0state;always(posedgeclk)begin if(rst)begin state=S_IDLE;P1=8h00;P0=8h00;end elsecase(state)S_IDLE:if(En)begin state=S_1;P1=Data;P0=P1;end S_1:begin state=S_FULL;P1=Data;P0=P1;end S_FULL:if(Load)begin if(En)begin state=S_1;P1=8h00;P0=8h00;end elsebegin state=S_IDLE;P1=8h00;P0=8h00;end Dout=P0;end elsebegin state=S_WAIT;end S_WAIT:if(Load)begin if(En)begin state=S_1;P1=Data;P0=P1;end elsebegin state=S_IDLE;P1=8h00;P0=8h00;end Dout=P0;end default:begin state=S_IDLE;P1=8h00;P0=8h00;end endcase end endmodulemodule statem(clk,in,reset,out);input clk,in,reset;output 3:0 out;reg 3:0 out;reg 1:0 state;parameter zero=0,one=1,two=2,three=3;always(state)begin case(state)zero:out=4b0000;one:out=4b0001;two:out=4b0010;three:out=4b0100;default:out=4b0000;endcase endalways(posedge clk or posedge reset)begin if(reset)state=zero;else case(state)zero:state=one;one:if(in)state=zero;else state=two;two:state=three;three:state=zero;endcase endendmodule画出其状态图及功能？此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢