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

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，（D，E）转移为C，为单态转移；X=1时的次态转移为AB，BC，同属最小覆盖中的某一个相容类。最小闭合覆盖成立。 修正：去掉（A，D，E）中的重复状态A，用相容对代替最大相容类，得下表： * 4）画出最简状态表： 令：S1=（A，B，C）， S2=（D，E） 最简状态表 原始状态表 * 注意： 选择全部最大相容类组成相容类集，不一定能满足最小化的要求；（例1、例2） 选择部分最大相容类组成相容类集，有可能不满足闭合性要求；（例2） 适当选择最大相容类、相容类组成相容类集，可以得到最小化状态表。（例2） * 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 } 在等效关系中，等效对是狭义的概念，针对两个状态而言。等效类是广义的概念，针对若干个状态而言，甚至一个状态可称为等效类。 等 效 类 * 不是任何其它等效类子集的等效类称为最大等效类。 完全给定同步时序电路原始状态表的化简过程，就是寻找最大等效类，将每个最大等价类中的所有状态合并为一个新状态，从而得到最小状态表的过程。 化