第8章 状态机

2020/1/181计算机及具有内存或按照所存储信息执行一系列操作的其它数字系统统称为时序状态机，其电路可以通过时序逻辑进行建模。时序状态机的性能与组合逻辑不同，因为时序状态机的输出不仅取决于当前的输入值，而且取决于历史的输入。时序状态机被广泛应用于需要指定顺序操作的应用中，例如用时序状态机的输出控制计算机的同步数据通路及寄存器操作。所有的时序状态机都具有如图11-1所示的通用回馈结构，在这种结构中时序状态机的下一状态是由当前状态和当前输入一起形成的2020/1/182时序状态机可以按是否受一个公共的时钟控制（钟控）分为同步状态机和异步状态机.1.如果具有钟控则为同步状态机，反之为异步状态机；2.根据状态数目是否有限可以将时序状态机分为有限状态机和无限状态机。我们只讨论同步有限状态机（FiniteStateMachine，FSM），它在数字系统中应用很广泛，•例如，它可以作为计算单元与处理中的数据通路控制器。同步有限状态机的特点是具有有限个状态，并且状态的转换是由时钟驱动的（钟控）2020/1/183有限状态机有两种基本类型：米利（Mealy）机和摩尔Moore）机，1.米利机的下一状态和输出取决于当前状态和当前输入；2.摩尔机的下一状态取决于当前状态和当前输入，但其输出仅取决于当前状态。这两类有限状态机的下一状态和输出都是由组合逻辑电路形成的。1.米利（Mealy）机米利（Mealy）机的结构如图11-2所示。由图11-2可见，米利（Mealy）机的下一状态和输出都取决于当前状态和当前输入8.1有限状态机（FSM）的分类2020/1/1842.摩尔（Moore）机摩尔（Moore）机的结构如图11-3所示。由图11-3可见，摩尔（Moore）机的下一状态取决于当前状态和当前输入，但其输出仅取决于当前状态。8.3有限状态机常用的描述、开发方法状态转移图（StateTransitionGraph，STG）是一种有向图，图中带有标记的节点或顶点与时序状态机的状态一一对应。当系统处于弧线起点的状态时，用有向边或弧线表示在输入信号的作用下可能发生的状态转移。米利机STG的顶点用状态进行标记，状态转移图的有向边有下面两种标记方法：（1）用能够导致状态向指定的下一状态转移的输入信号来标记。（2）在当前状态下，用由输入信号确定的输出来进行标记。有限状态机可以借助时序图、状态表、状态图以及ASM图进行系统的描述与设计。时序图可用于说明系统中及系统与周围环境的接口中信号的有效输入与状态转移之间的关系。例如，静态随机访问内存的写周期可以用一个时序图加以说明，该时序图表明存储单元的地址必须在写使能信号有效之前就已经被确定。在面向综合的设计方法中，设计的时序指标构成了对必须由设计工具实现的电路的限制。状态表或状态转移表以表格的形式表示在当前状态和输入的各种组合下状态机的下一状态和输出。摩尔机的状态转移图与米利机相类似，但它的输出是由各状态的顶点来表示的，而不是在弧线上表示。算法状态机（ASM）图是时序状态机功能的一种抽象，是模拟其行为特性的关键工具。它类似于软件流程图，但显示的是计算动作（如寄存器操作）的时间顺序，以及在状态机输入影响下发生的时序步骤。ASM图描述的是状态机的行为动作，而不是存储组件所存储的内容。有时候用机器工作期间的行为动作来描述状态机的状态，比起用状态机产生的数据进行描述更为方便也更重要。例如，我们可以用16位的计数器内容来描述计数器本身，我们也可以将它视为一个数据信道单元来描述它的动作（如计数、等待等）。在描述时序状态机的行为方面，以及设计状态机来控制数据信道方面，ASM图是非常有帮助的。ASMD图是ASM图的扩展。状态机的一个重要应用就是控制时序状态机数据信道上的寄存器操作，而该时序状态机已被划分为控制器和数据信道。控制器可以用ASM图来描述，我们修改ASM图的目的是把它连接到状态机所控制的数据信道上。当控制器的状态沿着通道发生转移时，通过标注每个数据信道来指出那些在相关数据信道单元中所发生的寄存器操作。以这种方式连接到数据信道的ASM图被称为算法状态机和数据信道（ASMD）图。在把时序状态机数据信道的设计从控制器的设计中分离出来，并在两个单元之间保持清晰联系的情况下，ASMD图有助于阐明这样的时序状态机设计方法。与状态转移并行发生的寄存器操作是在图的通道上标注的，而不是在通道上的条件框或状态框中标注的，因为这些寄存器不是控制器的一部分。由控制器产生的输出是那些控制数据信道寄存器的信号，以及引发ASM图上标注的寄存器操作的信号。8.4基于状态转移图（STG）的设计1.设计要点对于一个同步时序状态机的给定STG，设计的任务就是确定下一状态和输出逻辑。如果用一个二进制代码来表示时序状态机的状态，那么其值可以存储在触发器中。在时钟的各个有效沿处，状态保持触发器的输入变成下一个时钟周期的状态。同步时序状态机的设计就是要根据机器的状态和外部输入来确定能形成触发器输入的逻辑，该逻辑为组合逻辑，并且应该是最简逻辑。对于有效的STG而言，其每个顶点必须表示一个唯一的状态；每个弧线则表示在指定输入信号的作用下，从给定状态到下一个状态的转移，并且从一个节点出发的各弧线必须对应一个唯一的输入。通常，与从一个节点出发的一组弧线有关的布尔条件必须满足和为1（即状态转移图必须考虑到从一个节点出发的所有可能的状态转移），并且在给定状态下与输入变量判定有关的每个分支条件必须对应于一条唯一的弧线（实时序状态机仅可以由一个节点经过一条弧线转移到下一个状态）。根据时钟到来之前的状态值和当前输入值，由同步时序状态机的STG所表示的状态转移将在时钟信号的有效沿处发生。有限状态机的系统设计方法通常包括以下几个步骤（1）构建状态机的STG。（2）消去等价状态。（3）选取状态码（如二进制代码）。（4）编写状态表。（5）推出描述保持状态位的D触发器的输入布尔方程。（6）利用卡诺图优化布尔方程。【例1】设计一个串行数据检测器，在连续输入4个或4个以上的1时输出1,否则输出0。解:(串行数据输入方向为：从左至右。)①逻辑抽象输入──X(串行数据)Sn──电路现态输出──Z(检测结果)Sn+1──电路次态定义：S0──没有输入1;0S1──输入1个1;1S2──连续输入2个1;11S3──连续输入3个1;111S4──连续输入4个或4个以上个1;1111SnSn+1/ZXS0S1S2S3S40S0/0S0/0S0/0S0/0S0/01S1/0S2/0S3/0S4/1S4/1状态转移表：S2S3S1S00/01/10/01/00/00/01/01/0②状态简化：简化两个状态如果“等价”，则这两个状态可以合并为一个状态。两个状态等价的条件是：(1)在所有输入条件下，两个状态对应输出完全相同；(2)在所有输入条件下，两个状态转移效果完全相同。③状态分配∵M=4(状态)∴选n=2，定义:S000、S101、S211、S310④选定FF由状态转换表有:Q2Q1X00011110000/000/000/000/0101/011/010/010/1Q2n+1Q1n+1/ZQ2Q1X000111100000010111Q2n+1Q2Q1X000111100000011100Q1n+1状态方程2112112QXQXQXQQnn④选定FF由状态转换表有:Q2Q1X00011110000/000/000/000/0101/011/010/010/1Q2n+1Q1n+1/ZQ2Q1X000111100000010001Z输出方程12QXQZQKQJQJKn1_特性方程：对比121211211221222112)()()()()(QQXQQXQQQXQXQQXQXQQQXQQnn有：2121212,,QXKQXJXKXQJ则：选JK触发器状态方程2112112QXQXQXQQnnQKQJQJKn1_特性方程：对比121211211221222112)()()()()(QQXQQXQQQXQXQQXQXQQQXQQnn有：2121212,,QXKQXJXKXQJ则：⑤由驱动方程和输出方程画逻辑电路图输出方程12QXQZ驱动方程2121212,,QXKQXJXKXQJ12QXQZ⑥检查自启动该电路没有无效状态，不用检查自启动。程序modulestat(x,z,clk,rst);inputx,clk,rst;outputz;reg[1:0]state;//wirez;parameteridle='b00,a='b01,b='b10,c='b11,d='b100;assignz=(state==d&&x==1)?1:0;always@(posedgeclkornegedgerst)if(!rst)beginstate=idle;endelsecase(state)idle:if(x==1)beginstate=a;endelsebeginstate=idle;enda:if(x==1)beginstate=b;endelsebeginstate=idle;endb:if(x==1)beginstate=c;endelsebeginstate=idle;endc:if(x==1)beginstate=d;endelsebeginstate=idle;enddefault:state=idle;endcaseendmodule总结：时序逻辑电路设计主要有4个过程：1.确定原始状态转移图和原始状态表。2.状态简化；3.状态编码；4.存储电路类型的选择。【例6-6】设计模6同步计数器§6.3.2采用SSI设计同步计数器定义：S0=000S1=001S2=011S3=111S4=110S5=100CPQ3nQ2nQ1nQ3n+1Q2n+1Q1n+1Z0000001010010110201111103111110041101000510000010137642.建模实例利用STG构建一个BCD码到余3码的转换器一个串行发送的BCD码Bin被转换成为一个余3码串行比特流Bout是这样得到的：给BCD码对应的十进制数加上310，并将其转换为等价的二进制数就得到了该十进制数的余3码，表11-1给出了十进制数及其相应的4位BCD码和余3码。余3码是自补码，即余3码的9补，在硬件上可以通过对码字逐位取反得到（即取码字的二进制反码）。例如610的余3码为10012，逐位取反后为01102，这就是310的余3码。余3码的这一特性使得计算以BCD形式编码的基数减1的反码变得很容易，这类似于减去带符号二进制数可以通过给减数加上被减数的二进制补码实现，二进制补码可由被减数的二进制反码加1得到。于是，610的十进制补码可由610的余3码10012逐位取反后再加1得到，01102+00012=01112，即410的余3码。表11-1BCD码与余3码十进制数字8421码（BCD码）余3码000000011100010100200100101300110110401000111501011000601101001701111010810001011910011100串行比特流的BCD码到余3码转换器可以用米利型FSM实现。图11-4给出了输入该转换器的串行比特流Bin，以及转换器输出的相应余3码的串行比特流。应注意Bin是先从最低位LSB（LeastSignificantBit）开始按顺序发送的，因此要对Bin和Bout进行正确译码应该多加小心。波形中各位的顺序是随时间t的增加从左向右行进的，左边是最低位LSB，右边是最高位MSB（MostSignificantBit）。在这种转换器中，波形的位顺序必须反转，如图11-4所示，从而形成发送和接收码字的二进制数值。如图11-4所示，从而