第8章 状态机.ppt

1、2020/7/14,1,计算机及具有内存或按照所存储信息执行一系列操作的其它数字系统统称为时序状态机，其电路可以通过时序逻辑进行建模。时序状态机的性能与组合逻辑不同，因为时序状态机的输出不仅取决于当前的输入值，而且取决于历史的输入。时序状态机被广泛应用于需要指定顺序操作的应用中，例如用时序状态机的输出控制计算机的同步数据通路及寄存器操作。所有的时序状态机都具有如图11-1所示的通用回馈结构，在这种结构中时序状态机的下一状态是由当前状态和当前输入一起形成的,2020/7/14,2,时序状态机可以按是否受一个公共的时钟控制（钟控）分为同步状态机和异步状态机. 如果具有钟控则为同步状态机，反之为异步

2、状态机； 根据状态数目是否有限可以将时序状态机分为有限状态机和无限状态机。我们只讨论同步有限状态机（Finite State Machine，FSM），它在数字系统中应用很广泛， 例如，它可以作为计算单元与处理中的数据通路控制器。同步有限状态机的特点是具有有限个状态，并且状态的转换是由时钟驱动的（钟控）,2020/7/14,3,有限状态机有两种基本类型：米利（Mealy）机和摩尔Moore）机， 米利机的下一状态和输出取决于当前状态和当前输入； 摩尔机的下一状态取决于当前状态和当前输入，但其输出仅取决于当前状态。 这两类有限状态机的下一状态和输出都是由组合逻辑电路形成的。 1. 米利（Meal

3、y）机 米利（Mealy）机的结构如图11-2所示。由图11-2可见，米利（Mealy）机的下一状态和输出都取决于当前状态和当前输入,8.1 有限状态机（FSM）的分类,2020/7/14,4,2. 摩尔（Moore）机,摩尔（Moore）机的结构如图11-3所示。,由图11-3可见，摩尔（Moore）机的下一状态取决于当前状态和当前输入，但其输出仅取决于当前状态。,8.3 有限状态机常用的描述、开发方法,状态转移图（State Transition Graph，STG）是一种有向图，图中带有标记的节点或顶点与时序状态机的状态一一对应。当系统处于弧线起点的状态时，用有向边或弧线表示在输入信号的

4、作用下可能发生的状态转移。米利机STG的顶点用状态进行标记，状态转移图的有向边有下面两种标记方法： （1）用能够导致状态向指定的下一状态转移的输入信号来标记。 （2）在当前状态下，用由输入信号确定的输出来进行标记。,有限状态机可以借助时序图、状态表、状态图以及ASM图进行系统的描述与设计。时序图可用于说明系统中及系统与周围环境的接口中信号的有效输入与状态转移之间的关系。例如，静态随机访问内存的写周期可以用一个时序图加以说明，该时序图表明存储单元的地址必须在写使能信号有效之前就已经被确定。在面向综合的设计方法中，设计的时序指标构成了对必须由设计工具实现的电路的限制。 状态表或状态转移表以表格的形

5、式表示在当前状态和输入的各种组合下状态机的下一状态和输出。,摩尔机的状态转移图与米利机相类似，但它的输出是由各状态的顶点来表示的，而不是在弧线上表示。算法状态机（ASM）图是时序状态机功能的一种抽象，是模拟其行为特性的关键工具。它类似于软件流程图，但显示的是计算动作（如寄存器操作）的时间顺序，以及在状态机输入影响下发生的时序步骤。ASM图描述的是状态机的行为动作，而不是存储组件所存储的内容。有时候用机器工作期间的行为动作来描述状态机的状态，比起用状态机产生的数据进行描述更为方便也更重要。例如，我们可以用16位的计数器内容来描述计数器本身，我们也可以将它视为一个数据信道单元来描述它的动作（如计数

