同步时序逻辑电路下.ppt

《同步时序逻辑电路下.ppt》由会员分享，可在线阅读，更多相关《同步时序逻辑电路下.ppt（72页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、同步时序逻辑电路下现在学习的是第1页，共72页同步时序逻辑电路设计同步时序逻辑电路设计设计分五步进行设计分五步进行设计分五步进行设计分五步进行:(1)(1)(1)(1)根据功能要求作出原始状态图和状态表（含多余状态）根据功能要求作出原始状态图和状态表（含多余状态）根据功能要求作出原始状态图和状态表（含多余状态）根据功能要求作出原始状态图和状态表（含多余状态）(2)(2)(2)(2)状态化简状态化简状态化简状态化简(消去多余状态消去多余状态消去多余状态消去多余状态)(3)(3)(3)(3)状态分配状态分配状态分配状态分配(状态编码状态编码状态编码状态编码)(4)(4)(4)(4)选定触发器，求出

2、输出函数和激励函数表达式选定触发器，求出输出函数和激励函数表达式选定触发器，求出输出函数和激励函数表达式选定触发器，求出输出函数和激励函数表达式(5)(5)(5)(5)画出逻辑电路画出逻辑电路画出逻辑电路画出逻辑电路 (按输出函数和激励函数式按输出函数和激励函数式按输出函数和激励函数式按输出函数和激励函数式)现在学习的是第2页，共72页（1）建立原始状态图和状态表）建立原始状态图和状态表l l设计要求设计要求设计要求设计要求 原始状态图（关键）原始状态图（关键）原始状态图（关键）原始状态图（关键）不要想着节省状态，一定要画全；要考虑到从每个状态不要想着节省状态，一定要画全；要考虑到从每个状态不

3、要想着节省状态，一定要画全；要考虑到从每个状态不要想着节省状态，一定要画全；要考虑到从每个状态出来所有的输出情况。出来所有的输出情况。出来所有的输出情况。出来所有的输出情况。l l从两个方面着手从两个方面着手从两个方面着手从两个方面着手确定输入与输出变量确定输入与输出变量确定输入与输出变量确定输入与输出变量确定电路应包含的状态数确定电路应包含的状态数确定电路应包含的状态数确定电路应包含的状态数 (一个不能少一个不能少一个不能少一个不能少)和状态之间的关系和状态之间的关系和状态之间的关系和状态之间的关系 (关关关关系不能错系不能错系不能错系不能错)。即即即即 输入为串行二进制码输入为串行二进制码

4、输入为串行二进制码输入为串行二进制码 当当当当x=101x=101x=101x=101时，输出时，输出时，输出时，输出Z=1Z=1Z=1Z=1【例例例例1 1】：输入序列：输入序列：输入序列：输入序列101 101 检测器的设计检测器的设计检测器的设计检测器的设计当当当当xxxx 101101101101时，输出时，输出时，输出时，输出Z=0Z=0Z=0Z=0现在学习的是第3页，共72页2.2.从状态看从状态看从状态看从状态看状态数目状态数目状态数目状态数目的确定：的确定：的确定：的确定：起始状态起始状态起始状态起始状态 S S0 0记忆序列记忆序列记忆序列记忆序列101101的第一个的第一个

5、的第一个的第一个1 1的状态的状态的状态的状态 S S1 1记忆序列记忆序列记忆序列记忆序列101101的第二个的第二个的第二个的第二个0 0的状态的状态的状态的状态 S S2 2记忆序列记忆序列记忆序列记忆序列101101的第三个的第三个的第三个的第三个1 1的状态的状态的状态的状态 S S3 3Z=0Z=0Z=0Z=0Z=0Z=0Z=1Z=11.1.从输入与输出方面看，必须输入从输入与输出方面看，必须输入从输入与输出方面看，必须输入从输入与输出方面看，必须输入x x，和一个输出，和一个输出，和一个输出，和一个输出Z Z（1）建立原始状态图和状态表）建立原始状态图和状态表现在学习的是第4页，

6、共72页MealyMealy图的状态关系：图的状态关系：图的状态关系：图的状态关系：S S0 0S S1 1S3 3S S21/01/00/00/01/11/1(1)(1)主线关系主线关系主线关系主线关系(2)(2)相互关系相互关系相互关系相互关系 在在在在S S0 0处，当处，当处，当处，当 x=0 x=0时，不是检测的，时，不是检测的，时，不是检测的，时，不是检测的，S S0 0保持不变保持不变保持不变保持不变Z=0Z=0 在在在在S S1 1处处处处，当当当当x=1x=1时时时时，可可可可能能能能是是是是101101的的的的第第第第1 1个个个个1 1。用用用用S S1 1记记记记下下下

