数字电路与逻辑设计第五章.ppt

第五章 同步时序逻辑电路,第 五 章 同步时序逻辑电路,本章知识要点:,时序逻辑电路的基本概念;同步时序逻辑电路的分析和设计方法;典型同步时序逻辑电路的分析和设计。,第五章 同步时序逻辑电路,5.1 概 述,5.1.1 时序逻辑电路的定义、结构和特点,若逻辑电路在任何时刻产生的稳定输出信号不仅与电路该时刻的输入信号有关，还与电路过去的输入信号有关，则称为时序逻辑电路。,一定义,第五章 同步时序逻辑电路,二结构,第五章 同步时序逻辑电路,时序逻辑电路由组合电路和存储电路两部分组成，通过反馈回路将两部分连成一个整体。,图中，x1,，xn为输入信号；Z1,，Zm为输出信号；y1,，ys为时序逻辑电路的“状态”；Y1,，Yr为时序逻辑电路中的激励信号；CP为时钟脉冲信号，是否存在CP，取决于时序逻辑电路的类型。,时序逻辑电路的状态y1,，ys是存储电路对过去输入信号记忆的结果，它随着外部信号的作用而变化。,次态与现态的概念:在对电路功能进行研究时，通常将某一时刻的状态称为“现态”，记作yn，简记为 y；将在某一现态下，外部信号发生变化后到达的新的状态称为“次态”，记作 yn+1。,第五章 同步时序逻辑电路,注意：次态与现态的概念是相对的！,三特点,第五章 同步时序逻辑电路,由组合电路和存储电路组成，具有对过去输入进行记忆的功能；包含反馈回路，通过反馈使电路功能与“时序”相关；输出由电路当时的输入和状态(过去的输入)共同决定。,5.1.2 时序逻辑电路的分类,通常按照电路的工作方式、电路输出对输入的依从关系或者输入信号的形式进行分类。,一按电路的工作方式分类,按照电路的工作方式，时序逻辑电路可分为同步时序逻辑电路和异步时序逻辑电路两种类型。,1.同步时序电路（1）特点：电路中有统一的定时信号，存储器件采用时钟控制触发器，电路状态在时钟脉冲控制下同时发生转换，即电路状态的改变依赖于输入信号和时钟脉冲信号。具体：状态如何变？取决与输入信号；状态何时变?取决于时钟信号；每个状态维持多久？取决于时钟脉冲的周期。,通常不把同步时钟信号作为输入信号处理，而是将它当成一种默认的时间基准。,第五章 同步时序逻辑电路,（2）现态与次态 同步时序电路中的现态与次态是针对某个时钟脉冲而言的。现态-指时钟脉冲作用之前电路所处的状态。次态-指时钟脉冲作用之后电路到达的状态。注意：前一个脉冲的次态即后一个脉冲的现态！,2.异步时序逻辑电路 异步时序逻辑电路的存储电路可由触发器或延时元件组成，电路中没有统一的时钟信号同步，电路输入信号的变化将直接导致电路状态的变化。,第五章 同步时序逻辑电路,（3）对时钟的要求 脉冲的宽度：必须保证触发器可靠翻转；脉冲的频率：必须保证前一个脉冲引起的电路响应完全结束后，后一个脉冲才能到来。,二按电路输出对输入的依从关系分类,1Mealy型电路：若时序逻辑电路的输出是电路输入和电路状态的函数，则称为Mealy型时序逻辑电路。2Moore型电路：若时序逻辑电路的输出仅仅是电路状态的函数，则称为Moore型时序逻辑电路。,Mealy型电路的输入和输出之间存在直接联系，而Moore型电路则是将全部输入转换成电路状态后再和输出建立联系。,第五章 同步时序逻辑电路,若一个时序逻辑电路没有专门的外部输出信号，而是以电路状态作为输出，则可视为Moore型电路的特殊情况。无论是同步时序逻辑电路或是异步时序逻辑电路，均有Mealy型和Moore型两种模型。,同步时序逻辑电路中两种模型的结构框图如下图所示。,第五章 同步时序逻辑电路,三按输入信号形式分类,时序逻辑电路的输入信号可以是脉冲信号也可以是电平信号。根据输入信号形式的不同，时 序逻辑电路通常又被分为脉冲型和电平型两种类型。下图所示为不同输入信号的波形图。,第五章 同步时序逻辑电路,5.1.3 同步时序逻辑电路的描述方法,同步时序电路可采用逻辑表达式、状态表、状态图进行描述。状态表和状态图是同步时序逻辑电路分析和设计的重要工具。此外，必要时还可以通过时间图加以描述。,一逻辑函数表达式,同步时序电路的结构和功能，可用3组逻辑函数表达式描述。,1输出函数表达式：Zi=fi(x1，xn,y1,，ys)i=1,2,m（Mealy型电路)Zi=fi(y1，ys)i=1,2,m（Moore型电路）,第五章 同步时序逻辑电路,2激励函数表达式：激励函数又称为控制函数，它反映了存储电路的输入Y与外部输入x和电路状 态y之间的关系。其函数表达式为 Yj=gj(x1，xn,y1,，ys)j=1,2,r,3次态函数表达式：次态函数用来反映同步时序电路的次态yn+1与激励函数Y和电路现态y之间的关系，它与触发器类型相关。其函数表达式为 y ln+1=kl(Yj，yl)j=1,2,r；l=1,2,，s,第五章 同步时序逻辑电路,二状态表,状态表：反映同步时序电路输出Z、次态yn+1与电路输入x、现态y之间关系的表格，又称为状态转移表。,表格的上方从左到右列出一位输入x的全部取值组合，表格左边从上到下列出电路的全部状态y，表格的中间列出对应不同输入组合和现态下的次态yn+1和输出Z。,表中，列数=一位输入的所有取值组合数；行数=触发器的状态组合数。,第五章 同步时序逻辑电路,状态表是同步时序电路分析和设计中常用的工具，它非常清晰地给出了同步时序电路在不同输入和现态下的次态和输出。,Moore型电路状态表的格式如左下表所示。,考虑到Moore型电路的输出Z仅与电路的现态y有关，为了清晰起见，将输出单独作为一列，表示其值完全由现态确定。,第五章 同步时序逻辑电路,三状态图,状态图：是一种反映同步时序电路状态转换规律及相应输入、输出取值关系的有向图。在状态图中，用圆圈表示电路的状态，连接圆圈的有向线段表示状态的转换关系，箭头的起点表示现态，终点表示次态，当箭头起止于同一状态时，表明在指定输入下状态不变。,第五章 同步时序逻辑电路,用状态图描述同步时序电路的逻辑功能具有直观、形象等优点。状态图和状态表示是同步时序电路分析和设计的重要工具，相比之下，状态表更规范，状态图更形象。,四时间图,时间图是用波形图的形式来表示输入信号、输出信号和电路状态等的取值在各时刻的对应关系，通常又称为工作波形图。在时间图上，可以把电路状态转换的时刻形象地表示出来。,第五章 同步时序逻辑电路,第五章 同步时序逻辑电路,5.2 同步时序逻辑电路分析,5.2.1 分析方法概述,分析同步时序电路有两种常用的方法，一种是表格法，另一种是代数法。,一.表格分析法的一般步骤,第五章 同步时序逻辑电路,1写出输出函数和激励函数表达式；,2借助触发器功能表列出电路次态真值表；,3作出状态表和状态图（画出时间图）；,4归纳出电路的逻辑功能。,二.代数分析法的一般步骤,第五章 同步时序逻辑电路,1写出输出函数和激励函数表达式；,2把激励函数表达式代入触发器的次态方 程，导出电路的次态方程组；,3作出状态表和状态图（画出时间图）；,4归纳出电路的逻辑功能。,5.2.2 分析举例,例1 用表格法分析下图所示同步时序逻辑电路。,解:电路由两个J-K触发器和一个异或门组成，电路的输入为x，电路的状态(即触发器状态)用y2、y1表示。电路的输出即状态变量，因此，该电路属于Moore型电路的特例。,1.写出输出函数和激励函数表达式 该电路的输出即为状态，各触发器的激励函数表达式为 J1=K1=1；J2=K2=xy1,第五章 同步时序逻辑电路,2列出电路次态真值表,第五章 同步时序逻辑电路,演示动画,第五章 同步时序逻辑电路,作出状态表 和状态图,4描述电路的逻辑功能。由状态图可知，该电路是一个2 位二进制数可逆计数器。,在时序逻辑电路分析中，除了状态图和状态表之外，通常还用到时间图。,第五章 同步时序逻辑电路,作时间图的一般步骤：假设电路初始状态，并拟定一典型输入序列；作出状态和输出响应序列；根据响应序列画出波形图。,CP:1 2 3 4 5 6 7 8 9 x:1 1 1 1 0 0 0 0 0 y2:0 1 1 0 0 0 1 1 0 y1:0 1 0 1 0 1 0 1 0 y2n+1:1 1 0 0 0 1 1 0 0 y1n+1:1 0 1 0 1 0 1 0 1,第五章 同步时序逻辑电路,设电路的初始状态y2y1=00,输入x为电平信号，典型输入序列为111100000，根据状态图可作出电路的状态响应序列如下：,根据状态响应序列，可作出时间图。由于前一个时钟脉冲的次态即为后一个时钟脉冲的现态，所以，时间图中可以将现态和次态共用一个波形表示。,CP:1 2 3 4 5 6 7 8 9 x:1 1 1 1 0 0 0 0 0 y2:0 1 1 0 0 0 1 1 0 y1:0 1 0 1 0 1 0 1 0 y2n+1:1 1 0 0 0 1 1 0 0y1n+1:1 0 1 0 1 0 1 0 1,第五章 同步时序逻辑电路,例2 分析下图所示的同步时序电路。,解 该电路有一个输入x和一个输出Z。输出Z与输入x及电路状态均有直接联系，因此属于Mealy型。,1写出输出函数和激励函数的表达式,第五章 同步时序逻辑电路,2.列出电路次态真值表 根据激励函数表达式和D触发器的功能表，可作出该电路的次态真值表如下表所示。,第五章 同步时序逻辑电路,3.作出状态表和状态图 根据输出函数表达式和次态真值表，可作出该电路的状态表和状态图如下。,演示动画,第五章 同步时序逻辑电路,4.说明电路的逻辑功能,CP:1 2 3 4 5 6 7 8 9x:0 1 0 1 1 0 1 0 0y2:0 0 0 1 0 0 1 0 1y1:0 0 1 0 1 1 0 1 0y2n+1:0 0 1 0 0 1 0 1 0y1 n+1:0 1 0 1 1 0 1 0 0Z:0 0 0 1 0 0 1 0 0,设电路初始状态为“00”，输入x为脉冲信号，其输入序列为010110100。根据状态图可作出电路的状态响应序列和输出响应序列如下:,由输入、输出序列可以看出，一旦输入x出现信号“101”，输出Z便产生一个相应的1，其他情况下输出Z为0。因此，该电路是一个“101”序列检测器。,第五章 同步时序逻辑电路,例3 试用代数法分析下图所示同步时序逻辑电路的逻辑功能。,解 该电路由一个J-K触发器和四个逻辑门构成，电路有两个输入端x1和x2，一个输出端Z。输出Z与输入和状态均有直接联系，属于Mealy 型电路。,1写出输出函数和激励函数表达式,第五章 同步时序逻辑电路,2把激励函数表达式代入触发器的次态方程，得到电路的次态方程组,该电路的存储电路只有一个触发器，因此，电路只有一个次态方程。,第五章 同步时序逻辑电路,3 根据次态方程和输出函数表达式作出状态表和状态图,根据次态方程和输出函数表达式，可以作出该电路的状态表和状态图如下。,第五章 同步时序逻辑电路,4 画出时间图，并说明电路的逻辑功能,时钟节拍：1 2 3 4 5 6 7 8 输入x1：0 0 1 1 0 1 1 0 输入x2：0 1 0 1 1 1 0 0 状态 y：0 0 0 0 1 1 1 1 输出Z：0 1 1 0 0 1 0 1,设电路初态为“0”，输入x1为00110110，输入x2为01011100，根据状态图可作出电路的输出和状态响应序列如下:,第五章 同步时序逻辑电路,根据状态响应序列可作出时间图如下：,时钟节拍：1 2 3 4 5 6 7 8输入x1：0 0 1 1 0 1 1 0输入x2：0 1 0 1 1 1 0 0状态 y：0 0 0 0 1 1 1 1输出Z：0 1 1 0 0 1 0 1,第五章 同步时序逻辑电路,电路实现了何功能？,电路实现了串行加法器的功能。x1为被加数，x2为加数，按照先低位后高位的顺序串行地输入。每位相加产生的进位由触发器保存下来参加下一位相加，输出Z从低位到高位串行输出“和”。时间图给出了x1=01101100,x2=00111010相加得到“和”Z=10100110的过程。状态y=11110000是由低位到高位依次产生的进位信号。,第五章 同步时序逻辑电路,状态表有何规律？,为了使逻辑功能更清晰，亦可按照左高右低的顺序将输入输出序列表示如下：时钟节拍：8 7 6 5 4 3 2 1 x1(被加数)：0 1 1 0 1 1 0 0 x2(加数)：0 0 1 1 1 0 1 0 y(进位)：1 1 1 1 0 0 0 0 Z(和数)：1 0 1 0 0 1 1 0,上面举例介绍了采用两种方法分析同步时序逻辑电路的全过程。实际问题分析时，可视具体情况灵活运用，根据给定逻辑电路的复杂程度不同，通常可以省去某些步骤。例如，列次态真值表或画时间图等。,演示动画,第五章 同步时序逻辑电路,5.3 同步时序逻辑电路的设计,同步时序逻辑电路的设计是指根据特定的逻辑要求，设计出能实现其逻辑功能的时序逻辑电路。显然，设计是分析的逆过程，即：,同步时序逻辑电路设计追求的目标是，使用尽可能少的触发器和逻辑门实现预定的逻辑要求！,第五章 同步时序逻辑电路,设计一般步骤,第五章 同步时序逻辑电路,1形成原始状态图和原始状态表；,2状态化简，求得最小化状态表；,3状态编码，得到二进制状态表；,4选定的触发器类型，并求出激励函数 和输出函数最简表达式；,5画出逻辑电路图。,5.3.1 建立原始状态图和原始状态表,原始状态图和原始状态表是对设计要求的最原始的抽象。建立正确的原始状态图和状态表是最关键的一步。由于状态图比状态表更形象、灵活，一般先画状态图后作状态表；其次，由于在开始时往往不知道描述一个给定的逻辑问题需要多少状态，因此，一般用字母或数字表示状态。,一.确定电路模型 设计成Mealy型？Moore型？将电路设计成哪种模型?有的问题已由设计要求规定，有的问题可由设计者选择。不同的模型对应的电路结构不同，设计者在选择时，应根据问题中的信号形式、电路所需器件的多少等综合考虑。,形成原始状态图应考虑如下4个方面问题：,第五章 同步时序逻辑电路,采用何方法？,二.设立初始状态 时序逻辑电路在输入信号开始作用之前的状态称为初始状态。建立原始状态图时，应首先设立初始状态，然后从初始状态出发考虑在各种输入作用下的状态转移和输出响应。,三.根据需要记忆的信息增加新的状态 同步时序电路中状态数目的多少取决于需要记忆和区分的信息量。一般来说，若在某个状态下出现的输入信号能用已有状态表示，则应转向已有状态。仅当某个状态下出现的输入信号不能用已有状态表示时，才令其转向新的状态。,第五章 同步时序逻辑电路,四确定各时刻电路的输出 时序逻辑电路的功能是通过输出对输入的响应来体现的。在建立原始状态图时，必须确定各时刻的输出值。在Moore型电路中，应指明每种状态下对应的输出；在Mealy型电路中应指明从每一个状态出发，在不同输入作用下的输出值。,注意：在描述一个逻辑问题的原始状态图和原始状态表中，状态数目不一定能达到最少，这一点无关紧要，因为可以对它再进行状态化简。设计者应把清晰、正确地描述设计要求放在第一位。,第五章 同步时序逻辑电路,如果对于所设立的每一个状态，在不同输入取值下都有确定的次态和输出。则将这类状态图和状态表称为完全确定状态图和状态表，由它们所描述的电路称为完全确定电路。,实际应用中，根据某些设计要求建立的原始状态图和原始状态表中往往存在不确定的次态或输出，即某些状态在某些输入取值下的次态或输出是随意的。这种状态图和状态表被称为不完全确定状态图和状态表，所描述的电路称为不完全确定电路。,第五章 同步时序逻辑电路,例1 设计一个模5可逆计数器，该电路有一个输入x和一个输出Z。输入x为加、减控制信号。当x=0时，计数器在时钟脉冲作用下进行加1计数；当x=1时，计数器在时钟脉冲作用下进行减1计数。输出Z为进位或借位信号。试建立该计数器的Mealy型原始状态图和状态表。,解 该问题已指定电路模型为Mealy型，且输入和状态、输出之间的关系也非常清楚，所以状态图的建立很容易。,第五章 同步时序逻辑电路,假设模5计数器的5个状态分别用0、1、2、3、4表示，其中0为初始状态。,根据题意可作出原始状态图和原始状态表如下。,第五章 同步时序逻辑电路,原始状态表,例2 某序列检测器有一个输入端x和一个输出端Z。输入端 x 输入一串随机的二进制代码，当输入序列中出现“011”时，输出Z产生一个1输出，平时Z输出0。典型输入、输出序列如下。输入x:1 0 1 0 1 1 1 0 0 1 1 0 输出Z:0 0 0 0 0 1 0 0 0 0 1 0 试作出该序列检测器的原始状态图和原始状态表。,解 1.假定用Mealy型同步时序逻辑电路实现该序列检测器的逻辑功能。,设:状态A-电路的初始状态；状态B-表示收到了序列“011”中的第一个信号“0”；状态C-表示收到了序列“011”中的前面两位“01”；状态D-表示收到了序列“011”。,第五章 同步时序逻辑电路,该序列检测器Mealy型状态图的构造过程如下。相应的原始状态表如右下表所示。,演示动画,第五章 同步时序逻辑电路,从上述过程可知，一个序列检测器所需要的状态数与要识别的序列长度相关，序列越长，需要记忆的代码位数越多，状态数也就越多。,2假定用Moore型同步时序逻辑电路实现该序列检测器的逻辑功能.由于电路输出完全取决于状态，而与输入无直接联系。在作状态图时，应将输出标记在代表各状态的圆圈内。,设电路初始状态为A，并用状态B、C、D分别表示收到了输入x送来的0、01、011。显然，根据题意，仅当处于状态D时电路输出为1，其他状态下输出均为0。,第五章 同步时序逻辑电路,构造Moore型原始状态图的过程如下：,相应的原始状态表如下表所示。,第五章 同步时序逻辑电路,例3 设计一个代码检测器，用于检测串行输入的8421码，其输入的顺序是先低位后高位，当出现非法数字(即输入1010，1011，1100，1101，1110，1111)时，电路的输出为1。试作出该时序电路的Mealy模型状态图和状态表。,解 根据题意，电路有一个输入和一个输出。设输入为x，输出为Z。由于输入的8421码是先低位后高位，因此，判断输入是否为非法数字时，应从低位到高位查看各位输入值。,第五章 同步时序逻辑电路,与序列检测器有何区别？,设：状态A-起始状态；状态B和C-表示最低一位代码的两种不同取值0和1；状态D，E，F，G-表示低两位的码的四种不同取值0011；状态H，I，J，K，L，M，N，P-表示低三位代码的八种取值000111。当x输入的第四位代码到来时，即可对输入代码进行判断，若出现非法数字，电路的输出为1，否则为0，并返回到起始状态A。,第五章 同步时序逻辑电路,根据以上分析假设，可以得到下图所示的原始状态图。,注意：当4位代码检测完后，应转向初始状态A，以便检查下一组代码。,演示动画,第五章 同步时序逻辑电路,由原始状态图转换后的原始状态表如下表所示。,思考:1.代码检测器与序列检测器的主要区别是什吗？2.若将该代码检测器设计成Moore型同步时序电路,该如何建立原始状态图？需增加几个状态？,第五章 同步时序逻辑电路,若将该代码检测器设计成Moore型同步时序电路，则电路输出只与状态相关。令：状态A-初始状态；状态B和C-表示代码最低位的取值0和1；状态D、E、F、G-分别表示代码低二位的4种取值组合0011；状态H、I、J、K、L、M、N、P-分别表示低三位的8种取值组合00 0111；状态X-表示4位代码中的10种合法码；状态Y-表示4位代码中的6种非法码。显然，电路仅当处于状态Y时输出为1，其他状态下均输出0。,第五章 同步时序逻辑电路,原始状态图如下图所示，原始状态表略。从该例可以看出，实现同一逻辑功能的Moore型电路比Mealy型电路需要的状态数多。,思考：1.该Moore型状态图在Mealy状态图的基础上增加了两个状态，请问是否能只增加一个状态？2.该Moore型状态图中，从状态X、Y出发输入0或1时，为什么不转向初始状态A?,第五章 同步时序逻辑电路,上述各例所建立的原始状态图和原始状态表中，对于所设立的每一个状态，在不同输入取值下都有确定的次态和输出。通常将这类状态图和状态表称为完全确定状态图和状态表，由它们所描述的电路称为完全确定电路。,实际应用中，根据某些设计要求建立的原始状态图和原始状态表中往往存在不确定的次态或输出，即某些状态在某些输入取值下的次态或输出是随意的。这种状态图和状态表被称为不完全确定状态图和状态表，所描述的电路称为不完全确定电路。,第五章 同步时序逻辑电路,例4 设计一个用于引爆控制的同步时序电路，该电路有一个输入端 x 和一个输出端Z。平时输入 x 始终为0，一旦需要引爆，则从 x 连续输入4个1 信号(不被0间断)，电路收到第四个1后在输出端 Z 产生一个1信号点火引爆，该电路连同引爆装置一起被炸毁。试建立该电路的Mealy型状态图和状态表。（该问题的实际意义？-施工的安全性！）,解 该电路实际上是一个用于特殊场所的“1111”序列检测器。它与一般序列检测器有两点不同：1.输入带有约束条件，即一旦输入出现1，则一定是不被0间断的连续4个1；2.收到4个1后，输出产生的引爆信号使电路自毁，故此时不再存在次态问题。,第五章 同步时序逻辑电路,设：状态A-电路初始状态；状态B-表示收到了第一个1输入；状态C-表示收到了连续2个1输 入；状态D-表示收到了连续3个1输入。根据题意，可得到该电路的Mealy型原始状态图和原始状态表如下。图、表中用“d”表示不确定次态或不确定输出。,演示动画,第五章 同步时序逻辑电路,注意:在时序电路设计中，利用不完全确定状态表中不确定次态和不确定输出的随意性，通常可使 设计方案变得更简单。这一点类似包含无关最小项的组合电路设计，只不过在处理上要复杂一些。,第五章 同步时序逻辑电路,5.3.2 状态化简,什么叫状态化简？指采用某种化简技术从原始状态表中消去多余状态，得到一个描述给定的逻辑功能的包含状态数目达到最少的状态表，通常称为最小化状态表。,目的：简化电路结构。状态数目的多少直接决定电路中所需触发器数目的多少。设状态数目为n,所需触发器数目为m,则应满足如下关系：2m n 2 m-1 为了降低电路的复杂性和电路成本，应尽可能状态表中包含的状态数达到最少。,方法：常用方法有观察法、输出分类法、隐含表法等。下面讨论最常用的一种方法-隐含表法。,第五章 同步时序逻辑电路,化简完全给定原始状态表和不完全给定原始状态表引用了不同的概念，并且处理过程有所不同。,一.完全确定状态表的化简,1几个概念,(1)等效状态,定义 设状态Si和Sj是完全确定状态表中的两个状态，若对于所有可能的输入序列，分别从状态Si和状态Sj出发，所得到的输出响应序列完全相同，则状态Si和Sj是等效的，记作(Si，Sj)，又称状态Si和Sj 为等效对。,请注意掌握三点：定义、判断方法和性质。,第五章 同步时序逻辑电路,判断方法 若状态Si和Sj 是完全确定的原始状态表中的两个现态，则Si和Sj 等效的条件为在一位输入的各种取值组合下满足两条：第一，输出相同；第二，次态属于下列情况之一：a.次态相同；b.次态交错或为各自的现态；c.次态循环或为等效对。,第五章 同步时序逻辑电路,交错？例如，在右表中当X=0时，现态A、B的次态相同，现态C、D的次态交错；,循环？当X=1时，现态A、B的次态为C、D,而现态C、D的次态为A、B，构成次态循环，即,等效类是一个广义的概念，两个状态或多个状态均可以组成一个等效类，甚至一个状态也可以称为等效类，因为任何状态和它自身必然是等效的。,第五章 同步时序逻辑电路,(3)最大等效类 所谓最大等效类，是指不被任何别的等效类所包含的等效类。注意：这里所指的最大，并不是指包含的状态最多，而是指它的独立性，即使是一个状态，只要它不被包含在别的等效类中，也是最大等效类。即：如果一个等效类不是任何其他等效类的子集，则该等效类称为最大等效类。,完全给定原始状态表的化简过程，就是寻找出表中的所有最大等效类，然后将每个最大等效类中的状态合并为一个新的状态，从而得到最小化状态表。简化后的状态数等于最大等效类的个数！,第五章 同步时序逻辑电路,2状态化简,(1)隐含表化简法的一般步骤,作隐含表 隐含表是一个直角三角形阶梯网格，横向和纵向的网格数等于原始状态表中的状态数n减1。表的横向从左到右依次标上原始状态表中的前n-1个状态，纵向自上到下依次标上原始状态表中的后n-1个状态。表中每个方格代表一个状态对。,第五章 同步时序逻辑电路,顺序比较：按照隐含表中从上至下、从左至右的顺序，对照原始状态表依次对所有“状态对”进行逐一检查和比较，并将检查结果标注在隐含表中的相应方格内。,比较结果标注如下：等效-在相应方格内填上“”；不等效-在相应方格内填上“”；与其他状态对相关-在相应方格内填上相关的状态对。,关联比较：指对那些在顺序比较时尚未确定是否等效的状态对作进一步检查。直到判别出状态对等效或不等效为止。,寻找等效对 利用隐含表寻找“等效对”一般需要进行两轮比较，首先进行顺序比较，然后进行关联比较。,第五章 同步时序逻辑电路,求出最大等效类 在找出所有等效对之后，可利用等效状态的传递性，求出各最大等效类。确定各最大等效类时应注意两点：,各最大等效类之间不应出现相同状态；原始状态表中的每一个状态必须属于某一个最大等效类，否则，化简后的状态表不能描述原始状态表的功能。,状态合并，作出最小化状态表 将每个最大等效类中的全部状态合并为一个状态，即可得到和原始状态表等价的最小化状态表。,第五章 同步时序逻辑电路,为什么？,(2)化简举例,例 化简下表所示原始状态表。,解 作隐含表 给定原始状态表具有7个状态，根据画隐含表的规则，可画出隐含表框架如下。,演示动画,第五章 同步时序逻辑电路,寻找等效对 根据等效状态的判断标准，依次检查每个状态对，可得到顺序比较结果如图(a)所示。关联比较的结果如图(b)所示。,第五章 同步时序逻辑电路,图中，由状态C和F等效，可判断出状态A和B等效。检查状态A、E的次态对时，出现如下所示关系：,已知状态C和F等效，状态BE与状态AE构成循环，故状态A和E是等效状态对，B和E也是等效状态对。状态D、G对应的方格中含有CD和DE，因状态CD不等效，故状态D和G不等效，故在对应的方格中加记号“/”。,由判断结果可知，原始状态表中的7个状态共有四个等效对：(A，B)，(A，E)，(B，E)，(C，F)。,第五章 同步时序逻辑电路,状态合并，作出最小化状态表 令 A,B,E-a、C,F-b、D-c、G-d，并代入原始状态表中，即可得到化简后的状态表如下边右表所示。,求出最大等效类 由所得到的等效对和最大等效类的定义可知，原始状态表中的7个状态共构成A,B,E,C,F,D,G四个最大等效类。,第五章 同步时序逻辑电路,二.不完全确定状态表的化简,化简不完全确定原始状态表时，将引入一个新的概念相容状态。,1相容状态和相容类,定义 假定状态Si 和Sj 是不完全确定状态表中的两个状态，若对于所有的有效输入序列，分别从状态Si和Sj出发，所得到的确定输出响应序列是完全相同的，则状态Si和Sj是相容的，又称为相容对，记作(Si，Sj)。,有效输入序列：若从状态S出发，某输入序列作用下所得到的状态响应序列除最后一个次态外，其他次态都是确定的，则该输入序列对状态S是有效的。,第五章 同步时序逻辑电路,（1）相容状态,例如，对如下状态表中的状态A而言，序列000011、01111是有效的，而序列011010、11001是无效的。,第五章 同步时序逻辑电路,为什么？,相容状态的判断 假定状态Si 和Sj是不完全确定状态表中的两个现态，状态Si 和Sj 相容的条件为在一位输入的各种取值组合下满足如下两条。第一，输出相同，或者其中的一个(或两个)输出不确定。第二，次态属于下列情况之一：a.次态相同；b.次态交错或为各自的现态；c.次态循环或为相容对；d.其中的一个(或两个)为不确定状态。,第五章 同步时序逻辑电路,注意!相容状态不具备传递性！这是因为判断两个状态是否相容时，对于不给定的输出和不给定的次态可以随意指定的缘故。例如，在下表中，有状态A、B 相容，状态B、C 相容，但状态A、C不相容。,第五章 同步时序逻辑电路,(2)相容类 相容类是由彼此相容的状态构成的集合。处于同一相容类中的所有状态之间都是两两相容的。例如，若有相容对(S1,S2)、(S2,S3)和(S1,S3)，则可构成相容类S1,S2,S3。,(3)最大相容类 若一个相容类不是任何其他相容类的子集，则该相容类称为最大相容类。注意：由于相容状态无传递性，所以，同一原始状态表的各最大相容类之间可能存在相同状态，即同一状态可能出现在不同的最大相容类中。,第五章 同步时序逻辑电路,2.不完全确定状态表的化简,(1)化简步骤,作隐含表，寻找相容状态对 利用隐含表寻找相容对的过程与化简完全确定状态表时寻找等效对的过程是相同的，仅仅是状态相容与状态等效的判断有所不同而已。,第五章 同步时序逻辑电路,利用状态合并图，求出最大相容类 状态合并图：是求最大相容类工具。它将状态表的所有状态以“点”的形式均匀地绘在圆周上，然后把所有相容对用线段连接起来。若某些顶点任意两点之间都有连线，则这些顶点状态的集合构成一个最大相容类。,图（a）、（b）、（c）分别表示包含3个、4个和5个状态的最大相容类状态合并图。,第五章 同步时序逻辑电路,利用闭覆盖表，求最小闭覆盖 最小闭覆盖：是从最大相容类(或相容类)中选出一个相容类的集合，该相容类集合满足以下3个条件：a.覆盖-即所选相容类集合应包含原始状态表的全部状 态。b.最小-即所选相容类集合中相容类个数应最少。c.闭合-即所选相容类集合中的任一相容类，在原始状 态表中任一输入条件下产生的次态组合应该属 于该集合中的某一个相容类。,化简不完全确定状态表的关键是寻找一个最小闭覆盖。,第五章 同步时序逻辑电路,为什么？,闭覆盖表：闭覆盖表反映相容类集合对状态的覆盖情况和相容类的闭合关系。表的左边自上而下列出所选相容类，表的中间覆盖栏列出各相容类对原始状态表中状态的覆盖情况，表的右边闭合栏列出各相容类在一位输入各种取值组合下的次态组合。注意：相容类包括最大相容类和它们的子集。,状态合并，作出最小化状态表 将最小闭覆盖中的每个相容类用一个新的状态符号表示，再将其代入原始状态表中，即可得到与原始状态表功能相同的最小化状态表。,第五章 同步时序逻辑电路,(2)化简举例,解 原始状态表中存在不确定的次态和输出，属于不完全确定状态表。,例 化简原始状态表。,第五章 同步时序逻辑电路,作隐含表，寻找相容状态对 利用隐含表，根据相容状态的判断标准对各状态对进行顺序比较和关联比较后的结果如右下图所示。,由隐含表可知，该状态表中的相容状态对有：(A,B)、(A,C)、(A,D)、(A，E)、(B，D)、(C，D)、(C，E)。,第五章 同步时序逻辑电路,作状态合并图，找出最大相容类 根据相容状态对(A,B)、(A,C)、(A,D)、(A，E)、(B，D)、(C，D)、(C，E)。可作出状态合并图如下图所示。,从状态合并图得到最大相容类为A,B,D、A,C,D、A,C,E。,第五章 同步时序逻辑电路,作闭覆盖表，求最小闭覆盖 由3个最大相容类，可作出其闭覆盖表如下表所示。,由闭覆盖表和选择最小闭覆盖的3个条件可知，该例的最小闭覆盖可由最大相容类A,B,D和A,C,E组成。,思考：若闭覆盖表中A,B,D在X=1时的次态组合为CD,最小闭覆盖由最大相容类A,B,D和A,C,E组成行吗？为什么？,第五章 同步时序逻辑电路,第五章 同步时序逻辑电路,构成最小闭覆盖的相容类并不一定是最大相容类。在某些情况下，如果仅仅从最大相容类中去选择最小闭覆盖，则合并后的状态表不一定是最简的。而如果在满足覆盖的前提下，在最大相容类和非最大相容类之间作恰当的选择，却能得到最简的状态表。,注 意：状态合并时，若存在确定的次态和不确定的次态，则应取确定的次态；若存在确定的输出和不确定的输出，则应取确定的输出值。例如，原始状态表中的状态A、B、D在输入x=0时的输出有1和d两种，合并后的状态a在x=0时的输出应为1。,第五章 同步时序逻辑电路,看一个例子！,为什么？,解 该原始状态表中存在不确定的次态和输出，属于不完全确定状态表。,例2 化简如下原始状态表。,第五章 同步时序逻辑电路,第五章 同步时序逻辑电路,从状态合并图得到最大相容类为A,B,C、A,C,D、A,D,E。,第五章 同步时序逻辑电路,由3个最大相容类，可作出其闭覆盖表如下表所示。,由闭覆盖表和选择最小闭覆盖的3个条件可知，该例的最小闭覆盖可由最大相容类A,B,C、A,C,D和A,D,E。,第五章 同步时序逻辑电路,如果不从最大相容类中选最小闭覆盖，而是选最大相容类A,B,C和相容类D,E，可作出其闭覆盖表如下表所示。,由闭覆盖表和选择最小闭覆盖的3个条件可知，该例的最小闭覆盖可由最大相容类A,B,C 和D,E组成。显然，这样更简单！,5.3.3 状态编码,状态编码：是指给最小化状态表中用字母或数字表示的状态，指定一个二进制代码，形成二进制状态表。状态编码也称状态分配，或者状态赋值。,状态编码的任务是：确定状态编码的长度(即二进制代码的位数，或者说所需触发器个数)；寻找一种最佳的或接近最佳的状态分配方案。以便使所设计的时序电路最简单。,第五章 同步时序逻辑电路,一确定二进制代码的位数,设最小化状态表的状态数为N，状态编码的长度为m,则状态数N与状态编码长度m的关系为2m N 2m-1 例如，若某状态表的状态数N=7，则状态分配时，二进制代码的位数应为 m=3。或者说状态变量个数为3。,二确定状态分配方案,第五章 同步时序逻辑电路,随着状态数目的增加，分配方案的数目急剧增加。如何从众多的分配方案中寻找出一种最佳方案?在实际工作中，工程技术人员通常按照一定的原则、凭借设计的经验去寻找相对最佳的编码方案。一种常用方法称为相邻分配法。,相邻分配法的基本思想：在选择状态编码时，尽可能使激励函数和输出函数在卡诺图上的“1”方格处在相邻位置，从而有利于激励函数和输出函数的化简。,第五章 同步时序逻辑电路,相邻分配法的状态编码原则如下：次态相同，现态相邻。(即在相同输入条件下，具有相同次态的现态应尽可能分配相邻的二进制代码；)同一现态，次态相邻。(即在相邻输入条件下，同一现态的次态应尽可能分配相邻的二进制代码；)输出相同，现态相邻。(即在每一种输入取值下均具有相同输出的现态应尽可能分配相邻的二进制代码。),某些状态表常常出现不能同时满足3条原则的情况。此时，可按从至的优先顺序考虑。此外，从电路实际工作状态考虑，一般将初始状态分配“0”状态.,第五章 同步时序逻辑电路,为什么？,三举例,例 对如下状态表进行状态编码（设A为初始状态）。,解 所示状态表中，状态数N=4，故状态编码的长度应为 m=2。即实现该状态表的功能需要两个触发器。,第五章 同步时序逻辑电路,根据相邻法的编码原则，4个状态的相邻关系如下：根据原则，状态B和C应分配相邻的二进制代码；根据原则，状态B和C、A和D、C和D应分配相邻的二进制代码；根据原则，状态A和D应分配相邻的二进制代码。综合可知，状态分配时要求满足B和C、A和D、C和D相邻。在进行状态分配时，为了使状态之间的相邻关系一目了然，通常将卡诺图作为状态分配的工具。,假定状态变量用y2y1表示，并将A分配“0”，一种满足上述相邻关系的分配方案如右图所示。即状态A、B、C、D的状态编码依次为y2y1的取值00、01、11、10。,第五章 同步时序逻辑电路,将状态表中的状态A、B、C、D分别用编码00、01、11、10代替，即可得到该状态表的二进制状态表如右下表所示。,注意：满足分配原则的方案通常可以有多种，设计者可从中任选一种。,第五章 同步时序逻辑电路,5.3.4 确定激励函数和输出函数并画出逻辑电路图,任务