清华大学数字逻辑电路课件四时序5电路设计状态化简

1、第四章 时序电路Sequential Circuits434 同步时序电路设计（2）状态化简（Reduction of State）(书263273) l 同一时序逻辑，不同状态设立方案所得原始状态图中状态数之所以不同是因为状态数目较多的设计结果中存在着多余状态。l 如消除多余态，则可得相同的设计结果。l 无法确保通过合适的状态设立方法直接得到最少状态数的原始状态图，但有某些规范方法将原始状态图中的多余状态消除，此过程之为状态化简。l 随着集成电路密度的提高和可编程器件的发展，以及出于设计中的特殊考虑，不一定将电路状态化至最简，但电路尽量简化的原则还是应该遵循的。l 状态化简工作可由计算机完成

2、。l 所谓多余状态就是状态图中存在着可被另一状态所代替的状态。l 可以相互代替的状态称之为状态等价。l 如能找出原始状态图中所有相互等价态，则可只留不相互等价态，得到最简状态图。状态等价如果将同一时序电路的两个状态Si和Sj分别作为起始态，不论何种输入序列，电路均产生相同的输出序列，我们称Si和Sj是等价状态或等价对，记作SiSj。等价具有传递性。即如有SiSj，SjSK，则有SiSK。等价类：多个相互等价状态之集合。如上述SiSjSk构成一等价类。最大等价类：在同一时序电路中，包含所有状态的等价类的集合。不与其它任何状态等价的单个状态也须看成一个等价类。 等价的时序电路：满足等价条件的两个状

3、态分别在两个时序电路M1和M2中，两个状态也为等价态。两个时序电路M1M2，它们各自的每个状态都能在对方电路中至少找到一个等价态，则称M1M2 是等价的时序电路，否则，是可区分的时序电路。等价态可以互相替代或合并：因从输入和输出的角度看，等价态的表现相同，无法区分。状态化简：找出时序电路原始状态图中的最大等价类，并从每个等价类选一状态作为代表留用，消除其余态，得到最小化的状态图和表。完全确定的时序电路：在原始状态图、表中，对于各种输入，每个状态都有唯一确定的次态和输出。包含有不确定次态、输出时序电路为不完全确定时序电路。完全确定的时序电路状态：化简方法1：蕴含图法。方法2：分隔法。(补充)蕴含

4、图法化简： 原理与步骤：1原始状态集中寻找所有的状态等价对；2组合出最大等价类；3状态合并，构成最简状态集；4由最简状态集导出最小化状态图和表。关键步骤：1.列出原始状态集中所有可能状态对；2.对所有状态对等价判定。组对易，判定难，利用推论。根据等价定义，等价的先决（必要）条件是在所有可能输入情况下状态对输出必须相同，不相同肯定不等价；相同则可能等价，真等价否？取决于转入次态等价对后，所有可能输入作用下输出的情况。由此可得状态对等价判定推论：推论1：在所有可能的相同输入条件下，状态对输出只要有不同，两态一定不等价；推论2：在所有可能的相同输入条件下，状态对输出均相同，且对应次态对等价，则两态等

5、价；对应次态不等价，此两态也不等价。如状态对SiSj现对所有可能相同输入情况其输出均相同，则需考虑次态对情况才能对状态对此SiSj进行等价判定。对应次态对可能出现下两种情况：1、 原态（仍为SiSj）；交错原态（即为SjSi）；同态（即同为Sk）2隐含态。（即对于所有可能相同输入，新的次态对SmSn的输出相同，则称为状态隐含。如次态对的次态对最终为原态对，则称状态互为隐含。）不难验证，当次态对属这两种情况时，对所有相同的输入序列状态对都产生相同输出序列，因此，欲判状态对等价，由此得推论3：推论3：在所有可能的相同输入条件下，状态对的输出相同，且对应次态对为原态、交错原态、同态和互为隐含时，状态

6、对等价。根据推论1、2、3，可对状态对进行直观地等价判定。如状态对的等价判定出现需对次态的次态继续进行等价判定，称追踪判定，经追踪判定最终终可根据三推判定等价否。对于比较简单的原始状态图表可用观察法化简。例：观察法简化三位一判101检测器。观察可得，状态S3、S4和S6在所有同样输入情况下，输出相同，且次态相同，因此相互等价，可合并为一个状态，用状态S3代表。得最小化的状态图。三位一判101 检测器 简化状态图三位一判101检测器 原始状态图 例：观察法化简不重码101检测器原始状态图。 S0和S3输出同态，相互等价，合并为一状态S0，得简化状态图。不重码101检测器不简化状态图不重码101检