7、下来来来来，故故故故S S1 1保保保保持持持持不不不不变。变。变。变。0/00/01/01/0 在在在在S2S2处，当处，当处，当处，当 x=0 x=0时时时时(此时已收到此时已收到此时已收到此时已收到 x=10)x=10)则序列为则序列为则序列为则序列为100100，不是要检，不是要检，不是要检，不是要检的的的的,返回返回返回返回S0S0。即。即。即。即S2 S2 S0 S0，Z=0Z=00/00/0（1）建立原始状态图和状态表）建立原始状态图和状态表现在学习的是第5页，共72页在在 S3 处处，当当 x=1时时，可可能能是是又又一一个个101的的开开始始，就就用用 S1 记记下下来来；当

8、当 x=0 时时，是是第第二二个个101中中的的0，用用 S2记记下下来来，故故 Z=0S3S20/0S11/0（1）建立原始状态图和状态表）建立原始状态图和状态表现在学习的是第6页，共72页S0S1S2S3 1/00/0 1/1Mealy状态图状态图现态现态次态次态/输出输出x=0 x=1S0S1S2S3S0/0S2/0S0/0S1/0S1/0S1/0S3/1S2/0Mealy状态表状态表 0/00/01/00/01/0101序列检测器的状态图和状态表：序列检测器的状态图和状态表：（1）建立原始状态图和状态表）建立原始状态图和状态表现在学习的是第7页，共72页Moore图图，由由于于Z只只与

9、与现现态态有有关关，而而与与输输入入无无关关，Z 写写于于状状态图的圆圈内。其他分析与态图的圆圈内。其他分析与Mealy 相同。相同。现态现态次态次态x=0 x=1S0S1S2S3S0S2S0S2S1S1S3S1输出输出00010S0/0S1/0S2/0S3/1 1 0011x1 0（1）建立原始状态图和状态表）建立原始状态图和状态表现在学习的是第8页，共72页 【例例例例2 2 2 2】：检检检检测测测测中中中中行行行行输输输输入入入入(从从从从高高高高位位位位低低低低)的的的的8421BCD8421BCD8421BCD8421BCD码码码码数数数数字字字字的的的的正正正正确确确确性性性性，

