电子技术基础数字部分第五版(康华光)6 . 时序逻辑电路的分析与设计

.,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时序电路逻辑功能的表达,.,4,6.1.1时序逻辑电路的模型与分类时序电路由组合电路和存储电路两部分组成，并形成反馈回路。它是一种在任何时刻输出不仅取决于该电路的输入，而且还与电路过去输入有关的逻辑电路。时序电路具有以下两个特点：1.时序电路中的存储电路（通常由触发器组成），具有记忆过去输入信号的能力。2.存储电路的输出反馈到时序电路的输入端，同输入信号共同决定组合电路的输出。,.,5,时序逻辑电路的模型,*电路由组合电路和存储电路组成。,*电路存在反馈。,结构特征:,外部输出（输出）,内部输出（激励）,内部输入（状态）,外部输入（输入）,.,6,组合逻辑部分用来产生电路的输出和“激励”；存储元件则用来记忆电路以前时刻的输入情况，并用“状态”表征。时钟信号起同步作用。“状态”是同步时序电路的一个重要概念，它表示时序电路的过去属性。并且，常称电路当前状态为现态，用或表示（右上标可省），将改变后的状态称为次态，用或表示。由此可见，同步时序电路的输出不仅与当时的输入有关，而且与过去的输入情况（即现态）有关。组合电路和时序电路的主要区别,.,7,输出方程:Of1(I，S),激励方程:Ef2(I，S),状态方程:Sn+1f3(E，Sn),表达输出信号与输入信号、状态变量的关系式,表达激励信号与输入信号、状态变量的关系式,表达存储电路从现态到次态的转换关系式,激励,输出,状态,输入,.,8,时序电路可从不同的角度进行分类：1.若按电路中状态改变的方式来分，可分为：同步时序电路：有统一的时钟脉冲，只有在时钟脉冲作用下，时序电路的状态才能发生改变，时钟脉冲起着同步的作用。即存储电路里所有触发器有一个统一的时钟源，它们的状态在同一时刻更新。异步时序电路：无统一的时钟脉冲或没有时钟脉冲，任何输入信号的变化都可能引起电路状态的改变。即电路的状态更新不是同时发生的。2.若按时序电路中输出变量和输入变量之间的关系来分，可分为：Mealy（米利）型：输出是输入与现态的函数。Moore（穆尔）型：输出仅与电路的现态有关。Moore型电路的特殊情况是无外部输出，而此时，电路的状态可看作是电路的输出。,.,9,米利型和穆尔型时序电路,.,10,.,11,组合电路的逻辑功能可以用输出方程（表达式）、真值表和波形图来表达。时序电路的逻辑功能可以用逻辑方程组、状态表、状态图和时序图来表达。逻辑方程组包括：输出方程组、激励方程组、状态方程组。三组方程、状态表和状态图之间可直接实现相互转换。且根据其中的任意一种表达方式，都可以画出时序图。从理论上讲，有了输出方程组、激励方程组和状态方程组，时序电路的逻辑功能就可以被唯一地确定了。但实际上仅从这三组方程还不易判断其逻辑功能。尤其是在设计时序电路时，往往很难根据给出的逻辑需求直接写出这三组方程。因此，还需要用能直观反映电路状态变化序列全过程的状态表和状态图来帮助。,6.1.2时序电路功能的表达方法,.,12,时序电路的输入、输出、现态以及次态之间的关系可用状态表和状态图来描述。1.状态表（状态转移表）是以表格的方式来描述同步时序电路的逻辑功能。类似于组合电路中的真值表。又可分为：Mealy型电路状态表Moore型电路状态表,.,13,Mealy型电路状态表其格式如下：,现态,现态y,某电路的状态表,.,14,表格左边列出现态；右边的顶部列出电路输入X的全部组合；表格的内部则列出对应不同输入组合和现态下的次态及输出Z。该表读作：处于状态y的同步时序电路，当输入为X时，在时钟脉冲作用下，电路进入次态且输出为Z。如：某时序电路有一个输入X，一个输出Z，两个状态变量y2和y1。电路输入的全部组合共有两个（“0”和“1”）。电路的全部状态共有四个，即y2y1=00（记为A）y2y1=01（记为B）y2y1=10（记为C）y2y1=11（记为D）并且该电路的状态表如前页所示。从状态表中可知：若电路的初始状态为A，当输入X=1时，在时钟脉冲的作用下，电路将进入次态C，且输出Z=1。若输入X又由1变为0，则在时钟脉冲到来时，电路的次态变为B，且输出Z为1。进一步讨论。,.,15,若电路的输入序列为：X：10100110初态为A则与每个输入信号对应的状态转换及输出响应序列如下：时钟脉冲：12345678输入序列X：10100110状态转y：ACBADACD换序列：CBADACDA输出响应序列Z：11000100注：电路的现态和次态是针对某一时刻而言的，且该时刻的次态即为下一时刻的现态。若电路的初态不同，则尽管输入序列相同，状态转换序列和输出响应序列也将不同。,.,16,且读作：处于状态y的同步时序电路，输出为Z；当输入为X时，在时钟脉冲作用下，电路进入（次态）。注：Moore型电路的当前输出由现态确定。,Moore型电路状态表由于Moore型电路的输出仅与现态有关。即不论输入如何变化，对一个给定的现态，总有相同的输出。故将输出单独作为一列。其状态表格式如下：,.,17,如：某Moore型电路的状态表如右所示：当电路处于态时，电路输出为；若=1（输入），则在脉冲到来时，电路进入状态，此时，电路的输出为；若则电路将进入状态。此时电路的输出（在状态）为。,设电路的初态为，输入序列为：,则与每个输入信号对应的状态转换和输出响应序列如下：时钟脉冲：输入序列：y：状态转换：序列输出序列：结论：只要给定状态表及电路的初始状态，便可求出在输入序列作用下电路的输出响应序列和状态转换序列。,初始状态,.,18,状态图（状态转换图）它是用图形对时序电路进行描述。是一种反映同步时序电路状态转换规律及相应输入、输出取值关系的有向图。在图中可见状态的转换方向和条件。也可分为：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型电路的状态图,由左图可知：若电路处于状态B，则当输入X=1时，电路输出Z=0。,.,20,Moore型状态图与Mealy型类似，图中用圆圈表示电路的状态，连接圆圈的有向线段表示状态的转换关系，引起状态转换的输入条件X标注在有向线段旁边，但电路的输出标注在状态圈内。如下所示：x,现态次态Moore型状态图形式,输出,.,21,如：某Moore型状态图为从状态图可看出，当电路处于A时，电路输出为0，此时若输入为0，则电路将由A状态转换到状态C，且新的输出值为0；若输入为1，则电路状态将由A转换至B，且新的输出值为1。结论：用状态图描述同步时序电路的逻辑功能直观、形象。它与状态表一样，是分析和设计同步时序电路的重要工具。,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.2时序逻辑电路的分析,6.2.1分析同步时序逻辑电路的一般步骤,6.2.2同步时序逻辑电路分析举例,.,29,时序逻辑电路分析的任务：,分析时序逻辑电路在输入信号的作用下，其状态和输出信号变化的规律，进而确定电路的逻辑功能。,6.2时序逻辑电路的分析,时序电路的逻辑功能是由其状态和输出信号的变化的规律呈现出来的。所以,分析过程主要是列出电路状态表或画出状态图、工作波形图。,分析过程的主要表现形式:,.,30,6.2.1分析同步时序逻辑电路的一般步骤:,1.了解电路的组成；电路的输入、输出信号、触发器的类型等。,.确定电路的逻辑功能。,3.列出状态转换表或画出状态图和波形图；,2.根据给定的时序电路图,写出下列各逻辑方程式：,()输出方程；,()各触发器的激励方程;,（3）状态方程:将每个触发器的驱动方程代入其特性方程得状态方程。,.,31,例1试分析如图所示时序电路的逻辑功能。,6.2.2同步时序逻辑电路分析举例,电路是由两个T触发器组成的同步时序电路。,解：,(1)了解电路组成。,.,32,(2)根据电路列出三个方程组,激励方程组:T0=AT1=AQ0,输出方程组:Y=AQ1Q0,将激励方程组代入T触发器的特性方程得状态方程组:,.,33,(3)根据状态方程组和输出方程列出状态表,Y=AQ1Q0,状态表,.,34,(4)画出状态图,.,35,(5)画出时序图,若输入A存在较大噪声，这可能错误地触发进位操作。如果删除电路图中A和与门G2输入之间的连线，将电路转换为穆尔型，使输出信号仅取决于电路的状态，其变化始终与时钟同步，而输入信号A影响电路状态的时间仅限于CP脉冲上升沿前后的瞬间，从而提高电路的抗干扰性能。,.,36,(6)逻辑功能分析,观察状态图和时序图可知，电路是一个由信号A控制的可控二进制计数器。当A=0时停止计数，电路状态保持不变；当A=1时，在CP上升沿到来后电路状态值加1，一旦计数到11状态，Y输出1，且电路状态将在下一个CP上升沿回到00。输出信号Y的下降沿可用于触发进位操作。,该电路也是序列信号检测器。用来检测同步脉冲信号序列A中1的个数，一旦检测到四个1状态（这四个1状态可以不连续），电路则输出高电平。,.,37,例2试分析如图所示时序电路的逻辑功能。,电路是由两个JK触发器组成的莫尔型同步时序电路。,解：,(1)了解电路组成。,J2=K2=XQ1,J1=K1=1,Y=Q2Q1,(2)写出下列各逻辑方程式：,输出方程:,激励方程:,.,38,J2=K2=XQ1,J1=K1=1,将激励方程代入JK触发器的特性方程得状态方程:,整理得：,FF2,FF1,.,39,(3)列出其状态转换表，画出状态转换图和波形图,Y=Q2Q1,.,40,状态图,.,41,根据状态转换表，画出波形图。,.,42,X=0时,电路功能：可逆计数器,X=1时,Y可理解为进位或借位端。,电路进行加1计数,电路进行减1计数。,()确定电路的逻辑功能.,.,43,例3分析下图所示的同步时序电路。,激励方程组,输出方程组Z0=Q0Z1=Q1Z2=Q2,解：（1）根据电路列出逻辑方程组:,.,44,得状态方程,（2）列出其状态表,.,45,（3）画出状态图,状态图,.,46,（4）画出时序图,.,47,由状态图可见，电路的有效状态是三位循环码。从时序图可看出，电路正常工作时，各触发器的Q端轮流出现一个宽度为一个CP周期脉冲信号,循环周期为3TCP。电路的功能为脉冲分配器或节拍脉冲产生器。,（5）逻辑功能分析,.,48,6.3同步时序逻辑电路的设计,6.3.1设计同步时序逻辑电路的一般步骤,6.3.2同步时序逻辑电路设计举例,.,49,6.3同步时序逻辑电路的设计,同步时序逻辑电路的设计是分析的逆过程,其任务是根据实际逻辑问题的要求，设计出能实现给定逻辑功能的电路。,6.3.1设计同步时序逻辑电路的一般步骤,同步时序电路的设计过程：,若给定的电路比较典型，则可跳过其中的一些步骤，即2、3步骤是可省的。（已为最简状态或状态编码方案已给定时）,.,50,直接从设计要求的文字描述得到的状态图称为原始状态图。建立原始状态图的过程，就是对设计要求进行分析的过程。状态图用图形的形式反映了同步时序电路的逻辑特性，这一步是极其重要的，它是时序电路设计的基础。若建立的原始状态图不能正确反映设计要求，则整个设计工作都将建立在错误的基础上，导致的最后结果也将是错误的。原始状态图不一定是最简单的，主要着眼于正确性，不能漏掉一个状态，至于所设定的状态是否多余，则不必过多考虑。,下面对以上的具体步骤分别加以具体的讨论。,一、根据给定的逻辑功能建立原始状态图和原始状态表,.,51,1.分析命题，确定电路的输入个数与输出个数，并用字母表示之。2.确定电路中有多少个输入信息需要记忆，并对每个需要记忆的输入信息用一个状态来表示（该状态可用字母或数字表示）。3.从假定的一个初态开始，每加入一个输入信号，就用其次态“记忆”下来，并标出相应的输出值。该次态可能是现态，也可能是已设定的另一个状态，或者为新增加的状态。该过程一直继续下去，直到每一个现态向次态的转换均被考虑，且不再出现新的状态为止。,建立原始状态图的过程大致如下：,下面举例来说明如何建立原始状态图。,.,52,例1.某序列检测器有一个输入端x与一个输出端z，从x输入的一组按时间顺序排列的串行二进制码，当输入序列出现101时，输出z1，否则为0，试作出该序列检测器的Mealy型和Moore型的状态图和状态表。,解：根据题意，可得该电路的框图如下所示，且该电路的典型输入输出波形如下：,序列检测器,x,时钟,z,.,53,若该序列检测器为Mealy型电路，则其设计步骤如下：1.根据所要检测的序列决定各个状态因该电路的功能为检测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。若第一个输入为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开始输入序列不是要检测的序列）。,当电路处于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型的相似。设初态为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的状态。当收到第四个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项）称为完全确定状态表。,一般状态图中不一定要求标d项，对不可能出现的情况是隐含的。即在状态图中凡是没有表示的情况都是不可能出现的。,.,61,从状态表中消去多余的状态，得到一个状态数比原来的要少的状态表，称为状态简化。状态简化的实质是寻找最小化的状态表。最小化状态表包含的状态数目最少，它与原始的状态表相比，虽代表的内部结构不同的电路，但均具有相同的逻辑特性，也即：对于任意的输入，他们对应的输出总是一样的。状态化简有观察法和隐含表法两种。,由于完全确定状态表与不完全确定状态表的简化方法不同，故在此分别加以讨论,二、状态化简（求出最简状态图和最简状态表）,.,62,1.完全确定状态表的简化是基于等效状态的基础上的，即利用状态与状态间的等效关系来进行状态简化。（1）状态等效是指在完全确定的状态表中，如对所有可能的输入序列，分别从某两个状态（假设为S1与S2）出发，所得到的输出序列都相同，则说这两个状态（S1与S2）等效。记做（S1，S2），此时S1与S2可以合并为一个状态，完全确定状态表的简化是根据这一原则进行的。,.,63,可以根据状态表中所列出的输入各种组合下的次态和输出来判断某两个状态是否等效。设S1和S2为完全确定的状态表中的两个现态，则S1和S2等效的条件可归纳为在输入的各种取值组合下：1）它们的输出完全相同。2）它们的次态满足下列条件之一：次态相同次态交错次态循环次态对等效,现态,S4,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）等效类若干个相互等效的状态，组成一个等效状态类，简称等效类。即若干个状态集合中，任何两个状态都相互等效，则将这些个状态组成一个等效类。如状态S1与S2等效，而S1与S3也等效，则状态S1、S2与S3就等效。其等效类为（S1，S2，S3），记为（S1，S2），（S2，S3）（S1，S2，S3）,.,65,指不被任何别的等效类所包含的等效类。该处的最大，并不指含的状态最多，而是指其独立性，即使是一个状态，只要它不被包含到别的等效类中，它就是最大等效类。利用上述判别状态等效的条件及状态等效的性质，便可简化原始状态表。实际上，原始状态表的简化过程就是寻找最大等效类，然后将各个最大等效类的所有状态合并为一个对应的新状态，从而得到最小化的状态表，简化后的状态数即最大等效类的个数。,（4）最大等效类,.,66,下面具体介绍状态简化的方法和步骤。观察法：是一种根据状态等效的条件直接对原始状态表中的各状态进行观察比较，找出等效的状态进行合并，从而求出最简状态表的方法。其具体过程为：先观察状态表中的输出部分，找出输出完全相同的那些现态，再进一步观察其次态是否相同、交错、循环或者次态对等效。显然，输出不同的两个状态不等效，即不能合并。若两个状态输出相同，则这两个状态有等效的可能。进一步观察其次态是否满足等效条件，若满足，则这两状态就可合并。一直到剩下的状态不能再合并而得到一个最小化的状态表为止。,.,67,该方法只适合于简单的状态表的化简。例如，简化下表所示的状态表。,现态,现态,简化,.,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可以删除，而其它状态行中出现的S2则用S1代替，S5用S3代替。便可得到最小化的状态表如上页右边所示。,.,69,隐含表法：,它是根据状态等效条件进行系统比较的方法，大致分三步进行。（1）作隐含表，寻找等效状态对隐含表是一个正直角三角形表格：两直角边的小方格数分别等于原始状态表中的状态数减1，且左垂直方向从上到下，按原始状态表中的状态顺序标注，但“缺头”；水平方向从左到右也是按表的状态顺序标注，但“缺尾”。如一个4变量A、B、C、D的隐含表为：,去头,去尾,.,70,1）顺序比较将隐含表中每个小方格对应的状态相对比，并且将比较结果填入表中，对照原始状态表，每个状态对的比较结果可能为下列三种情况之一：状态对等效在对应的小方格中填入状态对不等效在对应的小方格中填入状态对是否等效取决于其次态将次态对填入小方格,通过对隐含表中所有状态对的比较，来确定它们之间是否等效。比较分为：顺序比较将隐含表中每个小格对应的状态对相比；关联比较通过确定隐含表中所填次态对是否等效来确定原状态对是否等效。,.,71,2）关联比较进一步确定所填的次态对是否等效，并以此来确定原状态对是否等效（它是在隐含表上进行的）。若次态对不等效（只要有一对不等效），则原状态对不等效，并在小方格内添加/表示。（2）寻找最大等效类等效类是多个等效状态组成的集合。在该集合中，任何两个状态均等效。不被任何别的等效类所包含的等效类称为最大等效类。即最大等效类集合中，各最大等效类没有公共状态。（3）建立最小化状态表同属于一个最大等效类的所有状态，可以合并为一个状态。最大等效类的数量就是简化后的状态数。将每个最大等效类的状态用一个新的状态来代替，便得到最小化的状态表。,.,72,注：最大等效类的集合必须覆盖原始状态表中的全部状态，这样得到的最小化状态表才与原始状态表等效。原始状态表的简化过程即寻找最大等效类，再分别将各个最大等效类合并为一个新态，从而得最小化状态表。一般讲，对复杂的原始状态表，需要将观察法与隐含表法结合起来用，先用前者消去明显多余的状态，再用后者作进一步化简。,.,73,例：简化下表所示的状态表（用隐含表法）,现态,现态,.,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）最后建立最小化状态表将最大等效类（A，B，E）合并为一个状态a，（C，F）合并为b，（D）和（G）分别用c和d表示，则可得到最小化状态表（见原始表的右边）。,.,76,2.不完全确定状态表的简化它化简的步骤与前面介绍的完全确定状态表的类似，但是因为其中的部分状态和输出值不确定（任意项），所以不能用状态等效的概念，只能用状态相容的概念来进行化简。其几个基本概念为：（1）状态相容假如所设置的两个状态，对于所有可能的有效输入序列（从电路的某个状态出发，除最后一个次态外，总有确定的次态，该输入序列称为有效输入序列），他们相应的输出序列（除了出现任意项的那些外）是相同的，则该两个状态相容，即可以合并为一个状态。不完全确定状态表的简化就是根据这一原则进行的。,.,77,对一个不完全确定状态表，两个状态相容的条件可归纳为：1.在所有可能的输入条件下，输出相同，或者其中一个（或两个）输出为任意项。2.在所有可能的输入条件下，次态满足下列条件之一：a.次态相同b.次态交错c.次态循环d.次态对中有一个或两个为不确定的状态de.次态对相容,（2）相容类若干个相容状态的集合称为相容类。且该集合中所有状态之间都分别是两两相容的。如相容类（S1，S2，S3）中，S1与S2相容，S2与S3相容，S1与S3也相容。注：相容无传递性。（3）最大相容类是指不包含在任何其他相容类中的相容类。在最大相容类的集合中，各最大相容类可能有公共状态。,.,78,将原始状态表中的所有状态以点的形式均匀地标在一个圆周上，然后将所有相容的状态用线段连接起来。凡所有顶点之间都有连线的状态就构成一个最大相容类。以下分别为3、4、5个状态的最大相容类合并图。熟悉这些典型的状态合并图的结构后，就很容易从合并图中找出各种最大的相容类来。,S2,S3,S2,S4,S2,S3,S1,S1,S1,图a,S3,S4,S5,图b,图c,（4）状态合并图它是用来从相容对中快速寻找最大相容类的工具图。其作法为：,.,79,与完全确定状态表一样，不完全确定状态表的简化方法也有：观察法隐含表法1.作隐含表，寻找相容对。2.借助状态合并图，确定最大相容类。3.作最小化状态表（选择一个相容类集合）。且每种方法的步骤也与完全确定状态表的简化一样。在此，只详细介绍最后一步：作最小化状态表。作最小化状态表即选择一个相容类（包括最大相容类）集合，将每个相容类的状态用一个新的状态来代替，以得到一个新的状态表。该状态表即为最小化状态表。它与原先的状态表所表示的逻辑功能应相同。,.,80,故要求选择的相容类集合必须满足覆盖、闭合和最小三个条件。覆盖：是指所选的相容类（包括最大相容类）集合中，包含了原状态表中的全部状态，即：原状态表中任何一个状态至少包含在一个所选的相容类中。闭合：是指在一个相容类（包括最大相容类）集合中，任一相容类的所有次态均必须属于该集合中的一个相容类（不能有一些属于一个，而一些又属于另一个相容类）。最小：指满足覆盖的相容类（包括最大相容类）的数目最少。,同时满足覆盖、闭合、最小这三个条件的相容类（包括最大相容类）集合称为最小闭覆盖。,.,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,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表示，状态D、E用b表示，则可得简化表（见原状态表右侧）。,最小化状态表,.,85,结论：,在选取闭覆盖相容类集合时，并不要求全部由最大相容类组成（即不要求每个相容类都是最大的）有时不选择最大相容类集合，而选择相容类集合反倒可以得到最简结果。注：不完全确定状态表的最小化状态表不是唯一的。,.,86,三、状态编码（状态分配）,将状态表中用字母或数字表示的状态以一组二进制代码来代替，就称为状态编码或者状态赋值。状态分配则是根据最小化状态表的状态数，确定触发器的个数，指定每个状态的二进制编码。状态编码的任务主要解决两个问题:1.确定最小化状态表中每个状态的二进制代码位数.即确定电路中触发器的个数。2.确定二进制编码的分配方案，即哪个状态分配哪个代码。由前面可知，状态是由触发器的状态变量（y1.yr）的各种取值组合来表示的。r个触发器能表示的状态数为个，故各状态的二进制代码的位数就等于触发器的位数（个数）。,.,87,假设最小化状态表的状态数为m，则每个状态所需的二进制代码的位数为r（即触发器的个数）应满足下列关系：或r应取满足上式关系的最小整数。即故已知电路的状态数便可由上式求出状态需分配的二进制代码的位数。如，某状态表中有8个状态，则，即每个状态可用3位二进制代码表示。以上解决了第一个问题，如何解决第二个问题呢？,二进制代码的位数确定后，可以有许多种的状态分配方案。采用同样数量的触发器，若选用的状态编码不同，将导致所设计的电路复杂度不同。如用2位代码对四个状态进行编码，则方案可达24种（4的全排列为4！24）。要想得到较简单的电路，必须选择一个最佳的分配方案，若对所有方案一一进行比较显然不合适。目前，还不能准确的估计采用那种状态分配方案更有利于获得最简单的电路结构。,.,88,规则1同一输入下的相同次态所对应的现态应给予相邻的编码规则2同一现态在相邻输入下的不同次态应给予相邻的编码规则3在所有输入条件下，输出完全相同的现态应给予相邻的编码规则4出现次数最多的状态分配逻辑0一般，对前三个规则应尽量满足，但当出现不能同时满足时，应从前到后依次考虑。注：对于某些状态表，满足前面所给定的分配规则的分配方案不一定是唯一的，设计者可以任选一种。,从理论上讲，有可能找到一种确定最佳状态编码的算法，然而至今尚未获得满意而又实用的结果。现在在工程上采用的方法虽不能说是最佳，也接近最佳，有一定的实用价值。这是人们对编码理论的研究和实践的总结，其状态编码规则如下：对于状态表中,.,89,例：对下表进行状态编码,状态表,二进制状态表,y,.,90,解：1.先确定二进制的位数由表中可知状态数为m5，故所需的二进制代码的位数为r为3，在此用y3y2y1表示。2.再确定状态编码的分配方案根据规则1，状态A与C，B与D，A与D均应分配相邻的二进制代码；根据规则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,采用不同类型的触发器作为存储电路，将影响所设计电路的繁简程度。选择哪种触发器可以从电路结构简单、逻辑功能灵活和价格低廉等方面来考虑。下面先介绍各种触发器的激励表。触发器的激励表，是把触发器的现态和次态作自变量，而将触发器的输入（或激励）作为因变量的一种真值表。也即，触发器的激励表说明了从现态转移到某种次态时，对输入条件的要求。,四、选定触发器，求出电路的激励方程和输出方程,注：各触发器的激励表是由各触发器的特性表得来的。参见第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-K触发器的激励表可列出激励函数真值表（如状态表右侧所示）。由激励函数真值表作出激励函数的卡诺图如下：,J1,J2,K1,K2,.,96,化简后得到激励函数表达式为：,2.再求出输出函数表达式可将已知的二进制状态表中的z值直接填入卡诺图中（如下表所示）化简后得输出函数表达式为：,Z,.,97,结论：,先根据给定的二进制状态表及触发器的激励表列出激励函数真值表，再根据真值表写出激励函数式，然后用卡诺图进行化简（或直接由真值表作激励函数的卡诺图）得最简激励式。输出函数式则可直接由二进制状态表的z值作出输出函数卡诺图便得到简化后的输出函数。,.,98,五、画出逻辑电路图并检查自启动能力。,根据激励函数和输出函数的逻辑表达式，就可以画出电路图。首先，画出所选的触发器，并编好序号（一般将低位状态变量相应的触发器安排在输入端，而将高位状态变量所对应的触发器安排在输出端）。然后，根据激励函数及输出函数表达式画出组合部分的逻辑图。注意：时钟脉冲信号不能忘了画上。例如：前面刚讲的那个例子，其激励函数和输出函数表达式为：,.,99,根据以上各表达式，再按刚才介绍的方法，先画触发器，再画组合部分，从而作出逻辑电路图如下：,.,100,例1.设计一个序列检测器，用来检测二进制序列。每当连续收到3个1（或3个以上1）时，该检测器输出为1，否则为0。解：据题意，电路有一个输入端x，用以接收二进制信号序列，还有一个输出端z，用来指示对“111”序列的识别，且输入与输出之间的关系见下面典型序列所示：x：11011110z：00000110,6.3.2同步时序逻辑电路设计举例,.,101,1.先建立原始状态图据题意，电路在连续收到3个1（或者3个以上1）时，输出为1，其它情况输出则为0，因此，要求电路能记忆收到1个1，连续两个1，连续3个1的情况。设电路的初始状态为S0，并将以上三种情况分别用S1，S2，S3来表示，则可得出主干转移图，见下图所示：,S0,S2,S3,S1,0/0,0/0,0/0,1/1,1/1,1/0,1/0,0/0,现态,原始状态表,再对上图作进一步的完善（见红线所示），便得到原始状态图，据它可以作出原始状态表如上表所示。,.,102,2.状态化简由于获得的是完全确定的状态表，故用观察法化简便可以得等效状态对为（S2，S3）。且最大等效类为：（S0），（S1），（S2，S3）。将等效对（S2，S3）合并为一个状态，记为S2，则可作出最小化状态表如下：,现态,.,103,3.状态编码,因为最小化状态表中只有三个状态，所以只需要2位二进制代码来表示各个状态。根据编码规则，找出最佳编码方案。由规则1知，S1与S2，S0与S2，S0与S1均应分配相邻的二进制代码。由规则2知，S0与S1，S0与S2均应分配相邻的二进制代码。由规则3知，S0与S1应分配相邻的二进制代码。由规则4知，S0应分配逻辑0。由以上分析得到的状态分配图及编码如下：y201y2y1y10S0S0001S1S2S101S211,将以上分配的状态编码代入最小化状态表中，便可得到二进制状态表。,.,104,4.选定触发器，求出激励函数式和输出函数式若选J-K触发器作存储元件，则由J-K触发器的激励表与二进制的状态表可作出激励函数真值表如下：,由于状态表中只有三个状态，而10状态没有用上，故10状态可作任意状态处理。,.,105,将上表中的激励函数值及状态表中的输出值填入相应的卡诺图，如下所示：,J2,K2,J1,K1,z,将卡诺图化简，便可得到最简的激励函数式和输出函数式如下：,.,106,5.画出逻辑电路图根据上面求出的逻辑表达式，可作出序列检测器的逻辑图如下所示：,.,107,6.讨论,一般来讲，当电路所需的工作状态数m小于触发器所能表示的状态数时，需要对所设计的电路进行实际工作状态讨论，其目的主要是查两个问题：a.电路若进入无效状态，能否在输入和时钟的作用下进入有效状态。若能，则称其具有自恢复功能，否则，称为挂起。b.电路万一处于无效状态，是否会产生错误的输出信号。一旦发现存在挂起现象或者错误输出的现象，则必须对电路进行修改，否则将影响电路工作的可靠性，甚至破坏正常工作。,.,108,讨论的过程实际上是对所设计的电路进行分析的过程，即根据设计电路作相应的状态表和状态图后，则可使检查的两个问题一目了然。至于修改设计的方案问题，则只涉及激励函数和输出函数化简时对无效状态下无关项的处理。现分析得到的逻辑电路。当电路进入无效状态10时，在加入输入信号后，能否进入正常的工作状态？（1）将激励函数式代入到J-K触发器的次态方程得电路的次态方程组：,.,109,00,11,10,01,0/0,1/1,1/1,1/0,1/0,0/0,0/0,（2）再根据次态方程组及输出函数式作出该电路的状态表及状态图，如下所示。,0/0,从状态图可看到，一旦进入10，则不论在x=1还是在x=0，经过一个时钟节拍，电路将自动进入到有效序列，但此时的输出在x=1时，会输出1（错误），为了消除它，需要对输出函数作适当的修改。,.,110,见右侧卡诺图，得新的z为：Z=xy2y1根据修改后得到的z式，再对原电路进行修改，即加上一根线（用红线示意）。,z,.,111,例2.设计一个二进制数码串行加法器。,解：串行加法运算和二进制数的算术加法运算规则是一致的，即从低位到高位逐位相加，被加数和加数从低位到高位串行地输入到加法器，相加时除获得每位和数Si外，还应记住每位的进位yi，以便将yi加到第i+1位上。详见下列框图所示：,组合电路,时钟,清零,(a),框图,在图（a）中，ai与bi为加数和被加数，输出的Si为串行输出端，是和数。本位产生的进位yi则用存储元件来记忆。,.,112,0,1,11/0,00/1,01/010/011/1,10/101/100/0,(b)状态图,1.建立原始状态图由于进位的值只可能为0和1两种状态，故状态图中只画了两个状态，设其为0和1。据加法规则有：aibi为00，01和10,由于以上已为最小化状态表，且各个状态的代码已定，故可以省略状态简化和状态编码两个步骤。,时，无进位，其本位的和分别为0，1，1；aibi为11时，有进位，其本位的和为0。因此可以得出串行加法器的状态图如图（b）所示，并由其作出状态表如下：,.,113,2.选定触发器，求出激励函数及输出函数表达式若选用D触发器，由D触发器的激励表及状态表可直接得到激励函数与输出函数的卡诺图。,aibi,aibi,Yi-1,Yi-1,D,Si,化简后（画卡诺图）得激励函数与输出函数的表达式为：,.,114,3.画逻辑图,.,115,例3.用T触发器作存储元件，设计一个两位二进制减1计数器。电路工作状态受输入信号x的控制。当x=0时，电路状态不变；当x=1时，在时钟脉冲作用下进行减1计数。计数器有一个输出z，当产生借位时z=1，否则z=0。解：1.先根据题意建立原始状态表和状态图据题意是两位二进制数减1计数器，故设状态变量为y2和y1，计数器的二进制状态图如下：,00,11,10,01,0/0,1/0,1/0,0/0,0/0,1/0,1/1,0/0,由状态图可得状态表如下：,.,116,x,y2y1,x,y2y1,T2,T1,2.用观察法可知该状态表已为最简，故省去状态简化的步骤。而该状态表已经为二进制状态表，故又可省去状态编码的步骤。现可直接利用T触发器的激励函数表和二进制状态表得到激励函数真值表，并由其真值表可作出激励函数的卡诺图，再得到激励函数的表达式，同时，可以从二进制状态表直接得出输出函数z：,.,117,3.画出逻辑电路图,.,118,例4用D触发器设计一个8421BCD码同步十进制加计数器。,1、列出8421码同步十进制加计数器的状态表,解：,.,119,2、确定激励方程组,D3、D2、D1、D0是触发器现态的函数,