eg54状悫化简 eg54状态化简 ●蕴含表是一个直角梯形网格,特点是缺头少尾,任何 个状态都能在一个网格中相遇一 ●相同输入下输出相同,且下1个状态相同,等价填"v ●相同输入下输出相同,且下1个状态交错或自环,等价 ●不等价网格中填”×”;其它情形填相F ×|×(x eg54状态化简:=一柔叠 2)不完全确定的时序电路 最小化状态表 Incompletely Specified Circuit ◆ Compatible States 两个状态S和S相容:当且仅当对于每一种可能的输 入,S和S确定的输出相容或确定的次态相容 00 ◆寻找相容状态 ●利用“蕴涵表 ◆关联结果 ●最大等价类(S1S2,S7) 区K区 ◆寻找最大相容类 (S3S),(S4),(S) x×1 ●当且仅当相容类包含所有与之相容状态 ●从每个最大等价类中选一个状 ●通过“归井图( Merger diagram)得到 态,列出最小化状态表 √×× Is state minimization really necessary 状态分配(状志躺码 O These procedures are seldom used by most designers 状态分配( State assignment) O By carefully matching state meanings to the ●把状态表中每个字符表示的状态对应地规定一个二 requirements of the problem, experienced digital 进制代码,得出代码形式状态表——状态编码 designers produce state tables for small problems with ●分配合理,能使电路得到简化 a minimal or near-minimal number of states. without ◆状态分配方案 using a formal minimization procedure ●n个变量有2种组合,用来对s个状态进行编码共有 OAlso, there are situations where increasing the number 叫/(2-s)分配方案 of states may simplify the design or reduce the cost, so ●已证明,独立的状态分配方案数为(2-1)/(2s)n even an automated state-minimization procedure 码方案数 doesn t necessarily help L图 7L8 140420840840[0810800 55 41 示例 原始状态表 当前状 下一个状态 S(n+1) 输出 Z(n) 态 S(n) X=0 X=1 X=0 X=1 S1 S7 S1 0 0 S2 S7 S1 0 0 S3 S1 S5 0 1 S4 S2 S6 0 1 S5 S7 S3 0 1 S6 S7 S2 0 1 S7 S1 S7 0 0 S2 S3 S4 S5 S6 S7 S1 S2 S3 S4 S5 S6 × √ × × × ×× × × × √ 1,7 × × × 1,2 5,6 1,7 5,3 1,7 5,2 2,7 6,3 2,7 6,2 7,7 3,2 z 蕴含表是一个直角梯形网格，特点是“缺头少尾”，任何 两个状态都能在一个网格中相遇一次； z 相同输入下输出相同，且下1个状态相同，等价填″√″ z 相同输入下输出相同，且下1个状态交错或自环，等价 z 不等价网格中填‘″×″；其它情形填相应等价条件 e.g.5.4 e.g.5.4 状态化简 42 S2 S3 S4 S5 S6 S7 S1 S2 S3 S4 S5 S6 × 9 × × × ×× × × × 9 1,7 × × × 1,2 5,6 1,7 5,3 1,7 5,2 2,7 6,3 2,7 6,2 7,7 3,2 1,7 3,2 9 8 9 8 8 8 8 S2 S3 S4 S5 S6 S7 S1 S2 S3 S4 S5 S6 × √ × × ××× × × × √ × × × × × × × × √ √ e.g.5.4 e.g.5.4 状态化简 43 S2 S3 S4 S5 S6 S7 S1 S2 S3 S4 S5 S6 × √ × × ××× × × × √ × × × × × × × × √ √ 最小化状态表 当前状 下一个状态 S(n+1) 输出 z(n) 态 S(n) X=0 X=1 X=0 X=1 S1 S1 S1 0 0 S3 S1 S3 0 1 S4 S1 S6 0 1 S6 S1 S1 0 1 ‹关联结果 z 最大等价类(S1，S2，S7)， (S3，S5)，(S4)，(S6) z 从每个最大等价类中选一个状 态，列出最小化状态表 示例 原始状态表 当前状 下一个状态 S(n+1) 输出 Z(n) 态 S(n) X=0 X=1 X=0 X=1 S1 S7 S1 0 0 S2 S7 S1 0 0 S3 S1 S5 0 1 S4 S2 S6 0 1 S5 S7 S3 0 1 S6 S7 S2 0 1 S7 S1 S7 0 0 e.g.5.4 e.g.5.4 状态化简 44 2)不完全确定的时序电路 ‹Incompletely Specified Circuit ‹Compatible States z 两个状态Si 和Sj 相容：当且仅当对于每一种可能的输 入，Si 和Sj 确定的输出相容或确定的次态相容 ‹寻找相容状态 z 利用“蕴涵表” ‹寻找最大相容类 z 当且仅当相容类包含所有与之相容状态 z 通过“归并图”(Merger diagram)得到 45 Is state minimization really necessary? ‹These procedures are seldom used by most designers ‹By carefully matching state meanings to the requirements of the problem, experienced digital designers produce state tables for small problems with a minimal or near-minimal number of states, without using a formal minimization procedure ‹Also, there are situations where increasing the number of states may simplify the design or reduce the cost, so even an automated state-minimization procedure doesn’t necessarily help 46 状态分配(状态编码) ‹状态分配(State assignment) z把状态表中每个字符表示的状态对应地规定一个二 进制代码，得出代码形式状态表——状态编码 z分配合理，能使电路得到简化 ‹状态分配方案 zn个变量有2n种组合，用来对s个状态进行编码共有 2n!/ (2n-s)!分配方案 z已证明，独立的状态分配方案数为(2n-1)!/ (2n-s)! n! 编码方案数 s 2 3 4 5 6 7 8 9 n 1 2 2 3 3 3 3 4 N 1 3 3 140 420 840 840 10810800