10、即即即即当当当当出出出出现现现现非非非非法法法法数数数数字字字字(如如如如1010,1010,1010,1010,1011,1011,1011,1011,1100,1100,1100,1100,1101,1101,1101,1101,1110,1110,1110,1110,1111)1111)1111)1111)时时时时电电电电路路路路输输输输出出出出为为为为1(1(1(1(检错信号检错信号检错信号检错信号)。设计此。设计此。设计此。设计此8421842184218421码误码检测器的状态图。码误码检测器的状态图。码误码检测器的状态图。码误码检测器的状态图。（1）建立原始状态图和状态表）建立原

11、始状态图和状态表解：解：解：解：设计设计设计设计MealyMealyMealyMealy型电路型电路型电路型电路输入与输出：输入与输出：输入与输出：输入与输出：一个输出端用以反映判别一个输出端用以反映判别一个输出端用以反映判别一个输出端用以反映判别8421BCD8421BCD8421BCD8421BCD码码码码一个输入端用以接收一个输入端用以接收一个输入端用以接收一个输入端用以接收8421BCD8421BCD8421BCD8421BCD码码码码现在学习的是第9页，共72页状态数目与状态关系：状态数目与状态关系：状态数目与状态关系：状态数目与状态关系：84218421码码码码是是是是一一一一种种

12、种种四四四四位位位位二二二二进进进进制制制制码码码码。因因因因此此此此，输输输输入入入入是是是是按按按按四四四四位位位位一一一一组组组组，一一一一组组组组组组组组地地地地串串串串行行行行输输输输入入入入，每每每每组组组组都都都都应应应应检检检检测测测测它它它它的的的的真真真真伪伪伪伪，是是是是否否否否是是是是84218421码码码码？换换换换句句句句话话话话说说说说，不不不不应应应应出出出出现现现现非非非非法法法法数数数数字字字字(8421(8421码码码码所所所所去去去去掉掉掉掉的的的的6 6种种种种组组组组合合合合 10101111)10101111)，若出现时，则输出于以指示。即检测出。

13、，若出现时，则输出于以指示。即检测出。，若出现时，则输出于以指示。即检测出。，若出现时，则输出于以指示。即检测出。A A初态；设为初态；设为初态；设为初态；设为（1）建立原始状态图和状态表）建立原始状态图和状态表现在学习的是第10页，共72页0/01/0FDABCEG0/01/00/01/00/01/0记忆第一位代码：记忆第一位代码：记忆第一位代码：记忆第一位代码：记忆第二位代码：记忆第二位代码：记忆第二位代码：记忆第二位代码：记忆第三位代码：记忆第三位代码：记忆第三位代码：记忆第三位代码：BC0/00/01/01/0DE0/00/01/01/0FG0/00/01/01/0（1）建立原始状态图

14、和状态表）建立原始状态图和状态表现在学习的是第11页，共72页第第第第四四四四位位位位到到到到来来来来时时时时，无无无无论论论论是是是是0 0或或或或1 1，状状状状态态态态均均均均应应应应转转转转到到到到初初初初态态态态，以以以以便便便便检检检检测测测测下下下下一一一一组组组组代代代代码码码码。些些些些时时时时的的的的0 0或或或或1,1,就就就就不不不不用用用用记记记记忆忆忆忆了了了了。已已已已记记记记住住住住了了了了前前前前三三三三位位位位，此此此此第第第第4 4位位位位一一一一来来来来就就就就可可可可判判判判出出出出代代代代码码码码的的的的真真真真伪伪伪伪了了了了。如如如如下下下下图图

15、图图右右右右下下下下检检检检出出出出6 6个个个个误误误误码码码码,Z Z=1 1，其他，其他，其他，其他 Z=0 Z=0。完整的状态图如下：有完整的状态图如下：有完整的状态图如下：有完整的状态图如下：有 2 20 0+2+21 1+2+22 2+2+23 3=15=15个状态。个状态。个状态。个状态。（1）建立原始状态图和状态表）建立原始状态图和状态表现在学习的是第12页，共72页ABC0/00/01/01/0DE0/00/01/01/0HI0/00/01/01/0FG0/00/01/01/0JK0/00/01/01/0NP0/00/01/01/0LM0/00/01/01/00/00/01/

16、01/00/00/01/01/00/00/01/01/00/00/01/01/00/00/01/01/00/10/11/11/10/10/11/11/10/10/11/11/1（1）建立原始状态图和状态表）建立原始状态图和状态表现在学习的是第13页，共72页HDAB1/00/0CEI0/00/01/01/0FG0/01/0NJKP0/00/01/01/0LM0/01/00/01/00/01/00/01/00/01/00/01/00/11/10/11/10/11/1状态图状态图101011001110101111011111误码误码第第1位位第第2位位第第3位位第第4位位现在学习的是第14页，共

17、72页现态现态次态次态/输出输出x x=0=0 x x=1=1A AB BC CD DE EF FG GH HI IJ JK KL LMMN NP PB/0B/0D/0D/0J/0J/0F/0F/0H/0H/0A/0A/0A/0A/0A/0A/0A/0A/0L/0L/0N/0N/0A/0A/0A/1A/1A/1A/1A/1A/1C/0C/0E/0E/0K/0K/0G/0G/0I/0I/0A/0A/0A/0A/0A/0A/0A/0A/0M/0M/0P/0P/0A/0A/0A/1A/1A/1A/1A/1A/1状态表状态表状态表状态表注意：注意：注意：注意：原始状态数目可能有冗余。原始状态数目可能有

18、冗余。原始状态数目可能有冗余。原始状态数目可能有冗余。接后会进行简化。接后会进行简化。接后会进行简化。接后会进行简化。现在学习的是第15页，共72页（2）状态简化）状态简化原始状态图，可能有许多冗余状态，必须给于简化，原始状态图，可能有许多冗余状态，必须给于简化，原始状态图，可能有许多冗余状态，必须给于简化，原始状态图，可能有许多冗余状态，必须给于简化，状态多，状态多，状态多，状态多，构成电路越复杂，使用的元器件多，成本高，安全性差。构成电路越复杂，使用的元器件多，成本高，安全性差。构成电路越复杂，使用的元器件多，成本高，安全性差。构成电路越复杂，使用的元器件多，成本高，安全性差。化简后的状态

19、图输入输出关系不变。化简后的状态图输入输出关系不变。化简后的状态图输入输出关系不变。化简后的状态图输入输出关系不变。状态简化的目的就是要消去多余状态，以得到最简状态图和最简状态简化的目的就是要消去多余状态，以得到最简状态图和最简状态简化的目的就是要消去多余状态，以得到最简状态图和最简状态简化的目的就是要消去多余状态，以得到最简状态图和最简状态表。状态表。状态表。状态表。状态化简的两种情况状态化简的两种情况状态化简的两种情况状态化简的两种情况:l l 完全确定的状态表下的状态化简完全确定的状态表下的状态化简完全确定的状态表下的状态化简完全确定的状态表下的状态化简l l 不完全确定的状态表下的状态

20、化简不完全确定的状态表下的状态化简不完全确定的状态表下的状态化简不完全确定的状态表下的状态化简所谓完全确定的状态表：所谓完全确定的状态表：所谓完全确定的状态表：所谓完全确定的状态表：状态表上所有的次态与输出状态表上所有的次态与输出状态表上所有的次态与输出状态表上所有的次态与输出均有确定的值，无不确定的值，均有确定的值，无不确定的值，均有确定的值，无不确定的值，均有确定的值，无不确定的值，否则否则否则否则,为不完全确定的为不完全确定的为不完全确定的为不完全确定的状态表。状态表。状态表。状态表。在状态图中，不可能出现的情况是隐含的。在状态图中，不可能出现的情况是隐含的。在状态图中，不可能出现的情况

21、是隐含的。在状态图中，不可能出现的情况是隐含的。现在学习的是第16页，共72页化简方法：化简方法：化简方法：化简方法：l l 观察法，观察等效状态观察法，观察等效状态观察法，观察等效状态观察法，观察等效状态l l 隐含表法，用隐含表寻找等效状态隐含表法，用隐含表寻找等效状态隐含表法，用隐含表寻找等效状态隐含表法，用隐含表寻找等效状态完全确定的状态表下的状态化简完全确定的状态表下的状态化简现在学习的是第17页，共72页l l化简的原理：状态等效化简的原理：状态等效化简的原理：状态等效化简的原理：状态等效,就可以化简。就可以化简。就可以化简。就可以化简。l l状态等效的条件：状态等效的条件：状态等

22、效的条件：状态等效的条件：两个状态的输出相同、次态也相同两个状态的输出相同、次态也相同两个状态的输出相同、次态也相同两个状态的输出相同、次态也相同 两个状态的输出相同、次态与原态交错两个状态的输出相同、次态与原态交错两个状态的输出相同、次态与原态交错两个状态的输出相同、次态与原态交错 一组状态的输出相同、次态循环一组状态的输出相同、次态循环一组状态的输出相同、次态循环一组状态的输出相同、次态循环DCAB等效等效等效等效1/10/00/01/1x/z利用等效状态可以合并利用等效状态可以合并利用等效状态可以合并利用等效状态可以合并(用一个状态表示用一个状态表示用一个状态表示用一个状态表示)来进行状

23、态来进行状态来进行状态来进行状态简化。简化。简化。简化。完全确定的状态表下的状态化简完全确定的状态表下的状态化简现在学习的是第18页，共72页 使用等效状态时的几个名词概念使用等效状态时的几个名词概念使用等效状态时的几个名词概念使用等效状态时的几个名词概念等效状态的传递性等效状态的传递性等效状态的传递性等效状态的传递性：若：若：若：若S S1 1和和和和S S2 2等效，等效，等效，等效，S S2 2又和又和又和又和S S3 3 等效，则等效，则等效，则等效，则S S1 1也和也和也和也和S S3 3等效。写作：等效。写作：等效。写作：等效。写作：等效类：等效类：等效类：等效类：彼此等效的状态

24、集合，称为等效类，如上彼此等效的状态集合，称为等效类，如上彼此等效的状态集合，称为等效类，如上彼此等效的状态集合，称为等效类，如上(S(S1 1，S S2 2，S S3 3)。最大等效类：最大等效类：最大等效类：最大等效类：若一个等效类不是其它等效类的子集，则称此若一个等效类不是其它等效类的子集，则称此若一个等效类不是其它等效类的子集，则称此若一个等效类不是其它等效类的子集，则称此等效类为最大等效类。即使等效类只含有一个状态，只要它等效类为最大等效类。即使等效类只含有一个状态，只要它等效类为最大等效类。即使等效类只含有一个状态，只要它等效类为最大等效类。即使等效类只含有一个状态，只要它不包含于

25、其他等效类中，它亦是最大等效类。不包含于其他等效类中，它亦是最大等效类。不包含于其他等效类中，它亦是最大等效类。不包含于其他等效类中，它亦是最大等效类。(S(S1 1，S S2 2)，(S(S2 2，S S3 3)(S(S1 1，S S2 2，S S3 3)完全确定的状态表下的状态化简完全确定的状态表下的状态化简现在学习的是第19页，共72页完全确定的状态表下的状态化简完全确定的状态表下的状态化简状态化简实质：状态化简实质：状态化简实质：状态化简实质：找出最大等效类后，找出最大等效类后，找出最大等效类后，找出最大等效类后，它是独立的等效类，再它是独立的等效类，再它是独立的等效类，再它是独立的等

26、效类，再不可能合并了，所以状态化简的实质是寻找最大等效类的状态不可能合并了，所以状态化简的实质是寻找最大等效类的状态不可能合并了，所以状态化简的实质是寻找最大等效类的状态不可能合并了，所以状态化简的实质是寻找最大等效类的状态表表表表(即最小化的状态表即最小化的状态表即最小化的状态表即最小化的状态表)。考虑到最大等效类的概念，则等效状态的判别条件如下：考虑到最大等效类的概念，则等效状态的判别条件如下：考虑到最大等效类的概念，则等效状态的判别条件如下：考虑到最大等效类的概念，则等效状态的判别条件如下：假定假定假定假定SiSiSiSi和和和和SjSjSjSj是完全确定状态表中的两个现态，是完全确定状

27、态表中的两个现态，是完全确定状态表中的两个现态，是完全确定状态表中的两个现态，SiSiSiSi和和和和SjSjSjSj等效等效等效等效的两个条件：在所有输入取值下的两个条件：在所有输入取值下的两个条件：在所有输入取值下的两个条件：在所有输入取值下,它们的它们的它们的它们的输出完全相同输出完全相同输出完全相同输出完全相同,它们的它们的它们的它们的次次次次态满足下列情况之一态满足下列情况之一态满足下列情况之一态满足下列情况之一：1)1)1)1)次态相同次态相同次态相同次态相同2)2)2)2)次态交错次态交错次态交错次态交错(某一输入值下某一输入值下某一输入值下某一输入值下)SiSj0/00/0等效

