时序逻辑电路的分析与设计.ppt

《时序逻辑电路的分析与设计.ppt》由会员分享，可在线阅读，更多相关《时序逻辑电路的分析与设计.ppt（201页珍藏版）》请在三一文库上搜索。

1、1,6 . 时序逻辑电路的分析与设计,6.1 时序逻辑电路的基本概念,6.2 同步 时序逻辑电路的分析,6.3 同步 时序逻辑电路的设计,6.4 异步 时序逻辑电路的分析,6.5 若干典型的时序逻辑集成电路,6.6 时序逻辑可编程逻辑器件,2,教学基本要求,2、熟练掌握时序逻辑电路的分析方法,1、熟练掌握时序逻辑电路的描述方式及其相互转换。,3、熟练掌握时序逻辑电路的设计方法,4、熟练掌握典型时序逻辑电路计数器、寄存器、移位寄存器的逻辑功能及其应用。,5、正确理解时序可编程器件的原理及其应用。,3,6.1 时序逻辑电路的基本概念,6.1.1 时序逻辑电路的模型与分类,6.1.2 时序电路逻辑功

2、能的表达,4,6.1.1 时序逻辑电路的模型与分类 时序电路由组合电路和存储电路两部分组成，并形成反馈回路。它是一种在任何时刻输出不仅取决于该电路的输入，而且还与电路过去输入有关的逻辑电路。 时序电路具有以下两个特点： 1. 时序电路中的存储电路（通常由触发器组 成），具有记忆过去输入信号的能力。 2.存储电路的输出反馈到时序电路的输入端，同输入信号共同决定组合电路的输出。,5,时序逻辑电路的模型,*电路由组合电路和存储电路组成。,*电路存在反馈。,结构特征:,外部输出（输出）,内部输出（激励）,内部输入（状态）,外部输入（输入）,6,组合逻辑部分用来产生电路的输出和“激励”；存储元件则用来记

3、忆电路以前时刻的输入情况，并用“状态” 表征。时钟信号起同步作用。 “状态”是同步时序电路的一个重要概念，它表示时序电路的过去属性。并且，常称电路当前状态为现态，用 或 表示（右上标可省），将改变后的状态称为次态，用 或 表示。 由此可见，同步时序电路的输出不仅与当时的输入有关，而且与过去的输入情况（即现态）有关。 组合电路和时序电路的主要区别,7,输出方程: Of1(I，S),激励方程: Ef2(I，S),状态方程 : Sn+1f3(E，Sn),表达输出信号与输入信号、状态变量的关系式,表达激励信号与输入信号、状态变量的关系式,表达存储电路从现态到次态的转换关系式,激励,输出,状态,输入,8

4、,时序电路可从不同的角度进行分类： 1. 若按电路中状态改变的方式来分，可分为： 同步时序电路：有统一的时钟脉冲，只有在时钟脉冲作用下，时序电路的状态才能发生改变，时钟脉冲起着同步的作用。即存储电路里所有触发器有一个统一的时钟源，它们的状态在同一时刻更新。 异步时序电路：无统一的时钟脉冲或没有时钟脉冲，任何输入信号的变化都可能引起电路状态的改变。即电路的状态更新不是同时发生的。 2. 若按时序电路中输出变量和输入变量之间的关系来分，可分为： Mealy（米利）型：输出是输入与现态的函数。 Moore（穆尔）型：输出仅与电路的现态有关。 Moore型电路的特殊情况是无外部输出，而此时，电路的状态

5、可看作是电路的输出。,9,米利型和穆尔型时序电路,10,11,组合电路的逻辑功能可以用输出方程（表达式）、真值表和波形图来表达。 时序电路的逻辑功能可以用逻辑方程组、状态表、状态图和时序图来表达。逻辑方程组包括：输出方程组、激励方程组、状态方程组。 三组方程、状态表和状态图之间可直接实现相互转换。且根据其中的任意一种表达方式，都可以画出时序图。 从理论上讲，有了输出方程组、激励方程组和状态方程组，时序电路的逻辑功能就可以被唯一地确定了。但实际上仅从这三组方程还不易判断其逻辑功能。尤其是在设计时序电路时，往往很难根据给出的逻辑需求直接写出这三组方程。因此，还需要用能直观反映电路状态变化序列全过程

