四时序7电路设计:状态分配_682203142.doc
文本预览下载声明
时序电路
4.3.4 同步时序电路设计
…
(3)状态分配(State assignment)
虽然状态分配是重要的,但其处理又是非常棘手的。
原因:
1.随状态数增加,可能的分配方案数急剧增大;
2.没有找到一个简单有效的方法从中选择最佳方案。
状态数与触发器个数关系:
如设p为电路状态数,k为触发器个数(k、p均为正整数),则应有:
分配方案的个数N与状态数p的关系:
从2K可能状态中中选择p个状态的组合数应为:
但上述分配方案数中,有些是相互等效的。
例:四状态A、B、C、D状态分配。
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
可得激励函数:
方案1 方案2 方案3
(
将方案1的D1求补 )
方案2是将方案1中的Y1变补所得,所以,可将方案1结果中D1表达式中Y1变补后求补得出。
方案3是将方案1中的Y1、Y2交换所得,所以,可将方案1中的Y1、Y2和D1、D2交换得出。
三种分配方案得到的激励函数复杂度完全相同,可认为是等效的。将互不等效的状态分配称独立状态分配。
独立状态分配方案数与状态数NU的关系为:
下表例示了部分状态数和状态分配(独立NU、与不独立N)方案数的关系。
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 84075675600 N 2 24 24 6720 20160 40320 40320 4150000000 29100000000 可见随状态数增加,可分配方案数的急剧增加,从如此多的状态分配方案中寻找最佳自然十分困难。
虽然没有简单有效的方法得到最佳状态分配,但存在一些状态分配的指导原则,在状态分配中尽量遵循这些原则也能使我们得到相当好的结果。
状态分配指导原则:
激励卡诺图是由状态分配决定的,不同的状态分配对应不同的激励卡诺图。为争取得到尽量简单的激励函数,状态分配方案应尽量使激励卡诺图中的1(或0)相邻,以利形成1(或0)的群块。
状态分配时,如被分配的两状态的二元代码仅有一位不同,则称对两状态进行了相邻分配。下述分配规则有助卡诺图中1(或0)的群块的形成。
原则1:对于一个给定的输入,对应相同次态的那些状态应该尽量给予相邻分配。
原则2:对于同一状态,对应相邻输入的那些次态应该尽量给予相邻分配。
原则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、SR触发器,次态相同,则需激励相同,反之亦然。
对于原则1,由于在相同输入情况下,次态相同的那些态被尽量相邻分配,结果在激励卡诺图中,位置相邻的状态其次态是相同的可能性大,亦即意味着对于选择D、SR、JK触发器,其所需激励也相同,有利1、0形成团块、因此有利化简得到较简单的激励函数。
对于原则2,由于在相邻输入时,同一现态的次态在被相邻分配,则此种情况下,因大多触发器的改变相同导致所需激励也相同,且由于其在激励卡诺图中的位置也相邻,因此有利于激形成1(或0)的群块,以利简化的激励函数。
原则3的道理同上。
应用三原则进行状态分配时,如有冲突,则原则1优先级最高,原则3优先级最低。
状态分配步骤:
根据三分配原则分别列出所需相邻分配的状态对;
合并步骤1中分配原则1、2的结果,并按原则1、2和发生次数排队。
按步骤2的结果填写状态分配卡诺图。将0状态分配给状态转换表中起始态或出现最多的状态(使得卡诺图中0多)。
验证书页2
显示全部