28、等效等效等效现在学习的是第20页，共72页3)3)次态循环次态循环次态循环次态循环(某一输入取值下某一输入取值下某一输入取值下某一输入取值下)S Si i与与与与S Sk k 构本次态循环构本次态循环构本次态循环构本次态循环S Sj j与与与与S Sl l 构本次态循环构本次态循环构本次态循环构本次态循环(闭环闭环闭环闭环)SiSkSjSl0/01/00/01/0等效等效现在学习的是第21页，共72页4)“次态对次态对”等效等效Sk,Sl相相对对Si,Sj不不存存在在次次态态交交错错、循循环环，但但Sk,Sl之间为等效。之间为等效。互为等效互为等效等效等效0/10/1SiSkSjSl现在学习的

29、是第22页，共72页举例说明举例说明1.观察法观察法某原始状态表如下：某原始状态表如下：现态现态次态次态/输出输出x=0 x=1ABCDA/0A/0A/0A/0B/0C/0D/1D/1现态现态次态次态/输出输出x=0 x=1ABCA/0A/0A/0B/0C/0C/1最大等效类最大等效类：（A）、（）、（B）、（）、（C，D）,用用A、B、C表示表示现在学习的是第23页，共72页C/1C/1B/0B/0C/1C/1E/0E/0B/1B/1E/0E/0D/1D/1B/1B/1D/1D/1B/1B/1XXQQn n0 10 1A AB BC CDDE EB,CB,C输出相同，且次态对与输出相同，且次

