《数字逻辑ppt课件第7章状态化简.ppt》由会员分享，可在线阅读，更多相关《数字逻辑ppt课件第7章状态化简.ppt（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、7.3 状态化简状态化简 所谓状态化简，就是采用某种化简技术从所谓状态化简，就是采用某种化简技术从原始状态表中消去多余状态，得到一个既能正原始状态表中消去多余状态，得到一个既能正确描述给定的逻辑功能，又能使所包含的状态确描述给定的逻辑功能，又能使所包含的状态数目达到最少的状态表数目达到最少的状态表最常用的化简方法最常用的化简方法隐含表法隐含表法状态等效状态等效有有 关关 概概 念念 从整体上讲，原始状态表已经反映了各状态在从整体上讲，原始状态表已经反映了各状态在任意输入序列下的输出。任意输入序列下的输出。 等效状态可以合并为一个状态，这种合并不会等效状态可以合并为一个状态，这种合并不会改变电路
2、的外部特性。改变电路的外部特性。等效状态的三个特点：等效状态的三个特点：对称性：若（对称性：若（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 在等效关系中，等效对
3、是狭义的概念，针对两个状态在等效关系中，等效对是狭义的概念，针对两个状态而言。等效类是广义的概念，针对若干个状态而言，甚至而言。等效类是广义的概念，针对若干个状态而言，甚至一个状态可称为等效类。一个状态可称为等效类。等等 效效 类类不是任何其它等效类子集的等效类称为最大等效类。不是任何其它等效类子集的等效类称为最大等效类。原始状态表的化简过程，就原始状态表的化简过程，就是寻找最大等效类，将每个最大等价类中的所有状态合是寻找最大等效类，将每个最大等价类中的所有状态合并为一个新状态，从而得到并为一个新状态，从而得到的过程。的过程。 化简后的状态数等于最大等效类的个数。化简后的状态数等于最大等效类的
4、个数。最大等效类最大等效类 判断原始状态表中两个状态是否判断原始状态表中两个状态是否 等效（等价）等效（等价）的标准：的标准： 如果两个状态，对每一位可能的输入都满足下如果两个状态，对每一位可能的输入都满足下列两个条件，则这两个状态等效。列两个条件，则这两个状态等效。第一，它们的输出完全相同。第一，它们的输出完全相同。第二，它们的次态属于下列情况之一：第二，它们的次态属于下列情况之一： 1）次态相同）次态相同 2）次态交错或者次态维持）次态交错或者次态维持 3）后继状态等效）后继状态等效 4）次态循环次态循环S1S2S4S3输入输入/输出输出0/00/01/01/0次态相同次态相同S4S3S1
5、,S21/00/0在原始状态图上判别状态的等效在原始状态图上判别状态的等效S1S2S3输入输入/输出输出0/00/01/01/0次态交错次态交错S3S1,S21/00/0S1S2S3输入输入/输出输出0/00/01/01/0次态维持次态维持S3S1,S21/00/0S1S2S3,S4S50/00/01/11/11/00/1S1,S2S3,S4S50/01/11/00/1S1S2S4S3S50/00/01/11/11/01/00/10/1后继状态等效后继状态等效S1S2S3S4S6S5次态循环次态循环0/00/01/11/11/01/00/10/11/11/10/00/0S1,S2S3,S4S5
6、,S60/00/01/11/10/11/00B1E0B1E1D0A1E0A1E0B/EDCBA01XYZY1t/)( 在原始状态表中判断状态的等效在原始状态表中判断状态的等效输出不相等，则不等效。例如：输出不相等，则不等效。例如：C和和D输出相等时：输出相等时：1）次态相等，等效。如状态）次态相等，等效。如状态D 和和E等效；等效；2）次态交错，等效。如状态）次态交错，等效。如状态A 和和B等效；等效；3）后继状态等效，等效。此例）后继状态等效，等效。此例 中中B和和C是否等效，要看是否等效，要看E和和 D是不是等效，因为是不是等效，因为E和和D等等 效，所以效，所以B和和C等效。等效。根据等
7、效的传递性可知，根据等效的传递性可知，A和和B等效，等效，B和和C等效，则等效，则A和和C等效等效等效对等效对： (A, B) (B, C) (A, C) (D, E)最大等效类最大等效类:A, B, CD, E等效类：等效类：A, B, CD, E 将所有最大等效类重新命名，令：将所有最大等效类重新命名，令： S1= A，B，C S2= D，E 则可得到化简后的状态表则可得到化简后的状态表（最小化状态表）：（最小化状态表）：0S1S1S0S1221/21SS01XSZS1t/)( S1S211/01/00/10/化简后的状态图：化简后的状态图：0B1E0B1E1D0A1E0A1E0B/EDC
8、BA01XYZY1t/)( 完全完全1）作隐含表）作隐含表2）寻找等效对）寻找等效对3）求出最大等效类）求出最大等效类 注意：注意：a)各最大等效类之间不应出现相同状态各最大等效类之间不应出现相同状态 b)原始状态表中的每一个状态必须属于某一个最原始状态表中的每一个状态必须属于某一个最 大等效类大等效类4）作出最小化状态表）作出最小化状态表隐含表隐含表 隐含表是用来标注原始状态表中所有的状态对之间，按照隐含表是用来标注原始状态表中所有的状态对之间，按照等效的判定条件进行等效的判定条件进行“状态对状态对”比较的一种表格。比较的一种表格。 隐含表是一个直角三角形阶梯表，两直角边的网格数相同，隐含表
9、是一个直角三角形阶梯表，两直角边的网格数相同，它等于原始状态表中的状态数减它等于原始状态表中的状态数减 1，用状态名进行顺序标注。，用状态名进行顺序标注。纵坐标从上到下标注且纵坐标从上到下标注且“缺头缺头”（缺少第一个状态）；横坐标从（缺少第一个状态）；横坐标从左到右标注且左到右标注且“少尾少尾”（缺少最后一个状态）。横纵坐标交汇的（缺少最后一个状态）。横纵坐标交汇的每个方格代表一个状态对。每个方格代表一个状态对。0B1E0B1E1D0A1E0A1E0B/EDCBA01XYZY1t/)( EDCBABCD1B1D1B1D0E1B0E1C0B1C/EDCBA01XYZY1t/)( EDCBABC
10、D 例例1： 化简图示状态表。化简图示状态表。1）作隐含表）作隐含表2）求等效对）求等效对 顺序比较顺序比较 所有所有“状态对状态对”逐一检查、比较。逐一检查、比较。 等效：方格内画等效：方格内画 ； 不等效：方格内画不等效：方格内画 x ; 与其它状态对有关：方格内填写相关状态对。与其它状态对有关：方格内填写相关状态对。BEBCBEXXXXXX等效对为：等效对为： （B，C），（），（D，E） 关联比较关联比较 若相关状态对都等效，则方格对应的状态对等效。不增若相关状态对都等效，则方格对应的状态对等效。不增加标志。加标志。 若相关状态对有一个不等效，则方格对应的状态对不等若相关状态对有一个不
11、等效，则方格对应的状态对不等效。画效。画 / 。EDCBABCD BEBCBEXXXXXX3）求出最大等效类）求出最大等效类1S1S0S1S0S1S233222/321SSS01XSZS1t/)( 利用等效状态的对称性、自反性、传递性，求出等效类。利用等效状态的对称性、自反性、传递性，求出等效类。 B,C，D,E，A。等效类等效类 B，C，D，E，A 均不包含在任何其他等效类中，均不包含在任何其他等效类中， 所以所以 A，B，C，D，E 是最大等价类。是最大等价类。1B1D1B1D0E1B0E1C0B1C/EDCBA01XYZY1t/)( 4）作最小化状态表）作最小化状态表令令S1=A，S2=
12、B，C，S3=D，E例例2：化简图示原始状态表：化简图示原始状态表现态现态次态次态/输出输出输入输入X=0输入输入X=1AC/0B/1BF/0A/1CF/0G/0DD/1E/0EC/0E/1FC/0G/0GC/1D/0BCDEFGABCDEFCFXXXXXXXXXXXXXXXXBEAECFCDDE请同学自己求出最大等效类、作出最小状态表请同学自己求出最大等效类、作出最小状态表因为因为CF等效，所以等效，所以AB等效等效CF等效且等效且AE,BE次态次态循环，所以循环，所以AE等效，等效，BE也等效。也等效。作业：作业：P263265 5.4 5.7（用（用Verilog HDL建模）建模）补充
13、题：补充题：1）画出满足下列要求的序列检测器原始状态）画出满足下列要求的序列检测器原始状态 图和最简状态表。图和最简状态表。输入输入X: 0 0 1 0 1 0 1 1 0 1输出输出Z: 0 0 0 0 1 0 1 0 0 12）画出）画出3位二进制码的串行奇偶检测器的原始状位二进制码的串行奇偶检测器的原始状 态图态图和最简状态表和最简状态表。输入为。输入为X，每三位一组，每三位一组， 其中其中“1”的个数为偶数时，输出的个数为偶数时，输出Z=1，否则，否则 Z=0。特点：原始状态图（表）中含有无关状态特点：原始状态图（表）中含有无关状态化简：如何利用无关态化简：如何利用无关态 硬件描述语言
14、中的硬件描述语言中的if_else语句和语句和case语句的语句的default分支可以有效的处理无关状态。分支可以有效的处理无关状态。 所以，传统的所以，传统的方法不作为教学要求，但课件保留，供学生自学方法不作为教学要求，但课件保留，供学生自学时参考。时参考。 当原始状态表中含有不确定的次态或输出，即含有无关当原始状态表中含有不确定的次态或输出，即含有无关项（项（d）,它所对应的电路称为它所对应的电路称为 例如，用四位触发器构成十进制计数器时，只需要例如，用四位触发器构成十进制计数器时，只需要16个状态中的个状态中的10个，在原始状态表中有个，在原始状态表中有6个状态的次态被标注个状态的次态
15、被标注为无关项（无关态）。为无关项（无关态）。 若将非完全描述状态表变为完全描述状态表，当有若将非完全描述状态表变为完全描述状态表，当有n个个无关项，就会有无关项，就会有2n张状态表，化简后会有张状态表，化简后会有2n个繁简不同的个繁简不同的结果。因此，需要有新的逻辑工具简化设计过程。结果。因此，需要有新的逻辑工具简化设计过程。非非状态相容状态相容现态现态次态次态/输出输出输入输入X=0输入输入X=1AA/dd/dBC/1B/0CD/0d/1Dd/dB/dEA/0C/1非完全描述原始状态表非完全描述原始状态表对于状态对于状态B输入序列输入序列0010是有效的，因为它是有效的，因为它产生的次态响
16、应序列是产生的次态响应序列是CDBC，是，是确定的。确定的。而输入序列而输入序列0100是无效的，因为是无效的，因为它产生的次态响应序列是它产生的次态响应序列是C?，是不确定的是不确定的。相容状态不具有传递性。相容状态不具有传递性。 即：若（即：若（S1,S2）,（S1,S3）是相容对，不一定有）是相容对，不一定有S2和和S3相容。相容。 因为在判断两个状态是否相容时，不确定的输出因为在判断两个状态是否相容时，不确定的输出和不定的次态可以随意指定。和不定的次态可以随意指定。若干彼此相容的状态构成的集合。若干彼此相容的状态构成的集合。相容类相容类例如：有相容对例如：有相容对(S1, S2), (
17、S2, S3), (S1, S3)， 可构成相容类可构成相容类 S1, S2, S3. 不是任何其它相容类子集的相容类。不是任何其它相容类子集的相容类。 由于相容状态无传递性，同一原始状态表的各最大相由于相容状态无传递性，同一原始状态表的各最大相容类之间可能存在相同状态。容类之间可能存在相同状态。最大相容类最大相容类判别原始状态表中两个状态是否判别原始状态表中两个状态是否 相容的标准：相容的标准：如果两个状态，对每一位可能的输入都满足下列两个如果两个状态，对每一位可能的输入都满足下列两个条件，则这两个状态相容。条件，则这两个状态相容。第一，它们的输出相同（一方输出给定，一方输出为第一，它们的输
18、出相同（一方输出给定，一方输出为 无关项，均当作相同）。无关项，均当作相同）。第二，它们的次态属于下列情况之一：第二，它们的次态属于下列情况之一： 1）次态相同）次态相同 2）次态交错或者次态维持）次态交错或者次态维持 3）后继状态相容）后继状态相容 4）次态循环次态循环 （注：一方给定，一方不给定的次态均当作相同）（注：一方给定，一方不给定的次态均当作相同） 1）作隐含表，寻找相容状态对。）作隐含表，寻找相容状态对。2）利用完全图（状态合并图），求出最大相容类。）利用完全图（状态合并图），求出最大相容类。完全图是一种将完全图是一种将非完全描述状态表非完全描述状态表的状态，以的状态，以“点点”
19、的形式均匀的形式均匀地绘在圆周上，然后把所有相容对用线段连接起来，得到的图。地绘在圆周上，然后把所有相容对用线段连接起来，得到的图。在这种图中，所有点之间都有连线的多边形，构成一个最大在这种图中，所有点之间都有连线的多边形，构成一个最大相容类。相容类。S1S2S3S1, S2, S3S1S2S3S4S1, S2, S3, S4S1S2S3S4S5S1, S2, S3, S4, S53）利用闭覆盖表，求最小闭覆盖。）利用闭覆盖表，求最小闭覆盖。从最大相容类（或相容类）中选出一个相容类的集合，从最大相容类（或相容类）中选出一个相容类的集合，它必须满足以下三个条件。它必须满足以下三个条件。a)覆盖性
20、，包含原始状态表的全部状态。覆盖性，包含原始状态表的全部状态。b)最小性，相容类个数最少。最小性，相容类个数最少。c)闭合性，所选相容类集合中的任一相容类，在原始闭合性，所选相容类集合中的任一相容类，在原始 状态表中任一输入条件下产生的次态应该属于该集合状态表中任一输入条件下产生的次态应该属于该集合中的某一个相容类。中的某一个相容类。非完全描述状态表非完全描述状态表的化简，就是寻找一个最小闭覆盖。的化简，就是寻找一个最小闭覆盖。将其中的每个相容类用一个新的状态符号表示，代入将其中的每个相容类用一个新的状态符号表示，代入原始状态表中，得到最小化状态表。原始状态表中，得到最小化状态表。4）作出最小
21、化状态表。）作出最小化状态表。 例例1： 试化简图示的原始状态表试化简图示的原始状态表解：解：1）画隐含表求相容对：）画隐含表求相容对：1C0AB10D0B1CA/ EDCBA01XYZY1t/)( 列出相容对：列出相容对：（A，B），（），（A，C），（），（A，D），（），（A，E），），（B，D），（），（C，D），（），（C，E）。）。BCADADAC BCADADAC EDCBABCD 2）做完全图求最大相容类：）做完全图求最大相容类：ABCDE最大相容类有：最大相容类有：A，B，D，A，C，E，A，C，D。相容对：（相容对：（A，B），（），（A，C），（），（A，D），（），（A
22、，E），），（B，D），（），（C，D），（），（C，E）。）。3）做闭合覆盖表求最小闭合覆盖：）做闭合覆盖表求最小闭合覆盖：CADECAACEBADDCAACDBACDBAABD1X0XEDCBA 覆盖覆盖闭合闭合相容类相容类根据最小覆盖下的次态转移，进行闭合检查：根据最小覆盖下的次态转移，进行闭合检查：X=0时，（时，（A，B，D）次态转移为）次态转移为AC，属于（，属于（A,C,E）; （A，C，E）次态转移为）次态转移为AD，属于（，属于（A,B,D）；）；X=1时，均为单态转移，属于最小覆盖中的一个相容类。时，均为单态转移，属于最小覆盖中的一个相容类。所以，最小闭合覆盖成立。所以，最
23、小闭合覆盖成立。由于状态由于状态B仅属于（仅属于（A,B,D）状态状态E仅属于（仅属于（A,C,E）选择选择（A，B，D）和和（A，C，E）为最小覆盖。为最小覆盖。4）画出最简状态表：）画出最简状态表：令：令：S1=（A，B，D），）， S2=（A，C，E）1S0S0S1S2112/21SS01XSZS1t/)( 最简状态表最简状态表1C0AB10D0B1CA/ EDCBA01XYZY1t/)( 原始状态表原始状态表 例例2：试化简图示的原始状态表：试化简图示的原始状态表 /B1CCCB0DA0EADEDCBA01XYZY1t/)( 解：解：1）画隐含表求相容对：）画隐含表求相容对：EDCBA
24、BCDBCABDCBCACECACDCABEDABDE ,列出相容对：列出相容对：（A，B），（），（A，C），（），（A，D），（），（A，E），（），（B，C），（），（C，D），（），（D，E）。）。2）做完全图求最大相容类：）做完全图求最大相容类：最大相容类有：最大相容类有：（A，B，C），），（A，C，D），），（A，D，E）。）。ABCDE3）做闭合覆盖表求最小闭合覆盖：）做闭合覆盖表求最小闭合覆盖：ABCCDEDAADEABCCDDCAACDABDECBAABC1X0XEDCBA 覆盖覆盖闭合闭合相容类相容类选择（选择（A，B，C）和（）和（A，D，E）为最小覆盖，）为最小覆盖，
25、检查次态转移：检查次态转移：X=0时，（时，（A，B，C）转移为）转移为DE，属于（，属于（A，D，E）；但（）；但（A，D，E）转移）转移为为CD，而，而CD不属最小覆盖中的某一个相容类。不属最小覆盖中的某一个相容类。所以，最小闭合覆盖不成立。所以，最小闭合覆盖不成立。 /B1CCCB0DA0EADEDCBA01XYZY1t/)( BCCEDDEABCCDDCAACDABDECBAABC1X0XEDCBA 覆盖覆盖闭合闭合相容类相容类选择（选择（A，B，C）和（）和（D，E）为最小覆盖，）为最小覆盖，检查次态转移：检查次态转移：X=0时，（时，（A，B，C）转移）转移为为DE，（，（D，E）
26、转移为）转移为C，为单态转移；，为单态转移；X=1时的次态转移为时的次态转移为AB，BC，同属最小覆，同属最小覆盖中的某一个相容类。最小闭合覆盖成立。盖中的某一个相容类。最小闭合覆盖成立。修正：去掉（修正：去掉（A，D，E）中的重复状态）中的重复状态A，用相容对代替最大相容类用相容对代替最大相容类，得下表：得下表： /B1CCCB0DA0EADEDCBA01XYZY1t/)( 4）画出最简状态表：）画出最简状态表： 令：令：S1=（A，B，C），）， S2=（D，E） /1112S1SS0S21SS01XSZS1t/)( 最简状态表最简状态表原始状态表原始状态表 /B1CCCB0DA0EADEDCBA01XYZY1t/)( 注意：注意：选择全部最大相容类组成相容类集，不一定能满足最小化的选择全部最大相容类组成相容类集，不一定能满足最小化的要求；（例要求；（例1、例、例2）选择部分最大相容类组成相容类集，有可能不满足闭合性要选择部分最大相容类组成相容类集，有可能不满足闭合性要求；（例求；（例2）适当选择最大相容类、相容类组成相容类集，可以得到最小适当选择最大相容类、相容类组成相容类集，可以得到最小化状态表。（例化状态表。（例2）