6、、等待等）。在描述时序状态机的行为方面，以及设计状态机来控制数据信道方面，ASM图是非常有帮助的。,ASMD图是ASM图的扩展。状态机的一个重要应用就是控制时序状态机数据信道上的寄存器操作，而该时序状态机已被划分为控制器和数据信道。控制器可以用ASM图来描述，我们修改ASM图的目的是把它连接到状态机所控制的数据信道上。当控制器的状态沿着通道发生转移时，通过标注每个数据信道来指出那些在相关数据信道单元中所发生的寄存器操作。以这种方式连接到数据信道的ASM图被称为算法状态机和数据信道（ASMD）图。在把时序状态机数据信道的设计从控制器的设计中分离出来，并在两个单元之间保持清晰联系的情况下，ASMD

7、图有助于阐明这样的时序状态机设计方法。与状态转移并行发生的寄存器操作是在图的通道上标注的，而不是在通道上的条件框或状态框中标注的，因为这些寄存器不是控制器的一部分。由控制器产生的输出是那些控制数据信道寄存器的信号，以及引发 ASM图上标注的寄存器操作的信号。,8.4基于状态转移图（STG）的设计1. 设计要点,对于一个同步时序状态机的给定STG，设计的任务就是确定下一状态和输出逻辑。如果用一个二进制代码来表示时序状态机的状态，那么其值可以存储在触发器中。在时钟的各个有效沿处，状态保持触发器的输入变成下一个时钟周期的状态。同步时序状态机的设计就是要根据机器的状态和外部输入来确定能形成触发器输入的

8、逻辑，该逻辑为组合逻辑，并且应该是最简逻辑。对于有效的STG而言，其每个顶点必须表示一个唯一的状态；每个弧线则表示在指定输入信号的作用下，从给定状态到下一个状态的转移，并且从一个节点出发的各弧线必须对应一个唯一的输入。通常，与从一个节点出发的一组弧线有关的布尔条件必须满足和为1（即状态转移图必须考虑到从一个节点出发的所有可能的状态转移），并且在给定状态下与输入变量判定有关的每个分支条件必须对应于一条唯一的弧线（实时序状态机仅可以由一个节点经过一条弧线转移到下一个状态）。根据时钟到来之前的状态值和当前输入值，由同步时序状态机的STG所表示的状态转移将在时钟信号的有效沿处发生。,有限状态机的系统设

9、计方法通常包括以下几个步骤,（1）构建状态机的STG。 （2）消去等价状态。 （3）选取状态码（如二进制代码）。 （4）编写状态表。 （5）推出描述保持状态位的D触发器的输入布尔方程。 （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,状态转移表：,状态简化：,简化