30、态对与输出相同，且次态对与输出相同，且次态对与现态对交错，因此现态对交错，因此现态对交错，因此现态对交错，因此B,CB,C等效等效等效等效C/0C/0F/0F/0D/0D/0F/0F/0B/0B/0E/1E/1A/0A/0E/1E/1A/0A/0C/1C/1B/1B/1E/1E/1XXQQn n0 1A ABC CDDE EFA,BA,BC,DC,DABAB等效，且等效，且等效，且等效，且CDCD等效等效等效等效现在学习的是第24页，共72页2.2.隐含表法隐含表法隐含表法隐含表法观察法常常容易遗漏。观察法常常容易遗漏。观察法常常容易遗漏。观察法常常容易遗漏。隐隐隐隐含含含含表表表表法法法法：

31、是是是是一一一一种种种种系系系系统统统统的的的的状状状状态态态态化化化化简简简简方方方方法法法法。用用用用表表表表格格格格把把把把原原原原始始始始状状状状态态态态表表表表中中中中所所所所有有有有的的的的状状状状态态态态两两两两两两两两相相相相比比比比较较较较，找找找找出出出出等等等等效效效效状状状状态态态态对对对对；然然然然后后后后利利利利用用用用等等等等效效效效状状状状态态态态传传传传递递递递性性性性，得得得得到到到到等等等等效效效效类类类类和和和和最最最最大大大大等等等等效效效效类类类类；最最最最后后后后将将将将最最最最大大大大等等等等效效效效类类类类中中中中的的的的状状状状态态态态合合合

32、合并并并并，从而得到最小化状态表。从而得到最小化状态表。从而得到最小化状态表。从而得到最小化状态表。原始状态表原始状态表原始状态表原始状态表等效状态对等效状态对等效状态对等效状态对等效类等效类等效类等效类最大等效类最大等效类最大等效类最大等效类最小化状态表最小化状态表最小化状态表最小化状态表列表两列表两列表两列表两两比较两比较两比较两比较传递性传递性传递性传递性合并合并合并合并状态状态状态状态现在学习的是第25页，共72页举例说明：举例说明：已知原始状态表如下：已知原始状态表如下：已知原始状态表如下：已知原始状态表如下：现态现态现态现态次态次态次态次态/输出输出输出输出x=0 x=0 x=1x

