7.3 状态化简通过原始状态图就可以得到一张原始状态表通过原始状态图就可以得到一张原始状态表本节提出的问题是：这张状态表中的状态数是不是本节提出的问题是：这张状态表中的状态数是不是最少？这直接关系到电路的繁简和优化最少？这直接关系到电路的繁简和优化当采用硬件描述语言建模时，关系到当采用硬件描述语言建模时，关系到PLDPLD器件器件中逻辑资源的有效占用中逻辑资源的有效占用为求得最简状态表，需要我们将等价的状态从为求得最简状态表，需要我们将等价的状态从原始状态表中解析出来，进行化简后形成一张最简原始状态表中解析出来，进行化简后形成一张最简状态表（最小状态表）状态表（最小状态表）所谓状态化简，就是采用某种化简技术从原始状态表中消去多余状态，得到一个既能正确描述给定的逻辑功能，又能使所包含的状态 数目达到最少的状态表——最小状态表最小状态表最常用的化简方法——隐含表法7.3.1 7.3.1 完全给定同步时序电路状态表的化简完全给定同步时序电路状态表的化简完全给定同步时序电路状态表的化简，是利完全给定同步时序电路状态表的化简，是利用状态之间的用状态之间的等效关系等效关系进行的完全给定同步时序电路是指其状态表中的所有完全给定同步时序电路是指其状态表中的所有次态及输出都是确定的。
次态及输出都是确定的假设状态假设状态S SA A和和S SB B是完全给定同步时序电路状态是完全给定同步时序电路状态表中的两个状态，如果对于所有可能的输入序列，表中的两个状态，如果对于所有可能的输入序列， 分别从分别从S SA A和和S SB B出发，所得到的输出响应序列完全相出发，所得到的输出响应序列完全相同，则两个状态是等效（等价）的，称同，则两个状态是等效（等价）的，称S SA A和和S SB B为等为等效对，记作：（效对，记作：（S SA A，，S SB B）所有可能的输入序列，指输入序列的长度和结所有可能的输入序列，指输入序列的长度和结构是任意的构是任意的状态等效有 关 概 念从整体上讲，原始状态表已经反映了各状态在任意输入序列下的输出 等效状态可以合并为一个状态，这种合并不会 改变电路的外部特性等效状态的三个特点：●对称性：若（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/0 0/10/1后继状态等效S1S2S3S4S6S5次态循环0/00/01/11/1 1/01/00/10/11/11/10/00/0S1,S2S3,S4S5,S60/00/01/11/10/11/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}等效类：{A, B, C}{D, E}将所有最大等效类重新命名，令：S1={ A，B，C }S2={ D，E }则可得到化简后的状态表（最小化状态表）：S1S2化简后的状态图：利用隐含表进行利用隐含表进行完全给定同步时序电路状态表的化简给定同步时序电路状态表的化简1）作隐含表2）寻找等效对3）求出最大等效类注意：a)各最大等效类之间不应出现相同状态b)原始状态表中的每一个状态必须属于某一个最大等效类4）作出最小化状态表一般步骤：一般步骤：隐含表隐含表是用来标注原始状态表中所有的状态对之间，按照 等效的判定条件进行“状态对”比较的一种表格隐含表是一个直角三角形阶梯表，两直角边的网格数相同， 它等于原始状态表中的状态数减 1，用状态名进行顺序标注。
纵坐标从上到下标注且“缺头”（缺少第一个状态）；横坐标从 左到右标注且“少尾”（缺少最后一个状态）横纵坐标交汇的 每个方格代表一个状态对例1： 化简图示状态表1）作隐含表2）求等效对● 顺序比较所有“状态对”逐一检查、比较等效：方格内画 ；不等效：方格内画 x ;与其它状态对有关：方格内填写相关状态对BEBC BEXXXXXX等效对为： （B，C），（D，E）●关联比较若相关状态对都等效，则方格对应的状态对等效不增 加标志若相关状态对有一个不等效，则方格对应的状态对不等 效画 / BEBC BEXXXXXX3）求出最大等效类利用等效状态的对称性、自反性、传递性，求出等效类{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：化简图示原始状态表现态现态次态态/输输出输输入X=0输输入X=1AC/0B/1BF/0A/1CF/0G/0DD/1E/0EC/0E/1FC/0G/0GC/1D/0BCDEFGABCDEFCFXXXXXXXXXXXXXXXXBEAE CFCD DE√请同学自己求出最大等效类、作出最小状态表因为CF等效，所以AB等效CF等效且AE,BE次态 循环，所以AE等效， BE也等效。
作业：P263~2655.4 5.7（用Verilog HDL建模）补充题：1）画出满足下列要求的序列检测器原始状态图和最简状态表输入X: …0 0 1 0 1 0 1 1 0 1… 输出Z: …0 0 0 0 1 0 1 0 0 1…2）画出3位二进制码的串行奇偶检测器的原始状态图和最简状态表输入为X，每三位一组，其中“1”的个数为偶数时，输出Z=1，否则Z=07.3.2 7.3.2 不完全给定同步时序电路状态表的化简不完全给定同步时序电路状态表的化简特点：原始状态图（表）中含有无关状态化简：如何利用无关态硬件描述语言中的if_else语句和case语句的default 分支可以有效的处理无关状态所以，传统的不完全给定同步时序电路状态表的不完全给定同步时序电路状态表的 化简化简方法不作为教学要求，但课件保留，供学生自学 时参考当原始状态表中含有不确定的次态或输出，即含有无关 项（d）,它所对应的电路称为不完全给定同步时序电路不完全给定同步时序电路例如，用四位触发器构成十进制计数器时，只需要16 个状态中的10个，在原始状态表中有6个状态的次态被标注 为无关项（无关态）若将非完全描述状态表变为完全描述状态表，当有n个 无关项，就会有2n张状态表，化简后会有2n个繁简不同的 结果。
因此，需要有新的逻辑工具简化设计过程非完全描述状态表的化简是建立在完全描述状态表的化简是建立在状态相容状态相容基础上的基础上的7.3.2 7.3.2 不完全给定同步时序电路状态表的化简不完全给定同步时序电路状态表的化简假设状态假设状态S SA A和和S SB B是非完全描述状态表中的两个状态，如果是非完全描述状态表中的两个状态，如果 对于对于所有的有效输入序列所有的有效输入序列，分别从，分别从S SA A和和S SB B出发，所得到的输出出发，所得到的输出 响应序列（除不确定的那些位之外）完全相同，则两个状态是响应序列（除不确定的那些位之外）完全相同，则两个状态是 相容的，记为（相容的，记为（S SA A，，S SB B）或者说，状态或者说，状态S SA A和和S SB B是相容对是相容对状态相容有效输入序列：有效输入序列：从状态表中的状态从状态表中的状态S S出发，如果给定某输入序列所得到的出发，如果给定某输入序列所得到的 状态响应除最后一个次态外，其他次态都是确定的，那么，这状态响应除最后一个次态外，其他次态都是确定的，那么，这 个输入序列对状态个输入序列对状态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)闭合性，所选相容类集合中的任一相容类，在原始 状态表中任一输入条件下产生的次态应该属于该集合 中的某一个相容类非完全描述状态表的化简，就是寻找一个最小闭覆盖 将其中的每个相容类用一个新的状态符号表示，代。