6、的状态表和状态图来帮助。,6.1.2 时序电路功能的表达方法,12,时序电路的输入、输出、现态以及次态之间的关系可用状态表和状态图来描述。 1.状态表（状态转移表） 是以表格的方式来描述同步时序电路的逻辑功能。类似于组合电路中的真值表。又可分为： Mealy型电路状态表 Moore型电路状态表,13,Mealy型电路状态表 其格式如下：,现态,现态y,某电路的状态表,14,表格左边列出现态；右边的顶部列出电路输入X的全部组合；表格的内部则列出对应不同输入组合和现态下的次态 及输出Z。 该表读作：处于状态y的同步时序电路，当输入为X时，在时钟脉冲作用下，电路进入次态 且输出为Z。 如：某时序电路

7、有一个输入X，一个输出Z，两个状态变量y2 和y1。电路输入的全部组合共有两个（“0”和“1”）。电路的全部状态共有四个，即 y2 y1 = 00 （记为A） y2 y1 = 01 （记为B） y2 y1 = 10 （记为C） y2 y1 = 11 （记为D） 并且该电路的状态表如前页所示。 从状态表中可知：若电路的初始状态为A，当输入X = 1 时，在时钟脉冲的作用下，电路将进入次态C，且输出Z = 1。若输入X 又由1变为0，则在时钟脉冲到来时，电路的次态变为B，且输出Z为1。 进一步讨论。,15,若电路的输入序列为：X：1 0 1 0 0 1 1 0初态为A则与每 个输入信号对应的状态转

8、换及输出响应序列如下： 时钟脉冲： 1 2 3 4 5 6 7 8 输入序列X： 1 0 1 0 0 1 1 0 状态转 y： A C B A D A C D 换序列 ： C B A D A C D A 输出响应序列Z：1 1 0 0 0 1 0 0 注： 电路的现态和次态是针对某一时刻而言的，且该时刻的次态 即为下一时刻的现态。 若电路的初态不同，则尽管输入序列相同，状态转换序列和 输出响应序列也将不同。,16,且读作：处于状态y的同步时序电路，输出为Z；当输入为X时，在时钟脉冲作用下，电路进入 （次态）。 注：Moore型电路的当前输出由现态确定。,Moore型电路状态表 由于Moore型

9、电路的输出仅与现态有关。即不论输入如何变化，对一个给定的现态，总有相同的输出。故将输出单独作为一列。其状态表格式如下：,17,如：某Moore型电路的状态表如右所示： 当电路处于态时，电路输出为；若 = 1（输入），则在脉冲到来时，电路进入状态，此时，电路的输出为；若则电路将进入状态。此时电路的输出（在状态）为。,设电路的初态为，输入序列为：,则与每个输入信号对应的状态转换和输出响应序列如下： 时钟脉冲： 输入序列： y： 状态转换 ： 序列 输出序列： 结论： 只要给定状态表及电路的初始状态，便可求出在输入序列作用下电路的输出响应序列和状态转换序列。,初始状态,18,状态图（状态转换图） 它

10、是用图形对时序电路进行描述。是一种反映同 步时序电路状态转换规律及相应输入、输出取值关系 的有向图。在图中可见状态的转换方向和条件。也可 分为： Mealy型 Moore型 两种。,19,每一个状态用一个圆圈来代表，圈内用字母或数字表示该状态的名称，用还箭头的直线或弧线表示状态转换关系，并将引起这一转换的输入条件X以及在该输入和现态下的相应输出标注在有向线段的旁边，箭头的起点表示现态，终点表示次态。如：,Mealy型状态图，其形式如下所示：,x/z,输入条件 输出,现态 次态,A,B,D,C,0/0,0/0,1/0,1/0,0/1,1/1,1/1,0/1,某MEALY型电路的状态图,由左图可知

11、：若电路处于状态B，则当输入X = 1 时，电路输出Z = 0。,20, Moore型状态图 与Mealy型类似，图中用圆圈表示电路的状态，连接圆圈的有向线段表示状态的转换关系，引起状态转换的输入条件X标注在有向线段旁边，但电路的输出标注在状态圈内。如下所示： x,现态 次态 Moore 型状态图形式,输出,21,如：某Moore 型状态图为 从状态图可看出，当电路处于A时，电路输出为0，此时 若输入为0，则电路将由A状态转换到状态C，且新的输出值 为0；若输入为1，则电路状态将由A转换至B，且新的输出 值为1。 结论： 用状态图描述同步时序电路的逻辑功能直观、形象。 它与状态表一样，是分析和

12、设计同步时序电路的重要工具。,A/0,C/0,B/1,1,0,1,0,1,0,22,同一时序电路的状态图与状态表可相互转换。如：,状态图与状态表的转换关系,A,C,B,0/1,1/1,0/0,1/0,0/0,1/0,23,输出方程,激励方程组,状态方程组,1. 逻辑方程组,例：,下面通过实例来讨论时序电路逻辑功能的四种表达方法。,24,25,（2）将状态转换真值表转换为状态表,状态转换真值表,26,状态表,(3)根据状态表画出状态图,状态图,27,（4）根据状态表画出时序图（波形图）,时序逻辑电路的四种描述方式是可以相互转换的。,波形图,从波形图可以看出:输出Y不受时钟脉冲的影响。,28,6.