33、=1A AB BC CD DE EF FGGC/0C/0F/0F/0D/0D/0D/1D/1C/0C/0D/0D/0C/1C/1B/1B/1A/1A/1G/0G/0E/0E/0E/1E/1G/0G/0D/0D/0BCDEFGA B C D E FCFCFBEBEAEAECFCFCDCD DE DE现在学习的是第26页，共72页现态现态现态现态次态次态次态次态/输出输出输出输出a ab bc cd db/0b/0c/0c/0c/1c/1b/1b/1x=0 x=0 x=1x=1a/1a/1d/0d/0a/0a/0c/0c/0最小化状态表最小化状态表最小化状态表最小化状态表最大等效类：最大等效类：最

34、大等效类：最大等效类：(A,B,E)(A,B,E)、(C,F)(C,F)、(D)(D)、(G)(G)a ab bc cd d现在学习的是第27页，共72页XX1 1XX2 200 01 11 1000 01 11 10A AB BC CD DE EF FG GHHQ Qn n隐含表化简状态隐含表化简状态D/0D/0D/0D/0F/0F/0A/0A/0C/1C/1D/0D/0E/1E/1F/0F/0C/1C/1D/0D/0E/1E/1A/0A/0D/0D/0B/0B/0A/0A/0F/0F/0C/1C/1F/0F/0E/1E/1A/0A/0D/0D/0D/0D/0A/0A/0F/0F/0G/0G

35、/0G/0G/0A/0A/0A/0A/0B/1B/1D/0D/0E/1E/1A/0A/0A B C D E F GA B C D E F GB BC CD DE EF FG GHH BDBDAFAFDGDGAFAFDFDFBCBCAFAFDFDFAFAFBCBCAFAFBCBCDFDFBDBDBGBGAFAFDGDGAFAF 例例：化简状态化简状态这是两个输入，这是两个输入，这是两个输入，这是两个输入，8 8个状态的电路。隐含表化简方法相同。个状态的电路。隐含表化简方法相同。个状态的电路。隐含表化简方法相同。个状态的电路。隐含表化简方法相同。现在学习的是第28页，共72页2 2、两两两两种种种

36、种方方方方法法法法可可可可混混混混合合合合用用用用，先先先先用用用用观观观观察察察察法法法法，再再再再用用用用隐含表法，以加速简化过程。隐含表法，以加速简化过程。隐含表法，以加速简化过程。隐含表法，以加速简化过程。注注注注意意意意：1 1、最最最最大大大大等等等等效效效效类类类类的的的的集集集集合合合合必必必必须须须须覆覆覆覆盖盖盖盖原原原原始始始始状状状状态态态态表表表表的全部状态的全部状态的全部状态的全部状态现在学习的是第29页，共72页不完全确定状态的化简不完全确定状态的化简状态表中存在不确定的次态状态表中存在不确定的次态状态表中存在不确定的次态状态表中存在不确定的次态(或输出或输出或输

37、出或输出)。利用这些不确定的值，将。利用这些不确定的值，将。利用这些不确定的值，将。利用这些不确定的值，将有利于状态的化简。有利于状态的化简。有利于状态的化简。有利于状态的化简。对于完全确定的状态对于完全确定的状态对于完全确定的状态对于完全确定的状态(或输出或输出或输出或输出)的化简前面已介绍，这里关键的化简前面已介绍，这里关键的化简前面已介绍，这里关键的化简前面已介绍，这里关键是如何处理这些不确定的次态是如何处理这些不确定的次态是如何处理这些不确定的次态是如何处理这些不确定的次态(或输出或输出或输出或输出)。1.1.不完全确定状态不完全确定状态不完全确定状态不完全确定状态(或输出或输出或输出

38、或输出)的处理的处理的处理的处理处理法，引出相容状态的概念处理法，引出相容状态的概念处理法，引出相容状态的概念处理法，引出相容状态的概念 相相相相容容容容状状状状态态态态：设设设设S S1 1和和和和S S2 2是是是是不不不不完完完完全全全全确确确确定定定定状状状状态态态态表表表表上上上上的的的的两两两两个个个个状状状状态态态态。若若若若对对对对于于于于所所所所有有有有的的的的有有有有效效效效输输输输入入入入序序序序列列列列，分分分分别别别别从从从从状状状状态态态态S S1 1和和和和S S2 2出出出出发发发发，所所所所得得得得到到到到的的的的输输输输出出出出响响响响应应应应序序序序列列列

