第四章时序电路 状态分配( State ass ignment) 非常不幸」虽然状态分配是重要的,但其 处理又是非常棘手的。 原因:1随状态数的增加,可能的分配方案 数急剧增大; 2没有找到一个简单有效的方法从 中选择最佳方案。 状态数与触发器个数关系 如设p为电路状态数,k为触发器个数(k p均为正整数),则应有: 2-<p≤2k 分配方案的个数N与状态数p的关系: 从2中选择p的组合数。 (2-p)! 单一状态分配: 上述分配方案中,有些是等效的。 例:四状态A、B、G、D状态分配
第四章 时序电路 …… 状态分配（State assignment） 虽然状态分配是重要的，但其 处理又是非常棘手的。 原因：1.随状态数的增加，可能的分配方案 数急剧增大； 2.没有找到一个简单有效的方法从 中选择最佳方案。 状态数与触发器个数关系: 如设 p 为电路状态数，k 为触发器个数（k、 p 均为正整数），则应有： 1 2 K− < K p 2 分配方案的个数 N 与状态数 p 的关系: 从 2 K中选择 p 的组合数。 2 p ! 2 k k （ － ） N = ！ 单一状态分配： 上述分配方案中，有些是等效的。 例：四状态 A、B、C、D 状态分配。 非常不幸
分配方案 PS0 1 S 1 AA/0B/ Y1Y2Y1Y2 Y,Y2 A001000 B|A/0|c/0 B01111 cc/0|D/0 G|110111 D|0/1A/0 D1000|01 激励函数: 方案1 方案2 方案3 D,=YX+YX D=YX+Y,x D,=X+YX D2=YX+YX D2=YX+YX D=X+YX (n=元x+y,x=(x+x+x) YX+Y2X 方案2是将方案1中的Y1求补所得,所以, 可将方案1结果中Y1和D1求补得出。 方案3是将方案1中的Y1Y2交换所得,所 以,可将方案1中的Y1、Y2和D1、D2交换得出。 三种分配方案得到的激励函数复杂度相同, 可认为是等效的。不存在相互等效的所有状态分 配方案称为单一状态分配。单一状态分配方案数 与状态数N的关系为:
激励函数： 方案 1 方案 2 方案 3 D1 = Y1 X + Y2 X D1 = Y1 X + Y2 X D1 = Y2 X + Y2 X D2 = Y1 X + Y1X D2 = Y1 X + Y1X D2 = Y2 X + Y1X ( ( )( ) D1 = Y1 X +Y2X = Y1 + X Y2 + X = Y1 X + Y2 X ) 方案 2 是将方案 1 中的 Y1求补所得，所以， 可将方案 1 结果中 Y1和 D1求补得出。 方案 3 是将方案 1 中的 Y1、Y2交换所得，所 以，可将方案 1 中的 Y1、Y2和 D1、D2交换得出。 三种分配方案得到的激励函数复杂度相同， 可认为是等效的。不存在相互等效的所有状态分 配方案称为单一状态分配。单一状态分配方案数 与状态数 NU的关系为： PS X 0 1 A A/0 B/0 B A/0 C/0 C C/0 D/0 D C/1 A/0 S 分配方案 1 Y1Y2 2 Y1Y2 3 Y1Y2 A B C D 00 01 11 10 10 11 01 00 00 10 11 01
(2k-1) (2k-p)K! 下表例示了一些状态数和状态分配方案数 的关系。 140 840 1081080075675600 2242467202016040320403204150000002910000000 虽然没有简单有效的方法得到最佳状态分 配,但存在一些状态分配的指导原则,在状态分 配中尽量遵循这些原则也能使我们得到相当好 的结果。 状态分配指导原则 激励卡诺图是由状态卡诺图决定的,不同的 状态分配产生不同的激励卡诺图。为争取得到尽 量简单的激励函数,状态分配方案应尽量使激励 卡诺图中的1(或0)相邻,以利形成1(或0) 的群块。下述规则有助卡诺图中1(或0)的群 块的形成。 原则1:对于一个给定的输入,具有相同次 态的那些状态应该尽量给予相邻分配。 原则2:对于相邻输入情况下,同一状态的
2 p ! ! (2 1) k k K NU （ － ） = − ！ 下表例示了一些状态数和状态分配方案数 的关系。 虽然没有简单有效的方法得到最佳状态分 配，但存在一些状态分配的指导原则，在状态分 配中尽量遵循这些原则也能使我们得到相当好 的结果。 状态分配指导原则 激励卡诺图是由状态卡诺图决定的，不同的 状态分配产生不同的激励卡诺图。为争取得到尽 量简单的激励函数，状态分配方案应尽量使激励 卡诺图中的 1（或 0）相邻，以利形成 1（或 0） 的群块。下述规则有助卡诺图中 1（或 0）的群 块的形成。 原则 1：对于一个给定的输入，具有相同次 态的那些状态应该尽量给予相邻分配。 原则 2：对于相邻输入情况下，同一状态的 p 2 3 4 5 6 7 8 9 10 k 1 2 2 3 3 3 3 4 4 NU 1 3 3 140 420 840 840 10810800 75675600 N 2 24 24 6720 20160 40320 40320 4150000000 29100000000
那些次态应该尽量给予相邻分配。 原则3:对于具有相同输出的那些状态应该 尽量给予相邻分配。 分配原则之原理: 观察激励表可以发现,对于D触发器,无论 其原处何态,只要次态相同,则所需激励相同。 对于SR和K触发器,考虑到任意值,也只要次 态相同,则也可认为所需激励相同。 a)JK触发器 (b)SR触发器 Q(t) Q(t+1) Q(t) Q(t+1) OX 0101 10 (c)D触发器 (d)T触发器 Q(t) Q(t+1) D Q(t) Q(t+1) 0 0101
那些次态应该尽量给予相邻分配。 原则 3：对于具有相同输出的那些状态应该 尽量给予相邻分配。 分配原则之原理： 观察激励表可以发现，对于 D 触发器，无论 其原处何态，只要次态相同，则所需激励相同。 对于 SR 和 JK 触发器，考虑到任意值，也只要次 态相同，则也可认为所需激励相同。 (a) JK 触发器 (b) SR 触发器 Q(t) Q(t+1) JK Q(t) Q(t+1) SR 0 0 0X 0 0 0X 0 1 1X 0 1 10 1 0 X1 1 0 01 1 1 X0 1 1 X0 (c) D 触发器 (d) T 触发器 Q(t) Q(t+1) D Q(t) Q(t+1) T 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 1 0 1 1 1 1 1 1 0
由上可得,对于D、JK、R触发器,激励值 相同,即意味次态相同 对于原则1,由于在相同输入情况下,次态 相同的那些态被相邻分配,即意味着对于D、SR JK触发器在此种情况下不仅由于改变结果的相 同,因而所需激励值相同,而且相对于状态变量, 由于相邻分配,这所需相同激励值在激励卡诺图 中的位置也相邻,因此有利于激励卡诺图中的1 (或0)形成群块,使其较少依赖于状态变量。 对于原则2,由于在相邻输入情况下,次态 被相邻分配,意味着在此种情况下,大多触发器 的改变相同(所需激励值也相同),且相对于输 入变量,这些所需相同激励(值)在激励卡诺图 中的位置也相邻,因此有 分配方案 利于激励卡诺图中的1s 2 (或0)形成群块,使其 YiY2Y1Y2Y1Y2 较少依赖于输入变量。 A|001000 同理,原则3有利于B011110 输出函数卡诺图中的101101 或0)形成群块,减弱D100001
由上可得，对于 D、JK、SR 触发器，激励值 相同，即意味次态相同。 对于原则 1，由于在相同输入情况下，次态 相同的那些态被相邻分配，即意味着对于 D、SR JK 触发器在此种情况下不仅由于改变结果的相 同，因而所需激励值相同，而且相对于状态变量， 由于相邻分配，这所需相同激励值在激励卡诺图 中的位置也相邻，因此有利于激励卡诺图中的 1 （或 0）形成群块，使其较少依赖于状态变量。 对于原则 2，由于在相邻输入情况下，次态 被相邻分配，意味着在此种情况下，大多触发器 的改变相同（所需激励值也相同），且相对于输 入变量，这些所需相同激励（值）在激励卡诺图 中的位置也相邻，因此有 利于激励卡诺图中的 1 （或 0）形成群块，使其 较少依赖于输入变量。 同理，原则 3 有利于 输出函数卡诺图中的 1 （或 0）形成群块，减弱 S 分配方案 1 Y1Y2 2 Y1Y2 3 Y1Y2 A B C D 00 01 11 10 10 11 01 00 00 10 11 01
化简结果与状态变量的相关。 验证: X PS|01 A|A/0|B/0 A/ c/0 G|c/0|D/0 D|0/1A/0 应用三原则进行 状态分配时,如有冲突,则原则1优先级最高, 原则3优先级最低。 状态分配步骤: 1.根据三分配原则分别列出所需相邻分 配的状态对; 2.合并步骤1中分配原则1、2的结果, 并原则1、2和发生次数排队。 3.按步骤2的结果填写状态分配卡诺图。 将0状态分配给状态转换表中起始态或 出现最多的状态
化简结果与状态变量的相关。 验证： ⚫ 应用三原则进行 状态分配时，如有冲突，则原则 1 优先级最高， 原则 3 优先级最低。 状态分配步骤： 1． 根据三分配原则分别列出所需相邻分 配的状态对； 2． 合并步骤 1 中分配原则 1、2 的结果， 并原则 1、2 和发生次数排队。 3． 按步骤 2 的结果填写状态分配卡诺图。 将 0 状态分配给状态转换表中起始态或 出现最多的状态。 PS X 0 1 A A/0 B/0 B A/0 C/0 C C/0 D/0 D C/1 A/0
验证书页177例 利用状态分配指导原则核验下例时序电路 之状态分配。 现在状态 下一个状态 =1 0 0 0 存在840种单一分配方案。 1.由原则1得具有相同次态应尽量给予相 邻分配的状态对为: (S1S5)、(S2S)、(S3S)、(SS6) 2.由原则2得同态之次态应尽量给予相邻 分配的状态对为 (SS)、(S2S3)、(SS5)、(SS) 3.由原则3得具有相同输出同应尽量给予 相邻分配的状态对为 (SS6)、(SS)、(S1S3)、(SS7)、(SS8)、 (SS8)、(S2S3)、(S2S)(S2S)、(SS4、 (S3S5)、(SAS5)
验证书页 177 例： 利用状态分配指导原则核验下例时序电路 之状态分配。 存在 840 种单一分配方案。 1． 由原则 1 得具有相同次态应尽量给予相 邻分配的状态对为： （S1S5）、（S2S8）、（S3S7）、（S4S6）。 2． 由原则 2 得同态之次态应尽量给予相邻 分配的状态对为： （S1S6）、（S2S3）、（S4S5）、（S7S8）。 3． 由原则 3 得具有相同输出同应尽量给予 相邻分配的状态对为： （S1S6）、（S1S7）、（S1S8）、（S6S7）、（S6S8）、 （S7S8）、（S2S3）、（S2S4）（S2S5）、（S3S4）、 （S3S5）、（S4S5）。 现在状态 下一个状态 输出 x=0 x=1 x=0 x=1 S1 S3 S2 1 1 S2 S7 S8 0 0 S3 S6 S1 0 0 S4 S4 S5 0 0 S5 S3 S2 0 0 S6 S4 S5 1 1 S7 S6 S1 1 1 S8 S7 S8 1 1
4.对比分配方案1、2状态分配卡诺图。 CAB AB 0S, S3 S, S OS4 S3 S 0。s G|00011110c0001111 1S2 s4 SB S6 1S S, S 方案1 方案2 核验状态分配方案1、2的分配卡诺图可 证,方案2较好的遵循了状态分配原则。 利用状态分配指导原则状态分配举例 时序电路状态表。 PS A=0 A=1 U/1 V/1 TUvwxYz T/0 Y/0 Y/0 X/1 Y/0 X/0 Z/1 W/1 /0 U/0 X/0 Y/1
4． 对比分配方案 1、2 状态分配卡诺图。 方案 1 方案 2 核验状态分配方案 1、2 的分配卡诺图可 证，方案 2 较好的遵循了状态分配原则。 利用状态分配指导原则状态分配举例 时序电路状态表。 PS A=0 A=1 T U/1 V/1 U T/0 Y/0 V Y/0 X/1 W Y/0 X/0 X Z/1 W/1 Y W/0 U/0 Z X/0 Y/1 AB C 00 01 11 10 0 1 S1 S3 S7 S5 S2 S4 S8 S6 AB C 00 01 11 10 0 1 S4 S3 S2 S5 S6 S7 S8 S1
应用三状态分配原则得: 原则1:(V,W)2x;(U,Z) 原则2:(U,V);(T,Y);(X,Y)3x;(w,Z);(U,W) 原则3:(XT);(U,W);(U,Y);(w,Y;(,Z) 根据分配原则填状态分配卡诺图。 (因状态表中状态Y出现最多,分配其代码 为000)。 AB 00011110 0Y V WT X U Z 蕴含图 法状态 分配 蕴含图是确定状态对相邻分配的另一工具。 蕴含图法是在分配指导原则的基础上更多 的发掘和利用电路状态转移的规律,所以结果会 更好。 蕴含图用流图形式描述时序电路中状态对 在给定输入情况下相互转换之关系。状态对用节 点表示,节点之间由转移线连接 蕴含图例
应用三状态分配原则得： 原则 1：（V,W）2x;(U,Z). 原则 2：（U,V）;（T,Y）;（X,Y）3x;(W,Z);(U,W). 原则 3：（X,T）;（U,W）;（U,Y）;(W,Y);(V,Z). 根据分配原则填状态分配卡诺图。 （因状态表中状态 Y 出现最多，分配其代码 为 000）。 蕴 含 图 法 状 态 分配 蕴含图是确定状态对相邻分配的另一工具。 蕴含图法是在分配指导原则的基础上更多 的发掘和利用电路状态转移的规律，所以结果会 更好。 蕴含图用流图形式描述时序电路中状态对 在给定输入情况下相互转换之关系。状态对用节 点表示，节点之间由转移线连接。 蕴含图例。 AB C 00 01 11 10 0 1 Y V W T X U Z
(U,W) (X,Y (V,w) (T,) (U,V) (X,T) 闭子图2闭子图 如一状态对相邻分配对 PS A=0 A=1 简化激励函数有利,那么能 T U/1 V/ 相互转换的状态对群也应尽 U T/0 Y/0 量相邻分配,以利在激励卡 V Y/0 X/ 诺图中形成尽量大的1(或0) W Y/0 X/0 的群块。 Z/1W/1 XYz 蕴含图设法找出这样的 W/0U/0 群 X/0Y/1 包含了所有可能状态对 的蕴含图称为完全蕴含图。完全蕴含图的部分称 为子图。 如子图中所有状态对的转移仍在同一子图 内则称之为闭子图。转移线可进入闭子图,但决
闭子图 2 闭子图 1 如一状态对相邻分配对 简化激励函数有利，那么能 相互转换的状态对群也应尽 量相邻分配，以利在激励卡 诺图中形成尽量大的1（或 0） 的群块。 蕴含图设法找出这样的 群。 包含了所有可能状态对 的蕴含图称为完全蕴含图。完全蕴含图的部分称 为子图。 如子图中所有状态对的转移仍在同一子图 内则称之为闭子图。转移线可进入闭子图，但决 PS A=0 A=1 T U/1 V/1 U T/0 Y/0 V Y/0 X/1 W Y/0 X/0 X Z/1 W/1 Y W/0 U/0 Z X/0 Y/1 (V,W) (U,Z) (X,T) (T,Y) (W,Z) (X,Y) (U,V) (U,W)