逻辑电路设计精选PPT.ppt

逻辑电路设计第1页，此课件共56页哦 设计的一般过程：设计的一般过程：1.1.建立给定问题的逻辑描述建立给定问题的逻辑描述 这一步的关键是弄清楚电路的输入和输出，建立输入和输出之间的逻辑关系，得到描述给定问题的逻辑表达式。求逻辑表达式有两种常用方法，即真值表法真值表法和分析法分析法。2.2.求出逻辑函数的最简表达式求出逻辑函数的最简表达式 为了使逻辑电路中包含的逻辑门最少且连线最少，要对逻辑表达式进行化简，求出描述设计问题的最简表达式。3.3.选择逻辑门类型并将逻辑函数变换成相应形式选择逻辑门类型并将逻辑函数变换成相应形式 根据简化后的逻辑表达式及问题的具体要求，选择合适的逻辑门，并将逻辑表达式变换成与所选逻辑门对应的形式。4.4.画出逻辑电路图画出逻辑电路图 根据实际问题的难易程度和设计者熟练程度，有时可跳过其中的某些步骤。设计过程可视具体情况灵活掌握。第2页，此课件共56页哦1.2 1.2 设计举例设计举例 解解 分析分析:“多数表决电路”是按照少数服从多数的原则对某项决议进行表决，确定是否通过。令令 逻辑变量逻辑变量A A、B B、C C-分别代表参加表决的3个成员，并约定逻辑变量取值为0表示反对，取值为1表示赞成；逻辑函数逻辑函数 F F-表示表决结果。F取值为0表示决议被否定，F取值为1表示决议通过。按照少数服从多数的原则可知，函数和变量的关系是：当当3 3个变量个变量A A、B B、C C中有中有2 2个或个或2 2个以上取值为个以上取值为1 1时，函数时，函数F F的值为的值为1 1，其他情况下函数其他情况下函数F F的值为的值为0 0。例例 设计一个三变量设计一个三变量“多数表决电路多数表决电路”。第3页，此课件共56页哦 建立给定问题的逻辑描述建立给定问题的逻辑描述假定采用“真值表法”，可作出真值表如下表所示。00000010010001111000101111011111ABCF由真值表可写出函数F的最小项表达式为F(A,B,C)=m(3,5,6,7)第4页，此课件共56页哦 求出逻辑函数的最简表达式求出逻辑函数的最简表达式作出函数F(A,B,C)=m(3,5,6,7)的卡诺图如下图所示。用卡诺图化简后得到函数的最简“与-或”表达式为 选择逻辑门类型并进行逻辑函数变换选择逻辑门类型并进行逻辑函数变换假定采用与非门构成实现给定功能的电路，则应将上述表达式变换成“与非-与非”表达式。即第5页，此课件共56页哦 画出逻辑电路图画出逻辑电路图由函数的“与非-与非”表达式，可画出实现给定功能的逻辑电路图如下图所示。本例采用的是“真值表法真值表法”，真值表法的优点是规整、清晰；真值表法的优点是规整、清晰；缺点是不方便，尤其当变量较多时十分麻烦缺点是不方便，尤其当变量较多时十分麻烦。第6页，此课件共56页哦2同步时序逻辑电路的设计同步时序逻辑电路的设计同同步步时时序序逻逻辑辑电电路路的的设设计计是是指指根根据据特特定定的的逻逻辑辑要要求求，设设计计出出能能实实现现其其逻逻辑辑功功能能的的时时序序逻逻辑辑电电路路。显然，设计是分析的逆过程，即：同步时序逻辑电路设计追求的目标是，使用尽可能少的触发器和同步时序逻辑电路设计追求的目标是，使用尽可能少的触发器和逻辑门实现预定的逻辑要求！逻辑门实现预定的逻辑要求！逻辑电路逻辑电路逻辑功能逻辑功能分析分析设计设计第7页，此课件共56页哦2状态化简，求得最小化状态表；状态化简，求得最小化状态表；设计的一般步骤如下：设计的一般步骤如下：1形成原始状态图和原始状态表；形成原始状态图和原始状态表；3状态编码，得到二进制状态表；状态编码，得到二进制状态表；4选定触发器的类型，并求出激励函数和输出函数最简选定触发器的类型，并求出激励函数和输出函数最简表达式；表达式；5画出逻辑电路图。画出逻辑电路图。原始状态图是对设计要求最原始的抽象,根据逻辑问题的文字描述理解电路的输入、输出及状态转移关系，进而形成状态图和状态表。由于开始得到的状态图和状态表可能包含多余的状态，所以称为原始状态图和原始状态表。采用状态化简技术，消去原始状态表中的多余的状态，求得最小化状态表。目的：目的：简化电路结构。把状态表中用字母或数字标注的每个状态用二进制代码表示，以便和电路中触发器的状态一致。根据选定的触发器类型，列出激励函数真值表，并求出激励函数和输出函数的最简表达式。其中，激励函数是由二进制状态表和触发器激励表共同确定的。以上步骤是就一般设计问题而言的。实际中设计者可以根据具体问题灵活掌握。当设计方案中包含有冗余状态时，必须对冗余状态的处理结果加以讨论，以确保电路逻辑功能的可靠实现。第8页，此课件共56页哦5.3.1建立原始状态图和原始状态表建立原始状态图和原始状态表原始状态图和原始状态表是对设计要求的最原始的抽象，是构造相应电路的依据。由于状态图比状态表更形象、灵活，一般先画状态图后作状态表一般先画状态图后作状态表。如果原始状态图不能正确地反映设计要求，则依此设计出来的电路必然是错误的。因此，建立正确的原始状态图和状态表是同步时序电路设计中最关键的一步。原始状态图的形成是建立在对设计要求充分理解的基础之上的，设计者必须对给定的问题进行认真、全面地分析，弄清楚电路输出和输入的关系以及状态的转换关系。一、一、确定电路确定电路模型模型设计成设计成Mealy型？型？Moore型？型？形成原始状态图时一般应考虑如下几个方面问题：形成原始状态图时一般应考虑如下几个方面问题：二、二、设立初始状态设立初始状态时序逻辑电路在输入信号开始作用之前的状态称为初初始始状状态态。同一个电路用不同状态作为初始状态时，对相同输入序列所产生的状态响应序列和输出响应序列一般是不相同的。因此，在建立原始状态图时，应首先设立初始状态，然后从初始状态出发考虑在各种输入作用下的状态转移和输出响应。第9页，此课件共56页哦三、三、根据需要记忆的信息增加新的状态根据需要记忆的信息增加新的状态同步时序电路中状态数目的多少取决于需要记忆和区分的信息量。一般来说，若在某个状态下出现的输入信号能用已有状态表示，则应转向已有状态。仅当某个状态下出现的输入信号不能用已有状态表示时，才令其转向新的状态。这样，从初始状态出发，逐个增加和完善，直到每个状态下各种输入取值均已考虑而没有新的状态出现为止。四、四、确定各时刻电路的输出确定各时刻电路的输出在建立原始状态图时，必须确定各时刻的输出值。在Moore型电路中，应指明每种状态下对应的输出；在Mealy型电路中应指明从每一个状态出发，在不同输入作用下的输出值。在描述一个逻辑问题的原始状态图和原始状态表中，状态数目不一定能达到最少，这一点无关紧要，因为可以对它再进行状态化简。设计者应把清晰、正确地描述设计要求放在第一位。其次，由于在开始时往往不知道描述一个给定的逻辑问题需要多少状态，因此，在原始状态图和状态表中一般用字母或数字表示状态。第10页，此课件共56页哦例例某序列检测器有一个输入端x和一个输出端Z。输入端x输入一串随机的二进制代码，当输入序列中出现“011”时，输出Z产生一个1输出，平时Z输出0。典型输入、输出序列如下。输输入入x:101011100110输出输出Z:000001000010试作出该序列检测器的原始状态图和原始状态表。解解1.假定用假定用Mealy型同步时序逻辑电路实现该序列检测器的逻辑功型同步时序逻辑电路实现该序列检测器的逻辑功能能.设设:状态状态A-电路的初始状态；状态状态B-表示收到了序列“011”中的第一个信号“0”；状态状态C-表示收到了序列“011”中的前面两位“01”；状态状态D-表示收到了序列“011”。第11页，此课件共56页哦当电路处在状态A输入x为0时，应令输出Z为0转向状态B；而处在状态A输入x为1时，应令输出Z为0停留在状态A，因为输入1不是序列011的第一个信号，故不需要记住。该转换关系如图所示。当电路处于状态B输入x为0时，尽管它不是序列011的第二个信号，但仍可作为序列中的第一个信号，故可令电路输出为0，停留在状态B；若输入x为1，则意味着收到了序列011的前面两位01，可令电路输出0转向状态C。如图所示。第12页，此课件共56页哦当电路处于状态C输入x为0时，则收到的连续3位代码为010，不是关心的序列011，但此时输入的0依然可以作为序列的第一个信号，故应输出0转向状态B；若输入x为1，则表示收到了序列011，可用一个新的状态D记住，可令电路输出1转向状态D。如图所示。当电路处于状态D输入x为0时，应输出0转向状态B；若输入x为1，则应输出0，转向状态A。至此，得到了该序列检测器完整的Mealy型状态图，如图(d)所示。相应的原始状态表如表所示。第13页，此课件共56页哦可画出状态图如下：可画出状态图如下：相应状态表如下：相应状态表如下：第14页，此课件共56页哦2假假定定用用Moore型型同同步步时时序序逻逻辑辑电电路路实实现现该该序序列列检检测测器器的的逻逻辑辑功功能能.由于电路输出完全取决于状态，而与输入无直接联系。在作状态图时，应将输出标记在代表各状态的圆圈内。设电路初始状态为A，并用状态B、C、D分别表示收到了输入x送来的0、01、011。显然，根据题意，仅当处于状态D时电路输出为1，其他状态下输出均为0。第15页，此课件共56页哦当从初始状态开始，输入端x正好依次输入0、1、1时，则状态从A转至B、B转至C、C转至D。据此可得到部分状态图如图左图所示。若A状态下输入为1，则不是指定序列中的第一位信号，不必记忆，可令状态停留在A；B状态下输入为0时，它不是指定序列的第二位，但可作为指定序列的第一位，故可令其停留在B；C状态下输入0时，它不是指定序列的第三位，但同样可作为第一位，故令其转向状态B；D状态下输入0时，同样应转向B，而输入为1时，则应令其进入状态A。完整的Moore型原始状态图如图右图所示。1第16页，此课件共56页哦构造构造Moore型原始状态图如下：型原始状态图如下：相应的原始状态表如下表所示。相应的原始状态表如下表所示。1第17页，此课件共56页哦例例设计一个用于引爆控制的同步时序电路，该电路有一个输入端x和一个输出端Z。平时输入x始终为0，一旦需要引爆，则从x连续输入4个1信号(不被0间断)，电路收到第四个1后在输出端Z产生一个1信号点火引爆，该电路连同引爆装置一起被炸毁。试建立该电路的Mealy型状态图和状态表。（该问题的实际意义？（该问题的实际意义？-施工的安全性！）施工的安全性！）解分析解分析:该电路实际上是一个用于特殊场所的“1111”序序列检测器。列检测器。它与一般序列检测器有两点不同：1.输入带有约束条件，即一旦输入出现1，则一定是不被0间断的连续4个1；2.收到4个1后，输出产生的引爆信号使电路自毁，故此时不再存在次态问题。第18页，此课件共56页哦设：状态设：状态A-电路初始状态；状态状态B-表示收到了第一个1输入；状态状态C-表示收到了连续2个1输入；状态状态D-表示收到了连续3个1输入。根据题意，可得到该电路的Mealy型原始状态图和原始状态表如下。图、表中用“d”表示不确定次态或不确定输出。第19页，此课件共56页哦注意注意:在时序电路设计中，状态化简时利用不完全确定状在时序电路设计中，状态化简时利用不完全确定状态表中不确定次态和不确定输出的随意性，通常可使设态表中不确定次态和不确定输出的随意性，通常可使设计方案变得更简单。这一点类似包含无关最小项的组合计方案变得更简单。这一点类似包含无关最小项的组合电路设计，只不过在处理上要复杂一些。电路设计，只不过在处理上要复杂一些。第20页，此课件共56页哦2.2状态化简状态化简什什么么叫叫状状态态化化简简？所谓状态化简，是指采用某种化简技术从原始状态表中消去多余状态，得到一个既能正确地描述给定的逻辑功能，又能使所包含的状态数目达到最少的状态表，通常称这种状态表为最小化状态表。目的：目的：简化电路结构。状态数目的多少直接决定电路中所需触发器数目的多少。设状态数目为n,所需触发器数目为m,则应满足如下关系：2mn2m-1方法方法：常用方法有观察法、输出分类法、隐含表法等。下面讨论最常用的一种方法-隐含表法。隐含表法。在利用隐含表进行化简时，对于完全给定原始状态表和不完全给定原始状态表引用了不同的概念，并且处理过程有所不同。第21页，此课件共56页哦一、一、完全确定状态表的化简完全确定状态表的化简1几个概念几个概念(1)等效状态等效状态定义定义设状态Si和Sj是完全确定状态表中的两个状态，若对于所有可能的输入序列，分别从状态Si和状态Sj出发，所得到的输出响应序列完全相同，则状态Si和Sj是等效的，记作(Si，Sj)，又称状态Si和Sj为等效对。请注意掌握三点：定义、判断方法和性质。第22页，此课件共56页哦 判断方法判断方法若状态Si和Sj是完全确定的原始状态表中的两个现态，则Si和Sj等效的条件可归纳为在一位输入的各种取值组合下满足如下两条：第一，输出相同；第一，输出相同；第二，次态属于下列情况之一：第二，次态属于下列情况之一：a.次态相同；次态相同；b.次态交错或为各自的现态；次态交错或为各自的现态；c.次态循环或为等效对。次态循环或为等效对。第23页，此课件共56页哦性质性质等效状态具有传递性。即假若S1和S2等效，S2和S3等效,那么，一定有S1和S3等效。记作(S1，S2)，(S2，S3)(S1，S3)(2)等效类等效类等效类：等效类：由若干彼此等效的状态构成的集合。在同一个等效类中的任意两个状态都是等效的。例如，由(S1，S2)和(S2，S3)可以推出(S1，S3)，进而可知S1、S2、S3属于同一等效类，记作S1，S2，S3，即(S1，S2)，(S2，S3)S1，S2，S3第24页，此课件共56页哦(3)最大等效类最大等效类所谓最大等效类，是指不被任何别的等效类所包含的等效类。注注意意：这里所指的最大，并不是指包含的状态最多，而是指它的独立性，即使是一个状态，只要它不被包含在别的等效类中，也是最大等效类。换而言之，如如果果一一个个等等效效类类不不是是任任何何其其他他等等效效类类的的子子集集，则则该该等等效效类类称称为为最最大等效类。大等效类。完全给定原始状态表的化简过程，就是寻找出表中的所有最大等效类，然后将每个最大等效类中的状态合并为一个新的状态，从而得到最小化状态表。简化后的状态数等于最大等效类的个数！简化后的状态数等于最大等效类的个数！第25页，此课件共56页哦2状态化简状态化简(1)隐含表化简法的一般步骤隐含表化简法的一般步骤作隐含表作隐含表隐含表是一个直角三角形阶梯网格，横向和纵向格数相同，即等于原始状态表中的状态数减1。隐含表中的方格是用状态名称来标注的，即横向从左到右按原始状态表中的状态顺序依次标上第一个状态至倒数第二个状态的状态名称，而纵向自上到下依次标上第二个状态至最后一个状态的名称。表中每个方格代表一个状态对。作隐含表作隐含表找等效对找等效对求最大等效类求最大等效类状态合并状态合并作最简状态表作最简状态表12345第26页，此课件共56页哦顺顺序序比比较较：按照隐含表中从上至下、从左至右的顺序，对照原始状态表依次对所有“状态对”进行逐一检查和比较，并将检查结果标注在隐含表中的相应方格内。比较结果标注如下：等效等效-在相应方格内填上“”；不等效不等效-在相应方格内填上“”；与其他状态对相关与其他状态对相关-在相应方格内填上相关的状态对。关关联联比比较较：指对那些在顺序比较时尚未确定是否等效的状态对作进一步检查。直到判别出状态对等效或不等效为止。寻找等效对寻找等效对利用隐含表寻找状态表中的全部等效对一般需要进行两轮比较，首先进行顺序比较顺序比较，然后进行关联比较关联比较。第27页，此课件共56页哦关联比较关联比较时，首先要确定隐含表中待检查的那些次态对是否等效，并由此确定原状态对是否等效。如果隐含表中某方格内有一个次态对不等效，则该方格所对应的两个状态就不等效，并在相应方格中增加标志/。若方格内的次态对均为等效状态对，则与该方格对应的状态为等效状态，该方格不增加任何标志。这种判别有时要反复多次，直到判别出状态对等效或不等效为止。第28页，此课件共56页哦求出最大等效类求出最大等效类在找出原始状态表中的所有等效对之后，可利用等效状态的传递性，求出各最大等效类。状态合并，作出最小化状态表状态合并，作出最小化状态表将每个最大等效类中的全部状态合并为一个状态，即可得到和原始状态表等价的最小化状态表。确定各最大等效类时应注意两点：确定各最大等效类时应注意两点：各最大等效类之间不应出现相同状态，因为若两个等效类之间有相同状态，则根据等效的传递性可令其合为一个等效类；原始状态表中的每一个状态都必须属于某一个最大等效类，换句话说，各最大等效类所包含的状态之和必须覆盖原始状态表中的全部状态，否则，化简后的状态表不能描述原始状态表所描述的功能。第29页，此课件共56页哦(2)化简举例化简举例例例化简下表所示原始状态表。解解作隐含表作隐含表给定原始状态表具有7个状态，根据画隐含表的规则，可画出隐含表框架如下。第30页，此课件共56页哦寻找等效对寻找等效对根据等效状态的判断标准，依次检查每个状态对，可得到顺序比较结果如图(a)所示。关联比较的结果如图(b)所示。图(a)图(b)第31页，此课件共56页哦由判断结果可知，原始状态表中的7个状态共有四个等效对：(A，B)，(A，E)，(B，E)，(C，F)。第32页，此课件共56页哦状态合并，作出最小化状态表状态合并，作出最小化状态表令令A,B,E-a、C,F-b、D-c、G-d，并代入原始状态表中，即可得到化简后的状态表如下边右表所示。求出最大等效类求出最大等效类由所得到的等效对和最大等效类的定义可知，原始状态表中的7个状态共构成A,B,E,C,F,D,G四个最大等效类。第33页，此课件共56页哦二、不完全确定状态表的化简二、不完全确定状态表的化简不完全确定状态表中存在不确定的次态或输出，这些不确定的状态和输出对于状态化简是有利的，关键是必须恰当处理，以确保化简前后状态表的逻辑功能不变。为此，引入出了一个新的概念-相容状态。1相容状态和相容类相容状态和相容类（1）相容状态）相容状态定义定义假定状态Si和Sj是不完全确定状态表中的两个状态，如果对于所有的有效输入序列有效输入序列，分别从状态Si和Sj出发，所得到的输出响应序列(除不确定的那些位之外)是完全相同的，那么，状态Si和Sj是相容的，或者说状态Si和Sj是相容对，记作(Si，Sj)。有效输入序列：从状态表中的状态S出发，如果给定某输入序列所得到的状态响应序列除最后一个次态外，其他次态都是确定的，那么，这个输入序列对状态S是有效的。所有的有效输入序列，是指有效输入序列的长度和结构是任意的。第34页，此课件共56页哦相容状态的判断相容状态的判断假定状态Si和Sj是不完全确定状态表中的两个现态，状态Si和Sj相容的条件可归纳为在一位输入的各种取值组合下满足如下两条。满足如下两条。第一，它们的输出完全相同，或者其中的一个第一，它们的输出完全相同，或者其中的一个(或两个或两个)输出不确定。输出不确定。第二，它们的次态属于下列情况之一：第二，它们的次态属于下列情况之一：a.次态相同；次态相同；b.次态交错或为各自的现态；次态交错或为各自的现态；c.次态循环或为相容对；次态循环或为相容对；d.其中的一个其中的一个(或两个或两个)为不确定状态。为不确定状态。注意注意!相容状态不具有传递性。相容状态不具有传递性。这是因为判断两个状态是否相容时，对于不给定的输出和不给定的次态可以随意指定的缘故。例如，在表中，有状态A、B相容，状态A、C相容，但状态B、C不相容。现态y次态/输出(y（n+1）/Z)x=0 x=1ABCDA/0A/0A/0B/1D/dD/0D/1d/1第35页，此课件共56页哦(2)相容类相容类相容类是由彼此相容的状态构成的集合。处于同一相容类中的所有状态之间都是两两相容的。例如，若有相容对(S1,S2)、(S2，S3)和(S1,S3)，则可构成相容类S1,S2，S3。(3)最大相容类最大相容类若一个相容类不是任何其他相容类的子集，则该相容类称为最大相容类。由于相容状态无传递性，所以，同一原始状态表的各最大相容类之间可能存在相同状态，即同一状态可能出现在不同的最大相容类中。第36页，此课件共56页哦2.不完全确定状态表的化简不完全确定状态表的化简(1)化简步骤化简步骤一般步骤如下：作隐含表，寻找相容状态对。作隐含表，寻找相容状态对。利用隐含表寻找相容对的过程与化简完全确定状态表时寻找等效对的过程是相同的，仅仅是状态相容与状态等效的标准有所不同而已。即在顺序比较完成后，可利用已建立的隐含表继续进行关联比较，直至判断出所有状态对相容或不相容为止，便可列出原始状态表中的全部相容对。利用状态合并图，求出最大相容类。利用状态合并图，求出最大相容类。状态合并图：状态合并图是求最大相容类工具。它将状态表的所有状态以状态合并图：状态合并图是求最大相容类工具。它将状态表的所有状态以点点的形式均匀的形式均匀地绘在圆周上，然后把所有相容对用线段连接起来。若某些顶点任意两点之间都有连线，则地绘在圆周上，然后把所有相容对用线段连接起来。若某些顶点任意两点之间都有连线，则其顶点状态的集合构成一个最大相容类。其顶点状态的集合构成一个最大相容类。第37页，此课件共56页哦图图(a)、(b)、(c)分别表示包含分别表示包含3个、个、4个和个和5个状态的最大相容类状态合并图。个状态的最大相容类状态合并图。第38页，此课件共56页哦利用闭覆盖表，求最小闭覆盖。利用闭覆盖表，求最小闭覆盖。最小闭覆盖-是从最大相容类(或相容类)中选出一个相容类的集合，该相容类集合满足满足以下以下3个条件个条件：a.覆盖性，即所选相容类集合应包含原始状态表的全部状态。覆盖性，即所选相容类集合应包含原始状态表的全部状态。b.最小性，即所选相容类集合中相容类个数应最少。最小性，即所选相容类集合中相容类个数应最少。c.闭合性，即所选相容类集合中的任一相容类，在原始状态表中任一输入条件下产生的闭合性，即所选相容类集合中的任一相容类，在原始状态表中任一输入条件下产生的次态应该属于该集合中的某一个相容类。次态应该属于该集合中的某一个相容类。（思考：为什么要满足覆盖？为什么要满足闭合？）（思考：为什么要满足覆盖？为什么要满足闭合？）化简不完全确定状态表的关键关键，就是寻找一个最小闭覆盖。闭覆盖表：所谓闭覆盖表是指反映闭合和覆盖这两个性质的表格，该表反映相容类集合对状态的覆闭覆盖表：所谓闭覆盖表是指反映闭合和覆盖这两个性质的表格，该表反映相容类集合对状态的覆盖情况和相容类的闭合关系。表的左边自上而下列出所选相容类，表的中间覆盖部分列出各相容类对盖情况和相容类的闭合关系。表的左边自上而下列出所选相容类，表的中间覆盖部分列出各相容类对原始状态表中状态的覆盖情况，表的右边闭合部分列出各相容类在一位输入各种取值组合下的次态组原始状态表中状态的覆盖情况，表的右边闭合部分列出各相容类在一位输入各种取值组合下的次态组合。合。（注意，这里所说的相容类包括最大相容类和它们的子类注意，这里所说的相容类包括最大相容类和它们的子类。）作出最小化状态表。作出最小化状态表。将最小闭覆盖中的每个相容类用一个新的状态符号表示，再将其代入原始状态表中，即可得到与原始状态表功能相同的最小化状态表。第39页，此课件共56页哦例例化简下表所示的原始状态表。化简下表所示的原始状态表。解解表中所示是一个具有5个状态的原始状态表，表中存在不确定的次态和输出，因此，属于不完全确定状态表。作隐含表，寻找相容状态对。作隐含表，寻找相容状态对。作出隐含表，并根据相容状态的判断标准对各状态对进行顺序比较和关联比较后的结果如图所示。第40页，此课件共56页哦作状态合并图，找出最大相容类。作状态合并图，找出最大相容类。根据相容状态对可作出状态合并图如图5.25所示。从状态合并图得到最大相容类为A,B,D、A,C,D、A,C,E。由隐含表中的标注可知，该状态表中的相容状态对有：(A,B)、(A，C)、(A，D)、(A，E)、(B，D)、(C，D)、(C，E)。第41页，此课件共56页哦作闭覆盖表，求最小闭覆盖。作闭覆盖表，求最小闭覆盖。由得到的3个最大相容类，可作出其闭覆盖表如表所示由表所示闭覆盖表和选择最小闭覆盖的3个条件可知，该例的最小闭覆盖可由最大相容类A,B,D和A,C,E组成。a.覆盖性，即所选相容类集合应包含原始状态表的全部状态。覆盖性，即所选相容类集合应包含原始状态表的全部状态。b.最小性，即所选相容类集合中相容类个数应最少。最小性，即所选相容类集合中相容类个数应最少。c.闭合性，即所选相容类集合中的任一相容类，在原始状态表中任一输入条件下产闭合性，即所选相容类集合中的任一相容类，在原始状态表中任一输入条件下产生的次态应该属于该集合中的某一个相容类。生的次态应该属于该集合中的某一个相容类。第42页，此课件共56页哦作出最小化状态表。作出最小化状态表。假定最小闭覆盖中的相容类A,B,D用状态a表示，相容类A,C,E用状态b表示，将其代入表所示原始状态表中，可得到最小化状态表如表所示。注意：在填写最小化状态表中的输出值时，若原始状态表中的相应输出值有确定的和不确定的两种类型，注意：在填写最小化状态表中的输出值时，若原始状态表中的相应输出值有确定的和不确定的两种类型，则应填入确定的输出值。例如，原始表中的状态则应填入确定的输出值。例如，原始表中的状态A、B、D在输入在输入x=0时的输出有时的输出有1和和d两种，合并后的状态两种，合并后的状态a在在x=0时的输出应为时的输出应为1。最小化状态表最小化状态表现态次态/输出x=0 x=1ab/1a/0ba/0b/1值得指出的是，在化简不完全给定状态表时，构成最小闭覆盖的相容类并不一定是最大相容类。例如，本例中选最大相容类A,B,D和相容类C,E作为最小闭覆盖，可得到相同的结果。在某些情况下，如果仅仅从最大相容类中去选择最小闭覆盖，则合并后的状态表不一定是最简的。而如果在满足最小覆盖的前提下，在最大相容类和非最大相容类之间作恰当的选择，却能得到最简的状态表。第43页，此课件共56页哦2.3状态编码状态编码状状态态编编码码：是指给最小化状态表中用字母或数字表示的状态，指定一个二进制代码，形成二进制状态表。状态编码也称状态分配，或者状态赋值。一般情况下，采用的状态编码方案不同，所得到的输出函数和激励函数的表达式也不同，从而设计出来的电路其复杂程度也不同。状态编码的任务是：状态编码的任务是：确确定定状状态态编编码码的的长长度度(即即二二进进制制代代码码的的位位数数，或或者者说说所所需需触触发器个数发器个数)；寻寻找找一一种种最最佳佳的的或或接接近近最最佳佳的的状状态态分分配配方方案案。以以便便使使所所设设计的时序电路最简单。计的时序电路最简单。第44页，此课件共56页哦一、确定二进制代码的位数一、确定二进制代码的位数设设最最小小化化状状态态表表的的状状态态数数为为N，状状态态编编码码的的长长度度为为m,则则状状态态数数N与状态编码长度与状态编码长度m的关系为的关系为2m-1N2m例如，若某状态表的状态数N=7，则状态分配时,二进制代码的位数应为m=3。或者说状态变量个数为3。二、确定状态分配方案二、确定状态分配方案状态与代码之间的对应关系可以有许多种。一般说来，用m位二进制代码的2m种组合来对N个状态进行分配时，可能出现的状态分配方案数Ks为例如，当N=4,m=2时，KS=24。第45页，此课件共56页哦例如例如，当N=4,m=2时，KS=24。随着状态数目的增加，分配方案的数目急剧增加。如何从众多的分配方案中寻找出一种最佳方案，使所设计的电路最简单，是一件十分困难的事情。而且，分配方案的好坏还与所采用的触发器类型相关，即一种分配方案对某种触发器是最佳的，但对另一种触发器则不一定是最佳的。因此，状态分配是一个比较复杂的问题。尽管做了大量研究工作，但从理论上讲，寻求最佳状态编码的问题尚未完全解决。在实际工作中，工程技术人员通常按照一定的原则、凭借设计的经验去寻找相对最佳的编码方案。第46页，此课件共56页哦一种常用方法称为相邻分配法相邻分配法。相相邻邻分分配配法法的的基基本本思思想想是是：在选择状态编码时，尽可能使激励函数和输出函数在卡诺图上的“1”方格处在相邻位置，从而有利于激励函数和输出函数的化简。第47页，此课件共56页哦相邻分配法的状态编码原则如下：相邻分配法的状态编码原则如下：次态相同，现态相邻。次态相同，现态相邻。(即在相同输入条件下，具有相同次态的现态应尽可能分配相邻的二进制代码；)同一现态，次态相邻。同一现态，次态相邻。(即在相邻输入条件下，同一现态的次态应尽可能分配相邻的二进制代码；)输出相同，现态相邻。输出相同，现态相邻。(即在每一种输入取值下均具有相同输出的现态应尽可能分配相邻的二进制代码。)一般来说，上述3条原则在大多数情况下是有效的。但由于3条原则是分别实施的，因此，对于某些状态表常常出现不能同时满足3条原则的情况。此时，可按从至的优先顺序考虑，即把原则放在首位。此外，从电路实际工作状态考虑，一般将初始状态分配一般将初始状态分配“0”状态。状态。第48页，此课件共56页哦三、举例三、举例例例对如下状态表进行状态编码（设A为初始状态）。现态 次态/输出 x=0 x=1 A C/1 B/0 B A/0 A/1 C A/1 D/1 D D/1 C/0解解所示状态表中，状态数N=4，故状态编码的长度应为m=2。即实现该状态表的功能需要两个触发器。第49页，此课件共56页哦根据相邻法的编码原则，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。现态次态/输出 x=0 x=1 A C/1 B/0 B A/0 A/1 C A/1 D/1 D D/1 C/0第50页，此课件共56页哦将状态表中的状态A、B、C、D分别用编码00、01、11、10代替，即可得到该状态表的二进制状态表如右下表所示。注注意意：满足分配原则的方案通常可以有多种，设计者可从中任选一种。现态 y2y1次态y2(n+1)y1(n+1)/输出 x=0 x=1 00 11/0 01/0 01 00/0 00/1 11 00/1 10/1 10 10/0 11/0 现态 次态/输出 x=0 x=1 A C/1 B/0 B A/0 A/1 C A/1 D/1 D D/1 C/0第51页，此课件共56页哦2.4确定激励函数和输出函数并画出逻辑电路图确定激励函数和输出函数并画出逻辑电路图任任务务：根据二进制状态表和所选触发器的激励表，求出触发器的激励函数表达式和电路的输出函数表达式，并予以化简。以便用适当的逻辑门和所选定的触发器构成实现给定逻辑功能的逻辑电路。在得到二进制状态表之后，同步时序电路的下一个设计步骤是根据二进制状态表和所选触发器的激励表，求出触发器的激励函数表达式和电路的输出函数表达式，并予以化简。最后，用适当的逻辑门和所选定的触发器构成实现给定逻辑功能的逻辑电路。第52页，此课件共56页哦根据二进制状态表和触发器激励表，求激励函数和输出函数的最简表达式一般分为两步：两步：列出激励函数和输出函数真值表；列出激励函数和输出函数真值表；用用卡诺图化简后写出最简表达式。卡诺图化简后写出最简表达式。例例用J-K触发器和适当的逻辑门实现如下二进制状态表的功能。现态 y2y1次态y2(n+1)y1(n+1)/输出 x=0 x=1 00 11/0 01/0 01 00/0 00/1 10 01/0 11/0 11 00/1 10/1第53页，此课件共56页哦解解根据给定的二进制状态表和J-K触发器的激励表可列出激励函数和输出函数的真值表如右下表所示。现态 y2y1次态y2(n+1)y1(n+1)/输出 x=0 x=1 00 11/0 01/0 01 00/0 00/1 10 01/0 11/0 11 00/1 10/1QQ(n+1)JK000110110d1dd1d0第54页，此课件共56页哦由真值表可作出激励函数和输出函数的卡诺图如下图所示。J1=1K1=1Z第55页，此课件共56页哦经化简后得到激励函数和输出函数的最简表达式如下：相应逻辑电路图如下图所示。第56页，此课件共56页哦