《四时序7电路设计：状态分配》由会员分享，可在线阅读，更多相关《四时序7电路设计：状态分配（16页珍藏版）》请在金锄头文库上搜索。
1、第四章时序电路434 同步时序电路设计 (3)状态分配(State assignment)非常不幸虽然状态分配是重要的，但其处 理又是非常棘手的。原因：1. 随状态数增加，可能的分配方案数急剧增大；2. 没有找到一个简单有效的方法从中选择最佳 方案。状态数与触发器个数关系:如设p为电路状态数，k为触发器个数（k、P均 为正整数），则应有：2 K-1 p 2 K分配方案的个数 N 与状态数 p 的关系:从2k可能状态中中选择p个状态的组合数应为：2k - p )!N 二 2 k !但上述分配方案数中，有些是相互等效的。例：C、D 状态分配。PSX 0 1AA/0B/0BA/0C/0CC/0D/0
2、DC/1A/0S分配方案例1 YY1 22 YY1 23YY1 2A00-1000 -B011110C110111D100001可得激励函数：方案 1方案 2方案 3D 二YX+Y X112D 二YX+YX211D 二YX+0XD 二Y X+YX112122D =Y X+YXD 二Y X +YX211221(D 二 YX + YX 二(Y + X )(Y + X)1 1 2 1 2二yx + Yx将方案1的D1求补)12方案2是将方案1中的Y1变补所得，所以，可将 方案1结果中D表达式中Y变补后求补得出。1 1方案3是将方案1中的Y、Y交换所得，所以，12可将方案1中的Y、Y和D、D交换得出。
3、1 2 1 2三种分配方案得到的激励函数复杂度完全相同，可认为是等效的。将互不等效的状态分配称独立状态 分配。独立状态分配方案数与状态数N的关系为:U(2k2 k - p )! K !下表例示了部分状态数和状态分配（独立儿、与 不独立N）方案数的关系。p2345678910k122333344NU1331404208408401081080075675600N224246720201604032040320415000000029100000000可见随状态数增加，可分配方案数的急剧增加，从如此多的状态分配方案中寻找最佳自然十分困难。虽然没有简单有效的方法得到最佳状态分配，但存在一些状态分配的
4、指导原则，在状态分配中尽量遵 循这些原则也能使我们得到相当好的结果。状态分配指导原则：激励卡诺图是由状态分配决定的，不同的状态分 配对应不同的激励卡诺图。为争取得到尽量简单的激 励函数，状态分配方案应尽量使激励卡诺图中的 1（或 0）相邻，以利形成 1（或0）的群块。状态分配时，如被分配的两状态的二元代码仅有 一位不同，则称对两状态进行了相邻分配。下述分配 规则有助卡诺图中 1（或0）的群块的形成。原则 1：对于一个给定的输入，对应相同次态的 那些状态应该尽量给予相邻分配。原则 2：对于同一状态，对应相邻输入的那些次 态应该尽量给予相邻分配。原则 3：对于具有相同输出的那些状态应该尽量 给予相
5、邻分配。分配原则之原理：观察激励表可以发现，对于 D 触发器，无论其原 处何态，只要次态相同，则所需激励相同。对于SR 和JK触发器，考虑到任意项，也只要次态相同，则 也可认为所需激励相同。(a) JK触发器(b) SR触发器Q(t)Q(t+1)JKQ(t)Q(t+1)SR000X000X011X011010X1100111X011X0(c) D触发器(d) T触发器Q(t)Q(t+1)DQ(t)Q(t+1)T000000011011100101111110由上可得，对于 D、JK、SR 触发器，次态相同， 则需激励相同，反之亦然。对于原则 1，由于在相同输入情况下，次态相同 的那些态被尽量相
6、邻分配，结果在激励卡诺图中，位 置相邻的状态其次态是相同的可能性大，亦即意味着 对于选择 D、SR、JK 触发器，其所需激励也相同，有 利 1、0 形成团块、因此有利化简得到较简单的激励函数。对于原则 2，由于在相邻输入时，同一现态的次 态在被相邻分配，则此种情况下，因大多触发器的改 变相同导致所需激励也相同，且由于其在激励卡诺图 中的位置也相邻，因此有利于激形成 1（或 0）的群 块，以利简化的激励函数。原则 3的道理同上。应用三原则进行状态分配时，如有冲突，则原则 1 优先级最高，原则 3 优先级最低。状态分配步骤：1 根据三分配原则分别列出所需相邻分配的 状态对；2 合并步骤1中分配原则
7、 1、2的结果，并按 原则1、2 和发生次数排队。3 按步骤 2的结果填写状态分配卡诺图。将 0 状态分配给状态转换表中起始态或出现最多的状态 （使得卡诺图中 0 多）。验证书页 274例：利用状态分配指导原则核验下例时序电路之状 态分配。现在状态下一个状态输出x=0x=1x=0x=1S1S3S211S2S7S800S3S6S100S4S4S500S5S3S200S6S4S511S7S6S111S8S7S811存在840种单一分配方案。1 由原则 1 得具有相同次态应尽量给予相邻 分配的状态对为：（SS ）、（SS ）、（SS ）、（SS ）。1 5 2 8 3 7 4 62 由原则 2得同态
8、之次态应尽量给予相邻分配 的状态对为：（SS ）、（SS ）、（SS ）、（SS ）。1 6 2 3 4 5 7 83 由原则 3 得具有相同输出同应尽量给予相 邻分配的状态对为：（SS）（SS 、（S S ）、（S S ）（S S 、（SS）、1 61 71 86 76 87 8（SS）（SS）（SS）、（SS）（SS 、（SS）。2 32 42 53 43 54 54 对比分配方案 1、2 状态分配卡诺图。A000111100SSSS方3751方SSS486A000111100SSSS43251SSSS6781案 1 方案 2核验表明，方案 2比方案1较好的遵循了状态分 配原则，因此激励函
9、数简单。状态分配举例对右状态图中状态应用三状态分配原则进行状态分配。PSA=0A=1TU/1V/1UT/0Y/0VY/0X/1WY/0X/0XZ/1W/1YW/0U/0ZX/0Y/1原则 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）;AB00 01 11C TO0YVW1TX U Z（W,Y）;（V,Z）. 根据分配原则填状态分配卡诺 图。（因状态表中状态Y出现最多, 分配其代码为 000）。蕴含图法状态分配蕴含图法是得到好的状态分配的另一辅助工具蕴含图法是在分配指导原则的基础上更多的发
10、 掘和利用电路状态转移的规律，所以结果会更好。蕴含图用流图形式描述时序电路中状态对在给 定输入情况下相互转换之关系。状态对用节点表示，节点之间由转移线连接。蕴含图例PSA=0A=1TU/1V/1UT/0Y/0VY/0X/1WY/0X/0XZ/1W/1YW/0U/0ZX/0Y/1(U,V)(V,W)(U,Z)(X,T)闭子图 2 闭子图 1 如一状态对相邻分配对简化激励函数有利，那么 能相互转换的状态对群也应尽量相邻分配，有利于在 激励卡诺图中形成尽量大的 1（或 0）的群块，蕴含 图通过权衡设法找出应尽量相邻分配的群。包含了所有可能状态对的蕴含图称为 完全蕴含 图。完全蕴含图的部分称为子图。如
11、在子图中，所有从状态对出发的转移线仍终止于同一子图内的状态对，则称之为闭子图。转移线可 进入闭子图，但决不从闭子图中发出。闭子图中的状态对构成状态对链。链中的状态对应相邻分配，以构成激励卡诺图中 1的大团块。 用蕴图进行状态分配步骤1 应用状态分配三原则导出初始相邻分配对。2 以原则 1、2所得状态对开始，导出蕴含图 图中要包含所有的原则 1、2导出的状态对。3 找出蕴含图中存在的闭子图。列出闭子图 的状态对链。4 排优先状态对列。大闭子图优先，闭子图 中多次出现和被多次访问优先。5 尽量按所排状态对列相邻分配填状态分配 卡诺图。用蕴含图法对上例实施状态分配1步骤 1 得：原则 1：(V,W)
12、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).2步骤2 得闭子图 1、2。3步骤3 得状态链：闭子图 1：(U,Z)、(X,T)。闭子图 2：(U,V)、(T,Y)、(U,W)、(X,Y)、(W,Z)4 步骤 4得状态对优先级排列：(X,Y) (U,W)(T,Y)(V,U)(W,Z) (T,X)(U,Z)(V,W)3 /2闭子图 2闭子图 15 填状态分配卡诺图。（三种分配方案对比）八100 01 11 100Y V W T1X U Z用分配原则）八100 01 11 100T Y W Z卫用蕴含图法）（出现最多态Y设0）（起始态T设为0）（出现最多态Y设0）SFFF3 2 1FFF3 2 1FFF3 2 1T100000100U011111011V010101111W110110010X001011001Y000010000Z111100110三种方案状态表F3F:1000111100011000000001101