39、列(除除除除不不不不确确确确定定定定的的的的那那那那些些些些值值值值之之之之外外外外)是是是是完完完完全全全全相相相相同同同同的的的的。则则则则称称称称S S1 1和和和和S S2 2相相相相容容容容。记作记作记作记作(S(S1 1,S,S2 2)相容对可以合并。相容对可以合并。相容对可以合并。相容对可以合并。现在学习的是第30页，共72页SiSjSkSl0/00/00/00/00/00/00/00/01/01/01/11/11/d1/dS Si i和和和和S Sj j相容相容相容相容 (除一个输出值为除一个输出值为除一个输出值为除一个输出值为d d之外，之外，之外，之外，其他输出值均相同其他

40、输出值均相同其他输出值均相同其他输出值均相同)SjSj和和和和SkSk相容相容相容相容(理由同上理由同上理由同上理由同上)但但但但SiSi和和和和SkSk不相容不相容不相容不相容 (x=1(x=1时，输出值时，输出值时，输出值时，输出值不相同不相同不相同不相同)有效输入序列有效输入序列有效输入序列有效输入序列:从状态从状态从状态从状态S S出发，如果给定的输入序列所得到的状出发，如果给定的输入序列所得到的状出发，如果给定的输入序列所得到的状出发，如果给定的输入序列所得到的状态响应序列态响应序列态响应序列态响应序列(除最后一个次态外除最后一个次态外除最后一个次态外除最后一个次态外)，其他状态均是

41、确定的。则称此输，其他状态均是确定的。则称此输，其他状态均是确定的。则称此输，其他状态均是确定的。则称此输入序列为状态入序列为状态入序列为状态入序列为状态S S的有效输入序列。的有效输入序列。的有效输入序列。的有效输入序列。相容状态无传递性相容状态无传递性相容状态无传递性相容状态无传递性:若若若若S1S1和和和和S2S2相容，相容，相容，相容，S2S2又和又和又和又和S3S3相容，但相容，但相容，但相容，但S1S1和和和和S3S3不一定相容。不一定相容。不一定相容。不一定相容。现在学习的是第31页，共72页相容状态的判别条件：相容状态的判别条件：相容状态的判别条件：相容状态的判别条件：(判判判

42、判S Si i和和和和S Sj j两状态两状态两状态两状态)在输入的各种取值下在输入的各种取值下在输入的各种取值下在输入的各种取值下:它它它它们们们们的的的的输输输输出出出出值值值值完完完完全全全全相相相相同同同同；或或或或者者者者其其其其中中中中的的的的一一一一个个个个(或或或或两两两两个个个个)输输输输出出出出为为为为任任任任意值，而其他均相同。意值，而其他均相同。意值，而其他均相同。意值，而其他均相同。它们的次态满足下列条件之一它们的次态满足下列条件之一它们的次态满足下列条件之一它们的次态满足下列条件之一:1)1)次态相同；次态相同；次态相同；次态相同；2)2)其中的一个其中的一个其中的

43、一个其中的一个(或两个或两个或两个或两个)为任意状态；为任意状态；为任意状态；为任意状态；3)3)次态交错；次态交错；次态交错；次态交错；4)4)次态循环；次态循环；次态循环；次态循环；5)5)次态对相容；次态对相容；次态对相容；次态对相容；现在学习的是第32页，共72页相容类相容类：两两相容的状态集合，称为相容类。：两两相容的状态集合，称为相容类。最最大大相相容容类类：若若一一个个相相容容类类不不是是任任何何其其他他相相容容类类的的子子集集，则则称该相容类为最大相容类。称该相容类为最大相容类。类类似似于于完完全全确确定定的的状状态态化化简简。对对于于不不完完全全确确定定的的状状态态化化简简则

44、则是是寻寻找找最大相容类最大相容类。状状态态合合并并图图：是是相相容容状状态态简简捷捷找找到到最最大大相相容容类类的的工工具具,它它是是一一个个圆圆周上的点线图。周上的点线图。圆周上均匀分布的点圆周上均匀分布的点表示状态表示状态点间连线点间连线表示相容关系表示相容关系所所有有点点之之间间均均有有连连线线的的多多边边形形(即即任任一一点点和和其其他他点点均均有有连连线线)为最大相容类。为最大相容类。现在学习的是第33页，共72页下图示出下图示出下图示出下图示出3,4,53,4,5个状态的最大相容类的个状态的最大相容类的个状态的最大相容类的个状态的最大相容类的状态合并图状态合并图状态合并图状态合并

