2010-5-21 作者：清华大学电子工程系 罗嵘 第 229页
习题 6 9-3,9-5,9-10
习题 7 9-11,9-14
2010-5-21 作者：清华大学电子工程系 罗嵘 第 230页
设计要求
触发器的激励函数
最小化状态表 触发器选型
原始状态图原始状态表
输出函数
代码形式的状态表
时序电路逻辑图
状态化简
状态分配
自启动检查
4.3.1同步时序逻辑电路的设计
1.设计步骤
2010-5-21 作者：清华大学电子工程系 罗嵘 第 231页
2.原始状态表和图的构成
分析清楚时序电路的输入条件和输出条件, 确定有多少种
输入信息的历史情况, 由相应的电路状态记忆, 从而确定
原始状态图的状态数
把每一个状态作为电路当时所处的现在状态, 根据设计要
求和各种可能的输入情况, 确定该时刻的现在的输出和下
一时刻电路的下一个状态, 画出状态转换线, 注明输入和
输出, 完成原始状态图 。 可多设几个状态, 不要发生遗漏
和错误 。
根据原始状态图列出原始状态表
2010-5-21 作者：清华大学电子工程系 罗嵘 第 232页
例 1设计判断输入序列为 101的检测器 。 输入为 x,输出为 z。
画出下述三种要求下的原始状态图 （ 表 ）
(1)对输入序列每三位进行一次判决：若三位代码是 101,则
对应其最后一个 1时, 输出 z为 1；其它情况 z为 0
x 010 100 101 010
z 000 000 001 000
设 S0,初始状态, 每次判定由此状态开始,
S1,收到一个 0，
S2,收到一个 1，
S3,收到两个 0,S4,收到 01,S5,收到 10,S6,收到 11
2010-5-21 作者：清华大学电子工程系 罗嵘 第 233页
0/0
S0
S1 S2
S3 S4 S5 S6
1/00/0
1/00/0 1/0 0/0
1/0 1/00/0 0/0 1/10/01/0
表 4,1 7 （ 1 ）解的原始状态表
下一个状态 输出 z 现在
状态 x= 0 x= 1 x= 0 x= 1
S
0
S
1
S
2
0 0
S
1
S
3
S
4
0 0
S
2
S
5
S
6
0 0
S
3
S
0
S
0
0 0
S
4
S
0
S
0
0 0
S
5
S
0
S
0
0 1
S
6
S
0
S
0
0 0
2010-5-21 作者：清华大学电子工程系 罗嵘 第 234页
(2)每逢遇到输入序列为 101,输出 z为 1。 但是相邻的 101代码
不可重叠 （ 即输入的代码不可重复使用 ）
x 010 100 101 010
z 000 100 001 000
设 S0,连续收到的输入为 0,S1,收到一个 1,S2,收到 10,S3：
收到 101
表 4, 18 （ 2 ）解的原始状态表
下一个状态 输出 z 现在状态
x= 0 x= 1 x= 0 x= 1
S 0 S 1 S 1 0 0
S 1 S 2 S 1 0 0
S 2 S 0 S 3 0 1
S 3 S 0 S 1 0 0
S0 S1 S2 S3
1/0
0/0
1/00/0
1/0
0/0
1/10/0
2010-5-21 作者：清华大学电子工程系 罗嵘 第 235页
(3)每逢遇到输入序列为 101,输出 z为 1,而且相邻的 101代码
可重叠 （ 即前一个 101的最后一个 1,可以作为下一 个 101的
头一个 1使用 ）
x 010 100 101 010
z 000 100 001 010
设 S0,连续收到的输入为 0,S1,收到一个 1,S2,收到 10
S0 S1 S2
1/0
0/0
0/0
1/0
1/1
0/0
表 4, 19 （ 3 ）解的原始状态表
下一个状态 输出 z 现在状态
x= 0 x= 1 x= 0 x= 1
S 0 S 0 S 1 0 0
S 1 S 2 S 1 0 0
S 2 S 0 S 1 0 1
2010-5-21 作者：清华大学电子工程系 罗嵘 第 236页
例 2一个时序电路有两个输入 x1,x2和两个输出 z1，
z2。 规定在同一时刻, x1和 x2不能同时为 1。 当 x1为 1
时, 若 x2端已输入了两个或两个以上 1（ 这些 1不一
定是连续输入的 ）, 则输出 z1为 1,z2为 0；若 x2端没
有输入过两个或两个以上 1,则输出 z1为 0,z2为 1；
当 x1为 0时, 不论 x2为何值, 输出 z1,z2都为 0。 此外,
每当 x1为 1时, 电路回到起始状态, 又重新开始上述
过程, 试画出电路的原始状态图 （ 表 ）
设 SA,起始状态, x2端尚未输入过 1,SB,x2端输入
了一个 1,SC,x2端输入过两个或两个以上的 1
2010-5-21 作者：清华大学电子工程系 罗嵘 第 237页
表 4, 20 状态表
输出 下一个状态
z 1 z 2
现在
状态
x 1 x 2
= 00
x 1 x 2
= 01
x 1 x 2
= 1 1
x 1 x 2
= 10
x 1 x 2
= 00
x 1 x 2
= 01
x 1 x 2
= 1 1
x 1 x 2
= 10
x 1 x 2 =
00
x 1 x 2 =
01
x 1 x 2 =
11
x 1 x 2 =
10
S A S A S B ? S A 0 0 ? 0 0 0 ? 1
S B S B S C ? S A 0 0 ? 0 0 0 ? 1
S C S C S C ? S A 0 0 ? 1 0 0 ? 0
SA SB
SC
x1x2/z1z2
10/01
00/00
01/00
00/00
01/00
10/01
00/00 01/00
10/10
2010-5-21 作者：清华大学电子工程系 罗嵘 第 238页
3.状态化简
完全确定的时序电路,对于输入变量取值的所有组合都唯
一地确定了该时刻的输出和下一个状态的时序电路 。 它具
有完全描述的状态表, 如例 1中的三张表
不完全确定的时序电路,状态表中包含不确定的输出或不
确定的下一个状态, 则称为不完全描述的状态表, 对应的
时序电路为不完全确定的时序电路, 如例 2
?
状态的等价,若 Si和 Sj分别为时序电路 M1和 M2（ 二者可为
同一个电路 ） 的两个状态 。 作为初始状态时, 不论加入何
种形式的相同的输入序列, 电路均给出相同的输出序列,
则称 Si和 Sj是等价状态或等价对, 记作 Si Sj ； 否则, Si
和 Sj是不等价的或可区分的状态 。
2010-5-21 作者：清华大学电子工程系 罗嵘 第 239页
两个时序电路的两个等价状态, 加入任何输入序列所得到的
输出序列总是相等的, 从输入, 输出角度看, 两个等价状态
是无法区分的, 故可以合并 。
等价的时序电路,两个 时序电路 M1和 M2,当且仅当 M1的每
一个状态能在 M2中至少找到一个等价的状态, 并且 M2的每
一个状态也都能在 M1中至少找到一个等价的状态, 则 M1和
M2是等价的时序逻辑电路 。
完全确定的时序电路的状态化简,
找出最大等价类 （ 包含所有彼此等价的状态的等价类 ）
kikjji SSSSSS ??? 则,,
等价状态具有传递性
2010-5-21 作者：清华大学电子工程系 罗嵘 第 240页
0/0
S0
S1 S2
S3 S4 S5 S6
1/00/0
1/00/0 1/0 0/0
1/0 1/00/0 0/0 1/10/01/0
S3,S4,S6,最大等价类
0/0
S0
S1 S2
S3 S5
1/00/0
1/00/0 1/0 0/0
1/0 0/0 1/1
2010-5-21 作者：清华大学电子工程系 罗嵘 第 241页
用蕴含表法进行状态化简
蕴含表是一个正直角三角形的网格, 两个直角边的网格数相同, 都等
于原始状态表的状态数减 1,使任何两个状态都能在一个网格中相遇
一次 。
1)对于两个状态, 若同样的输入下输出不等, 则不等价, 在相应网格
中填入 ‘ ?× ?；
2)若同样的输入下输出相等, 且下一个状态也相同, 则等价, 在相应
网格中填入 ‘ ???；
3)若 对于两个状态 Si和 Sk,若同样的输入下输出相等, 而且下一个时
刻的状态是相互交错的 （ 即 Si?Sk,Sk ? Si） 或是各自该时刻的状态
（ 即 Si?Si,Sk ? Sk）, 则此两个状态等价, 在相应网格中填入 ‘ ???；
4)若 对于两个状态, 在同样的输入下输出相等, 但下一个时刻的状态
既不是上述 2的情况, 也不是上述 3的情况, 则将不同的下一个状态标
在蕴含表的相应格中, 以待进一步比较 ；相同或交错的下一个状态不
必标出
2010-5-21 作者：清华大学电子工程系 罗嵘 第 242页
表 4, 21 例 3 原始状态表
下一个状态 S(t j+1 ) 输出 z (t j ) 现在状态
S(t j ) x= 0 x= 1 x= 0 x= 1
S 1 S 7 S 1 0 0
S 2 S 7 S 1 0 0
S 3 S 1 S 5 0 1
S 4 S 2 S 6 0 1
S 5 S 7 S 3 0 1
S 6 S 7 S 2 0 1
S 7 S 1 S 7 0 0
S2
S3
S4
S5
S6
S7
S2S1 S3 S5S4 S6
×
?
×
×
× × ×
×
×
×
?
1,7
× ×
×
1,2
5,6
1,7
1,7
5,2
7,2
3,6
7,2
2,6 3,2
1,7
5,3 7,7
3,2
关联比较
检查 × 格, 若 × 格的坐标为 Si,Sk,则表中填有 （ Si,Sk ） 的格对
应的状态对也肯定不等价, 应改为 × ；继续寻找所有不等价的状
态 。 如 S2和 S3不等价, 则 S5和 S6不等价
检查 ?格, 若 ?格的坐标为 Si,Sk,则表中填有 （ Si,Sk ） 的格对应
的状态对便有等价的可能, 若两个状态的输出相等, 而且下一个
状态也都是等价的, 则这两个状态等价, 应改为 ? 。 如 S1和 S7等价,
标有 （ 1,7） 的格的对应状态对 S2和 S7,S3和 S5等价
2010-5-21 作者：清华大学电子工程系 罗嵘 第 243页
S2
S3
S4
S5
S6
S7
S2S1 S3 S5S4 S6
×
?
×
×
× × ×
×
×
×
?
1,7
× ×
×
1,7
×
×
××
×
S2
S3
S4
S5
S6
S7
S2S1 S3 S5S4 S6
×
?
×
×
× × ×
×
×
×
?
× ×
×
×
×
××
×
?
?
最大等价类,（ S1,S2, S7 ）, （ S3, S5 ）, （ S4 ）, （ S6）
从每个最大等价类中选一个状态为代表, 列出包含状态数目最少的
最小化状态表
表 4, 22 例 3 最小化状态表
下一个状态 S (t j+1 ) 输出 z (t j ) 现在状态
S (t j ) x= 0 x= 1 x= 0 x= 1
S 1 S 1 S 1 0 0
S 3 S 1 S 3 0 1
S 4 S 1 S 6 0 1
S 6 S 1 S 1 0 1
2010-5-21 作者：清华大学电子工程系 罗嵘 第 244页
表 4, 2 3 例 4 原始状态表
下一个状态 S(t j+ 1 ) 输出 z (t j ) 现在状态
S(t j ) x= 0 x= 1 x= 0 x= 1
S 1 S 5 S 3 0 0
S 2 S 5 S 4 0 0
S 3 S 6 S 1 1 1
S 4 S 6 S 2 1 1
S 5 S 3 S 1 0 1
S 6 S 4 S 2 0 1
S2
S3
S4
S5
S6
S2S1 S3 S5S4
×
×
×
×
×
×
3,4
× ×
1,2
××
××
3,4
1,2
S2
S3
S4
S5
S6
S2S1 S3 S5S4
×
×
×
×
×
×
× ×
?
××
××
?
?
关联比较
S1和 S2是否等价取决于 S3和 S4是否等价,
而 S3和 S4是否等价取决于 S1和 S2是否等价,
这种情况下, S1和 S2,S3和 S4等价 。 因为
以 S1或 S2作为初始状态, 不论加入什么输
入序列, 均能给出相同的输出序列, 对
S3和 S4是一样的 。
2010-5-21 作者：清华大学电子工程系 罗嵘 第 245页
最大等价类,（ S1,S2 ）, （ S3, S4）, （ S5,S6）
从每个最大等价类中选一个状态为代表, 列出包含状态
数目最少的最小化状态表
表 4, 24 例 4 最小化状态表
下一个状态 S (t j+1 ) 输出 z (t j ) 现在状态
S (t j ) x= 0 x= 1 x= 0 x= 1
S 1 S 5 S 3 0 0
S 3 S 5 S 1 1 1
S 5 S 3 S 1 0 1
2010-5-21 作者：清华大学电子工程系 罗嵘 第 246页
4.状态分配
把状态表中每个字符表示的状态对应地规定一个二元代码,
得出代码形式状态表, 以便设计出时序逻辑电路的逻辑图 。
分配合适, 可简化电路的复杂度
例 7 用 D触发器设计如下表的时序电路
表 4, 29 状态表
下一个状态 输出 现在状态
x= 0 x= 1 x= 0 x= 1
S 1 S 3 S 2 1 1
S 2 S 7 S 8 0 0
S 3 S 6 S 1 0 0
S 4 S 4 S 5 0 0
S 5 S 3 S 2 0 0
S 6 S 4 S 5 1 1
S 7 S 6 S 1 1 1
S 8 S 7 S 8 1 1
表 4,3 0 状态分配方案（一）
状态代码 状
态 A B C
S 1 0 0 0
S 2 0 0 1
S 3 0 1 0
S 4 0 1 1
S 5 1 0 0
S 6 1 0 1
S 7 1 1 0
S 8 1 1 1
2010-5-21 作者：清华大学电子工程系 罗嵘 第 247页
表 4,3 1 代码形式的状态表
现在状态 下一个状态
A
n
B
n
C
n
输入
x
n
A
n+1
B
n+1
C
n+1
输出
z
n
0 0 1 0 1 0 0 0
1 0 0 1 1
0 1 1 0 0 0 0 1
1 1 1 1 0
0 1 0 1 0 0 1 0
1 0 0 0 0
0 0 1 1 0 0 1 1
1 1 0 0 0
0 0 1 0 0 1 0 0
1 0 0 1 0
0 0 1 1 1 1 0 1
1 1 0 0 1
0 1 0 1 1 1 1 0
1 0 0 0 1
0 1 1 0 1 1 1 1
1 1 1 1 1
2010-5-21 作者：清华大学电子工程系 罗嵘 第 248页
C
n
x
n
A
n
B
n
00 01 11 10
00 0 0 1 1
01 1 0 1 0
11 1 0 1 1
10 0 0 1 0
C
n
x
n
A
n
B
n
00 01 11 10
00 1 0 1 1
01 0 0 0 1
11 0 0 1 1
10 1 0 0 1
C
n
x
n
A
n
B
n
00 01 11 10
00 0 1 1 0
01 1 0 0 1
11 1 0 1 0
10 0 1 0 1
C
n
x
n
A
n
B
n
00 01 11 10
00 1 1 0 0
01 0 0 0 0
11 1 1 1 1
10 0 0 1 1
zn的卡诺图Cn+1的卡诺图
Bn+1的卡诺图An+1的卡诺图
2010-5-21 作者：清华大学电子工程系 罗嵘 第 249页
nnnnnnnnnnn
nnnnnnnnnn
nnnnnnnnnnnn
nnnnnnnnnnnn
xCBAxBAxCBA
xCBxCBxBAC
CBACBAxCBxCB
CBACBAxCBxCA
???
???
????
????
?
?
?
1
1
1
nnnnnnnn CBACABAz ???
nnnnnnnnnnn
nnnnnnnnnnn
C
nnnnnnnnnnnnn
B
nnnnnnnnnnnnn
A
xCBAxBAxCBA
xCBxCBxBACD
CBACBAxCBxCBD
CBACBAxCBxCAD
???
????
?????
?????
?
?
?
1
1
1
2010-5-21 作者：清华大学电子工程系 罗嵘 第 250页
表 4,3 2 状态分配方案（二）
状态代码 状态
A B C
S 1 1 0 1
S 2 1 1 0
S 3 0 1 0
S 4 0 0 0
S 5 1 0 0
S 6 0 0 1
S 7 0 1 1
S 8 1 1 1
表 4,3 3 代码形式的状态表
现在状态 下一个状态
A
n
B
n
C
n
输入
x
n
A
n +1
B
n +1
C
n +1
输出
z
n
0 0 1 0 1 1 0 1
1 1 1 0 1
0 0 1 1 0 1 1 0
1 1 1 1 0
0 0 0 1 0 0 1 0
1 1 0 1 0
0 0 0 0 0 0 0 0
1 1 0 0 0
0 0 1 0 0 1 0 0
1 1 1 0 0
0 0 0 0 1 0 0 1
1 1 0 0 1
0 0 0 1 1 0 1 1
1 1 0 1 1
0 0 1 1 1 1 1 1
1 1 1 1 1
2010-5-21 作者：清华大学电子工程系 罗嵘 第 251页
A
n
B
n
C
n
x
n
00 01 11 10
00 0 0 0 0
01 1 1 1 1
11 1 1 1 1
10 0 0 0 0
A
n
B
n
C
n
x
n
00 01 11 10
00 0 0 1 1
01 0 0 1 1
11 0 0 1 1
10 0 0 1 1
A
n
B
n
C
n
x
n
00 01 11 10
00 0 1 1 0
01 0 1 1 0
11 0 1 1 0
10 0 1 1 0
A
n
B
n
C
n
x
n
00 01 11 10
00 0 0 0
01 0 0 0
11 1 1 1 1
10 1 1 1 1
zn的卡诺图Cn+1的卡诺图
Bn+1的卡诺图An+1的卡诺图
2010-5-21 作者：清华大学电子工程系 罗嵘 第 252页
表 4,3 4 编码的方案数
p 2 3 4 5 6 7 8 9
k 1 2 2 3 3 3 3 4
N 1 3 3 140 420 840 840 10810800
nn
nnn
C
nnn
B
nnn
A
Cz
BCD
ABD
xAD
?
??
??
??
?
?
?
1
1
1
!)!2(
)!12(
2
kp
N
p
k
k
k
?
?
?
?
2010-5-21 作者：清华大学电子工程系 罗嵘 第 253页
5.确定激励函数和输出函数
表 4,3 5 激励表
触发器激励信号
R － S J － K
状态变化
Q
n
? Q
n +1
R S
D T
J K
转移
符号
0 ? 0 ? 0 0 0 0 ? 0
0 ? 1 0 1 1 1 1 ? ?
1 ? 0 1 0 0 1 ? 1 ?
1 ? 1 0 ? 1 0 ? 0 1
表 4,3 6 转移符号代换表
转移符号的代换 触发器输入
1 项 0 项 随意项
R ? ?,1 0 R － S
S ? ?,0 1
D ?,1 ?,0
T ?,? 0,1
J ? 0 ?,1 J － K
K ? 1 ?,0
2010-5-21 作者：清华大学电子工程系 罗嵘 第 254页
表 4,3 7 状态表
现在状态 下一个状态 转移符号
C
n
B
n
A
n
C
n + 1
B
n + 1
A
n + 1
C B A
0 0 0 0 0 1 0 0 ?
0 0 1 0 1 0 0 ? ?
0 1 0 0 1 1 0 1 ?
0 1 1 1 0 0 ? ? ?
1 0 0 1 0 1 1 0 ?
1 0 1 0 0 0 ? 0 ?
例 8
2010-5-21 作者：清华大学电子工程系 罗嵘 第 255页
BA
C
00 01 11 10
0 ? ? ? ?
1 ? ? ? ?
BA
C
00 01 11 10
0 0 0 ? 0
1 1 ? ? ?
BA
C
00 01 11 10
0 0 ? ? 1
1 0 0 ? ?
A触发器的转换图 B触发器的转换图 C触发器的转换图
AKAKK
BAJACJJ
CBA
CBA
???
???
,,1
,,1
ABRBARAR
BASABCSAS
CBA
CBA
???
???
,,
,,
ACBAD
ABABCD
AD
C
B
A
??
??
?
CABAT
ACT
T
C
B
A
??
?
? 1
习题 6 9-3,9-5,9-10
习题 7 9-11,9-14
2010-5-21 作者：清华大学电子工程系 罗嵘 第 230页
设计要求
触发器的激励函数
最小化状态表 触发器选型
原始状态图原始状态表
输出函数
代码形式的状态表
时序电路逻辑图
状态化简
状态分配
自启动检查
4.3.1同步时序逻辑电路的设计
1.设计步骤
2010-5-21 作者：清华大学电子工程系 罗嵘 第 231页
2.原始状态表和图的构成
分析清楚时序电路的输入条件和输出条件, 确定有多少种
输入信息的历史情况, 由相应的电路状态记忆, 从而确定
原始状态图的状态数
把每一个状态作为电路当时所处的现在状态, 根据设计要
求和各种可能的输入情况, 确定该时刻的现在的输出和下
一时刻电路的下一个状态, 画出状态转换线, 注明输入和
输出, 完成原始状态图 。 可多设几个状态, 不要发生遗漏
和错误 。
根据原始状态图列出原始状态表
2010-5-21 作者：清华大学电子工程系 罗嵘 第 232页
例 1设计判断输入序列为 101的检测器 。 输入为 x,输出为 z。
画出下述三种要求下的原始状态图 （ 表 ）
(1)对输入序列每三位进行一次判决：若三位代码是 101,则
对应其最后一个 1时, 输出 z为 1；其它情况 z为 0
x 010 100 101 010
z 000 000 001 000
设 S0,初始状态, 每次判定由此状态开始,
S1,收到一个 0，
S2,收到一个 1，
S3,收到两个 0,S4,收到 01,S5,收到 10,S6,收到 11
2010-5-21 作者：清华大学电子工程系 罗嵘 第 233页
0/0
S0
S1 S2
S3 S4 S5 S6
1/00/0
1/00/0 1/0 0/0
1/0 1/00/0 0/0 1/10/01/0
表 4,1 7 （ 1 ）解的原始状态表
下一个状态 输出 z 现在
状态 x= 0 x= 1 x= 0 x= 1
S
0
S
1
S
2
0 0
S
1
S
3
S
4
0 0
S
2
S
5
S
6
0 0
S
3
S
0
S
0
0 0
S
4
S
0
S
0
0 0
S
5
S
0
S
0
0 1
S
6
S
0
S
0
0 0
2010-5-21 作者：清华大学电子工程系 罗嵘 第 234页
(2)每逢遇到输入序列为 101,输出 z为 1。 但是相邻的 101代码
不可重叠 （ 即输入的代码不可重复使用 ）
x 010 100 101 010
z 000 100 001 000
设 S0,连续收到的输入为 0,S1,收到一个 1,S2,收到 10,S3：
收到 101
表 4, 18 （ 2 ）解的原始状态表
下一个状态 输出 z 现在状态
x= 0 x= 1 x= 0 x= 1
S 0 S 1 S 1 0 0
S 1 S 2 S 1 0 0
S 2 S 0 S 3 0 1
S 3 S 0 S 1 0 0
S0 S1 S2 S3
1/0
0/0
1/00/0
1/0
0/0
1/10/0
2010-5-21 作者：清华大学电子工程系 罗嵘 第 235页
(3)每逢遇到输入序列为 101,输出 z为 1,而且相邻的 101代码
可重叠 （ 即前一个 101的最后一个 1,可以作为下一 个 101的
头一个 1使用 ）
x 010 100 101 010
z 000 100 001 010
设 S0,连续收到的输入为 0,S1,收到一个 1,S2,收到 10
S0 S1 S2
1/0
0/0
0/0
1/0
1/1
0/0
表 4, 19 （ 3 ）解的原始状态表
下一个状态 输出 z 现在状态
x= 0 x= 1 x= 0 x= 1
S 0 S 0 S 1 0 0
S 1 S 2 S 1 0 0
S 2 S 0 S 1 0 1
2010-5-21 作者：清华大学电子工程系 罗嵘 第 236页
例 2一个时序电路有两个输入 x1,x2和两个输出 z1，
z2。 规定在同一时刻, x1和 x2不能同时为 1。 当 x1为 1
时, 若 x2端已输入了两个或两个以上 1（ 这些 1不一
定是连续输入的 ）, 则输出 z1为 1,z2为 0；若 x2端没
有输入过两个或两个以上 1,则输出 z1为 0,z2为 1；
当 x1为 0时, 不论 x2为何值, 输出 z1,z2都为 0。 此外,
每当 x1为 1时, 电路回到起始状态, 又重新开始上述
过程, 试画出电路的原始状态图 （ 表 ）
设 SA,起始状态, x2端尚未输入过 1,SB,x2端输入
了一个 1,SC,x2端输入过两个或两个以上的 1
2010-5-21 作者：清华大学电子工程系 罗嵘 第 237页
表 4, 20 状态表
输出 下一个状态
z 1 z 2
现在
状态
x 1 x 2
= 00
x 1 x 2
= 01
x 1 x 2
= 1 1
x 1 x 2
= 10
x 1 x 2
= 00
x 1 x 2
= 01
x 1 x 2
= 1 1
x 1 x 2
= 10
x 1 x 2 =
00
x 1 x 2 =
01
x 1 x 2 =
11
x 1 x 2 =
10
S A S A S B ? S A 0 0 ? 0 0 0 ? 1
S B S B S C ? S A 0 0 ? 0 0 0 ? 1
S C S C S C ? S A 0 0 ? 1 0 0 ? 0
SA SB
SC
x1x2/z1z2
10/01
00/00
01/00
00/00
01/00
10/01
00/00 01/00
10/10
2010-5-21 作者：清华大学电子工程系 罗嵘 第 238页
3.状态化简
完全确定的时序电路,对于输入变量取值的所有组合都唯
一地确定了该时刻的输出和下一个状态的时序电路 。 它具
有完全描述的状态表, 如例 1中的三张表
不完全确定的时序电路,状态表中包含不确定的输出或不
确定的下一个状态, 则称为不完全描述的状态表, 对应的
时序电路为不完全确定的时序电路, 如例 2
?
状态的等价,若 Si和 Sj分别为时序电路 M1和 M2（ 二者可为
同一个电路 ） 的两个状态 。 作为初始状态时, 不论加入何
种形式的相同的输入序列, 电路均给出相同的输出序列,
则称 Si和 Sj是等价状态或等价对, 记作 Si Sj ； 否则, Si
和 Sj是不等价的或可区分的状态 。
2010-5-21 作者：清华大学电子工程系 罗嵘 第 239页
两个时序电路的两个等价状态, 加入任何输入序列所得到的
输出序列总是相等的, 从输入, 输出角度看, 两个等价状态
是无法区分的, 故可以合并 。
等价的时序电路,两个 时序电路 M1和 M2,当且仅当 M1的每
一个状态能在 M2中至少找到一个等价的状态, 并且 M2的每
一个状态也都能在 M1中至少找到一个等价的状态, 则 M1和
M2是等价的时序逻辑电路 。
完全确定的时序电路的状态化简,
找出最大等价类 （ 包含所有彼此等价的状态的等价类 ）
kikjji SSSSSS ??? 则,,
等价状态具有传递性
2010-5-21 作者：清华大学电子工程系 罗嵘 第 240页
0/0
S0
S1 S2
S3 S4 S5 S6
1/00/0
1/00/0 1/0 0/0
1/0 1/00/0 0/0 1/10/01/0
S3,S4,S6,最大等价类
0/0
S0
S1 S2
S3 S5
1/00/0
1/00/0 1/0 0/0
1/0 0/0 1/1
2010-5-21 作者：清华大学电子工程系 罗嵘 第 241页
用蕴含表法进行状态化简
蕴含表是一个正直角三角形的网格, 两个直角边的网格数相同, 都等
于原始状态表的状态数减 1,使任何两个状态都能在一个网格中相遇
一次 。
1)对于两个状态, 若同样的输入下输出不等, 则不等价, 在相应网格
中填入 ‘ ?× ?；
2)若同样的输入下输出相等, 且下一个状态也相同, 则等价, 在相应
网格中填入 ‘ ???；
3)若 对于两个状态 Si和 Sk,若同样的输入下输出相等, 而且下一个时
刻的状态是相互交错的 （ 即 Si?Sk,Sk ? Si） 或是各自该时刻的状态
（ 即 Si?Si,Sk ? Sk）, 则此两个状态等价, 在相应网格中填入 ‘ ???；
4)若 对于两个状态, 在同样的输入下输出相等, 但下一个时刻的状态
既不是上述 2的情况, 也不是上述 3的情况, 则将不同的下一个状态标
在蕴含表的相应格中, 以待进一步比较 ；相同或交错的下一个状态不
必标出
2010-5-21 作者：清华大学电子工程系 罗嵘 第 242页
表 4, 21 例 3 原始状态表
下一个状态 S(t j+1 ) 输出 z (t j ) 现在状态
S(t j ) x= 0 x= 1 x= 0 x= 1
S 1 S 7 S 1 0 0
S 2 S 7 S 1 0 0
S 3 S 1 S 5 0 1
S 4 S 2 S 6 0 1
S 5 S 7 S 3 0 1
S 6 S 7 S 2 0 1
S 7 S 1 S 7 0 0
S2
S3
S4
S5
S6
S7
S2S1 S3 S5S4 S6
×
?
×
×
× × ×
×
×
×
?
1,7
× ×
×
1,2
5,6
1,7
1,7
5,2
7,2
3,6
7,2
2,6 3,2
1,7
5,3 7,7
3,2
关联比较
检查 × 格, 若 × 格的坐标为 Si,Sk,则表中填有 （ Si,Sk ） 的格对
应的状态对也肯定不等价, 应改为 × ；继续寻找所有不等价的状
态 。 如 S2和 S3不等价, 则 S5和 S6不等价
检查 ?格, 若 ?格的坐标为 Si,Sk,则表中填有 （ Si,Sk ） 的格对应
的状态对便有等价的可能, 若两个状态的输出相等, 而且下一个
状态也都是等价的, 则这两个状态等价, 应改为 ? 。 如 S1和 S7等价,
标有 （ 1,7） 的格的对应状态对 S2和 S7,S3和 S5等价
2010-5-21 作者：清华大学电子工程系 罗嵘 第 243页
S2
S3
S4
S5
S6
S7
S2S1 S3 S5S4 S6
×
?
×
×
× × ×
×
×
×
?
1,7
× ×
×
1,7
×
×
××
×
S2
S3
S4
S5
S6
S7
S2S1 S3 S5S4 S6
×
?
×
×
× × ×
×
×
×
?
× ×
×
×
×
××
×
?
?
最大等价类,（ S1,S2, S7 ）, （ S3, S5 ）, （ S4 ）, （ S6）
从每个最大等价类中选一个状态为代表, 列出包含状态数目最少的
最小化状态表
表 4, 22 例 3 最小化状态表
下一个状态 S (t j+1 ) 输出 z (t j ) 现在状态
S (t j ) x= 0 x= 1 x= 0 x= 1
S 1 S 1 S 1 0 0
S 3 S 1 S 3 0 1
S 4 S 1 S 6 0 1
S 6 S 1 S 1 0 1
2010-5-21 作者：清华大学电子工程系 罗嵘 第 244页
表 4, 2 3 例 4 原始状态表
下一个状态 S(t j+ 1 ) 输出 z (t j ) 现在状态
S(t j ) x= 0 x= 1 x= 0 x= 1
S 1 S 5 S 3 0 0
S 2 S 5 S 4 0 0
S 3 S 6 S 1 1 1
S 4 S 6 S 2 1 1
S 5 S 3 S 1 0 1
S 6 S 4 S 2 0 1
S2
S3
S4
S5
S6
S2S1 S3 S5S4
×
×
×
×
×
×
3,4
× ×
1,2
××
××
3,4
1,2
S2
S3
S4
S5
S6
S2S1 S3 S5S4
×
×
×
×
×
×
× ×
?
××
××
?
?
关联比较
S1和 S2是否等价取决于 S3和 S4是否等价,
而 S3和 S4是否等价取决于 S1和 S2是否等价,
这种情况下, S1和 S2,S3和 S4等价 。 因为
以 S1或 S2作为初始状态, 不论加入什么输
入序列, 均能给出相同的输出序列, 对
S3和 S4是一样的 。
2010-5-21 作者：清华大学电子工程系 罗嵘 第 245页
最大等价类,（ S1,S2 ）, （ S3, S4）, （ S5,S6）
从每个最大等价类中选一个状态为代表, 列出包含状态
数目最少的最小化状态表
表 4, 24 例 4 最小化状态表
下一个状态 S (t j+1 ) 输出 z (t j ) 现在状态
S (t j ) x= 0 x= 1 x= 0 x= 1
S 1 S 5 S 3 0 0
S 3 S 5 S 1 1 1
S 5 S 3 S 1 0 1
2010-5-21 作者：清华大学电子工程系 罗嵘 第 246页
4.状态分配
把状态表中每个字符表示的状态对应地规定一个二元代码,
得出代码形式状态表, 以便设计出时序逻辑电路的逻辑图 。
分配合适, 可简化电路的复杂度
例 7 用 D触发器设计如下表的时序电路
表 4, 29 状态表
下一个状态 输出 现在状态
x= 0 x= 1 x= 0 x= 1
S 1 S 3 S 2 1 1
S 2 S 7 S 8 0 0
S 3 S 6 S 1 0 0
S 4 S 4 S 5 0 0
S 5 S 3 S 2 0 0
S 6 S 4 S 5 1 1
S 7 S 6 S 1 1 1
S 8 S 7 S 8 1 1
表 4,3 0 状态分配方案（一）
状态代码 状
态 A B C
S 1 0 0 0
S 2 0 0 1
S 3 0 1 0
S 4 0 1 1
S 5 1 0 0
S 6 1 0 1
S 7 1 1 0
S 8 1 1 1
2010-5-21 作者：清华大学电子工程系 罗嵘 第 247页
表 4,3 1 代码形式的状态表
现在状态 下一个状态
A
n
B
n
C
n
输入
x
n
A
n+1
B
n+1
C
n+1
输出
z
n
0 0 1 0 1 0 0 0
1 0 0 1 1
0 1 1 0 0 0 0 1
1 1 1 1 0
0 1 0 1 0 0 1 0
1 0 0 0 0
0 0 1 1 0 0 1 1
1 1 0 0 0
0 0 1 0 0 1 0 0
1 0 0 1 0
0 0 1 1 1 1 0 1
1 1 0 0 1
0 1 0 1 1 1 1 0
1 0 0 0 1
0 1 1 0 1 1 1 1
1 1 1 1 1
2010-5-21 作者：清华大学电子工程系 罗嵘 第 248页
C
n
x
n
A
n
B
n
00 01 11 10
00 0 0 1 1
01 1 0 1 0
11 1 0 1 1
10 0 0 1 0
C
n
x
n
A
n
B
n
00 01 11 10
00 1 0 1 1
01 0 0 0 1
11 0 0 1 1
10 1 0 0 1
C
n
x
n
A
n
B
n
00 01 11 10
00 0 1 1 0
01 1 0 0 1
11 1 0 1 0
10 0 1 0 1
C
n
x
n
A
n
B
n
00 01 11 10
00 1 1 0 0
01 0 0 0 0
11 1 1 1 1
10 0 0 1 1
zn的卡诺图Cn+1的卡诺图
Bn+1的卡诺图An+1的卡诺图
2010-5-21 作者：清华大学电子工程系 罗嵘 第 249页
nnnnnnnnnnn
nnnnnnnnnn
nnnnnnnnnnnn
nnnnnnnnnnnn
xCBAxBAxCBA
xCBxCBxBAC
CBACBAxCBxCB
CBACBAxCBxCA
???
???
????
????
?
?
?
1
1
1
nnnnnnnn CBACABAz ???
nnnnnnnnnnn
nnnnnnnnnnn
C
nnnnnnnnnnnnn
B
nnnnnnnnnnnnn
A
xCBAxBAxCBA
xCBxCBxBACD
CBACBAxCBxCBD
CBACBAxCBxCAD
???
????
?????
?????
?
?
?
1
1
1
2010-5-21 作者：清华大学电子工程系 罗嵘 第 250页
表 4,3 2 状态分配方案（二）
状态代码 状态
A B C
S 1 1 0 1
S 2 1 1 0
S 3 0 1 0
S 4 0 0 0
S 5 1 0 0
S 6 0 0 1
S 7 0 1 1
S 8 1 1 1
表 4,3 3 代码形式的状态表
现在状态 下一个状态
A
n
B
n
C
n
输入
x
n
A
n +1
B
n +1
C
n +1
输出
z
n
0 0 1 0 1 1 0 1
1 1 1 0 1
0 0 1 1 0 1 1 0
1 1 1 1 0
0 0 0 1 0 0 1 0
1 1 0 1 0
0 0 0 0 0 0 0 0
1 1 0 0 0
0 0 1 0 0 1 0 0
1 1 1 0 0
0 0 0 0 1 0 0 1
1 1 0 0 1
0 0 0 1 1 0 1 1
1 1 0 1 1
0 0 1 1 1 1 1 1
1 1 1 1 1
2010-5-21 作者：清华大学电子工程系 罗嵘 第 251页
A
n
B
n
C
n
x
n
00 01 11 10
00 0 0 0 0
01 1 1 1 1
11 1 1 1 1
10 0 0 0 0
A
n
B
n
C
n
x
n
00 01 11 10
00 0 0 1 1
01 0 0 1 1
11 0 0 1 1
10 0 0 1 1
A
n
B
n
C
n
x
n
00 01 11 10
00 0 1 1 0
01 0 1 1 0
11 0 1 1 0
10 0 1 1 0
A
n
B
n
C
n
x
n
00 01 11 10
00 0 0 0
01 0 0 0
11 1 1 1 1
10 1 1 1 1
zn的卡诺图Cn+1的卡诺图
Bn+1的卡诺图An+1的卡诺图
2010-5-21 作者：清华大学电子工程系 罗嵘 第 252页
表 4,3 4 编码的方案数
p 2 3 4 5 6 7 8 9
k 1 2 2 3 3 3 3 4
N 1 3 3 140 420 840 840 10810800
nn
nnn
C
nnn
B
nnn
A
Cz
BCD
ABD
xAD
?
??
??
??
?
?
?
1
1
1
!)!2(
)!12(
2
kp
N
p
k
k
k
?
?
?
?
2010-5-21 作者：清华大学电子工程系 罗嵘 第 253页
5.确定激励函数和输出函数
表 4,3 5 激励表
触发器激励信号
R － S J － K
状态变化
Q
n
? Q
n +1
R S
D T
J K
转移
符号
0 ? 0 ? 0 0 0 0 ? 0
0 ? 1 0 1 1 1 1 ? ?
1 ? 0 1 0 0 1 ? 1 ?
1 ? 1 0 ? 1 0 ? 0 1
表 4,3 6 转移符号代换表
转移符号的代换 触发器输入
1 项 0 项 随意项
R ? ?,1 0 R － S
S ? ?,0 1
D ?,1 ?,0
T ?,? 0,1
J ? 0 ?,1 J － K
K ? 1 ?,0
2010-5-21 作者：清华大学电子工程系 罗嵘 第 254页
表 4,3 7 状态表
现在状态 下一个状态 转移符号
C
n
B
n
A
n
C
n + 1
B
n + 1
A
n + 1
C B A
0 0 0 0 0 1 0 0 ?
0 0 1 0 1 0 0 ? ?
0 1 0 0 1 1 0 1 ?
0 1 1 1 0 0 ? ? ?
1 0 0 1 0 1 1 0 ?
1 0 1 0 0 0 ? 0 ?
例 8
2010-5-21 作者：清华大学电子工程系 罗嵘 第 255页
BA
C
00 01 11 10
0 ? ? ? ?
1 ? ? ? ?
BA
C
00 01 11 10
0 0 0 ? 0
1 1 ? ? ?
BA
C
00 01 11 10
0 0 ? ? 1
1 0 0 ? ?
A触发器的转换图 B触发器的转换图 C触发器的转换图
AKAKK
BAJACJJ
CBA
CBA
???
???
,,1
,,1
ABRBARAR
BASABCSAS
CBA
CBA
???
???
,,
,,
ACBAD
ABABCD
AD
C
B
A
??
??
?
CABAT
ACT
T
C
B
A
??
?
? 1