10、,两个状态如果“等价”，则这两个状态可以合并为一个状态。两个状态等价的条件是： (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; pa

11、rameter idle=b00,a=b01, b=b10,c=b11,d=b100; assign z=(state=d 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.确定

12、原始状态转移图和原始状态表。,2.状态简化；,3.状态编码；,4.存储电路类型的选择。,【例6-6】设计模6同步计数器,6.3.2 采用SSI设计同步计数器,定义：S0=000 S1=001 S2=011 S3=111 S4=110 S5=100,0 1 3 7 6 4,2. 建模实例,利用STG构建一个BCD码到余3码的转换器 一个串行发送的BCD码Bin被转换成为一个余3码串行比特流Bout是这样得到的：给BCD码对应的十进制数加上310，并将其转换为等价的二进制数就得到了该十进制数的余3码，表11-1给出了十进制数及其相应的4位BCD码和余3码。余3码是自补码，即余3码的9补，在硬件上可

13、以通过对码字逐位取反得到（即取码字的二进制反码）。例如610的余3码为10012，逐位取反后为01102，这就是310的余3码。余3码的这一特性使得计算以BCD形式编码的基数减1的反码变得很容易，这类似于减去带符号二进制数可以通过给减数加上被减数的二进制补码实现，二进制补码可由被减数的二进制反码加1得到。于是，610的十进制补码可由610的余3码10012逐位取反后再加1得到，01102+00012=01112，即410的余3码。,表11-1 BCD码与余3码,串行比特流的BCD码到余3码转换器可以用米利型FSM实现。图11-4给出了输入该转换器的串行比特流Bin，以及转换器输出的相应余3码的

14、串行比特流。应注意Bin是先从最低位LSB（Least Significant Bit）开始按顺序发送的，因此要对Bin和Bout进行正确译码应该多加小心。波形中各位的顺序是随时间t的增加从左向右行进的，左边是最低位LSB，右边是最高位MSB（Most Significant Bit）。在这种转换器中，波形的位顺序必须反转，如图11-4所示，从而形成发送和接收码字的二进制数值。,如图11-4所示，从而形成发送和接收码字的二进制数值。,实现表11-1中的串行转换器的STG如图11-5所示，其异步复位信号与时钟无关，一旦该信号有效，状态机就会转移到S_0状态，复位后状态机在第一个时钟沿从S_0状态

15、开始动作，并对输入位流的连续4位字段重复进行加00112的操作。码字的LSB是输入样值序列的第一位，也是所产生的输出码字的第一位。表11-2的状态表以表格的形式给出了与状态转移图相同的信息。符号-/-表示某种不确定的或不可能的条件。 表11-2 用米利型FSM实现的BCD码到余3码串行转换器状态表,一般而言，用于表示状态机状态的触发器数目必须足够多，以满足状态的二进制表示，如具有12个状态的时序状态机至少需要4个触发器。对于一组给定的触发器，需要为各个状态指定唯一的二进制代码字，而且所用码字的数量在给各状态指定二进制代码的过程中将随着触发器的数目呈指数增长，如何选定也将直接影响到实现状态机所需

16、逻辑的复杂度。本例中为各状态分配的码字如表11-3所示，采用简单的（顺序的）3位二进制代码为状态机的7个状态进行编码，表11-4则给出了下一状态编码和输出表。,表11-3 状态分配表,表11-4 下一状态编码与输出表,下一步将研究状态编码的每个位以及作为当前状态位和输入（Bin）函数的输出卡诺图，这些卡诺图及其相应的布尔方程如图11-6所示，表中的不确定输入可作为任意项处理。各方程已分别进行了化简，尽管这样做未必会得到逻辑的最优（逻辑与面积之比）实现。,modulemealy_fsm1(clk,Bin,Bout); inputclk,Bin; outputBout; regq0,q1,q2;

17、always(posedgeclk) begin q0=q1_bar; q1=q0; q2=(q1_bar endmodule,通过上例可以看到，基于布尔方程的状态机建模需要通过卡诺图进行化简。如果状态机逻辑比较复杂，用卡诺图化简就变得十分困难。因此，在实际应用中的状态机通常采用行为级建模。例如，上例的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; inp

18、utclk,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; Bo

19、ut=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

20、: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 endmodule,通过上例可知，基于行为级的状态机建模提高了程序代码的编程效率、可读性和可维护性。但是，采用化简后的布尔方程描述的状态机则占用最小的硬件资源,11.1.4 基于算法状态机（ASM）图的设计,1. 算法状态机图 算法状态机图是时序状态机功能的一种抽象，是模拟其行为的关键工具，类似于软件流程图。但是显示的是计算动作的

21、时间顺序，以及在状态机输入影响下发生的时序步骤。ASM图描述的是状态机的行为动作，而不是存储组件所存储的内容。 在描述时序状态机的行为方面，以及设计状态机来控制数据信道方面，ASM图是非常有用的。ASM图由如图11-9所示的基本元素组成：状态框、条件输出或寄存器操作框及判决框。,ASM图的基本单元是ASM块，如图11-10所示。它包含一个状态框、一个可选的判决框和在分支信道上放置的条件框。ASM块图等同于状态机的时序。对一个给定的ASM图，用状态转移图也可以表示同样的信息。,两种类型的状态机（米利型和摩尔型）都可以用ASM图表示。摩尔型状态机的输出常常在状态框中列出。条件输出放置在条件框中，条

22、件框中还可以表示状态转移时的寄存器操作。在数据信道中的判决框隐含了优先权解碼。,状态机具有同步复位到空闲状态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,Lo

23、ad; 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=