13、2 时序逻辑电路的分析,6.2.1 分析同步时序逻辑电路的一般步骤,6.2.2 同步时序逻辑电路分析举例,29,时序逻辑电路分析的任务：,分析时序逻辑电路在输入信号的作用下，其状态和输出信号变化的规律，进而确定电路的逻辑功能。,6.2 时序逻辑电路的分析,时序电路的逻辑功能是由其状态和输出信号的变化的规律呈现出来的。所以,分析过程主要是列出电路状态表或画出状态图、工作波形图。,分析过程的主要表现形式:,30,6.2.1 分析同步时序逻辑电路的一般步骤:,1.了解电路的组成； 电路的输入、输出信号、触发器的类型等。,.确定电路的逻辑功能。,3.列出状态转换表或画出状态图和波形图；,2. 根据给定

14、的时序电路图,写出下列各逻辑方程式：,() 输出方程；,() 各触发器的激励方程;,（3）状态方程: 将每个触发器的驱动方程代入其特性方程得状态方程。,31,例1 试分析如图所示时序电路的逻辑功能。,6.2.2 同步时序逻辑电路分析举例,电路是由两个T 触发器组成的同步时序电路。,解：,(1)了解电路组成。,32,(2) 根据电路列出三个方程组,激励方程组: T0=A T1=AQ0,输出方程组: Y=AQ1Q0,将激励方程组代入T触发器的特性方程得状态方程组:,33,(3) 根据状态方程组和输出方程列出状态表,Y =A Q1Q0,状态表,34,(4) 画出状态图,35,(5) 画出时序图,若输

15、入A存在较大噪声，这可能错误地触发进位操作。如果删除电路图中A和与门G2输入之间的连线，将电路转换为穆尔型，使输出信号仅取决于电路的状态，其变化始终与时钟同步，而输入信号A影响电路状态的时间仅限于CP脉冲上升沿前后的瞬间，从而提高电路的抗干扰性能。,36,(6) 逻辑功能分析,观察状态图和时序图可知，电路是一个由信号A控制的可控二进制计数器。当A=0时停止计数，电路状态保持不变； 当A=1时，在CP上升沿到来后电路状态值加1，一旦计数到 11状态，Y 输出1，且电路状态将在下一个CP上升沿回到00。 输出信号Y的下降沿可用于触发进位操作。,该电路也是序列信号检测器。用来检测同步脉冲信号序列A中

16、1的个数，一旦检测到四个1状态（这四个1状态可以不连续），电路则输出高电平。,37,例2 试分析如图所示时序电路的逻辑功能。,电路是由两个JK触发器组成的莫尔型同步时序电路。,解：,(1)了解电路组成。,J2=K2=X Q1,J1=K1=1,Y=Q2Q1,(2)写出下列各逻辑方程式：,输出方程:,激励方程:,38,J2=K2=X Q1,J1=K1=1,将激励方程代入JK触发器的特性方程得状态方程:,整理得：,FF2,FF1,39,(3)列出其状态转换表，画出状态转换图和波形图,Y=Q2Q1,40,状态图,41,根据状态转换表，画出波形图。,42,X=0时,电路功能：可逆计数器,X=1时,Y可理

17、解为进位或借位端。,电路进行加1计数,电路进行减1计数 。,()确定电路的逻辑功能.,43,例3 分析下图所示的同步时序电路。,激励方程组,输出方程组 Z0=Q0 Z1=Q1 Z2=Q2,解：（1）根据电路列出逻辑方程组:,44,得状态方程,（2）列出其状态表,45,（3）画出状态图,状态图,46,（4） 画出时序图,47,由状态图可见，电路的有效状态是三位循环码。 从时序图可看出，电路正常工作时，各触发器的Q端轮流出现 一个宽度为一个CP周期脉冲信号,循环周期为3TCP。电路的功能为脉冲分配器或节拍脉冲产生器。,（5）逻辑功能分析,48,6.3 同步时序逻辑电路的设计,6.3.1 设计同步时

