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

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）次态循环S1S2S4S3输入/输出0/00/01/01/0次态相同S4S3S1,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,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等效。根据等效的传递性可知，A和B等效，B和C等效，则A和C等效等效对：(A,B)(B,C)(A,C)(D,E)最大等效类:{A,B,C}{D,E}等效类：{A,B,C}{D,E}将所有最大等效类重新命名，令：S1={A，B，C}S2={D，E}则可得到化简后的状态表（最小化状态表）：0S1S1S0S1221////21SS01XSZS1t/)(S1S211/01/00/10/化简后的状态图：0B1E0B1E1D0A1E0A1E0B//////////EDCBA01XYZY1t/)(利用隐含表进行完全给定同步时序电路状态表的化简1）作隐含表2）寻找等效对3）求出最大等效类注意：a)各最大等效类之间不应出现相同状态b)原始状态表中的每一个状态必须属于某一个最大等效类4）作出最小化状态表一般步骤：隐含表隐含表是用来标注原始状态表中所有的状态对之间，按照等效的判定条件进行“状态对”比较的一种表格。隐含表是一个直角三角形阶梯表，两直角边的网格数相同，它等于原始状态表中的状态数减1，用状态名进行顺序标注。纵坐标从上到下标注且“缺头”（缺少第一个状态）；横坐标从左到右标注且“少尾”（缺少最后一个状态）。横纵坐标交汇的每个方格代表一个状态对。0B1E0B1E1D0A1E0A1E0B//////////EDCBA01XYZY1t/)(EDCBABCD1B1D1B1D0E1B0E1C0B1C//////////EDCBA01XYZY1t/)(EDCBABCD例1：化简图示状态表。1）作隐含表2）求等效对●顺序比较所有“状态对”逐一检查、比较。等效：方格内画；不等效：方格内画x;与其它状态对有关：方格内填写相关状态对。BEBCBEXXXXXX等效对为：（B，C），（D，E）●关联比较若相关状态对都等效，则方格对应的状态对等效。不增加标志。若相关状态对有一个不等效，则方格对应的状态对不等效。画/。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={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也等效。作业：P263~2655.45.7（用VerilogHDL建模）补充题：1）画出满足下列要求的序列检测器原始状态图和最简状态表。输入X:…0010101101…输出Z:…0000101001…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是有效的。所有的有效输入序列：指有效输入序列的长度和结构是任意的。现态次态/输出输入X=0输入X=1AA/dd/dBC/1B/0CD/0d/1Dd/dB/dEA/0C/1非完全描述原始状态表对于状态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）利用完全图（状态合并图），求出最大相容类。完全图是一种将非完全描述状态表的状态，以“点”的形式均匀地绘在圆周上，然后把所有相容对用线段连接起来，得到的图。在这种图中，所有点之间都有连线的多边形，构成一个最大相容类。S1S2S3{S1,S2,S3}S1S2S3S4{S1,S2,S3,S4}S1S2S3S4S5{S1,S2,S3,S4,S5}3）利用闭覆盖表，求最小闭覆盖。从最大相容类（或相容类）中选出一个相容类的集合，它必须满足以下三个条件。a)覆盖性，包含原始状态表的全部状态。b)最小性，相容类个数最少。c)闭合性，所选相容类集合中的任一相容类，在原始状态表中任一输入条件下产生的次态应该属于该集合中的某一个相容类。非完全描述状态表的化简，就是寻找一个最小闭覆盖。将其中的每个相容类用一个新的状态符号表示，代入原始状态表中，得到最小化状态表。4）作出最小化状态表。例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，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时，均为单态转移，属于最小覆盖中的一个相容类。所以，最小闭合覆盖成立。由于状态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/)(