第四章时序电路 状态分配( 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