18、序逻辑电路的一般步骤,6.3.2 同步时序逻辑电路设计举例,49,6.3 同步时序逻辑电路的设计,同步时序逻辑电路的设计是分析的逆过程,其任务是根据实际逻辑问题的要求，设计出能实现给定逻辑功能的电路。,6.3.1 设计同步时序逻辑电路的一般步骤,同步时序电路的设计过程：,若给定的电路比较典型，则可跳过其中的一些步骤，即2、3步骤是可省的。（已为最简状态或状态编码方案已给定时）,50,直接从设计要求的文字描述得到的状态图称为原始状态图。 建立原始状态图的过程，就是对设计要求进行分析的过程。状 态图用图形的形式反映了同步时序电路的逻辑特性，这一步是 极其重要的，它是时序电路设计的基础。若建立的原始

19、状态图 不能正确反映设计要求，则整个设计工作都将建立在错误的基 础上，导致的最后结果也将是错误的。 原始状态图不一定是最简单的，主要着眼于正确性，不能漏 掉一个状态，至于所设定的状态是否多余，则不必过多考虑。,下面对以上的具体步骤分别加以具体的讨论。,一、根据给定的逻辑功能建立原始状态图和原始状态表,51,1.分析命题，确定电路的输入个数与输出个数，并用字母表示之。 2.确定电路中有多少个输入信息需要记忆，并对每个需要记忆的输入信息用一个状态来表示（该状态可用字母或数字表示）。 3.从假定的一个初态开始，每加入一个输入信号，就用其次态“记忆”下来，并标出相应的输出值。该次态可能是现态，也可能是

20、已设定的另一个状态，或者为新增加的状态。该过程一直继续下去，直到每一个现态向次态的转换均被考虑，且不再出现新的状态为止。,建立原始状态图的过程大致如下：,下面举例来说明如何建立原始状态图。,52,例1. 某序列检测器有一个输入端x与一个输出端z，从x输入的一组按时间顺序排列的串行二进制码，当输入序列出现101时，输出z1，否则为0，试作出该序列检测器的Mealy型和Moore型的状态图和状态表。,解：根据题意，可得该电路的框图如下所示， 且该电路的典型输入输出波形如下：,序列检测器,x,时钟,z,53,若该序列检测器为Mealy型电路，则其设计步骤如下： 1.根据所要检测的序列决定各个状态 因

21、该电路的功能为检测101序列，故一旦输入序列中出 现了1便要记下来；接着再看输入是否为0；若是，则也记下 来；记住10后，再最后看输入是否为1，若是，则输出1。即 电路必须记住1，10和101这3种输入情况，且将这三种输入 情况与电路的一个状态相对应。 若设电路的初态为S0，用S1表示收到了输入为1时的电路 状态；S2表示收到10时的电路状态；S3表示收到101时电路 的状态，则有四个状态，如下图：,S0,S1,S2,S3,图a,54,S3,S0,S1,S2,1/1,0/0,1/0,图b,2. 确定主干状态的转移及输出 上面已确定电路的主干状态为S1，S2和S3，电路的初始状态为S0。 若第一

22、个输入为1，则可能是检测序列101的第一个数码，输出为0，状态从S0转移到S1，表示电路已收到检测序列的第一个数码；若第二个输入为0，则输出为0，状态从S1转到S2，表示已收到10序列；如果第三个输入为1，则输出应为1（因为此时电路已经收到101序列，状态从S2转至S3，如上图b ：,55,S3,S2,S1,S0,0/0,0/0,1/1,0/0,0/0,1/0,1/0,1/0,3. 进一步完善原始状态图 由于该电路只有一个输入变量，故从每个现态出发，可能有两个转移方向，故须对图b完善。 当电路处于S0时，若输入为0，则输出为0，且电路保持原态。（因从0开始输入序列不是要检测的序列）。,当电路处

23、于S1时，若输入为1，则输出为0，且状态保持不 变。（因为它可能是又一个101序列的开始） 当电路处于S2时，若输入为0，则输出为0，且状态转移至S0，以便重新开始检测。 当电路处于S3时，若输入为1，则可能是又一个101 序列的开始，因此电路应从状态S3转移到S1，若输入为0，则应从S3转移至S2（注:不是转移至S0），因为此时的0可能为101的序列中的0，故完整的原始状态图见图c所示。,图c,56,S3,S2,S1,S0,0/0,0/0,1/1,0/0,0/0,1/0,1/0,1/0,现态,由状态图可以方便地作出状态表如下：,57,若按Moore型电路设计，其过程与Mealy型的相似。设初

24、态为S0，由于Moore型电路的输出仅与现态有关，故输出标在圈内，详见下图所示：,S3/1,S2/0,S1/0,S0/0,0,0,1,0,0,1,1,1,状态图,状态表,现态,输出,58,例2. 某一引爆电路的框图如图a所示，图中的x为一启动开关。当x=1时，在四个时钟脉冲的作用下，使电路的输出为z=1。以此触发炸药包的爆炸。其输入/输出之间的关系如图b所示。试作出该引爆电路的状态图及状态表。,x,CP,z,图a,图b,引爆电路,59,解：根据题意，设电路的初态为S0，因电路需记忆住4个连续的1信号，故需增设状态S1,S2和S3，用其分别表示电路收到的1个1，2个1和 3个1的状态。当收到第四