45、图S1S2S33 3状态状态状态状态S3S1S4S24 4状态状态状态状态S5S1S3S4S25 5状态状态状态状态最大相容类合并图最大相容类合并图最大相容类合并图最大相容类合并图现在学习的是第34页，共72页2.2.不完全确定的状态化简的步骤不完全确定的状态化简的步骤不完全确定的状态化简的步骤不完全确定的状态化简的步骤步骤类以完全确定状态化简步骤类以完全确定状态化简步骤类以完全确定状态化简步骤类以完全确定状态化简第一步第一步第一步第一步寻找相容状态对寻找相容状态对寻找相容状态对寻找相容状态对第二步第二步第二步第二步寻找最大相容状态类寻找最大相容状态类寻找最大相容状态类寻找最大相容状态类第三步

46、第三步第三步第三步作出最小化状态表作出最小化状态表作出最小化状态表作出最小化状态表第一步：第一步：第一步：第一步：作隐含表作隐含表作隐含表作隐含表 相容状态对相容状态对相容状态对相容状态对寻找寻找寻找寻找两两比较结果有两两比较结果有两两比较结果有两两比较结果有3 3种：种：种：种：（）（）（）（）相容：相容：相容：相容：隐含表中相应方格填入隐含表中相应方格填入隐含表中相应方格填入隐含表中相应方格填入“”（）（）（）（）不相容：不相容：不相容：不相容：填入填入填入填入“”（）暂暂暂暂不不不不定定定定：填填填填入入入入次次次次态态态态对对对对名名名名称称称称。虽虽虽虽然然然然输输输输出出出出相相相

47、相同同同同，但但但但其其其其次次次次态态态态尚尚尚尚不不不不能能能能直直直直接接接接确确确确定定定定是是是是否否否否相相相相容容容容，必必必必须须须须进进进进一一一一步步步步寻寻寻寻找找找找其其其其后后后后续续续续状状状状态态态态是是是是否否否否相相相相容容容容，若若若若相容则前面状态亦相容。相容则前面状态亦相容。相容则前面状态亦相容。相容则前面状态亦相容。现在学习的是第35页，共72页第二步第二步第二步第二步画状态合并图，找最大相容类画状态合并图，找最大相容类画状态合并图，找最大相容类画状态合并图，找最大相容类把相容对连起来，互相有连接的点，构成最大相容类。把相容对连起来，互相有连接的点，构

48、成最大相容类。把相容对连起来，互相有连接的点，构成最大相容类。把相容对连起来，互相有连接的点，构成最大相容类。第三步第三步第三步第三步作出最小化状态表作出最小化状态表作出最小化状态表作出最小化状态表首首首首先先先先需需需需要要要要从从从从最最最最大大大大相相相相容容容容类类类类(或或或或相相相相容容容容类类类类)中中中中先先先先出出出出一一一一组组组组，具具具具有有有有最最最最小小小小闭闭闭闭覆覆覆覆盖盖盖盖的相容类的相容类的相容类的相容类，将此组中每个相容类用一个状态符表示，最小化状态表。，将此组中每个相容类用一个状态符表示，最小化状态表。，将此组中每个相容类用一个状态符表示，最小化状态表。

49、，将此组中每个相容类用一个状态符表示，最小化状态表。所谓最小闭覆盖，它是满足下三个条件的一组相容类：所谓最小闭覆盖，它是满足下三个条件的一组相容类：所谓最小闭覆盖，它是满足下三个条件的一组相容类：所谓最小闭覆盖，它是满足下三个条件的一组相容类：覆盖性：覆盖性：覆盖性：覆盖性：所选相容集合应覆盖原始状态表中的全部状态。所选相容集合应覆盖原始状态表中的全部状态。所选相容集合应覆盖原始状态表中的全部状态。所选相容集合应覆盖原始状态表中的全部状态。最小性：最小性：最小性：最小性：即所选相容集合中相容类个数应最小。即所选相容集合中相容类个数应最小。即所选相容集合中相容类个数应最小。即所选相容集合中相容类

50、个数应最小。闭闭闭闭合合合合性性性性：即即即即所所所所选选选选相相相相容容容容集集集集合合合合中中中中任任任任一一一一相相相相容容容容类类类类，它它它它在在在在原原原原始始始始状状状状态态态态表表表表中中中中产产产产生生生生的的的的次态应属于该选中的相容类集合中的一个。次态应属于该选中的相容类集合中的一个。次态应属于该选中的相容类集合中的一个。次态应属于该选中的相容类集合中的一个。寻找最小闭覆盖的相容类，由闭覆盖表来完成寻找最小闭覆盖的相容类，由闭覆盖表来完成寻找最小闭覆盖的相容类，由闭覆盖表来完成寻找最小闭覆盖的相容类，由闭覆盖表来完成 (见下例见下例见下例见下例)现在学习的是第36页，共7