数字逻辑课件第7章状态化简.ppt

7.3 状态化简,通过原始状态图就可以得到一张原始状态表。本节提出的问题是：这张状态表中的状态数是不是最少？这直接关系到电路的繁简和优化。 当采用硬件描述语言建模时，关系到PLD器件中逻辑资源的有效占用。 为求得最简状态表，需要我们将等价的状态从原始状态表中解析出来，进行化简后形成一张最简状态表（最小状态表）。,所谓状态化简，就是采用某种化简技术从原始状态表中消去多余状态，得到一个既能正确描述给定的逻辑功能，又能使所包含的状态数目达到最少的状态表最小状态表。,最常用的化简方法隐含表法,7.3.1 完全给定同步时序电路状态表的化简,完全给定同步时序电路状态表的化简，是利用状态之间的等效关系进行的。,完全给定同步时序电路是指其状态表中的所有次态及输出都是确定的。,假设状态SA和SB是完全给定同步时序电路状态表中的两个状态，如果对于所有可能的输入序列，分别从SA和SB出发，所得到的输出响应序列完全相同，则两个状态是等效（等价）的，称SA和SB为等效对，记作：（SA，SB）。,所有可能的输入序列，指输入序列的长度和结构是任意的。,状态等效,有 关 概 念,从整体上讲，原始状态表已经反映了各状态在任意输入序列下的输出。,等效状态可以合并为一个状态，这种合并不会改变电路的外部特性。,等效状态的三个特点： 对称性：若（SA，SB），则（SB，SA)。 自反性：对任何状态，（SA，SA）。 传递性：若（SA，SB）且（SB，SC），则（SA，SC）。,若干彼此等价的状态构成的集合。,由（SA，SB）和（SB，SC），可以推出（SA，SC），进而可知SA、 SB 、SC属于同一等价类，记作： （SA，SB）， （SB，SC） SA ， SB ，SC ,在等效关系中，等效对是狭义的概念，针对两个状态而言。等效类是广义的概念，针对若干个状态而言，甚至一个状态可称为等效类。,等 效 类,不是任何其它等效类子集的等效类称为最大等效类。,完全给定同步时序电路原始状态表的化简过程，就是寻找最大等效类，将每个最大等价类中的所有状态合并为一个新状态，从而得到最小状态表的过程。 化简后的状态数等于最大等效类的个数。,最大等效类,判断原始状态表中两个状态是否 等效（等价）的标准： 如果两个状态，对每一位可能的输入都满足下列两个条件，则这两个状态等效。,第一，它们的输出完全相同。 第二，它们的次态属于下列情况之一： 1）次态相同 2）次态交错或者次态维持 3）后继状态等效 4）次态循环,S1,S2,S4,S3,输入/输出,1/0,1/0,次态相同,在原始状态图上判别状态的等效,S1,S2,S3,输入/输出,0/0,0/0,1/0,1/0,次态交错,S1,S2,S3,输入/输出,0/0,0/0,1/0,1/0,次态维持,在原始状态表中判断状态的等效,输出不相等，则不等效。例如：C和D,输出相等时：,1）次态相等，等效。如状态D 和E等效；,2）次态交错，等效。如状态A 和B等效；,3）后继状态等效，等效。此例 中B和C是否等效，要看E和 D是不是等效，因为E和D等 效，所以B和C等效。,根据等效的传递性可知，A和B等效，B和C等效，则A和C等效,等效对： (A, B) (B, C) (A, C) (D, E),等效类：,A, B, C,D, E,将所有最大等效类重新命名，令： S1= A，B，C S2= D，E ,则可得到化简后的状态表 （最小化状态表）：,利用隐含表进行完全给定同步时序电路状态表的化简,1）作隐含表 2）寻找等效对 3）求出最大等效类 注意：a)各最大等效类之间不应出现相同状态 b)原始状态表中的每一个状态必须属于某一个最 大等效类 4）作出最小化状态表,一般步骤：,隐含表,隐含表是用来标注原始状态表中所有的状态对之间，按照 等效的判定条件进行“状态对”比较的一种表格。,隐含表是一个直角三角形阶梯表，两直角边的网格数相同， 它等于原始状态表中的状态数减 1，用状态名进行顺序标注。 纵坐标从上到下标注且“缺头”（缺少第一个状态）；横坐标从 左到右标注且“少尾”（缺少最后一个状态）。横纵坐标交汇的 每个方格代表一个状态对。,例1： 化简图示状态表。,1）作隐含表,2）求等效对 顺序比较 所有“状态对”逐一检查、比较。 等效：方格内画 ； 不等效：方格内画 x ; 与其它状态对有关：方格内填写相关状态对。,BE,BC BE,X,X,X,X,X,X,等效对为： （B，C），（D，E）,关联比较 若相关状态对都等效，则方格对应的状态对等效。不增加标志。 若相关状态对有一个不等效，则方格对应的状态对不等效。画 / 。,BE,BC BE,X,X,X,X,X,X,3）求出最大等效类,利用等效状态的对称性、自反性、传递性，求出等效类。 B,C，D,E，A。 等效类 B，C，D，E，A 均不包含在任何其他等效类中， 所以 A，B，C，D，E 是最大等价类。,4）作最小化状态表,令S1=A，S2=B，C，S3=D，E,例2：化简图示原始状态表,CF,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,BE,AE CF,CD DE,请同学自己求出最大等效类、作出最小状态表,因为CF等效，所以AB等效,CF等效且AE,BE次态循环，所以AE等效，BE也等效。,作业：P263265 5.4 5.7（用Verilog HDL建模）,补充题：,1）画出满足下列要求的序列检测器原始状态 图和最简状态表。,2）画出3位二进制码的串行奇偶检测器的原始状 态图和最简状态表。输入为X，每三位一组， 其中“1”的个数为偶数时，输出Z=1，否则 Z=0。,7.3.2 不完全给定同步时序电路状态表的化简,特点：原始状态图（表）中含有无关状态,化简：如何利用无关态,硬件描述语言中的if_else语句和case语句的default分支可以有效的处理无关状态。,所以，传统的不完全给定同步时序电路状态表的化简方法不作为教学要求，但课件保留，供学生自学时参考。,当原始状态表中含有不确定的次态或输出，即含有无关项（d）,它所对应的电路称为不完全给定同步时序电路。,例如，用四位触发器构成十进制计数器时，只需要16个状态中的10个，在原始状态表中有6个状态的次态被标注为无关项（无关态）。,若将非完全描述状态表变为完全描述状态表，当有n个无关项，就会有2n张状态表，化简后会有2n个繁简不同的结果。因此，需要有新的逻辑工具简化设计过程。,非完全描述状态表的化简是建立在状态相容基础上的。,7.3.2 不完全给定同步时序电路状态表的化简,假设状态SA和SB是非完全描述状态表中的两个状态，如果对于所有的有效输入序列，分别从SA和SB出发，所得到的输出响应序列（除不确定的那些位之外）完全相同，则两个状态是相容的，记为（SA，SB）。或者说，状态SA和SB是相容对。,状态相容,有效输入序列： 从状态表中的状态S出发，如果给定某输入序列所得到的状态响应除最后一个次态外，其他次态都是确定的，那么，这个输入序列对状态S是有效的。,所有的有效输入序列： 指有效输入序列的长度和结构是任意的。,非完全描述原始状态表,对于状态B 输入序列0010是有效的，因为它产生的次态响应序列是CDBC，是确定的。 而输入序列0100是无效的，因为它产生的次态响应序列是C?，是不确定的。,相容状态不具有传递性。 即：若（S1,S2）,（S1,S3）是相容对，不一定有S2和S3相容。 因为在判断两个状态是否相容时，不确定的输出和不定的次态可以随意指定。,若干彼此相容的状态构成的集合。,相容类,例如：有相容对(S1, S2), (S2, S3), (S1, S3)， 可构成相容类 S1, S2, S3.,不是任何其它相容类子集的相容类。 由于相容状态无传递性，同一原始状态表的各最大相容类之间可能存在相同状态。,最大相容类,判别原始状态表中两个状态是否 相容的标准： 如果两个状态，对每一位可能的输入都满足下列两个条件，则这两个状态相容。,第一，它们的输出相同（一方输出给定，一方输出为 无关项，均当作相同）。 第二，它们的次态属于下列情况之一： 1）次态相同 2）次态交错或者次态维持 3）后继状态相容 4）次态循环 （注：一方给定，一方不给定的次态均当作相同）,用隐含表法进行非完全描述状态表的化简的一般步骤：,1）作隐含表，寻找相容状态对。,2）利用完全图（状态合并图），求出最大相容类。,完全图是一种将非完全描述状态表的状态，以“点”的形式均匀地绘在圆周上，然后把所有相容对用线段连接起来，得到的图。,在这种图中，所有点之间都有连线的多边形，构成一个最大相容类。,S1, S2, S3,S1, S2, S3, S4,S1, S2, S3, S4, S5,3）利用闭覆盖表，求最小闭覆盖。,从最大相容类（或相容类）中选出一个相容类的集合，它必须满足以下三个条件。,a)覆盖性，包含原始状态表的全部状态。 b)最小性，相容类个数最少。 c)闭合性，所选相容类集合中的任一相容类，在原始 状态表中任一输入条件下产生的次态应该属于该集合中的某一个相容类。,非完全描述状态表的化简，就是寻找一个最小闭覆盖。将其中的每个相容类用一个新的状态符号表示，代入原始状态表中，得到最小化状态表。,4）作出最小化状态表。,例1： 试化简图示的原始状态表,解：1）画隐含表求相容对：,列出相容对： （A，B），（A，C），（A，D），（A，E），（B，D），（C，D），（C，E）。,2）做完全图求最大相容类：,最大相容类有： A，B，D， A，C，E， A，C，D。,相容对：（A，B），（A，C），（A，D），（A，E），（B，D），（C，D），（C，E）。,3）做闭合覆盖表求最小闭合覆盖：,根据最小覆盖下的次态转移，进行闭合检查： X=0时，（A，B，D）次态转移为AC，属于（A,C,E）; （A，C，E）次态转移为AD，属于（A,B,D）； X=1时，均为单态转移，属于最小覆盖中的一个相容类。 所以，最小闭合覆盖成立。,由于状态B仅属于（A,B,D）,状态E仅属于（A,C,E）,选择（A，B，D）和（A，C，E）为最小覆盖。,4）画出最简状态表：,令：S1=（A，B，D）， S2=（A，C，E）,例2：试化简图示的原始状态表,解：1）画隐含表求相容对：,列出相容对： （A，B），（A，C），（A，D），（A，E），（B，C），（C，D），（D，E）。,2）做完全图求最大相容类：,最大相容类有： （A，B，C）， （A，C，D）， （A，D，E）。,3）做闭合覆盖表求最小闭合覆盖：,选择（A，B，C）和（A，D，E）为最小覆盖，检查次态转移：X=0时，（A，B，C）转移为DE，属于（A，D，E）；但（A，D，E）转移为CD，而CD不属最小覆盖中的某一个相容类。所以，最小闭合覆盖不成立。,选择（A，B，C）和（D，E）为最小覆盖，检查次态转移：X=0时，（A，B，C）转移为DE