25、个1时，便输出一个脉冲（Z1），使炸药爆炸，故电路的最后一个状态可用任意状态d表示。 由题意可知，一旦引爆序列开始（即x=1），则要继续下去，不能中断（即x0），直到z=1（引爆） 为止，故引爆电路的状态图如下：,状态图,d,S3,S2,S1,S0,1/0,1/0,0/0,1/0,1/1,60,由状态图可得状态表如下所示：由于电路处于状态S1， S2和S3时，不允许输入为0，因此状态表中当x=0时，次态及 输出都不能出现，可当作任意项处理。,现态,注：存在d的状态表称为不完全确定状态表（因表中含有不确定的状态或输出），其所描述的电路叫做不完全确定电路，否则（即无d项）称为完全确定状态表。,一般

26、状态图中不一定要求标d项，对不可能出现的情况是隐含的。即在状态图中凡是没有表示的情况都是不可能出现的。,61,从状态表中消去多余的状态，得到一个状态数比原来的要 少的状态表，称为状态简化。 状态简化的实质是寻找最小化的状态表。最小化状态表包 含的状态数目最少，它与原始的状态表相比，虽代表的内部结 构不同的电路，但均具有相同的逻辑特性，也即：对于任意的 输入，他们对应的输出总是一样的。 状态化简有观察法和隐含表法两种。,由于完全确定状态表与不完全确定状态表的简化方法不同，故在此分别加以讨论,二、状态化简（求出最简状态图和最简状态表）,62,1.完全确定状态表的简化 是基于等效状态的基础上的，即利

27、用状态与状态间的等效关系来进行状态简化。 （1）状态等效 是指在完全确定的状态表中，如对所有可能的输入序列，分别从某两个状态（假设为S1与S2）出发，所得到的输出序列都相同，则说这两个状态（S1与S2）等效。记做（S1，S2），此时S1与S2可以合并为一个状态，完全确定状态表的简化是根据这一原则进行的。,63,可以根据状态表中所列出的输入各种组合下的次态和输出来判断某两个状态是否等效。 设S1和S2为完全确定的状态表中的两个现态，则S1和S2等效的条件可归纳为在输入的各种取值组合下： 1）它们的输出完全相同。 2）它们的次态满足下列条件之一： 次态相同 次态交错 次态循环 次态对等效,现态,S

28、4,S3,S2,S1,64,其中，次态交错是指在某种输入取值下，S1的次态为S2， 而S2的次态为S1。次态循环是指在次态之间的关系构成闭环。 如S1和S2在某种输入取值下的次态为S3与S4，而S3与S4在某种 输入取值下的次态又是S1与S2，则S1与S3 ，S2与S4次态循 环。次态对等效是指S1与S2的次态满足以上状态等效的条件。 （2）等效关系的传递性 若S1与S2等效，S2与S3等效，则S1与S3等 效，记作（S1，S2），（S2，S3）（S1，S3） （3）等效类 若干个相互等效的状态，组成一个等效状态类，简称等效 类。即若干个状态集合中，任何两个状态都相互等效，则将这 些个状态组成

29、一个等效类。 如状态S1与S2等效，而S1与S3也等效，则状态S1、S2与S3 就等效。其等效类为（S1，S2，S3），记为 （S1，S2），（S2，S3）（S1， S2， S3）,65,指不被任何别的等效类所包含的等效类。 该处的最大，并不指含的状态最多，而是指其独立性， 即使是一个状态，只要它不被包含到别的等效类中，它就是最 大等效类。 利用上述判别状态等效的条件及状态等效的性质，便可 简化原始状态表。实际上，原始状态表的简化过程就是寻找最 大等效类，然后将各个最大等效类的所有状态合并为一个对应 的新状态，从而得到最小化的状态表，简化后的状态数即最大 等效类的个数。,（4）最大等效类,66

30、,下面具体介绍状态简化的方法和步骤。 观察法： 是一种根据状态等效的条件直接对原始状态表中的各状 态进行观察比较，找出等效的状态进行合并，从而求出最简状 态表的方法。 其具体过程为：先观察状态表中的输出部分，找出输出 完全相同的那些现态，再进一步观察其次态是否相同、交错、 循环或者次态对等效。 显然，输出不同的两个状态不等效，即不能合并。若两 个状态输出相同，则这两个状态有等效的可能。进一步观察其 次态是否满足等效条件，若满足，则这两状态就可合并。一直 到剩下的状态不能再合并而得到一个最小化的状态表为止。,67,该方法只适合于简单的状态表的化简。例如，简化下表所示的状态表。,现态,现态,简化,

