时序电路
……
状态分配（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
(
)
方案2是将方案1中的Y1求补所得，所以，可将方案1结果中Y1和D1求补得出。
方案3是将方案1中的Y1、Y2交换所得，所以，可将方案1中的Y1、Y2和D1、D2交换得出。
三种分配方案得到的激励函数复杂度相同，可认为是等效的。不存在相互等效的所有状态分配方案称为单一状态分配。单一状态分配方案数与状态数NU的关系为：
下表例示了一些状态数和状态分配方案数的关系。
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
虽然没有简单有效的方法得到最佳状态分配，但存在一些状态分配的指导原则，在状态分配中尽量遵循这些原则也能使我们得到相当好的结果。
状态分配指导原则激励卡诺图是由状态卡诺图决定的，不同的状态分配产生不同的激励卡诺图。为争取得到尽量简单的激励函数，状态分配方案应尽量使激励卡诺图中的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）形成群块，使其较少依赖于状态变量。
S
分配方案
1
Y1Y2
2
Y1Y2
3
Y1Y2
A
B
C
D
00
01
11
10
10
11
01
00
00
10
11
01
对于原则2，由于在相邻输入情况下，次态被相邻分配，意味着在此种情况下，大多触发器的改变相同（所需激励值也相同），且相对于输入变量，这些所需相同激励（值）在激励卡诺图中的位置也相邻，因此有利于激励卡诺图中的1（或0）形成群块，使其较少依赖于输入变量。
同理，原则3有利于输出函数卡诺图中的1（或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
应用三原则进行状态分配时，如有冲突，则原则1优先级最高，原则3优先级最低。
状态分配步骤：
根据三分配原则分别列出所需相邻分配的状态对；
合并步骤1中分配原则1、2的结果，并原则1、2和发生次数排队。
按步骤2的结果填写状态分配卡诺图。将0状态分配给状态转换表中起始态或出现最多的状态。
验证书页177例：
利用状态分配指导原则核验下例时序电路之状态分配。
现在状态
下一个状态
输出
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
存在840种单一分配方案。
由原则1得具有相同次态应尽量给予相邻分配的状态对为：
（S1S5）、（S2S8）、（S3S7）、（S4S6）。
由原则2得同态之次态应尽量给予相邻分配的状态对为：
（S1S6）、（S2S3）、（S4S5）、（S7S8）。
由原则3得具有相同输出同应尽量给予相邻分配的状态对为：
（S1S6）、（S1S7）、（S1S8）、（S6S7）、（S6S8）、（S7S8）、（S2S3）、（S2S4）（S2S5）、（S3S4）、（S3S5）、（S4S5）。
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、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
应用三状态分配原则得：
原则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
蕴含图法状态分配蕴含图是确定状态对相邻分配的另一工具。
蕴含图法是在分配指导原则的基础上更多的发掘和利用电路状态转移的规律，所以结果会更好。
蕴含图用流图形式描述时序电路中状态对在给定输入情况下相互转换之关系。状态对用节点表示，节点之间由转移线连接。
蕴含图例。
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
闭子图2 闭子图1
如一状态对相邻分配对简化激励函数有利，那么能相互转换的状态对群也应尽量相邻分配，以利在激励卡诺图中形成尽量大的1（或0）的群块。
蕴含图设法找出这样的群。
包含了所有可能状态对的蕴含图称为完全蕴含图。完全蕴含图的部分称为子图。
如子图中所有状态对的转移仍在同一子图内则称之为闭子图。转移线可进入闭子图，但决不从闭子图中发出。当连接状态对节点的转移线形成闭环时，则产生闭子图。
闭子图中的状态对构成状态对链。链中的状态对应相邻分配，以构成激励卡诺图中1的大团块。
用蕴图进行状态分配步骤应用状态分配三原则导出初始相邻分配对。
以原则1、2所得状态对开始，画出出蕴含图。蕴含图要包含所有的原则1、2导出的状态对。
找出蕴含图中存在的闭子图。列出闭子图的状态对链。
以大闭子图优先，闭子图中多次出现优先排列状态对。
尽量按所排状态对列相邻分配填状态分配卡诺图。
按蕴含图法对上例实施状态分配
1．步骤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）;(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得状态对列：
(X,Y)3(W,Z)(V,U)(T,Y)(U,W)(T,X)(U,Z)(V,W)2
闭子图2 闭子图1
填状态分配卡诺图。
F3F2
F1
00 01 11 10
0
1
T Y W Z
X U V
F3F2
F1
00 01 11 10
0
1
Y V W T
X U Z
F3F2
F1
00 01 11 10
0
1
Y W Z T
X U V
三种分配方案
（规则，Y＝0） （图，T＝0） （图，Y＝0）
S
F3F2F1
F3F2F1
F3F2F1
T
U
V
W
X
Y
Z
100
011
010
110
001
000
111
000
111
101
110
011
010
100
100
011
111
010
001
000
110
F3F2
F1X
00 01 11 10
00
01
11
10
111 110 010 011
101 111 011 010
ddd 110 010 011
ddd 100 000 010
F3F2
F1X
00 01 11 10
00
01
11
10
010 000 001 011
011 001 000 111
010 000 001 ddd
110 100 000 ddd
F3F2
F1X
00 01 11 10
00
01
11
10
110 000 000 011
011 001 001 010
110 000 000 ddd
111 100 001 ddd
三种方案状态表
F3F2
F1X
00 01 11 10
00
01
11
10
1 0 0 0
0 0 0 0
1 0 0 d
1 1 0 d
F3F2
F1X
00 01 11 10
00
01
11
10
1 1 0 0
1 1 0 0
d 1 0 0
d 1 0 0
F3F2
F1X
00 01 11 10
00
01
11
10
0 0 0 0
0 0 0 1
0 0 0 d
1 1 0 d
激励卡诺图F3
门：3与233、1或3 0 2与331或2
线：11线 0 8线
F3F2
F1X
00 01 11 10
00
01
11
10
1 0 0 1
1 0 0 1
1 0 0 d
1 0 0 d
F3F2
F1X
00 01 11 10
00
01
11
10
1 1 1 1
0 1 1 1
d 1 1 1
d 0 0 1
F3F2
F1X
00 01 11 10
00
01
11
10
1 0 0 1
1 0 0 1
1 0 0 d
1 0 0 d
激励卡诺图F2
门：0 3与2221或3 0
线：0 9线 0
F3F2
F1X
00 01 11 10
00
01
11
10
0 0 0 1
1 1 1 0
0 0 0 d
1 0 1 d
F3F2
F1X
00 01 11 10
00
01
11
10
1 0 0 1
1 1 1 0
d 0 0 1
d 0 0 0
F3F2
F1X
00 01 11 10
00
01
11
10
0 0 1 1
1 1 0 1
0 0 1 d
0 0 0 d
激励卡诺图F1
门：5与333331或5 4与23331或4 4与23331或4
线：20线 15线 15线比较：
蕴含图法比指导原则法效果好。其状态链中可出现指导原则没有出现的状态对，排列的优先次序也不同。
将出现次数多的状态分配0效果好。
注意到，对于D、JK、T触发器效果不同
……
状态分配（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
(
)
方案2是将方案1中的Y1求补所得，所以，可将方案1结果中Y1和D1求补得出。
方案3是将方案1中的Y1、Y2交换所得，所以，可将方案1中的Y1、Y2和D1、D2交换得出。
三种分配方案得到的激励函数复杂度相同，可认为是等效的。不存在相互等效的所有状态分配方案称为单一状态分配。单一状态分配方案数与状态数NU的关系为：
下表例示了一些状态数和状态分配方案数的关系。
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
虽然没有简单有效的方法得到最佳状态分配，但存在一些状态分配的指导原则，在状态分配中尽量遵循这些原则也能使我们得到相当好的结果。
状态分配指导原则激励卡诺图是由状态卡诺图决定的，不同的状态分配产生不同的激励卡诺图。为争取得到尽量简单的激励函数，状态分配方案应尽量使激励卡诺图中的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）形成群块，使其较少依赖于状态变量。
S
分配方案
1
Y1Y2
2
Y1Y2
3
Y1Y2
A
B
C
D
00
01
11
10
10
11
01
00
00
10
11
01
对于原则2，由于在相邻输入情况下，次态被相邻分配，意味着在此种情况下，大多触发器的改变相同（所需激励值也相同），且相对于输入变量，这些所需相同激励（值）在激励卡诺图中的位置也相邻，因此有利于激励卡诺图中的1（或0）形成群块，使其较少依赖于输入变量。
同理，原则3有利于输出函数卡诺图中的1（或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
应用三原则进行状态分配时，如有冲突，则原则1优先级最高，原则3优先级最低。
状态分配步骤：
根据三分配原则分别列出所需相邻分配的状态对；
合并步骤1中分配原则1、2的结果，并原则1、2和发生次数排队。
按步骤2的结果填写状态分配卡诺图。将0状态分配给状态转换表中起始态或出现最多的状态。
验证书页177例：
利用状态分配指导原则核验下例时序电路之状态分配。
现在状态
下一个状态
输出
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
存在840种单一分配方案。
由原则1得具有相同次态应尽量给予相邻分配的状态对为：
（S1S5）、（S2S8）、（S3S7）、（S4S6）。
由原则2得同态之次态应尽量给予相邻分配的状态对为：
（S1S6）、（S2S3）、（S4S5）、（S7S8）。
由原则3得具有相同输出同应尽量给予相邻分配的状态对为：
（S1S6）、（S1S7）、（S1S8）、（S6S7）、（S6S8）、（S7S8）、（S2S3）、（S2S4）（S2S5）、（S3S4）、（S3S5）、（S4S5）。
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、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
应用三状态分配原则得：
原则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
蕴含图法状态分配蕴含图是确定状态对相邻分配的另一工具。
蕴含图法是在分配指导原则的基础上更多的发掘和利用电路状态转移的规律，所以结果会更好。
蕴含图用流图形式描述时序电路中状态对在给定输入情况下相互转换之关系。状态对用节点表示，节点之间由转移线连接。
蕴含图例。
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
闭子图2 闭子图1
如一状态对相邻分配对简化激励函数有利，那么能相互转换的状态对群也应尽量相邻分配，以利在激励卡诺图中形成尽量大的1（或0）的群块。
蕴含图设法找出这样的群。
包含了所有可能状态对的蕴含图称为完全蕴含图。完全蕴含图的部分称为子图。
如子图中所有状态对的转移仍在同一子图内则称之为闭子图。转移线可进入闭子图，但决不从闭子图中发出。当连接状态对节点的转移线形成闭环时，则产生闭子图。
闭子图中的状态对构成状态对链。链中的状态对应相邻分配，以构成激励卡诺图中1的大团块。
用蕴图进行状态分配步骤应用状态分配三原则导出初始相邻分配对。
以原则1、2所得状态对开始，画出出蕴含图。蕴含图要包含所有的原则1、2导出的状态对。
找出蕴含图中存在的闭子图。列出闭子图的状态对链。
以大闭子图优先，闭子图中多次出现优先排列状态对。
尽量按所排状态对列相邻分配填状态分配卡诺图。
按蕴含图法对上例实施状态分配
1．步骤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）;(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得状态对列：
(X,Y)3(W,Z)(V,U)(T,Y)(U,W)(T,X)(U,Z)(V,W)2
闭子图2 闭子图1
填状态分配卡诺图。
F3F2
F1
00 01 11 10
0
1
T Y W Z
X U V
F3F2
F1
00 01 11 10
0
1
Y V W T
X U Z
F3F2
F1
00 01 11 10
0
1
Y W Z T
X U V
三种分配方案
（规则，Y＝0） （图，T＝0） （图，Y＝0）
S
F3F2F1
F3F2F1
F3F2F1
T
U
V
W
X
Y
Z
100
011
010
110
001
000
111
000
111
101
110
011
010
100
100
011
111
010
001
000
110
F3F2
F1X
00 01 11 10
00
01
11
10
111 110 010 011
101 111 011 010
ddd 110 010 011
ddd 100 000 010
F3F2
F1X
00 01 11 10
00
01
11
10
010 000 001 011
011 001 000 111
010 000 001 ddd
110 100 000 ddd
F3F2
F1X
00 01 11 10
00
01
11
10
110 000 000 011
011 001 001 010
110 000 000 ddd
111 100 001 ddd
三种方案状态表
F3F2
F1X
00 01 11 10
00
01
11
10
1 0 0 0
0 0 0 0
1 0 0 d
1 1 0 d
F3F2
F1X
00 01 11 10
00
01
11
10
1 1 0 0
1 1 0 0
d 1 0 0
d 1 0 0
F3F2
F1X
00 01 11 10
00
01
11
10
0 0 0 0
0 0 0 1
0 0 0 d
1 1 0 d
激励卡诺图F3
门：3与233、1或3 0 2与331或2
线：11线 0 8线
F3F2
F1X
00 01 11 10
00
01
11
10
1 0 0 1
1 0 0 1
1 0 0 d
1 0 0 d
F3F2
F1X
00 01 11 10
00
01
11
10
1 1 1 1
0 1 1 1
d 1 1 1
d 0 0 1
F3F2
F1X
00 01 11 10
00
01
11
10
1 0 0 1
1 0 0 1
1 0 0 d
1 0 0 d
激励卡诺图F2
门：0 3与2221或3 0
线：0 9线 0
F3F2
F1X
00 01 11 10
00
01
11
10
0 0 0 1
1 1 1 0
0 0 0 d
1 0 1 d
F3F2
F1X
00 01 11 10
00
01
11
10
1 0 0 1
1 1 1 0
d 0 0 1
d 0 0 0
F3F2
F1X
00 01 11 10
00
01
11
10
0 0 1 1
1 1 0 1
0 0 1 d
0 0 0 d
激励卡诺图F1
门：5与333331或5 4与23331或4 4与23331或4
线：20线 15线 15线比较：
蕴含图法比指导原则法效果好。其状态链中可出现指导原则没有出现的状态对，排列的优先次序也不同。
将出现次数多的状态分配0效果好。
注意到，对于D、JK、T触发器效果不同
