第四章 时序电路
Sequential Circuits
4.32 同步时序电路设计
…
状态化简（Reduction of State）(书页168－176)
在根据文字描述的设计要求建立原始状态图的过程中，由于状态设置的考虑与方法不同，可能得到多种形式的原始状态图。但只要过程正确，所得的各种形式原始状态图都是正确的，但状态图中的状态数和结构可能存在较大差别。
例：推导一时序电路原始状态图。其功能是对一随机串行输入序列进行检测，当对电路连续输入三个和三个以上的1时，输出Z为1，其它情况输出Z均为0。
解1：为对连续输入的三个二进值进行检测，对可能出现的八种情况设置状态进行记忆。
SA：000，SB：001，SC：010，SD：011，SE：100，SF：101，SG：110，SH：111。
分别以每种情况为现态，求出输入X为0和1时的次态及输出值，可得所有状态的转移连接。从而得如下状态图表。
解1的原始状态图现态
次态NS
输出Z
x=0
x=1
x=0
x=1
SA:000
SA
SB
0
0
SB:001
SC
SD
0
0
SC:010
SE
SF
0
0
SD:011
SG
SH
0
1
SE:100
SC
SB
0
0
SF:101
SC
SD
0
0
SG:110
SE
SF
0
0
SH:111
SG
SH
0
1
解1原始状态表
解2：直接设置状态记忆连续输入1 的个数：S0：输入一个0和连续输入0；
S1：输入一个1；
S2：连续输入二个和二个以上1。
如上设置电路状态，无论电路处于何态，对于任何输入，其次态均为三种状态之一。当处于S2态时，可检测连续输入三个和三个以上1的情况。连接三种状态之间的转移连接，可得状态设置方案2的原始状态图表如下。
解2 原始状态图
现态
次态
输出
x=0
x=1
x=0
x=1
S0
S0
S1
0
0
S1
S0
S2
0
0
S2
S0
S2
0
1
解2的原始状态表
从例看到，实现同样逻辑功能，解1用八个状态，解2用3个状态。状态数多则电路实现复杂，成本高，应尽量减少状态数。
同一时序逻辑，不同状态设置方案所得原始状态图中状态数之所以不同是因为状态数目较多的设计结果中存在着多余状态。
如消除多余态，则可得相同的设计结果。
无法确保通过合适的状态设置直接得到最少状态数的原始状态图，但有某些规范方法将原始状态图中的多余状态消除。将原始状态图中多余状态消除的过程之为状态化简。
随着集成电路密度的提高和可编程器件的发展，对时序电路状态化简的考虑有所变化。出于设计中的特殊考虑，不一定将电路状态化至最简。但电路尽量简化的原则还是应该遵循的。
状态化简工作可由计算机完成。
所谓多余状态就是状态图中存在着可被另一状态所代替的状态。
可以相互代替的状态称之为状态等价。
如能找出原始状态图中所有相互等价态，则可只留不相互等价态，得到最简状态图。
状态等价如果将同一时序电路的两个状态Si和Sj分别作为起始态，不论加入任何可能的输入序列，电路均产生相同的输出序列，我们称Si和Sj是等价状态或等价对，记作Si～Sj。
等价具有传递性。即如有Si～Sj，Sj～SK，则有Si～SK。
等价类：多个相互等价状态之集合。如上述SiSjSk构成一等价类。
最大等价类：在同一时序电路中，包含所有相互等价的状态的等价类。不与其它任何状态等价的单个状态也看成一个最大等价类。
等价的时序电路：满足等价条件的两个状态分别在两个时序电路M1和M2中，两个状态也为等价态。两个时序电路M1M2，它们各自的每个状态都能在对方电路中至少找到一个等价态，则称M1M2 是等价的时序电路，否则，是可区分的时序电路。
等价态是可以互相替代或合并：因从输入和输出的角度看，等价态的表现相同，无法区分。
状态化简：找出时序电路原始状态图中所有的最大等价类，并从每个最大等价类选一状态作为代表留用，消除其余态，得到最小化的状态图和表。
完全确定的时序电路：原始状态图表中，对应输入和现态的所有组合都有唯一确定的次态和输出。它具有完全描述的状态表。包含有不确定输出或次态的状态表为不完全描述的状态表，对应的时序电路为不完全确定时序电路。
化简原则：最小闭覆盖。
最小性。简化后的状态数最少。
2．完备或覆盖性。原始状态表中的每个状态都属于简化后状态中的一个。
封闭性。对简化后的最小化状态表中的每个状态而言，在任何一种输入情况下，其次态只能是简化后状态中的一个（而不是多个）。对完全确定的时序电路，封闭性是自动满足的。而对不完全确定的时序电路，不合理的选择简化后的状态，将导致不满足封闭性。
完全确定的时序电路状态化简：
方法1：蕴含图法。
方法2：分隔法。
蕴含图法化简：
原理与步骤：
1．原始状态集中寻找所有的状态等价对；
2．组合出最大等价类集；
3．状态合并，构成最简状态集；
4．由最简状态集导出最小化状态图和表。
关键步骤是从原始状态集中寻找所有的等价对：1.状态组对，2.等价判定。
组对易，判定难，利用推论。
判定等价就是考察在任一相同输入作用下判定作为起始的两态及产生对应次态序列的输出的是否相同，相同则等价，否则不等价。由此可得判定两态等价的推论1和2。
推论1：在任一相同输入条件下，两态的输出不同，两态一定不等价；两态输出相同，则需继续判定对应次态是否等价。
推论2：在任一相同输入条件下，两态的输出相同，若对应次态等价，则两态等价；对应次态不等价，两态也不等价。
次态输出相同，需再考察次态对情况。如设需等价判定的两态为SiSj，次态对的情况可分两类：1.不变（即仍为SiSj），交错（即为SjSi），相同（即同为Sk）2.不属1的其它情况(即为SmSn)。
当次态属1类情况时，无论谁作起始态，任一相同输入产生相同输出。
当次态属2 类情况时，状态SiSj等价否取决与SmSn，我们称之为状态隐含。状态隐含需对次态继续进行追踪判定。如次态符合输入同，输出同的同时，出现次态的次态又为原态，称之为互为隐含。当互为隐含时，在任一相同输入作用下，次态序列的输出也相同。
综上所述，可得推论3。
推论3,在任一相同输入条件下，两态的输出相同，且对应次态为不变、交错、相同和互为隐含四种情况之一时，则两态等价。
根据推论1、2、3，可对状态对进行直观地等价判定。
观察法等价对判定：适于比较简单的原始状态图表化简。
例：观察法简化三位一判101检测器。观察可得，状态S3、S4和S5在同样输入输出相同，且次态相同，因此相互等价，可合并为一个状态，用状态S3代表。得最小化的状态图。
例：观察法化简不重码101检测器原始状态图。 S0和S3输出同态，相互等价，合并为一状态S0，得简化状态图。
蕴含表法等价对判定：适于比较复杂的原始状态图表，可防止遗漏，条理清晰。
蕴含表格式：
设全部原始状态按序排列为S0…SN。 1.建立网格，“掐头”“去尾”标注。
逐格进行初始判定并填写结果。（等价，不等价，隐含。）
对隐含进行追踪判定，直至判定结果确定为等价或不等价。
完成追踪判定后，隐含表中所有非打“×”方格对应的状态对即是我们要找的全部等价对。
例：对连续3个1检测解1的原始状态图表表格法状态化简。
解1原始状态表现态
次态NS
输出Z
x=0
x=1
x=0
x=1
SA:000
SA
SB
0
0
SB:001
SC
SD
0
0
SC:010
SE
SF
0
0
SD:011
SG
SH
0
1
SE:100
SC
SB
0
0
SF:101
SC
SD
0
0
SG:110
SE
SF
0
0
SH:111
SG
SH
0
1
1.初始判定。（先审输出，再看次态）
2．追踪判定。如方格中有两项隐含状态对时，只要其中一项被判定不等价，则本方格对应状态为不等价，不必再对另项进行追踪判定。
列出所有等价状态对。
SASC，SASE，SASG，SBSF，SCSE，SCSG，SDSH，SESG。
导出最大等价类集。注意不要忘记检查完备性，即所有原始状态都必须出现在最大等价类集中。所得最大等价类集为：
SASCSESG，SBSF，SDSH。
合并状态，得最简状态集。
用S0、S1、S2顺序分别代表4中所得三个最大等价类。
列最小化状态表，画最小化状态图。
现态
次态
输出
x=0
x=1
x=0
x=1
S0
S0
S1
0
0
S1
S0
S2
0
0
S2
S0
S2
0
1
最小化状态表
最小化状态图
可以发现，与例解2的原始状态图与表完全相同。这说明，我们没有把握直接从设计要求导出最小化的状态图表，但可通过状态化简得之。
例：化简下示原始状态表。
现态S(tj)
次态S(tj+1)
输出z(tj)
x=0
x=1
x=0
x=1
S1
S7
S1
0
0
S2
S7
S1
0
0
S3
S1
S5
0
1
S4
S2
S6
0
1
S5
S7
S3
0
1
S6
S7
S2
0
1
S7
S1
S7
0
0
1.全部等价状态对为：
S1S2,S1S7,S2S7,S3S5。
2.最大等价类集为：
S1S2S7，S3S5，S4，S6。
注意千万不要忘记，没有等价对的S4、S5状态也应添加进来以保证完备性。
最简状态集。
S1、S3、S4、S6。
4．最小化状态表。
现态S(tj)
次态S(tj+1)
输出z(tj)
x=0
x=1
x=0
x=1
S1
S1
S1
0
0
S3
S1
S3
0
1
S4
S1
S6
0
1
S6
S1
S1
0
1
分割法化简：
蕴含表法是在原始状态集中寻找等价类集，与之对比，分割法是逐步从原始状态集分离不等价类，最后得到最大等价类集。
原理：定义原始状态集为P0，对其按分割原则进行分块。第一次分割结果为P1，第K次分割结果为Pk。当PK＋1＝PK时，分割完毕，结果为最大等价类集。
分割方法与步骤：
1．审查原始状态集中在所有各种输入情况下的输出，根据输出对原始状态集进行分块，将只把输出相同的状态放入同块，得P1。
（不同块的状态因输出不同肯定不等价。）
2．对PK中得每块中的状态在所有各种输入情况下的次态审查，根据次态情况再分块，把次态在PK中同块的状态放入同块，得PK＋1。
（次态不在同块中肯定不等价）
PK＋1＝PK，分割完毕，得最大等价类。
（各块中得状态无论输入何种序列输出均相同）
分割完毕，合并状态，得最简状态集。
例1：分割法化简。
(ABCDE)
11100
00011
分（ABC）（DE）
(ABC) (DE)
CCB DE
BEE BA
分（A）（BC）
(BC) (DE)
C CB DE
B EE BA
分（D）（E）
(BC) (D) (E)
C CB D E
B EE B A
(A) (BC) (D) (E)
P0
X=0
PS
NS/Z
X=0
X=1
A
C/1
B/0
B
C/1
E/0
C
B/1
E/0
D
D/0
B/1
E
E/0
A/1
X=1
P1
X=0
X=1
P2
X=0
X=1
P3
X=0
X=1
P4=P3
例2：分割法化简
PS
X1 X2
00
01
11
10
A
D/0
D/0
F/0
A/0
B
C/1
D/0
E/1
F/0
C
C/1
D/0
E/1
A/0
D
D/0
B/0
A/O
F/0
E
C/1
F/0
E/1
A/0
F
D/0
D/0
A/0
F/0
G
G/0
G/0
A/0
A/0
H
B/1
D/0
E/1
A/0
P1=（ADFG）(BCEH)
P2=（AFG）(D)(BCEH)
P3=(AF)(G)(D)(BCH)(E)
P4＝P3
令：a=（AF）,b=(BCH),c=(D),d=(E),e=(G).
PS
X1 X2
00
01
11
10
a
c/0
c/0
a/0
a/0
b
b/1
c/0
d/1
a/0
c
c/0
b/0
a/0
a/0
d
b/1
a/0
d/1
a/0
e
e/0
e/0
a/0
a/0
现态
次态NS
输出Z
x=0
x=1
x=0
x=1
SA:000
SA
SB
0
0
SB:001
SC
SD
0
0
SC:010
SE
SF
0
0
SD:011
SG
SH
0
1
SE:100
SC
SB
0
0
SF:101
SC
SD
0
0
SG:110
SE
SF
0
0
SH:111
SG
SH
0
1
例3：分割法化简解1。
P1＝（ABCEFG）（DH）
P2＝（ACEG）（BF）（DH）
P3＝P2
Sequential Circuits
4.32 同步时序电路设计
…
状态化简（Reduction of State）(书页168－176)
在根据文字描述的设计要求建立原始状态图的过程中，由于状态设置的考虑与方法不同，可能得到多种形式的原始状态图。但只要过程正确，所得的各种形式原始状态图都是正确的，但状态图中的状态数和结构可能存在较大差别。
例：推导一时序电路原始状态图。其功能是对一随机串行输入序列进行检测，当对电路连续输入三个和三个以上的1时，输出Z为1，其它情况输出Z均为0。
解1：为对连续输入的三个二进值进行检测，对可能出现的八种情况设置状态进行记忆。
SA：000，SB：001，SC：010，SD：011，SE：100，SF：101，SG：110，SH：111。
分别以每种情况为现态，求出输入X为0和1时的次态及输出值，可得所有状态的转移连接。从而得如下状态图表。
解1的原始状态图现态
次态NS
输出Z
x=0
x=1
x=0
x=1
SA:000
SA
SB
0
0
SB:001
SC
SD
0
0
SC:010
SE
SF
0
0
SD:011
SG
SH
0
1
SE:100
SC
SB
0
0
SF:101
SC
SD
0
0
SG:110
SE
SF
0
0
SH:111
SG
SH
0
1
解1原始状态表
解2：直接设置状态记忆连续输入1 的个数：S0：输入一个0和连续输入0；
S1：输入一个1；
S2：连续输入二个和二个以上1。
如上设置电路状态，无论电路处于何态，对于任何输入，其次态均为三种状态之一。当处于S2态时，可检测连续输入三个和三个以上1的情况。连接三种状态之间的转移连接，可得状态设置方案2的原始状态图表如下。
解2 原始状态图
现态
次态
输出
x=0
x=1
x=0
x=1
S0
S0
S1
0
0
S1
S0
S2
0
0
S2
S0
S2
0
1
解2的原始状态表
从例看到，实现同样逻辑功能，解1用八个状态，解2用3个状态。状态数多则电路实现复杂，成本高，应尽量减少状态数。
同一时序逻辑，不同状态设置方案所得原始状态图中状态数之所以不同是因为状态数目较多的设计结果中存在着多余状态。
如消除多余态，则可得相同的设计结果。
无法确保通过合适的状态设置直接得到最少状态数的原始状态图，但有某些规范方法将原始状态图中的多余状态消除。将原始状态图中多余状态消除的过程之为状态化简。
随着集成电路密度的提高和可编程器件的发展，对时序电路状态化简的考虑有所变化。出于设计中的特殊考虑，不一定将电路状态化至最简。但电路尽量简化的原则还是应该遵循的。
状态化简工作可由计算机完成。
所谓多余状态就是状态图中存在着可被另一状态所代替的状态。
可以相互代替的状态称之为状态等价。
如能找出原始状态图中所有相互等价态，则可只留不相互等价态，得到最简状态图。
状态等价如果将同一时序电路的两个状态Si和Sj分别作为起始态，不论加入任何可能的输入序列，电路均产生相同的输出序列，我们称Si和Sj是等价状态或等价对，记作Si～Sj。
等价具有传递性。即如有Si～Sj，Sj～SK，则有Si～SK。
等价类：多个相互等价状态之集合。如上述SiSjSk构成一等价类。
最大等价类：在同一时序电路中，包含所有相互等价的状态的等价类。不与其它任何状态等价的单个状态也看成一个最大等价类。
等价的时序电路：满足等价条件的两个状态分别在两个时序电路M1和M2中，两个状态也为等价态。两个时序电路M1M2，它们各自的每个状态都能在对方电路中至少找到一个等价态，则称M1M2 是等价的时序电路，否则，是可区分的时序电路。
等价态是可以互相替代或合并：因从输入和输出的角度看，等价态的表现相同，无法区分。
状态化简：找出时序电路原始状态图中所有的最大等价类，并从每个最大等价类选一状态作为代表留用，消除其余态，得到最小化的状态图和表。
完全确定的时序电路：原始状态图表中，对应输入和现态的所有组合都有唯一确定的次态和输出。它具有完全描述的状态表。包含有不确定输出或次态的状态表为不完全描述的状态表，对应的时序电路为不完全确定时序电路。
化简原则：最小闭覆盖。
最小性。简化后的状态数最少。
2．完备或覆盖性。原始状态表中的每个状态都属于简化后状态中的一个。
封闭性。对简化后的最小化状态表中的每个状态而言，在任何一种输入情况下，其次态只能是简化后状态中的一个（而不是多个）。对完全确定的时序电路，封闭性是自动满足的。而对不完全确定的时序电路，不合理的选择简化后的状态，将导致不满足封闭性。
完全确定的时序电路状态化简：
方法1：蕴含图法。
方法2：分隔法。
蕴含图法化简：
原理与步骤：
1．原始状态集中寻找所有的状态等价对；
2．组合出最大等价类集；
3．状态合并，构成最简状态集；
4．由最简状态集导出最小化状态图和表。
关键步骤是从原始状态集中寻找所有的等价对：1.状态组对，2.等价判定。
组对易，判定难，利用推论。
判定等价就是考察在任一相同输入作用下判定作为起始的两态及产生对应次态序列的输出的是否相同，相同则等价，否则不等价。由此可得判定两态等价的推论1和2。
推论1：在任一相同输入条件下，两态的输出不同，两态一定不等价；两态输出相同，则需继续判定对应次态是否等价。
推论2：在任一相同输入条件下，两态的输出相同，若对应次态等价，则两态等价；对应次态不等价，两态也不等价。
次态输出相同，需再考察次态对情况。如设需等价判定的两态为SiSj，次态对的情况可分两类：1.不变（即仍为SiSj），交错（即为SjSi），相同（即同为Sk）2.不属1的其它情况(即为SmSn)。
当次态属1类情况时，无论谁作起始态，任一相同输入产生相同输出。
当次态属2 类情况时，状态SiSj等价否取决与SmSn，我们称之为状态隐含。状态隐含需对次态继续进行追踪判定。如次态符合输入同，输出同的同时，出现次态的次态又为原态，称之为互为隐含。当互为隐含时，在任一相同输入作用下，次态序列的输出也相同。
综上所述，可得推论3。
推论3,在任一相同输入条件下，两态的输出相同，且对应次态为不变、交错、相同和互为隐含四种情况之一时，则两态等价。
根据推论1、2、3，可对状态对进行直观地等价判定。
观察法等价对判定：适于比较简单的原始状态图表化简。
例：观察法简化三位一判101检测器。观察可得，状态S3、S4和S5在同样输入输出相同，且次态相同，因此相互等价，可合并为一个状态，用状态S3代表。得最小化的状态图。
例：观察法化简不重码101检测器原始状态图。 S0和S3输出同态，相互等价，合并为一状态S0，得简化状态图。
蕴含表法等价对判定：适于比较复杂的原始状态图表，可防止遗漏，条理清晰。
蕴含表格式：
设全部原始状态按序排列为S0…SN。 1.建立网格，“掐头”“去尾”标注。
逐格进行初始判定并填写结果。（等价，不等价，隐含。）
对隐含进行追踪判定，直至判定结果确定为等价或不等价。
完成追踪判定后，隐含表中所有非打“×”方格对应的状态对即是我们要找的全部等价对。
例：对连续3个1检测解1的原始状态图表表格法状态化简。
解1原始状态表现态
次态NS
输出Z
x=0
x=1
x=0
x=1
SA:000
SA
SB
0
0
SB:001
SC
SD
0
0
SC:010
SE
SF
0
0
SD:011
SG
SH
0
1
SE:100
SC
SB
0
0
SF:101
SC
SD
0
0
SG:110
SE
SF
0
0
SH:111
SG
SH
0
1
1.初始判定。（先审输出，再看次态）
2．追踪判定。如方格中有两项隐含状态对时，只要其中一项被判定不等价，则本方格对应状态为不等价，不必再对另项进行追踪判定。
列出所有等价状态对。
SASC，SASE，SASG，SBSF，SCSE，SCSG，SDSH，SESG。
导出最大等价类集。注意不要忘记检查完备性，即所有原始状态都必须出现在最大等价类集中。所得最大等价类集为：
SASCSESG，SBSF，SDSH。
合并状态，得最简状态集。
用S0、S1、S2顺序分别代表4中所得三个最大等价类。
列最小化状态表，画最小化状态图。
现态
次态
输出
x=0
x=1
x=0
x=1
S0
S0
S1
0
0
S1
S0
S2
0
0
S2
S0
S2
0
1
最小化状态表
最小化状态图
可以发现，与例解2的原始状态图与表完全相同。这说明，我们没有把握直接从设计要求导出最小化的状态图表，但可通过状态化简得之。
例：化简下示原始状态表。
现态S(tj)
次态S(tj+1)
输出z(tj)
x=0
x=1
x=0
x=1
S1
S7
S1
0
0
S2
S7
S1
0
0
S3
S1
S5
0
1
S4
S2
S6
0
1
S5
S7
S3
0
1
S6
S7
S2
0
1
S7
S1
S7
0
0
1.全部等价状态对为：
S1S2,S1S7,S2S7,S3S5。
2.最大等价类集为：
S1S2S7，S3S5，S4，S6。
注意千万不要忘记，没有等价对的S4、S5状态也应添加进来以保证完备性。
最简状态集。
S1、S3、S4、S6。
4．最小化状态表。
现态S(tj)
次态S(tj+1)
输出z(tj)
x=0
x=1
x=0
x=1
S1
S1
S1
0
0
S3
S1
S3
0
1
S4
S1
S6
0
1
S6
S1
S1
0
1
分割法化简：
蕴含表法是在原始状态集中寻找等价类集，与之对比，分割法是逐步从原始状态集分离不等价类，最后得到最大等价类集。
原理：定义原始状态集为P0，对其按分割原则进行分块。第一次分割结果为P1，第K次分割结果为Pk。当PK＋1＝PK时，分割完毕，结果为最大等价类集。
分割方法与步骤：
1．审查原始状态集中在所有各种输入情况下的输出，根据输出对原始状态集进行分块，将只把输出相同的状态放入同块，得P1。
（不同块的状态因输出不同肯定不等价。）
2．对PK中得每块中的状态在所有各种输入情况下的次态审查，根据次态情况再分块，把次态在PK中同块的状态放入同块，得PK＋1。
（次态不在同块中肯定不等价）
PK＋1＝PK，分割完毕，得最大等价类。
（各块中得状态无论输入何种序列输出均相同）
分割完毕，合并状态，得最简状态集。
例1：分割法化简。
(ABCDE)
11100
00011
分（ABC）（DE）
(ABC) (DE)
CCB DE
BEE BA
分（A）（BC）
(BC) (DE)
C CB DE
B EE BA
分（D）（E）
(BC) (D) (E)
C CB D E
B EE B A
(A) (BC) (D) (E)
P0
X=0
PS
NS/Z
X=0
X=1
A
C/1
B/0
B
C/1
E/0
C
B/1
E/0
D
D/0
B/1
E
E/0
A/1
X=1
P1
X=0
X=1
P2
X=0
X=1
P3
X=0
X=1
P4=P3
例2：分割法化简
PS
X1 X2
00
01
11
10
A
D/0
D/0
F/0
A/0
B
C/1
D/0
E/1
F/0
C
C/1
D/0
E/1
A/0
D
D/0
B/0
A/O
F/0
E
C/1
F/0
E/1
A/0
F
D/0
D/0
A/0
F/0
G
G/0
G/0
A/0
A/0
H
B/1
D/0
E/1
A/0
P1=（ADFG）(BCEH)
P2=（AFG）(D)(BCEH)
P3=(AF)(G)(D)(BCH)(E)
P4＝P3
令：a=（AF）,b=(BCH),c=(D),d=(E),e=(G).
PS
X1 X2
00
01
11
10
a
c/0
c/0
a/0
a/0
b
b/1
c/0
d/1
a/0
c
c/0
b/0
a/0
a/0
d
b/1
a/0
d/1
a/0
e
e/0
e/0
a/0
a/0
现态
次态NS
输出Z
x=0
x=1
x=0
x=1
SA:000
SA
SB
0
0
SB:001
SC
SD
0
0
SC:010
SE
SF
0
0
SD:011
SG
SH
0
1
SE:100
SC
SB
0
0
SF:101
SC
SD
0
0
SG:110
SE
SF
0
0
SH:111
SG
SH
0
1
例3：分割法化简解1。
P1＝（ABCEFG）（DH）
P2＝（ACEG）（BF）（DH）
P3＝P2