31、68,解：先观察S3与S5。由于它们在x=0和x=1时的输出均相同，并且次态也相同，故S3与S5等效。 再看S1和S2，在所有输入的条件下，他们的输出也相同，且当x=1时，他们的次态对S5和S3是等效的；当x=0时，它们的次态交错，故S1与S2也等效。 继续观察，发现其它状态均不等效。因此，得到等效类为(S1,S2)，(S3,S5)，(S4)，(S6)。 由于以上等效类不包含在任何其它等效类中，因此，等效类(S1,S2)，(S3,S5)，(S4)，(S6)即为最大等效类。再将(S1,S2)合并为一个状态S1， (S3,S5)合并为一个状态S3，则原始状态表中的S2和S5可以删除，而其它状态行中

32、出现的S2则用S1代替，S5用S3代替。便可得到最小化的状态表如上页右边所示。,69,隐含表法：,它是根据状态等效条件进行系统比较的方法，大致分三步 进行。 （1）作隐含表，寻找等效状态对 隐含表是一个正直角三角形表格：两直角边的小方格数分 别等于原始状态表中的状态数减1，且左垂直方向从上到下，按 原始状态表中的状态顺序标注，但“缺头”；水平方向从左到右 也是按表的状态顺序标注，但“缺尾”。如一个4变量A、B、C、D 的隐含表为：,去头,去尾,70,1）顺序比较 将隐含表中每个小方格对应的状态相对比，并且将比较结果填入表中，对照原始状态表，每个状态对的比较结果可能为下列三种情况之一： 状态对等

33、效 在对应的小方格中填入 状态对不等效 在对应的小方格中填入 状态对是否等效取决于其次态 将次态对填入小方格,通过对隐含表中所有状态对的比较，来确定它们之间是否等效。比较分为：顺序比较将隐含表中每个小格对应的状态对相比；关联比较通过确定隐含表中所填次态对是否等效来确定原状态对是否等效。,71,2）关联比较 进一步确定所填的次态对是否等效，并以此来确定原状态对是否等效（它是在隐含表上进行的）。 若次态对不等效（只要有一对不等效），则原状态对不等效，并在小方格内添加 / 表示。 （2）寻找最大等效类 等效类是多个等效状态组成的集合。在该集合中，任何两个状态均等效。不被任何别的等效类所包含的等效类称

34、为最大等效类。即最大等效类集合中，各最大等效类没有公共状态。 （3）建立最小化状态表 同属于一个最大等效类的所有状态，可以合并为一个状态。最大等效类的数量就是简化后的状态数。将每个最大等效类的状态用一个新的状态来代替，便得到最小化的状态表。,72,注： 最大等效类的集合必须覆盖原始状态表中的全部状态，这样得到的最小化状态表才与原始状态表等效。原始状态表的简化过程即寻找最大等效类，再分别将各个最大等效类合并为一个新态，从而得最小化状态表。 一般讲，对复杂的原始状态表，需要将观察法与隐含表法结合起来用，先用前者消去明显多余的状态，再用后者作进一步化简。,73,例：简化下表所示的状态表（用隐含表法）

35、,现态,现态,74,解：（1）先作隐含表，并找出等效状态对,现态,75,对照原始状态表，先进行顺序比较知：C与F是等效的。A与B等效取决于C与F是否等效，。由隐含表再进行关联比较，知C与F是等效的，故A与B等效。而 故B、E等效，A、E也等效。又因为C、D不等效，故D、G不等效，在相应的格中标以 / 。 因此得等效状态对是：(A,B)，(A,E)，(B,E)，(C,F) （2）再确定最大等效类 根据等效关系的传递性，等效对(A,B)，(A,E)，(B,E)可构成等效类为(A,B,E)。故全部最大等效类为： (A,B,E)， (C,F)，(D)，(G),循环,（3）最后建立最小化状态表 将最大等

36、效类（A，B，E）合并为一个状态a，（C，F）合并为b，（D）和（G）分别用c和d表示，则可得到最小化状态表（见原始表的右边）。,76,2.不完全确定状态表的简化 它化简的步骤与前面介绍的完全确定状态表的类似，但是因为其中的部分状态和输出值不确定（任意项），所以不能用状态等效的概念，只能用状态相容的概念来进行化简。其几个基本概念为： （1）状态相容 假如所设置的两个状态，对于所有可能的有效输入序列（从电路的某个状态出发，除最后一个次态外，总有确定的次态，该输入序列称为有效输入序列），他们相应的输出序列（除了出现任意项的那些外）是相同的，则该两个状态相容，即可以合并为一个状态。不完全确定状态表的