7、测器原始状态图 蕴含表法等价对判定适于比较复杂的原始状态图表，可防止遗漏，条理清晰。蕴含表状态等价判定步骤： 设全部原始状态按序排列为S0SN。 1 建立网格，“掐头”“去尾”标注。网格罗列了所有的状态对。2 根据原始状态表逐格进行初始判定并填写结果（等价，不等价，隐含）。3 对隐含状态对进行追踪判定，直至判定结果确定为等价或不等价。4完成追踪判定后，隐含表中所有非打“×”方格对应的状态对即是我们要找的全部等价对。例：对连续3个1检测解1的原始状态图表表格法状态化简。现态次态NS输出Zx=0x=1x=0x=1SA:000SASB00SB:001SCSD00SC:010SESF00SD

8、:011SGSH01SE:100SASB00SF:101SCSD00SG:110SESF00SH:111SGSH01 1初始判定。（先审输出，再看次态）2追踪判定。如方格中有两项隐含状态对时，只要其中一项被判定不等价，则本方格对应状态为不等价，不必再对另项进行追踪判定。（先判不等价）3 列出所有等价状态对。SASC，SASE，SASG，SBSF，SCSE，SCSG，SDSH，SESG。4 导出最大等价类集。注意不要忘记检查完备性，即所有原始状态都必须出现在最大等价类集中。所得最大等价类集为： SASCSESG，SBSF，SDSH。5 合并状态，得最简状态集。用S0、S1、S2顺序分别代表所得三

9、个最大等价类。6 列最小化状态表，画最小化状态图。现态次态输出x=0x=1x=0x=1S0S0S100S1S0S200S2S0S201 最小化状态表最小化状态图 可以发现，与例解2的原始状态图与表完全相同。这说明，最简状态图是唯一的。 例：化简下示原始状态表。现态S(tj)次态S(tj+1)输出z(tj)x=0x=1x=0x=1S1S7S100S2S7S100S3S1S501S4S2S601S5S7S301S6S7S201S7S1S700 1.全部等价状态对为：S1S2,S1S7,S2S7,S3S5。2.最大等价类集为： S1S2S7，S3S5，S4，S6。3 千万不要忘记，最简状态集。S1、

10、S3、S4、S6。4 最小化状态表。现态S(tj)次态S(tj+1)输出z(tj)x=0x=1x=0x=1S1S1S100S3S1S301S4S1S601S6S1S101分割法化简：蕴含表法化简思路是在原始状态集中寻找等价类集。与之对应，分割法是对原始状态集逐步分割为互不等价类，最后得到最大等价类集。（负向思维）原理与步骤：1、 设原始状态集为P0。2、 把P0分隔不同块，即把各种输入情况下输出相同的状态放入同块，结果为P1；所分结果，不同块的状态之间肯定不等价。同块中状态可能等价，也可能不等价。（根据：在各输入的作用下，输出不同肯定不等价。）3、 对P1进行继续分隔，即对每块中状态的次态进行

11、审察，把其次态都在P1中同块的状态仍放入同块，否则分为新块，结果为P2；所分结果，不同块的状态之间肯定不等价。同块中状态可能等价，也可能不等价。（根据：因在不同块中的次态肯定不等价，所以在各输入的作用下，次态在同块中的状态不等价，须分割。）4、 连续分进行步骤2，直至PK1PK，分割完毕。所分结果为最大等价类集。同块中状态等价，不同块状态不等价。（根据：各块中，在各输入的作用下，次态永同块，输出永相同，必等价。）例1：分割法化简。（p306 8-11）P1=（ADFG）(BCEH)00 DDDG CCCB01 DBDG DDFD11 FAAA EEEE10 AFFA FAAAP2=（AFG）(

12、D)(BCEH)00 DDG CCCB 01 DDG DDFD11 FAA EEEE10 AFA FAAAP3=(AF)(G)(D)(BCH)(E)P4P3令：a=（AF）,b=(BCH),c=(D),d=(E),e=(G).例2：PS NS/ZX=0X=1AC/1B/0BC/1E/0CB/1E/0DD/0B/1EE/0A/1(ABCDE)输出 11100输出 00011 ABC输出同DE输出同分（ABC）（DE） (ABC) (DE)次态 CCB DE次态 BEE BA BC次态在x0、1时均同块，A次态X1时与BC不同块，分出。D、E次态均同块，不分。分（A）（BC）（A）(BC) (DE)次态 C CB DE次态 B EE BAB、C次态均同块，不分。DE次态X1时不同块，分。分（D）（E）(A) (BC) (D) (E)次态 C CB D E次态 B EE B A(A) (BC) (D) (E) P0X=0 X=1 P1 X=0 X=1 P2 X=0 X=1 P3 X=0 X=1 P4=P3例3：分割法化简前例。（连续2个以上1检测）现态次态NS输出Zx=0x=1x=0x=1SA:000SASB00SB:001SCSD