37、简化就是根据这一原则进行的。,77,对一个不完全确定状态表，两个状态相容的条件可归纳为： 1.在所有可能的输入条件下，输出相同，或者其中一个（或两个）输出为任意项。 2.在所有可能的输入条件下，次态满足下列条件之一： a.次态相同 b.次态交错 c.次态循环 d.次态对中有一个或两个为不确定的状态d e.次态对相容,（2）相容类 若干个相容状态的集合称为相容类。且该集合中所有状态之间都分别是两两相容的。如相容类（S1，S2，S3）中，S1与S2相容，S2与S3相容，S1与S3也相容。注：相容无传递性。 （3）最大相容类 是指不包含在任何其他相容类中的相容类。在最大相容类的集合中，各最大相容类可

38、能有公共状态。,78,将原始状态表中的所有状态以点的形式均匀地标在一个圆周上，然后将所有相容的状态用线段连接起来。凡所有顶点之间都有连线的状态就构成一个最大相容类。以下分别为3、4、5个状态的最大相容类合并图。熟悉这些典型的状态合并图的结构后，就很容易从合并图中找出各种最大的相容类来。,S2,S3,S2,S4,S2,S3,S1,S1,S1,图a,S3,S4,S5,图b,图c,（4）状态合并图 它是用来从相容对中快速寻找最大相容类的工具图。其作法为：,79,与完全确定状态表一样，不完全确定状态表的简化方法也有： 观察法 隐含表法 1.作隐含表，寻找相容对。 2.借助状态合并图，确定最大相容类。

39、3.作最小化状态表（选择一个相容类集合）。 且每种方法的步骤也与完全确定状态表的简化一样。在此，只详细介绍最后一步：作最小化状态表。 作最小化状态表即选择一个相容类（包括最大相容类）集合，将每个相容类的状态用一个新的状态来代替，以得到一个新的状态表。该状态表即为最小化状态表。它与原先的状态表所表示的逻辑功能应相同。,80,故要求选择的相容类集合必须满足覆盖、闭合和最小三个条件。 覆盖：是指所选的相容类（包括最大相容类）集合中，包含了原状态表中的全部状态，即：原状态表中任何一个状态至少包含在一个所选的相容类中。 闭合：是指在一个相容类（包括最大相容类）集合中，任一相容类的所有次态均必须属于该集合

40、中的一个相容类（不能有一些属于一个，而一些又属于另一个相容类）。 最小：指满足覆盖的相容类（包括最大相容类）的数目最少。,同时满足覆盖、闭合、最小这三个条件的相容类（包括最大相容类）集合称为最小闭覆盖。,81,下面举例说明。 例：用隐含表法简化下表所示的状态表。,现态,现态,最小化状态表,82,解：1.先作出隐含表，并找出相容状态对。,B,A,C,D,E,状态合并图,从上隐含表中可以找到如下相容状态对： (A,B)，(A,C)，(A,D)，(A,E)，(B,C)，(C,D)，(D,E) 2.再确定最大相容类 通过作出状态合并图来确定，见右所示。,从状态合并图中可确定出最大相容类为： (A,B,

41、C)，(A,C,D)，(A,D,E),现态,83,3.最后作最小化状态表 满足覆盖的相容类集合可有下列几种组合： (A,B,C)，(A,C,D)，(A,D,E) (1) 闭合 (A,B,C)，(D,E) (2) 闭合 (B,C)，(A,D,E) (3) 不闭合 若选（1），则用闭合表一来检验其闭合情况，显然满足闭合条件，再选（2），则用闭合表二来检验其闭合情况，也满足闭合条件。,最大相容类,相容类,闭合表二,闭合表一,84,最小闭覆盖检测步骤： 1.先要求覆盖 2.再用闭合表检查是否闭合 3.最后确定最小,由此可知，相容类（A，B，C），（D，E）构成最小闭覆盖。,若将状态 A、B、C用a表示

42、，状态D、E用b表示，则可得 简化表（见原状态表右侧）。,最小化状态表,85,结论：,在选取闭覆盖相容类集合时，并不要求全部由 最大相容类组成（即不要求每个相容类都是最大 的）有时不选择最大相容类集合，而选择相容类集 合反倒可以得到最简结果。 注：不完全确定状态表的最小化状态表不是唯一的。,86,三、状态编码（状态分配）,将状态表中用字母或数字表示的状态以一组二进制代码 来代替，就称为状态编码或者状态赋值。 状态分配则是根据最小化状态表的状态数，确定触发器 的个数，指定每个状态的二进制编码。状态编码的任务主要 解决两个问题: 1.确定最小化状态表中每个状态的二进制代码位数.即确 定电路中触发器

43、的个数。 2.确定二进制编码的分配方案，即哪个状态分配哪个代 码。 由前面可知，状态是由触发器的状态变量（y1.yr） 的各种取值组合来表示的。r个触发器能表示的状态数为 个，故各状态的二进制代码的位数就等于触发器的位数 （个数）。,87,假设最小化状态表的状态数为m，则每个状态所需的二进制代码的位数为r（即触发器的个数）应满足下列关系： 或 r应取满足上式关系的最小整数。即 故已知电路的状态数便可由上式求出状态需分配的二进制代码的位数。如，某状态表中有8个状态，则 ， 即每个状态可用3位二进制代码表示。 以上解决了第一个问题，如何解决第二个问题呢？,二进制代码的位数确定后，可以有许多种的状态

44、分配方案。采用同样数量的触发器，若选用的状态编码不同，将导致所设计的电路复杂度不同。如用2位代码对四个状态进行编码，则方案可达24种（4的全排列为4！24）。要想得到较简单的电路，必须选择一个最佳的分配方案，若对所有方案一一进行比较显然不合适。目前，还不能准确的估计采用那种状态分配方案更有利于获得最简单的电路结构。,88,规则1 同一输入下的相同次态所对应的现态应给予相邻的编码 规则2 同一现态在相邻输入下的不同次态应给予相邻的编码 规则3 在所有输入条件下，输出完全相同的现态应给予相邻的编码 规则4 出现次数最多的状态分配逻辑0 一般，对前三个规则应尽量满足，但当出现不能同时满足时，应从前到

45、后依次考虑。 注：对于某些状态表，满足前面所给定的分配规则的分配方案不一定是唯一的，设计者可以任选一种。,从理论上讲，有可能找到一种确定最佳状态编码的算法，然而至今尚未获得满意而又实用的结果。现在在工程上采用的方法虽不能说是最佳，也接近最佳，有一定的实用价值。这是人们对编码理论的研究和实践的总结，其状态编码规则如下：对于状态表中,89,例：对下表进行状态编码,状态表,二进制状态表,y,90,解：1.先确定二进制的位数 由表中可知状态数为m5，故所需的二进制代码的位数为r为3，在此用y3y2y1表示。 2.再确定状态编码的分配方案 根据规则1，状态A与C，B与D，A与D均应分配相邻的二进制代码；

46、根据规则2，状态E与B，A与D，E与A，A与B，D与C均应分配相邻的二进制代码；根据规则3，状态A与C，A与E，C与E均应分配相邻的二进制代码；根据规则4 ，状态A应分配逻辑0。,该图的状态编码为：,由以上可得A、B、C、D的状态分配情况为：,将各状态的二进制代码带入已知状态表中，便可得 该表的二进制状态表，如原表右侧所示。,91,采用不同类型的触发器作为存储电路，将影响所设计电路的繁简程度。选择哪种触发器可以从电路结构简单、逻辑功能灵活和价格低廉等方面来考虑。下面先介绍各种触发器的激励表。 触发器的激励表，是把触发器的现态和次态作自变量，而将触发器的输入（或激励）作为因变量的一种真值表。也即

47、，触发器的激励表说明了从现态转移到某种次态时，对输入条件的要求。,四、选定触发器，求出电路的激励方程和输出方程,注：各触发器的激励表是由各触发器的特性表得来的。参见第5章47页始的PPT。,下面列出了四种触发器的激励表：,92,R-S触发器激励表,D触发器激励表,J-K触发器激励表,T触发器激励表,由R-S触发器特性表得,由D触发器特性表得,由J-K触发器特性表得,由T触发器特性表得,93,其中： R-S触发器的激励表是由时钟控制R-S触发器的特性表推出的，替他三种激励表也分别由各自的特性表推出。 在选定触发器后，就可以根据二进制状态表和选定的触发器的激励表求出激励函数和输出函数。,1.先列出激励函数真值表 2.求出激励函数表达式 3. 化简（用卡诺图）得最简式,可由二进制状态表直接得出,一般情况下，激励函数和输出函数的表达式并非最简，需要进行函数简化。,94,下面举例来具体说明如何由二进制状态表与触发器激励表来确定激励函数及输出函数的表达式。 例：若选用J-K触发器，试求出下面表所示的激励函数和输出函数表达式。,二进制状态表,激励函数真值表,95,解：1.先求出激励函数表达式 根据给定的二进制状态表和J