数字逻辑基础第四章 同步时序电路本章要求：
掌握同步时序电路的基本分析过程
掌握同步时序电路的设计原理
掌握状态表的化简过程组合电路记忆电路
x 1
x m
z 1
z n
Y 1
Y r
y 1
y r
4.1 时序电路的描述注：这是一个一般的结构，在实际的逻辑中可以合并某些输出和状态，也可以没有输入。
输入变量 输出变量状态变量
（现态）
状态变量
（次态）
同步时序电路和异步时序电路
同步时序电路,记忆电路一般由触发器构成，记忆电路中所有触发器状态的变化都是在同一时钟信号操作下同时发生的。触发器的时钟信号不计在输入之内。
异步时序电路,记忆电路可以由触发器构成，也可以由组合电路的反馈构成。记忆电路 状态的变化不是同时发生的,可能有公共的时钟信号，也可能没有公共的时钟信号。
现态与次态概念时钟状态时刻 t k t k +1 t k +2
当前状态 次态 当前状态 次态以两次驱动（在同步时序逻辑中就是时钟）的间隔时间作为时序电路的定时单位，把某个间隔时刻 tk 作为,当前时刻,,将下一个间隔时刻 tk+1 称为,次时刻,。
对于“当前时刻”和“次时刻”的表述，都是相对于时刻 tk 而言。当前时刻的状态为 现态,次时刻的状态为 次态 。
驱动信号时序电路的状态方程与输出方程
)](),([)(
)](),([)(
2
1
kkk
kkk
ttft
ttft
yxz
yxY
意义：
次态是输入与现态的函数（一般情况，也可以无输入）
输出是输入与现态的函数（一般情况，也可以无输入）
注意点：
Y 是次态变量，通常是一个隐含的变量，不一定是触发器的激励输入。只有记忆电路全部是 D 触发器时，次态才与激励相同。
1J
C1
X Z
CP
1K
1J
C1
1K
&
1
&
&
J1
J2
K1
K2
Q1
Q2
例 1 状态机
JK 触发器,Q1,Q2 是现态,X 是输入。
Z 是输出，仅是现态的函数。
次态隐含在 J1,K1,J2,K2 中。
1D
&
&
&
Q 3
Q 2
Q 1
Q 0
CP
≥1
≥1
≥1
C 1
C 1
C 1
C 1
1D
1D
1D
例 2 计数器
D 触发器，无输入，
Q0 ~ Q3 为状态同时也是输出。
次态是 D0 ~ D3，可以通过组合逻辑显式地写出。
米利模型和摩尔模型组合电路记忆电路
(触发器）
输入变量 组合电路激励状态变量输出变量时钟
x
z
y
)](),([)(
)](),([)(
2
1
kkk
kkk
ttft
ttft
yxY
yxz
米利（ Mealy）模型某时刻的输出是该时刻的输入和电路状态的函数
)](),([)(
)]([)(
2
1
kkk
kk
ttft
tft
yxY
yz
摩尔 (Moore)模型组合电路记忆电路
(触发器）
输入变量 组合电路激励状态变量输出变量时钟
x
z
y
某时刻的输出仅是该时刻电路状态的函数，
与该时刻的输入无关 。
米利模型和摩尔模型的区别：
一、米利模型的输出直接同输入有关，所以在输入变化时，
不管状态是否改变，输出立即产生变化。即输入不仅影响次态，同时影响输出。
二、摩尔模型的输出只同状态有关，所以在整个状态保持期间保持输出不变。输入的变化只影响次态。
三、根据上述情况，若输入与时钟同步，则两种模型的输出在整个时钟周期内均保持不变，但米利模型比摩尔模型提前一个时钟周期改变输出。
四、若输入存在干扰，一般不会影响摩尔模型的输出，但可以影响米利模型的输出。
状态转换表现态 次态 / 输出输入 1 输入 2 输入 n
现态 1 次态 11 / 输出 11 次态 12 / 输出 12 次态 1n / 输出 1n
现态 2 次态 21 / 输出 21 次态 22 / 输出 22 次态 2n / 输出 2n
现态 m 次态 m1 / 输出 m1 次态 m2 / 输出 m2 次态 mn / 输出 mn
以表格的形式描述现态、输入与次态、输出的关系。
米利模型的表格形式是：
摩尔模型的表格形式是：
现态 次态 输出输入 1 输入 2 输入 n
现态 1 次态 11 次态 12 次态 1n 输出 1
现态 2 次态 21 次态 22 次态 2n 输出 2
现态 m 次态 m1 次态 m2 次态 mn 输出 m
以信号流图形式显示状态转换关系。
米利模型形式将输出写在转换线上，摩尔模型形式将输出写在状态圈内。
状态转换图状态状态状态输入/ 输出输入/ 输出输入/ 输出输入/ 输出输入/ 输出输入/ 输出状态
/输出状态
/输出状态
/输出输入输入输入输入输入输入米利模型 摩尔模型状态转换图的特点
状态转换图中每个状态射出的状态转换线的根数同系统输入的组合数相同，转换条件包含了所有的输入组合。例如某系统输入组合有 3种,00、
01和 10，则无论哪个模型，每个状态射出的状态转换线都是 3根，分别对应 3个输入组合。这个特点常常被用来检查状态转换图的正确性。
摩尔模型的状态数通常大于米利模型的状态数。
形成这个特点的原因是由于米利模型中一个状态可以对应多个输出，而摩尔模型一个状态只能对应一个输出。
例自动售饮料机。可以投入 1元或 5角的硬币，饮料 1.5元 一杯。
当先后投入的硬币满 1元 5角后，机器送出一杯饮料；当投入的硬币满 2元后，机器送出一杯饮料以及送出一个 5角硬币。
作出上述自动售饮料机问题的状态转换图和状态转换表。
分析 1：
输出,设 Z1 =1→ 输出饮料； Z2 =1→ 输出找零。所有的输出情况为 Z1Z2 = 00,Z1Z2 = 10,Z1Z2 = 11。
输入,当前投入的币值,X1X2 = 00、币值为 0； X1X2 = 01、
币值为 5角； X1X2 = 10、币值为 1元。
状态,记录已经投入的币值,S0＝ 0,S1 ＝ 5角,S2 ＝ 1元。
S
0
S
1
S
2
00/00
00/00 00/00
01/00
10/10
01/00
10/00
01/10
10/11
X
1
X
2
/ Z
1
Z
2
米利模型的状态图初始状态已收 0.5元状态投币 0.5元已收 1元状态输出饮料投币 1元现态次态 / 输出 Z1Z2
X1X2 = 00 X1X2 = 01 X1X2 = 10
S0 S0 /00 S1 /00 S2 /00
S1 S1 /00 S2 /00 S0 /10
S2 S2 /00 S0 /10 S0 /11
米利模型的状态转换表分析 2：
输出,设 Z1=1→ 输出饮料； Z2=1→ 输出找零。所有的输出情况为 Z1Z2 = 00,Z1Z2 = 10,Z1Z2 = 11。
输入,当前投入的币值,X1X2 = 00、币值为 0；
X1X2 = 01、币值为 5角； X1X2 = 10、币值为 1元。
状态,记录已经投入的币值,S0＝ 0,S1＝ 5角、
S2 ＝ 1元,S2 ＝ 1.5元,S2 ＝ 2元。
S 0 / 0 0
S 1 / 0 0
S 2 / 0 0
00
00
01
01
01
10
S 3 / 1 0
S 4 / 1 1
10
10
01
00
00
01
10
10
00
摩尔模型的状态图初始状态已收 0.5元状态输出饮料已收 1.5元状态现态 次态 输出Z
1Z2X1X2 = 00 X1X2 = 01 X1X2 = 10
S0 S0 S1 S2 00
S1 S1 S2 S3 00
S2 S2 S3 S4 00
S3 S0 S1 S2 10
S4 S0 S1 S2 11
摩尔模型的状态转换表时钟状态输入
S 2 S 0
S 3状态输出输出
S 2
米利模型摩尔模型
X 2
Z 1
Z 1
两个模型的时序图状态：已经投入的硬币总值为 1元输入：再投入 1个 5角硬币输出：一杯饮料，即 Z1 =1
米利模型的输出 摩尔模型的输出两种基本模型的相互转换
1、摩尔模型转换为米利模型
将摩尔模型状态转换表的最后一列输出去掉。
在每个次态后面加上,/输出,。其中的输出对应于该次态在原模型中的输出。
观察修改后的状态转换表，合并相同的状态。
2、米利模型转换为摩尔模型
输出同类状态：
所有指向某个状态的状态转换线都具有相同的输出 。
这种类型的状态，次态和输出是统一的，所以只要将所有指向这个状态的状态转换线上的输出改写到表示状态的圆圈中，就可以将米利模型转换为摩尔模型。
输出非同类状态：
指向某个状态的状态转换线具有几个不同的输出 。
显然这个状态转换成摩尔模型后将对应几个状态，所以按照下列步骤改画这种类型的状态：一、将此状态分成几个新状态。每个新状态对应一个输出，写在表示新状态的圆圈中。二、按照不同的输出，将原来的状态转换线分别改画成指向具有对应输出的新状态。 三、原来从输出非同类状态出发的所有状态转换线，都应该在每个新状态中重新画出来，并且它们的目的状态应该与原来的相同。
4.2 同步时序电路的分析
根据给定的电路，确定电路的类型。列出触发器的激励方程。
将激励方程代入触发器的特征方程，写出电路的状态方程。同时写出电路的输出方程。
由状态方程和输出方程，列出电路的状态转换表或状态转换图。
分析电路的状态转换表或状态转换图，得到电路的功能表示或者相应的时序图。如果已知电路的功能，可以通过这一步的分析，验证电路功能的正确性。
1D
C1
1D
C1
&X
CP
Z
Q2
Q1
米利型电路。
1
1
2
1
1
121
2
1
21
1
1
21
,
,
,
QQXQ
QDXD
DQDQ
QXQZ
nn
nn
输出方程：
D触发器：
激励方程：
次态方程：
例 1
现态 次态 /输出 次态 /输出状态编号
Q1Q2 X=0 X=1
00 00/0 10/0 S0
01 00/0 10/0 S1
10 01/0 11/0 S2
11 01/0 11/1 S3
状态转换表
S0
S1
S3S2
0/0
1/1
1/0
1/0 0/0
0/0
0/0
1/0
CP
X
Z
S0 S2S0 S1S3S3S2S0S1
状态转换图和时序图例 2 1J
C1
&
X
CP
Z
Q2
Q1
&
&1 1K
1J
C1
1K
摩尔型电路。
输出方程：
JK触发器：
激励方程：
次态方程,2121211211
122121
1
21
,
,,,
QXQQXQXQQXQQ
XQKXJXKXQJ
QKQJQ
QQZ
nn
n
状态转换表
Q1Q2 X=0 X=1 Z
00 00 01 0 S0
01 00 10 0 S1
10 00 11 0 S2
11 00 11 1 S3
现态 次态 输出 编号
S 0 /
0
S 1 /
0
S 3 /
1
S 2 /
0
1
11
0
1
0
0
0
CP
X
Z
S0 S1S0 S0S3S2S1S0S0
状态转换图和时序图例 3
1J
C
1
X Z
CP
1K
1J
C
1
1K
&
1
&
&
J1
J2
K1
K2
Q1
Q2
摩尔型电路。
输出方程：
JK触发器：
激励方程：
次态方程,212121211
1221121
1
21
,
,,,
QXQQXQQXQQ
XQKXJQKXQJ
QKQJQ
QQZ
nn
n
S 0 /0
S 1 /0
S 2 /1
0
1
0
0
1
0
1
1
S 3 /0
S0,Q1Q2=00
S1,Q1Q2=01
S2,Q1Q2=11
S3,Q1Q2=10
CP
X
Z
S 0 S 1 S 1 S 1 S 1 S 1 S 1S 2 S 2 S 2S 0 S 0S 0
状态转换图和时序图例 4 串行加法器
&
&1
1
C1
1S
1R
& ≥ 1
CP
A
B
Z
BAR
ABS
激励方程状态方程、输出方程和时序图
BAQBABAQBAABQZ
BQAQABQBAABQRSQ
nnn
nnnnn
)()(
)(1
CP
A
Z
B
1 5432 6
Q
0
1
00
000
0
0
0
01
111
1111
1
1
0
0 1
Z'
Z ''
常见的同步时序电路分析
D
D
Q
A
Q
B
CP
Q
C
Q
D
=1
D=1
D=1
&
D
A
D
B
D
C
D
D
&
1
CBADnD
BACnC
ABnB
AnA
QQQQQ
QQQQ
QQQ
QQ
)1(
)1(
)1(
)1(
1、计数器类电路
4位二进制同步加法计数器状态方程：
0 ( 1 ) 0
1
( 1 )
0
( ),0
n
i
i n i j
j
QQ
Q Q Q i
二进制同步加法计数器的状态方程的一般形式时序图
CP
Q
A
Q
D
Q
C
Q
B
D
&
D
Q A
Q B
CP
≥1
=1
& ≥1
Q C
Q D
D
C
B
A
ENP
ENT
L O AD
CLR
(8 )
(4 )
(2 )
(1 )1,5 D
C5/ 2,3,4 +
M1
M2
G3
G4
5,CT=0
3,CT=1 5
CT RD IV 1 6
Q A
Q B
Q C
Q D
RCO
RCO
CP
D
C
B
A
ENP
ENT
L O AD
CLR
=1
&
D
& ≥1
=1
&
D
& ≥1
=1
&
1
=1
=1
&
1
≥1
≥1
1
=1
D A '
D B '
D C '
D D '
D A
D B
D C
D D带同步置数、同步复位、保持等多种功能的
4位二进制同步加法计数器
1
0
'
' ( )
' [ ( ) ( ) ],
nn
A A
i
nj n
j
D LO A D C LR n LO A D C LR D
D E N P E N T Q
D E N P E N T Q Q n A
利用与或门作为数据选择器实现多种逻辑功能转换
CLR LOAD ENP ENT 功能
0 X X X 复位（清零）
1 0 X X 加载（置数）
1 1 1 1 计数
1 1 0 X 保持
1 1 X 0 保持说明：
用,与或门,构成数据选择器 (或者它的变形 )，用控制端来控制 数据选择器，
对触发器激励端的输入信号加以选择，
从而构成不同的工作模式。这是实现多功能时序逻辑电路的一个常用手段。
(8 )
(4 )
(2 )
(1 )1,5 D
C 5 /2,3,4 +
M1
M2
G3
G4
5,CT =0
3,CT =1 5
C T R D I V 1 6
CP
并行输入
ENP
H
L O A D
CLR
(8 )
(4 )
(2 )
(1 )1,5 D
C 5 /2,3,4 +
M1
M2
G3
G4
5,CT =0
3,CT =1 5
C T R D I V 1 6
D 0 ~ D 3 D 4 ~ D 7Q 0 ~ Q 3 Q 4 ~ Q 7
并行输入计数输出 计数输出联往高位二进制加法计数器的串联
CBADnD
BACnC
ABnB
AnA
QQQQQ
QQQQ
QQQ
QQ
)1(
)1(
)1(
)1(
0),(
1
0
)1(
0)1(0
iQQQ
QQ
i
j
jini
n
二进制减法计数器状态方程二进制减法计数器的状态方程的一般形式与加法计数器的差别仅在于这个“非”
D
&
D
Q A
Q B
CP
≥1
&
≥1
Q C
Q D
D
C
B
A
E N P
E N T
L O A D
U / D
RCO
&
&
&
1
≥1
Q A '
Q B '
Q C '
Q D '
& ≥1
& ≥1
=1
=1
&
D
&
D
≥1
&
≥1
&
& ≥1
& ≥1
=1
=1
&
1
可逆计数器实现同步置数、保持等多功能的与或门实现可逆计数的与或门用二进制同步计数器构成其他进制计数器
A、同步置数法
(8 )
(4 )
(2 )
(1 )1,5 D
C5/ 2,3,4 +
M1
M2
G3
G4
5,CT=0
3,CT=1 5
CTR DI V 1 6
Q A
Q B
Q C
Q D
RCO
CP
D=0
C=0
B =1
A=1
ENP
ENT
LO AD
CLR
1
"1 "
"1 "
"1 "
15 3 414
利用进位信号进行同步置数，跳过若干状态。
例如 DCBA＝ 0011＝ 3，
则有以下时序图：
CP
Q
B、同步复位法
(8 )
(4 )
(2 )
(1 )1,5 D
C5/ 2,3,4 +
M1
M2
G3
G4
5,CT=0
3,CT=1 5
CTR DI V 1 6
Q A
Q B
Q C
Q D
RCO
CP
D
C
B
A
ENP
ENT
LO AD
CLR
1
"1"
"1"
"1"
8
4
2
1
B IN /H EX
n利用输出译码进行同步复位，跳过若干状态。
例如 n＝ 12，
则有以下时序图：
12 0 111
CP
Q
C
P
CP
1D
C1
1D
C1
1D
C1
1D
C1
1D
C1
P1 P2 P3 P4 P5
P1
P2
P3
P4
P5
≥1
2、移位寄存器类电路单活跃（ One-hot）电路单活跃电路常常用来作为状态机的状态输出通用移位寄存器
CP
≥1
C1
1R Q 0
1
1
R D
1S1
&
R
≥1
C1
1R Q 1
1S1
& R
≥1
C1
1R Q 2
1S1
& R
≥1
C1
1R Q 3
1S1
& R
1 1PE
P 0
P 1
P 2
P 3
J
K
Q 3
M1
1,2 J
1,2 K
C2 / 1
1,2 D
R
1,2 D
Q 0
Q 1
Q 2
Q 3
Q 3
CP
R D
PE
P 0
P 1
P 2
P 3
J
K
SRG 4
右移方式关联并行输入串行输入实现多功能的与或门
4.3 同步时序电路设计设计一个同步时序电路的一般步骤
确定采用何种模型
状态转换表或状态转换图
化简冗余状态
状态编码
确定触发器类型，状态激励表
触发器的激励方程，电路的输出方程
最终的逻辑电路图例 1：设计 101序列检测电路采用摩尔模型，状态转换图：
S 0 /0 S 1 /0 S 2 /00
1
S 3 /1
0
1
0
1
1 0
已是最简状态，无需化简状态编码如下,S0= 00,S1= 01,S2= 10,S3= 11
问题：输入序列为,101”时，输出,1”
状态 状态（编码） 次态（编码） 输出X = 0 X = 1
S0 Q1Q0 = 00 00 01 0
S1 Q1Q0 = 01 10 01 0
S2 Q1Q0 = 10 00 11 0
S3 Q1Q0 = 11 10 01 1
输入激励 J1K1,J0K0
Q1Q0 = 00 Q1Q0 = 01 Q1Q0 = 10 Q1Q0 = 11
X = 0 0d,0d 1d,d1 d1,0d d0,d1
X = 1 0d,1d 0d,d0 d0,1d d1,d0
状态转换表采用 JK触发器的状态激励表
Q 1 Q 0
X 00 01 11 10
0 1 d d
d0 0 d
0
1
J 1
Q 1 Q 0
X 00 01 11 10
d d 0 1
0d d 1
0
1
K 1
Q 1 Q 0
X 00 01 11 10
0 d d 0
11 d d
0
1
J 0
Q 1 Q 0
X 00 01 11 10
d 1 1 d
dd 0 0
0
1
K 0
激励函数
XKXJ
XQQXKQXJ
00
00101
,
,
01QQZ?
输出函数逻辑图
1J
&
1
Q 0
CP
≥1
C 1
1K
1J
Q 1
C 1
1K
&
X
& Z
例 2：设计 8进制计数器状态转换表状态 Q2Q1Q0 Q2(n+1)Q1(n+1)Q0(n+1)
S0 000 001
S1 001 010
S2 010 011
S3 011 100
S4 100 101
S5 101 110
S6 110 111
S7 111 000
采用 D触发器的激励卡诺图 Q 1 Q 0
Q2 00 01 11 10
0 0 1 0
11 1 0
0
1
D2
Q 1 Q 0
Q2 00 01 11 10
0 1 0 1
10 1 0
0
1
D1
Q 1 Q 0
Q2 00 01 11 10
1 0 0 1
11 0 0
0
1
D0
2 1 0 2 22 1 0
1 1 0
0 0
D Q Q Q Q Q Q Q
D Q Q
DQ
激励方程
&
Q 2
Q 1
Q 0
CP
=1
≥1
C 1
C 1
C 1
1D
1D
1D
逻辑图带有冗余状态的同步时序电路设计一个具有 n个状态的同步时序电路，如果 n不是恰巧等于 2m,一般总有 2m-n个冗余状态。
这些冗余状态在设计时必须加以处理。
若处理不当，会造成严重后果。
例 1：自动售饮料机
S 0
S 1
S 2
0 0 / 0 0
0 0 / 0 0 0 0 / 0 0
0 1 / 0 0
1 0 / 1 0
0 1 / 0 0
1 0 / 0 0
0 1 / 1 0
1 0 / 1 1
X 1 X 2 / Z 1 Z 2
米利模型，
状态转换图：
已是最简状态，无需化简状态编码如下,S0 = 00,S1= 01,S2= 11
S3=10是冗余状态。
现态 编码Q
1Q2
次态 Q1(N+1)Q2(N+1) / 输出 Z1Z2
X1X2 =
00
X1X2 =
01
X1X2 =
11
X1X2 =
10
S0 00 00 / 00 01 / 00 dd / dd 11 / 00
S1 01 01 / 00 11 / 00 dd / dd 00 / 10
S2 11 11 / 00 00 / 10 dd / dd 00 / 11
S3 10 dd / dd dd / dd dd / dd dd / dd
采用 D触发器设计
Qn+1=D
直接从上表得到激励表状态转换表
X 1 X 2
Q 1 Q 2
00 01 11 10
0 0 d 1
00 1 d
00
01
D 1
X 1 X 2
00 01 11 10
0 1 d 1
01 1 d
D 2
X 1 X 2
00 01 11 10
0 0 d 0
10 0 d
Z 1
X 1 X 2
00 01 11 10
0 0 d 0
00 0 d
Z 2
1 0 d 0
dd d d
1 0 d 0
dd d d
0 1 d 1
dd d d
0 0 d 1
dd d d
Q 1 Q 2
Q 1 Q 2 Q 1 Q 2
11
10
00
01
11
10
00
01
11
10
00
01
11
10
激励与输出卡诺图
112
12211
12212122
122212111
XQZ
XQXQZ
XQXQXXQD
XQXQQXXQD
激励函数与输出函数疑问,冗余状态是 Q1Q2 = 10，我们将此冗余状态代入上式。看输出方程：当 Q1Q2 = 10时，若输入 X1 = 1，
则 Z1 = 0,Z2 = 1。若输入 X2 = 1，则 Z1 = 1,Z2 = 0。换句话说，若系统进入冗余状态，那么投入 1圆硬币将没有饮料但有 5角找零；而只要投入 5角硬币，将会得到一杯饮料？
现态 编码Q
1Q2
次态 Q1(N+1)Q2(N+1) / 输出 Z1Z2
X1X2 = 00 X1X2 = 01 X1X2 = 11 X1X2 = 10
S0 00 00/ 00 01/ 00 11 / 00 11 / 00
S1 01 01/ 00 11 / 00 11 / 10 00 / 10
S2 11 11 / 00 00/ 10 00 / 11 00/ 11
S3 10 10 / 00 00 / 10 11 / 11 11 / 01
错误的冗余状态：
例如,X1X2 = 00,则 S3?S3
发生错误的原因：
按照上面化简后的激励函数重新得到实际的状态转换表现态 编码Q
1Q2
次态 Q1(N+1)Q2(N+1) / 输出 Z1Z2
X1X2 = 00 X1X2 = 01 X1X2 = 11 X1X2 = 10
S0 00 00 / 00 01 / 00 dd / dd 11 / 00
S1 01 01 / 00 11 / 00 dd / dd 00 / 10
S2 11 11 / 00 00 / 10 dd / dd 00/ 11
S3 10 00 / 00 01 / 00 dd / dd 11 / 00
修改方法：将冗余状态的次态和输出按照实际情况填入合理的值，修改后的状态转换表如下。按照此表进行设计，没有不合理的冗余状态。
由于输入 X1X2 = 11不可能发生，所以有关 X1X2 = 11的次态和输出不作调整。
例 2：五进制计数器现态 Q2Q1Q0 Q2(n+1)Q1(n+1)Q0(n+1)
S0 000 001
S1 001 010
S2 010 011
S3 011 100
S4 100 000
S5 101 000
S6 110 000
S7 111 000
为了避免出现自启动问题，在开始设计时将冗余状态指向 S0
Q 1 Q 0
Q 2 00 01 11 10
0 0 1 0
00 0 0
0
1
D 2
Q 1 Q 0
00 01 11 10
0 1 0 1
00 0 0
D 1
Q 1 Q 0
00 01 11 10
1 0 0 1
00 0 0
D 0
Q 2 Q 2
0
1
0
1
卡诺图中红色的 0是原来设计的冗余项。但是按照原来的设计，卡诺圈太小。所以可以修改设计，按照上图加大卡诺圈
（蓝色），相当于改变次态，仍然满足自启动要求。
S 2
S 3
S 4
S 1
S 6
S 0
S 5
有效循环
S 7
1,如果问题要求所有冗余状态都具有特定的输出和次态，则在开始进行设计时，除了明确不可能出现的状态以外，应该将所有的冗余状态的输出和次态考虑在状态转换表或状态转换图中。这样得到的设计可以满足问题的原始要求。
2,如果问题只要求满足自启动条件，则可以以任意项方式处理冗余状态，但是最后要进行自启动检查。
3,也可以以确定方式处理冗余状态，但可能得到的结果不是比较好的结果，所以应该进行优化检查。
4,无论上述哪种方法，若在检查后发现问题，都需要按照检查的结果重新修改设计。
冗余状态的处理规则现态 Q3Q2Q1Q0 Q3(n+1)Q2(n+1)Q1(n+1)Q0(n+1)
S0 0000 0001
S1 0001 0010
S2 0010 0011
S3 0011 0100
S4 0100 0101
S5 0101 0110
S6 0110 0111
S7 0111 1000
S8 1000 1001
S9 1001 0000
S10 1010 dddd
S11 1011 dddd
S12 1100 dddd
S13 1101 dddd
S14 1110 dddd
S15 1111 dddd
例：
十进制计数器问题
Q 1 Q 0
Q 3 Q 2
00 01 11 10
1 0 0 1
11 0 0
00
01
D 0
Q1Q0
00 01 11 10
0 1 0 1
10 1 0
D 1
Q1Q0
00 01 11 10
0 0 1 0
11 1 0
D 2
Q1Q0
00 01 11 10
0 0 0 0
00 0 1
D 3
d d d d
d1 0 d
d d d d
d0 0 d
d d d d
d0 0 d
d d d d
d1 0 d
Q3Q2Q3Q2Q3Q2
11
10
00
01
11
10
00
01
11
10
00
01
11
10
3102103
21020212
103101
00
QQQQQQD
QQQQQQQD
QQQQQD
QD
自启动检查：通过 S0
S1
S2
S6
S5
S4
S3
S 1 0
S9
S8
S7
S 1 1
S 1 4
S 1 3 S 1 2
S 1 5
用算法状态机方法设计同步时序电路状态名称摩尔型输出米利型输出输入条件0 1
状态框 判断框 条件输出框算法状态机方法是从计算机程序设计者那里借用了流程图的一些符号，构成算法状态机图（ ASM图）。
ASM图的主要包括以下 3种元件
S0
已收 0 元输出饮料投0,5 元
01
S1
已收 0,5 元投1 元投0,5 元
S2
已收 1 元
1
投1 元
0
0
投0,5 元
1 1
输出饮料
1 0
0
投1 元
01
输出找零售饮料机的 ASM图
S 0
S 1
S 2
00/00
00/00 00/00
01/00
10/10
01/00
10/00
01/10
10/11
X
1
X
2
/ Z
1
Z
2
售饮料机的状态转换图
S 0
X 1
01
S 1 X 2
S 2
1 0
S 3
S 1
S 0
S 3
1d 00
01
X 1 X 2
S 2
A S M 图 状态转换图优先级的处理例：反应时间测试电路该电路用来测量短跑运动员的反应速度，要求时间测量精确到毫秒。由于运动员的反应时间不可能小于 200ms，所以要求当反应时间小于 200ms时，要给出犯规信号。
晶体振荡器模1000
计数器
1kH z
计数控制电路
D A TA
锁存译码显示时钟发令枪运动员计数允许计数器清零计数值锁存时间阈值、计数值=200ms
G U N
A TH
C LR
EN
CP
LATC H
犯规指示
F OUL
LIMEN
系统复位
R ST
S 0 ( 准备)
CLR
ATH
01
S 4 ( 犯规)
FOUL
GUN
S 1 ( 计数1 )
EN
ATH
1
1 0
0
LIMEN
01
S 2 ( 计数2 )
EN
ATH
01
S 3 ( 锁存)
LATCH
RST
1 0
S 4 /
0001
S 0 /
1000
S 1 /
0100
00dd
1ddd
dddd
S 2 /
0100
S 3 /
0010
A TH / G U N / LIM EN / R ST
0d0d
ddd0
ddd1
1ddd
01dd
0d1d
1ddd
0ddd
C LR / EN / LA TC H / F OU L输出输入状态转换图状态分配时序电路的状态由状态变量（时序电路中记忆电路的输出）组合确定，将每个状态对应的状态变量组合分配一个唯一的二进制码的过程称为进行状态分配。
在时序电路设计中必须进行状态分配。分配之后用以代表状态变量的实际二进制码对于最终实现电路的代价有着重要影响。
状态分配问题没有通解。但是根据前人的经验，
按照一定的分配规则，可以得到比较好的分配结果。
!)!2(
)!12(
mn
S m
m
)!2(
)!2(
n
S m
m
用 m个状态变量实现 n个状态时，可能的状态分配数将等价的状态分配方案剔除后，以下函数给出了不等价的状态分配方案数。
状态分配规则 1
对于在相同输入条件下有相同次态的所有状态，在进行状态分配后，应当能形成一个质蕴含。
A
E
D
C
B
A
DC
B
Q 2 Q 1
Q 3
01
01
01
01
状态分配规则 2
对于一个现态的所有次态，在进行状态分配后，
最好能够形成一个质蕴含。
A
E
D
C
B
B EDC
Q 2 Q 1
Q 3
状态分配规则 3
有相同输出的状态最好给予相邻的状态分配。
对于状态分配的说明：
1、上述 3个规则，是一些经验规律，大部分情况下适用，
可能有不适用的例子。
2、对于大部分状态机，不可能全部满足 3条规则，只能按照实际情况运用。规则 1比规则 2的优先级要高，规则
3的优先级最低。除了涉及有大量输出的情况之外，一般很少考虑规则 3。有些资料根本就忽略规则 3。
例子参见讲义例 4－ 13。
4.4 时序电路的状态化简一、完全描述状态表的化简
“完全描述”是指在给定的输入条件下，表中所有的次态和输出均有确定值。
完全描述状态表的例：
现态次态 / 输出
X=0 X=1
S0 S0/0 S2/0
S1 S0/0 S2/0
S2 S1/0 S3/1
S3 S1/0 S3/0
状态的等价,
设某一时序电路（系统）内的两个状态 Si 和 Sj，如果用任意序列的输入加到此电路上，从 Si 或 Sj 出发所得到的输出序列都相同，则称状态 Si 和状态 Sj 等价。
可以证明，为了判别两个状态是否等价，所输入的任意序列只需要有限长度。具体地说，对于具有 n个状态的电路，最多只需要输入 n-1个符号的任意输入序列，
即可判别两个状态的等价与否。
等价的传递性,
若 Si 等价于 Sj，而 Sj 等价于 Sk，则 Si 等价于 Sk。
划分等价状态的规律：
1、如果某两个状态对应的输出不同，则它们显然是不等价的。
2、如果某两个状态在相同的输入下有相同的输出，并且次状态完全相等或为原状态时，这两个状态等价。
3、如果某两个状态在相同的输入下有相同的输出，但是次状态不相同，则此二状态等价与否还得视它们的次状态是否等价而定。
化简的方法：隐含表法
S 2
S 6S 5S 4S 3S 2S 1
S 7
S 6
S 5
S 4
S 3
S 1 S 3
S 7 S 6
S 5 S 3
S 7 S 6
S 2
S 6S 5S 4S 3S 2S 1
S 7
S 6
S 5
S 4
S 3
1,输出不同，肯定不等价，在相应的小方格中记以,×,号。
2,输出相同，并且在相同的输入下次态相同，或者仍为原状态对。肯定等价，在对应的小方格中记以,√”号 。
状态 次态 输出X=0 X=1 X=0 X=1
S1 S1 S7 0 1
S2 S2 S4 0 0
S3 S4 S5 1 0
S4 S7 S5 1 1
S5 S5 S7 0 1
S6 S6 S4 0 0
S7 S3 S6 0 13,输出相同，次态不同，记录次态对。
4,观察该次态对是否等价（等价传递）。若是则钩，若非则叉。
最后将所有等价态合并，就得到化简后的状态表。
对于上例，由于状态 S1 与 S5 等价，状态 S2 与 S6 等价，所以可以将这 4 个状态化简成 2 个状态，而其余 3个状态则无法进一步化简。
原状态 化简后 状态 次态 输出X=0 X=1 X=0 X=1
S1,S5 SA SA SE 0 1
S7 SE SC SB 0 1
S2,S6 SB SB SD 0 0
S3 SC SD SA 1 0
S4 SD SE SA 1 1
二、不完全描述状态表的化简不完全描述状态表：
表中某些状态在某些输入情况下的次态或输出没有确定的值，它们可以取 0也可以取 1，
状态 次态 输出X=0 X=1
S1 S2 S4 0
S2 S1 S4 d
S3 S3 S5 1
S4 d S5 1
相容：
1,输出相容,
如果两个输出序列的每一对有确定值的对应输出均相同，则称此两输出相容。
例,
00111
01110
11010
dZ
dZ
dZ
k
j
i
Zi与 Zj相容,Zj与 Zk也相容 。 而 Zi与 Zk则不相容。可见，相容不具有传递性 。
2,状态相容,
两个状态 Si 和 Sj，如果用任意序列的输入加到此系统上，从 Si 或 Sj 出发所得到的输出序列都相容，则称状态 Si 和状态 Sj 相容。
简单不相容,
在相同输入下，状态 Si 和 Sj 输出不相容。
简单相容,
对于任意输入，输出相容，有确定值的次状态相等或者仍为原状态。
状态 次态 输出X=0 X=1
S1 S3 d 1
S2 d S3 d
S3 d S2 d
S4 S4 d 0
S5 S5 S4 d
例：用 隐含表化简简单不相容简单相容简单相容简单相容简单相容简单相容简单相容
S 2
S 4S 3S 2S 1
S 5
S 4
S 3
S 3 S 5 S 2 S 4S 3 S 4
步骤 1、寻找相容关系打钩的为简单相容，打叉的为简单不相容。
其余三个状态对，既不是简单相容，也不是简单不相容。写上它们 有确定值的次态对 。
由于相容不具有传递性，所以不能简单地由简单相容外推两个不简单相容的状态是否相容。
例如上表中,S1与 S3相容,S3与 S4相容，但是 S1与 S4简单不相容。
同样，也不能推断上表中写上次态对的 3个方格,S1与 S5、
S2与 S5以及 S3与 S5的相容性。
若两个状态的输出相容，有确定值的次态不同，但是该次态对是简单相容的，则此两个状态仍然可能相容。我们称此两个状态 潜在相容 。
考察上述 3个状态对的次态对是否相容：其中两个次态对简单相容，一个次态对的次态对简单相容（潜在相容），所以上述 3个状态对均潜在相容。
步骤 2、寻找最大相容类集合所谓最大相容类集合，是含有不被其它相容类集合所覆盖的相容的一组状态或状态对。寻找最大相容类集合的目的是要将全体状态划分为尽可能少的组，每组内的状态都彼此相容。
利用合并图来寻找最大相容类集合：
合并图是将状态表中所有的状态以点的形式画在一个圆周上，然后将所有的相容状态对（包括潜在相容对）用直线连接起来。若在一组状态点中两两之间都有连线，
表示该组状态中所有状态两两相容，可以形成最大相容类。在图形上，它们将形成一个 内部两两相连的最大的多边形，该多边形的各个顶点就形成一个最大相容类集合。
S1
S5
S4S3
S2
在本例题中，共有 5个状态，构成的相容状态对有：
{S1,S2},{S1,S3},{S1,S5}
{S2,S3},{S2,S4},{S2,S5}
{S3,S4},{S3,S5}
{S4,S5}
最大相容类集合：
{ S1,S2,S3,S5 } 和 { S2,S3,S4,S5 }
S 2
S 4S 3S 2S 1
S 5
S 4
S 3
S 3 S 5 S 2 S 4S 3 S 4
潜在相容步骤 3、构成简化状态表由上面得到的最大相容类集合 {A},{B},…,{K} 可能有状态重叠，所以可以用其中的一部分作为一个简化状态。若用 {A'} 表示 {A} 的一个子集,{B'} 表示 {B} 的一个子集，等，则可以用 {A'},{B'},…,
{K'} 中的一部分 {A'},{B'},…,{N'}作为化简后的状态。其中
{A'},{B'},…,{N'} 应满足下列三个条件：
1,覆盖化,{A'},{B'},…,{N'}中必须包含原状态表中所有的状态。
2,最小化,由 {A'},{B'},…,{N'}构成的状态数目最少。也就是说，若在第一步得到 k个最大相容类集合，最后的简化状态个数可以小于 k。
3,闭合性,{A'},{B'},…,{N'}中任何一个新状态，它所包含的几个原来的状态在一定的输入下对应的次状态必须属于合并后的同一状态。否则简化表的次状态无法确定。
根据上述规则从最大相容类中选择化简后的状态集合来构成简化状态表，
其方法不是唯一的，部分地要凭经验进行试验。
回到原来的例子：
已经得到 2个最大相容类集合，分别是
{ S1,S2,S3,S5 } { S2,S3,S4,S5 }
根据前面所说的三个条件中的前面二个 —— 覆盖性 和 最小化考虑，选取上述 2个最大相容类集合中的部分子集，可以按下面的组合来选取简化后的状态组合：
(1) { S1,S5 } { S2,S3,S4 }
(2) { S1 } { S2,S3,S4,S5 }
(3) { S1,S2 } { S3,S4,S5 }
(4) { S1,S2,S3 } { S4,S5 }
上述 4个组合，每个组合中都包含了原来的所有状态，所以都满足覆盖性要求。这样组合以后的简化状态只有 2个，并且不可能进一步减少，所以满足最小化要求。
但是，方案 (1)和 (3)均不满足 闭合性 。
以方案 (1)为例，原始问题 S1,S5在输入 X = 0时对应的次状态分别为 S3和 S5。但如果按照 方案 (1)简化以后,S1和 S5将合并成一个状态，而它们的次状态 S3和 S5将分属于化简后的两个不同状态，这样一来，在化简后的状态表中新状态 { S1,S5 }
在输入 X = 0时的次态将无法选择。
状态 次态X=0
S1 S3
S5 S5
化简后的状态 次态X=0
SA={S1,S5} SA(S5)? SB(S3)?
SB={S2,S3,S4}
原始的状态转换关系 方案（ 1）的状态转换关系反之，方案 (2)和 (4)则可以满足上述三个条件。所以这两种简化方案是可取的。假定取第二种方案，以 SA代替 { S1 }而以 SB代替 { S2,S3,S4,S5 }，于是本问题的状态转换表便简化成只有两个状态，如下表所示。
状态次态输出X=0 X=1
SA SB d 1
SB SB SB 0
掌握同步时序电路的基本分析过程
掌握同步时序电路的设计原理
掌握状态表的化简过程组合电路记忆电路
x 1
x m
z 1
z n
Y 1
Y r
y 1
y r
4.1 时序电路的描述注：这是一个一般的结构，在实际的逻辑中可以合并某些输出和状态，也可以没有输入。
输入变量 输出变量状态变量
（现态）
状态变量
（次态）
同步时序电路和异步时序电路
同步时序电路,记忆电路一般由触发器构成，记忆电路中所有触发器状态的变化都是在同一时钟信号操作下同时发生的。触发器的时钟信号不计在输入之内。
异步时序电路,记忆电路可以由触发器构成，也可以由组合电路的反馈构成。记忆电路 状态的变化不是同时发生的,可能有公共的时钟信号，也可能没有公共的时钟信号。
现态与次态概念时钟状态时刻 t k t k +1 t k +2
当前状态 次态 当前状态 次态以两次驱动（在同步时序逻辑中就是时钟）的间隔时间作为时序电路的定时单位，把某个间隔时刻 tk 作为,当前时刻,,将下一个间隔时刻 tk+1 称为,次时刻,。
对于“当前时刻”和“次时刻”的表述，都是相对于时刻 tk 而言。当前时刻的状态为 现态,次时刻的状态为 次态 。
驱动信号时序电路的状态方程与输出方程
)](),([)(
)](),([)(
2
1
kkk
kkk
ttft
ttft
yxz
yxY
意义：
次态是输入与现态的函数（一般情况，也可以无输入）
输出是输入与现态的函数（一般情况，也可以无输入）
注意点：
Y 是次态变量，通常是一个隐含的变量，不一定是触发器的激励输入。只有记忆电路全部是 D 触发器时，次态才与激励相同。
1J
C1
X Z
CP
1K
1J
C1
1K
&
1
&
&
J1
J2
K1
K2
Q1
Q2
例 1 状态机
JK 触发器,Q1,Q2 是现态,X 是输入。
Z 是输出，仅是现态的函数。
次态隐含在 J1,K1,J2,K2 中。
1D
&
&
&
Q 3
Q 2
Q 1
Q 0
CP
≥1
≥1
≥1
C 1
C 1
C 1
C 1
1D
1D
1D
例 2 计数器
D 触发器，无输入，
Q0 ~ Q3 为状态同时也是输出。
次态是 D0 ~ D3，可以通过组合逻辑显式地写出。
米利模型和摩尔模型组合电路记忆电路
(触发器）
输入变量 组合电路激励状态变量输出变量时钟
x
z
y
)](),([)(
)](),([)(
2
1
kkk
kkk
ttft
ttft
yxY
yxz
米利（ Mealy）模型某时刻的输出是该时刻的输入和电路状态的函数
)](),([)(
)]([)(
2
1
kkk
kk
ttft
tft
yxY
yz
摩尔 (Moore)模型组合电路记忆电路
(触发器）
输入变量 组合电路激励状态变量输出变量时钟
x
z
y
某时刻的输出仅是该时刻电路状态的函数，
与该时刻的输入无关 。
米利模型和摩尔模型的区别：
一、米利模型的输出直接同输入有关，所以在输入变化时，
不管状态是否改变，输出立即产生变化。即输入不仅影响次态，同时影响输出。
二、摩尔模型的输出只同状态有关，所以在整个状态保持期间保持输出不变。输入的变化只影响次态。
三、根据上述情况，若输入与时钟同步，则两种模型的输出在整个时钟周期内均保持不变，但米利模型比摩尔模型提前一个时钟周期改变输出。
四、若输入存在干扰，一般不会影响摩尔模型的输出，但可以影响米利模型的输出。
状态转换表现态 次态 / 输出输入 1 输入 2 输入 n
现态 1 次态 11 / 输出 11 次态 12 / 输出 12 次态 1n / 输出 1n
现态 2 次态 21 / 输出 21 次态 22 / 输出 22 次态 2n / 输出 2n
现态 m 次态 m1 / 输出 m1 次态 m2 / 输出 m2 次态 mn / 输出 mn
以表格的形式描述现态、输入与次态、输出的关系。
米利模型的表格形式是：
摩尔模型的表格形式是：
现态 次态 输出输入 1 输入 2 输入 n
现态 1 次态 11 次态 12 次态 1n 输出 1
现态 2 次态 21 次态 22 次态 2n 输出 2
现态 m 次态 m1 次态 m2 次态 mn 输出 m
以信号流图形式显示状态转换关系。
米利模型形式将输出写在转换线上，摩尔模型形式将输出写在状态圈内。
状态转换图状态状态状态输入/ 输出输入/ 输出输入/ 输出输入/ 输出输入/ 输出输入/ 输出状态
/输出状态
/输出状态
/输出输入输入输入输入输入输入米利模型 摩尔模型状态转换图的特点
状态转换图中每个状态射出的状态转换线的根数同系统输入的组合数相同，转换条件包含了所有的输入组合。例如某系统输入组合有 3种,00、
01和 10，则无论哪个模型，每个状态射出的状态转换线都是 3根，分别对应 3个输入组合。这个特点常常被用来检查状态转换图的正确性。
摩尔模型的状态数通常大于米利模型的状态数。
形成这个特点的原因是由于米利模型中一个状态可以对应多个输出，而摩尔模型一个状态只能对应一个输出。
例自动售饮料机。可以投入 1元或 5角的硬币，饮料 1.5元 一杯。
当先后投入的硬币满 1元 5角后，机器送出一杯饮料；当投入的硬币满 2元后，机器送出一杯饮料以及送出一个 5角硬币。
作出上述自动售饮料机问题的状态转换图和状态转换表。
分析 1：
输出,设 Z1 =1→ 输出饮料； Z2 =1→ 输出找零。所有的输出情况为 Z1Z2 = 00,Z1Z2 = 10,Z1Z2 = 11。
输入,当前投入的币值,X1X2 = 00、币值为 0； X1X2 = 01、
币值为 5角； X1X2 = 10、币值为 1元。
状态,记录已经投入的币值,S0＝ 0,S1 ＝ 5角,S2 ＝ 1元。
S
0
S
1
S
2
00/00
00/00 00/00
01/00
10/10
01/00
10/00
01/10
10/11
X
1
X
2
/ Z
1
Z
2
米利模型的状态图初始状态已收 0.5元状态投币 0.5元已收 1元状态输出饮料投币 1元现态次态 / 输出 Z1Z2
X1X2 = 00 X1X2 = 01 X1X2 = 10
S0 S0 /00 S1 /00 S2 /00
S1 S1 /00 S2 /00 S0 /10
S2 S2 /00 S0 /10 S0 /11
米利模型的状态转换表分析 2：
输出,设 Z1=1→ 输出饮料； Z2=1→ 输出找零。所有的输出情况为 Z1Z2 = 00,Z1Z2 = 10,Z1Z2 = 11。
输入,当前投入的币值,X1X2 = 00、币值为 0；
X1X2 = 01、币值为 5角； X1X2 = 10、币值为 1元。
状态,记录已经投入的币值,S0＝ 0,S1＝ 5角、
S2 ＝ 1元,S2 ＝ 1.5元,S2 ＝ 2元。
S 0 / 0 0
S 1 / 0 0
S 2 / 0 0
00
00
01
01
01
10
S 3 / 1 0
S 4 / 1 1
10
10
01
00
00
01
10
10
00
摩尔模型的状态图初始状态已收 0.5元状态输出饮料已收 1.5元状态现态 次态 输出Z
1Z2X1X2 = 00 X1X2 = 01 X1X2 = 10
S0 S0 S1 S2 00
S1 S1 S2 S3 00
S2 S2 S3 S4 00
S3 S0 S1 S2 10
S4 S0 S1 S2 11
摩尔模型的状态转换表时钟状态输入
S 2 S 0
S 3状态输出输出
S 2
米利模型摩尔模型
X 2
Z 1
Z 1
两个模型的时序图状态：已经投入的硬币总值为 1元输入：再投入 1个 5角硬币输出：一杯饮料，即 Z1 =1
米利模型的输出 摩尔模型的输出两种基本模型的相互转换
1、摩尔模型转换为米利模型
将摩尔模型状态转换表的最后一列输出去掉。
在每个次态后面加上,/输出,。其中的输出对应于该次态在原模型中的输出。
观察修改后的状态转换表，合并相同的状态。
2、米利模型转换为摩尔模型
输出同类状态：
所有指向某个状态的状态转换线都具有相同的输出 。
这种类型的状态，次态和输出是统一的，所以只要将所有指向这个状态的状态转换线上的输出改写到表示状态的圆圈中，就可以将米利模型转换为摩尔模型。
输出非同类状态：
指向某个状态的状态转换线具有几个不同的输出 。
显然这个状态转换成摩尔模型后将对应几个状态，所以按照下列步骤改画这种类型的状态：一、将此状态分成几个新状态。每个新状态对应一个输出，写在表示新状态的圆圈中。二、按照不同的输出，将原来的状态转换线分别改画成指向具有对应输出的新状态。 三、原来从输出非同类状态出发的所有状态转换线，都应该在每个新状态中重新画出来，并且它们的目的状态应该与原来的相同。
4.2 同步时序电路的分析
根据给定的电路，确定电路的类型。列出触发器的激励方程。
将激励方程代入触发器的特征方程，写出电路的状态方程。同时写出电路的输出方程。
由状态方程和输出方程，列出电路的状态转换表或状态转换图。
分析电路的状态转换表或状态转换图，得到电路的功能表示或者相应的时序图。如果已知电路的功能，可以通过这一步的分析，验证电路功能的正确性。
1D
C1
1D
C1
&X
CP
Z
Q2
Q1
米利型电路。
1
1
2
1
1
121
2
1
21
1
1
21
,
,
,
QQXQ
QDXD
DQDQ
QXQZ
nn
nn
输出方程：
D触发器：
激励方程：
次态方程：
例 1
现态 次态 /输出 次态 /输出状态编号
Q1Q2 X=0 X=1
00 00/0 10/0 S0
01 00/0 10/0 S1
10 01/0 11/0 S2
11 01/0 11/1 S3
状态转换表
S0
S1
S3S2
0/0
1/1
1/0
1/0 0/0
0/0
0/0
1/0
CP
X
Z
S0 S2S0 S1S3S3S2S0S1
状态转换图和时序图例 2 1J
C1
&
X
CP
Z
Q2
Q1
&
&1 1K
1J
C1
1K
摩尔型电路。
输出方程：
JK触发器：
激励方程：
次态方程,2121211211
122121
1
21
,
,,,
QXQQXQXQQXQQ
XQKXJXKXQJ
QKQJQ
QQZ
nn
n
状态转换表
Q1Q2 X=0 X=1 Z
00 00 01 0 S0
01 00 10 0 S1
10 00 11 0 S2
11 00 11 1 S3
现态 次态 输出 编号
S 0 /
0
S 1 /
0
S 3 /
1
S 2 /
0
1
11
0
1
0
0
0
CP
X
Z
S0 S1S0 S0S3S2S1S0S0
状态转换图和时序图例 3
1J
C
1
X Z
CP
1K
1J
C
1
1K
&
1
&
&
J1
J2
K1
K2
Q1
Q2
摩尔型电路。
输出方程：
JK触发器：
激励方程：
次态方程,212121211
1221121
1
21
,
,,,
QXQQXQQXQQ
XQKXJQKXQJ
QKQJQ
QQZ
nn
n
S 0 /0
S 1 /0
S 2 /1
0
1
0
0
1
0
1
1
S 3 /0
S0,Q1Q2=00
S1,Q1Q2=01
S2,Q1Q2=11
S3,Q1Q2=10
CP
X
Z
S 0 S 1 S 1 S 1 S 1 S 1 S 1S 2 S 2 S 2S 0 S 0S 0
状态转换图和时序图例 4 串行加法器
&
&1
1
C1
1S
1R
& ≥ 1
CP
A
B
Z
BAR
ABS
激励方程状态方程、输出方程和时序图
BAQBABAQBAABQZ
BQAQABQBAABQRSQ
nnn
nnnnn
)()(
)(1
CP
A
Z
B
1 5432 6
Q
0
1
00
000
0
0
0
01
111
1111
1
1
0
0 1
Z'
Z ''
常见的同步时序电路分析
D
D
Q
A
Q
B
CP
Q
C
Q
D
=1
D=1
D=1
&
D
A
D
B
D
C
D
D
&
1
CBADnD
BACnC
ABnB
AnA
QQQQQ
QQQQ
QQQ
)1(
)1(
)1(
)1(
1、计数器类电路
4位二进制同步加法计数器状态方程：
0 ( 1 ) 0
1
( 1 )
0
( ),0
n
i
i n i j
j
Q Q Q i
二进制同步加法计数器的状态方程的一般形式时序图
CP
Q
A
Q
D
Q
C
Q
B
D
&
D
Q A
Q B
CP
≥1
=1
& ≥1
Q C
Q D
D
C
B
A
ENP
ENT
L O AD
CLR
(8 )
(4 )
(2 )
(1 )1,5 D
C5/ 2,3,4 +
M1
M2
G3
G4
5,CT=0
3,CT=1 5
CT RD IV 1 6
Q A
Q B
Q C
Q D
RCO
RCO
CP
D
C
B
A
ENP
ENT
L O AD
CLR
=1
&
D
& ≥1
=1
&
D
& ≥1
=1
&
1
=1
=1
&
1
≥1
≥1
1
=1
D A '
D B '
D C '
D D '
D A
D B
D C
D D带同步置数、同步复位、保持等多种功能的
4位二进制同步加法计数器
1
0
'
' ( )
' [ ( ) ( ) ],
nn
A A
i
nj n
j
D LO A D C LR n LO A D C LR D
D E N P E N T Q
D E N P E N T Q Q n A
利用与或门作为数据选择器实现多种逻辑功能转换
CLR LOAD ENP ENT 功能
0 X X X 复位（清零）
1 0 X X 加载（置数）
1 1 1 1 计数
1 1 0 X 保持
1 1 X 0 保持说明：
用,与或门,构成数据选择器 (或者它的变形 )，用控制端来控制 数据选择器，
对触发器激励端的输入信号加以选择，
从而构成不同的工作模式。这是实现多功能时序逻辑电路的一个常用手段。
(8 )
(4 )
(2 )
(1 )1,5 D
C 5 /2,3,4 +
M1
M2
G3
G4
5,CT =0
3,CT =1 5
C T R D I V 1 6
CP
并行输入
ENP
H
L O A D
CLR
(8 )
(4 )
(2 )
(1 )1,5 D
C 5 /2,3,4 +
M1
M2
G3
G4
5,CT =0
3,CT =1 5
C T R D I V 1 6
D 0 ~ D 3 D 4 ~ D 7Q 0 ~ Q 3 Q 4 ~ Q 7
并行输入计数输出 计数输出联往高位二进制加法计数器的串联
CBADnD
BACnC
ABnB
AnA
QQQQQ
QQQQ
QQQ
)1(
)1(
)1(
)1(
0),(
1
0
)1(
0)1(0
iQQQ
i
j
jini
n
二进制减法计数器状态方程二进制减法计数器的状态方程的一般形式与加法计数器的差别仅在于这个“非”
D
&
D
Q A
Q B
CP
≥1
&
≥1
Q C
Q D
D
C
B
A
E N P
E N T
L O A D
U / D
RCO
&
&
&
1
≥1
Q A '
Q B '
Q C '
Q D '
& ≥1
& ≥1
=1
=1
&
D
&
D
≥1
&
≥1
&
& ≥1
& ≥1
=1
=1
&
1
可逆计数器实现同步置数、保持等多功能的与或门实现可逆计数的与或门用二进制同步计数器构成其他进制计数器
A、同步置数法
(8 )
(4 )
(2 )
(1 )1,5 D
C5/ 2,3,4 +
M1
M2
G3
G4
5,CT=0
3,CT=1 5
CTR DI V 1 6
Q A
Q B
Q C
Q D
RCO
CP
D=0
C=0
B =1
A=1
ENP
ENT
LO AD
CLR
1
"1 "
"1 "
"1 "
15 3 414
利用进位信号进行同步置数，跳过若干状态。
例如 DCBA＝ 0011＝ 3，
则有以下时序图：
CP
Q
B、同步复位法
(8 )
(4 )
(2 )
(1 )1,5 D
C5/ 2,3,4 +
M1
M2
G3
G4
5,CT=0
3,CT=1 5
CTR DI V 1 6
Q A
Q B
Q C
Q D
RCO
CP
D
C
B
A
ENP
ENT
LO AD
CLR
1
"1"
"1"
"1"
8
4
2
1
B IN /H EX
n利用输出译码进行同步复位，跳过若干状态。
例如 n＝ 12，
则有以下时序图：
12 0 111
CP
Q
C
P
CP
1D
C1
1D
C1
1D
C1
1D
C1
1D
C1
P1 P2 P3 P4 P5
P1
P2
P3
P4
P5
≥1
2、移位寄存器类电路单活跃（ One-hot）电路单活跃电路常常用来作为状态机的状态输出通用移位寄存器
CP
≥1
C1
1R Q 0
1
1
R D
1S1
&
R
≥1
C1
1R Q 1
1S1
& R
≥1
C1
1R Q 2
1S1
& R
≥1
C1
1R Q 3
1S1
& R
1 1PE
P 0
P 1
P 2
P 3
J
K
Q 3
M1
1,2 J
1,2 K
C2 / 1
1,2 D
R
1,2 D
Q 0
Q 1
Q 2
Q 3
Q 3
CP
R D
PE
P 0
P 1
P 2
P 3
J
K
SRG 4
右移方式关联并行输入串行输入实现多功能的与或门
4.3 同步时序电路设计设计一个同步时序电路的一般步骤
确定采用何种模型
状态转换表或状态转换图
化简冗余状态
状态编码
确定触发器类型，状态激励表
触发器的激励方程，电路的输出方程
最终的逻辑电路图例 1：设计 101序列检测电路采用摩尔模型，状态转换图：
S 0 /0 S 1 /0 S 2 /00
1
S 3 /1
0
1
0
1
1 0
已是最简状态，无需化简状态编码如下,S0= 00,S1= 01,S2= 10,S3= 11
问题：输入序列为,101”时，输出,1”
状态 状态（编码） 次态（编码） 输出X = 0 X = 1
S0 Q1Q0 = 00 00 01 0
S1 Q1Q0 = 01 10 01 0
S2 Q1Q0 = 10 00 11 0
S3 Q1Q0 = 11 10 01 1
输入激励 J1K1,J0K0
Q1Q0 = 00 Q1Q0 = 01 Q1Q0 = 10 Q1Q0 = 11
X = 0 0d,0d 1d,d1 d1,0d d0,d1
X = 1 0d,1d 0d,d0 d0,1d d1,d0
状态转换表采用 JK触发器的状态激励表
Q 1 Q 0
X 00 01 11 10
0 1 d d
d0 0 d
0
1
J 1
Q 1 Q 0
X 00 01 11 10
d d 0 1
0d d 1
0
1
K 1
Q 1 Q 0
X 00 01 11 10
0 d d 0
11 d d
0
1
J 0
Q 1 Q 0
X 00 01 11 10
d 1 1 d
dd 0 0
0
1
K 0
激励函数
XKXJ
XQQXKQXJ
00
00101
,
,
01QQZ?
输出函数逻辑图
1J
&
1
Q 0
CP
≥1
C 1
1K
1J
Q 1
C 1
1K
&
X
& Z
例 2：设计 8进制计数器状态转换表状态 Q2Q1Q0 Q2(n+1)Q1(n+1)Q0(n+1)
S0 000 001
S1 001 010
S2 010 011
S3 011 100
S4 100 101
S5 101 110
S6 110 111
S7 111 000
采用 D触发器的激励卡诺图 Q 1 Q 0
Q2 00 01 11 10
0 0 1 0
11 1 0
0
1
D2
Q 1 Q 0
Q2 00 01 11 10
0 1 0 1
10 1 0
0
1
D1
Q 1 Q 0
Q2 00 01 11 10
1 0 0 1
11 0 0
0
1
D0
2 1 0 2 22 1 0
1 1 0
0 0
D Q Q Q Q Q Q Q
D Q Q
DQ
激励方程
&
Q 2
Q 1
Q 0
CP
=1
≥1
C 1
C 1
C 1
1D
1D
1D
逻辑图带有冗余状态的同步时序电路设计一个具有 n个状态的同步时序电路，如果 n不是恰巧等于 2m,一般总有 2m-n个冗余状态。
这些冗余状态在设计时必须加以处理。
若处理不当，会造成严重后果。
例 1：自动售饮料机
S 0
S 1
S 2
0 0 / 0 0
0 0 / 0 0 0 0 / 0 0
0 1 / 0 0
1 0 / 1 0
0 1 / 0 0
1 0 / 0 0
0 1 / 1 0
1 0 / 1 1
X 1 X 2 / Z 1 Z 2
米利模型，
状态转换图：
已是最简状态，无需化简状态编码如下,S0 = 00,S1= 01,S2= 11
S3=10是冗余状态。
现态 编码Q
1Q2
次态 Q1(N+1)Q2(N+1) / 输出 Z1Z2
X1X2 =
00
X1X2 =
01
X1X2 =
11
X1X2 =
10
S0 00 00 / 00 01 / 00 dd / dd 11 / 00
S1 01 01 / 00 11 / 00 dd / dd 00 / 10
S2 11 11 / 00 00 / 10 dd / dd 00 / 11
S3 10 dd / dd dd / dd dd / dd dd / dd
采用 D触发器设计
Qn+1=D
直接从上表得到激励表状态转换表
X 1 X 2
Q 1 Q 2
00 01 11 10
0 0 d 1
00 1 d
00
01
D 1
X 1 X 2
00 01 11 10
0 1 d 1
01 1 d
D 2
X 1 X 2
00 01 11 10
0 0 d 0
10 0 d
Z 1
X 1 X 2
00 01 11 10
0 0 d 0
00 0 d
Z 2
1 0 d 0
dd d d
1 0 d 0
dd d d
0 1 d 1
dd d d
0 0 d 1
dd d d
Q 1 Q 2
Q 1 Q 2 Q 1 Q 2
11
10
00
01
11
10
00
01
11
10
00
01
11
10
激励与输出卡诺图
112
12211
12212122
122212111
XQZ
XQXQZ
XQXQXXQD
XQXQQXXQD
激励函数与输出函数疑问,冗余状态是 Q1Q2 = 10，我们将此冗余状态代入上式。看输出方程：当 Q1Q2 = 10时，若输入 X1 = 1，
则 Z1 = 0,Z2 = 1。若输入 X2 = 1，则 Z1 = 1,Z2 = 0。换句话说，若系统进入冗余状态，那么投入 1圆硬币将没有饮料但有 5角找零；而只要投入 5角硬币，将会得到一杯饮料？
现态 编码Q
1Q2
次态 Q1(N+1)Q2(N+1) / 输出 Z1Z2
X1X2 = 00 X1X2 = 01 X1X2 = 11 X1X2 = 10
S0 00 00/ 00 01/ 00 11 / 00 11 / 00
S1 01 01/ 00 11 / 00 11 / 10 00 / 10
S2 11 11 / 00 00/ 10 00 / 11 00/ 11
S3 10 10 / 00 00 / 10 11 / 11 11 / 01
错误的冗余状态：
例如,X1X2 = 00,则 S3?S3
发生错误的原因：
按照上面化简后的激励函数重新得到实际的状态转换表现态 编码Q
1Q2
次态 Q1(N+1)Q2(N+1) / 输出 Z1Z2
X1X2 = 00 X1X2 = 01 X1X2 = 11 X1X2 = 10
S0 00 00 / 00 01 / 00 dd / dd 11 / 00
S1 01 01 / 00 11 / 00 dd / dd 00 / 10
S2 11 11 / 00 00 / 10 dd / dd 00/ 11
S3 10 00 / 00 01 / 00 dd / dd 11 / 00
修改方法：将冗余状态的次态和输出按照实际情况填入合理的值，修改后的状态转换表如下。按照此表进行设计，没有不合理的冗余状态。
由于输入 X1X2 = 11不可能发生，所以有关 X1X2 = 11的次态和输出不作调整。
例 2：五进制计数器现态 Q2Q1Q0 Q2(n+1)Q1(n+1)Q0(n+1)
S0 000 001
S1 001 010
S2 010 011
S3 011 100
S4 100 000
S5 101 000
S6 110 000
S7 111 000
为了避免出现自启动问题，在开始设计时将冗余状态指向 S0
Q 1 Q 0
Q 2 00 01 11 10
0 0 1 0
00 0 0
0
1
D 2
Q 1 Q 0
00 01 11 10
0 1 0 1
00 0 0
D 1
Q 1 Q 0
00 01 11 10
1 0 0 1
00 0 0
D 0
Q 2 Q 2
0
1
0
1
卡诺图中红色的 0是原来设计的冗余项。但是按照原来的设计，卡诺圈太小。所以可以修改设计，按照上图加大卡诺圈
（蓝色），相当于改变次态，仍然满足自启动要求。
S 2
S 3
S 4
S 1
S 6
S 0
S 5
有效循环
S 7
1,如果问题要求所有冗余状态都具有特定的输出和次态，则在开始进行设计时，除了明确不可能出现的状态以外，应该将所有的冗余状态的输出和次态考虑在状态转换表或状态转换图中。这样得到的设计可以满足问题的原始要求。
2,如果问题只要求满足自启动条件，则可以以任意项方式处理冗余状态，但是最后要进行自启动检查。
3,也可以以确定方式处理冗余状态，但可能得到的结果不是比较好的结果，所以应该进行优化检查。
4,无论上述哪种方法，若在检查后发现问题，都需要按照检查的结果重新修改设计。
冗余状态的处理规则现态 Q3Q2Q1Q0 Q3(n+1)Q2(n+1)Q1(n+1)Q0(n+1)
S0 0000 0001
S1 0001 0010
S2 0010 0011
S3 0011 0100
S4 0100 0101
S5 0101 0110
S6 0110 0111
S7 0111 1000
S8 1000 1001
S9 1001 0000
S10 1010 dddd
S11 1011 dddd
S12 1100 dddd
S13 1101 dddd
S14 1110 dddd
S15 1111 dddd
例：
十进制计数器问题
Q 1 Q 0
Q 3 Q 2
00 01 11 10
1 0 0 1
11 0 0
00
01
D 0
Q1Q0
00 01 11 10
0 1 0 1
10 1 0
D 1
Q1Q0
00 01 11 10
0 0 1 0
11 1 0
D 2
Q1Q0
00 01 11 10
0 0 0 0
00 0 1
D 3
d d d d
d1 0 d
d d d d
d0 0 d
d d d d
d0 0 d
d d d d
d1 0 d
Q3Q2Q3Q2Q3Q2
11
10
00
01
11
10
00
01
11
10
00
01
11
10
3102103
21020212
103101
00
QQQQQQD
QQQQQQQD
QQQQQD
QD
自启动检查：通过 S0
S1
S2
S6
S5
S4
S3
S 1 0
S9
S8
S7
S 1 1
S 1 4
S 1 3 S 1 2
S 1 5
用算法状态机方法设计同步时序电路状态名称摩尔型输出米利型输出输入条件0 1
状态框 判断框 条件输出框算法状态机方法是从计算机程序设计者那里借用了流程图的一些符号，构成算法状态机图（ ASM图）。
ASM图的主要包括以下 3种元件
S0
已收 0 元输出饮料投0,5 元
01
S1
已收 0,5 元投1 元投0,5 元
S2
已收 1 元
1
投1 元
0
0
投0,5 元
1 1
输出饮料
1 0
0
投1 元
01
输出找零售饮料机的 ASM图
S 0
S 1
S 2
00/00
00/00 00/00
01/00
10/10
01/00
10/00
01/10
10/11
X
1
X
2
/ Z
1
Z
2
售饮料机的状态转换图
S 0
X 1
01
S 1 X 2
S 2
1 0
S 3
S 1
S 0
S 3
1d 00
01
X 1 X 2
S 2
A S M 图 状态转换图优先级的处理例：反应时间测试电路该电路用来测量短跑运动员的反应速度，要求时间测量精确到毫秒。由于运动员的反应时间不可能小于 200ms，所以要求当反应时间小于 200ms时，要给出犯规信号。
晶体振荡器模1000
计数器
1kH z
计数控制电路
D A TA
锁存译码显示时钟发令枪运动员计数允许计数器清零计数值锁存时间阈值、计数值=200ms
G U N
A TH
C LR
EN
CP
LATC H
犯规指示
F OUL
LIMEN
系统复位
R ST
S 0 ( 准备)
CLR
ATH
01
S 4 ( 犯规)
FOUL
GUN
S 1 ( 计数1 )
EN
ATH
1
1 0
0
LIMEN
01
S 2 ( 计数2 )
EN
ATH
01
S 3 ( 锁存)
LATCH
RST
1 0
S 4 /
0001
S 0 /
1000
S 1 /
0100
00dd
1ddd
dddd
S 2 /
0100
S 3 /
0010
A TH / G U N / LIM EN / R ST
0d0d
ddd0
ddd1
1ddd
01dd
0d1d
1ddd
0ddd
C LR / EN / LA TC H / F OU L输出输入状态转换图状态分配时序电路的状态由状态变量（时序电路中记忆电路的输出）组合确定，将每个状态对应的状态变量组合分配一个唯一的二进制码的过程称为进行状态分配。
在时序电路设计中必须进行状态分配。分配之后用以代表状态变量的实际二进制码对于最终实现电路的代价有着重要影响。
状态分配问题没有通解。但是根据前人的经验，
按照一定的分配规则，可以得到比较好的分配结果。
!)!2(
)!12(
mn
S m
m
)!2(
)!2(
n
S m
m
用 m个状态变量实现 n个状态时，可能的状态分配数将等价的状态分配方案剔除后，以下函数给出了不等价的状态分配方案数。
状态分配规则 1
对于在相同输入条件下有相同次态的所有状态，在进行状态分配后，应当能形成一个质蕴含。
A
E
D
C
B
A
DC
B
Q 2 Q 1
Q 3
01
01
01
01
状态分配规则 2
对于一个现态的所有次态，在进行状态分配后，
最好能够形成一个质蕴含。
A
E
D
C
B
B EDC
Q 2 Q 1
Q 3
状态分配规则 3
有相同输出的状态最好给予相邻的状态分配。
对于状态分配的说明：
1、上述 3个规则，是一些经验规律，大部分情况下适用，
可能有不适用的例子。
2、对于大部分状态机，不可能全部满足 3条规则，只能按照实际情况运用。规则 1比规则 2的优先级要高，规则
3的优先级最低。除了涉及有大量输出的情况之外，一般很少考虑规则 3。有些资料根本就忽略规则 3。
例子参见讲义例 4－ 13。
4.4 时序电路的状态化简一、完全描述状态表的化简
“完全描述”是指在给定的输入条件下，表中所有的次态和输出均有确定值。
完全描述状态表的例：
现态次态 / 输出
X=0 X=1
S0 S0/0 S2/0
S1 S0/0 S2/0
S2 S1/0 S3/1
S3 S1/0 S3/0
状态的等价,
设某一时序电路（系统）内的两个状态 Si 和 Sj，如果用任意序列的输入加到此电路上，从 Si 或 Sj 出发所得到的输出序列都相同，则称状态 Si 和状态 Sj 等价。
可以证明，为了判别两个状态是否等价，所输入的任意序列只需要有限长度。具体地说，对于具有 n个状态的电路，最多只需要输入 n-1个符号的任意输入序列，
即可判别两个状态的等价与否。
等价的传递性,
若 Si 等价于 Sj，而 Sj 等价于 Sk，则 Si 等价于 Sk。
划分等价状态的规律：
1、如果某两个状态对应的输出不同，则它们显然是不等价的。
2、如果某两个状态在相同的输入下有相同的输出，并且次状态完全相等或为原状态时，这两个状态等价。
3、如果某两个状态在相同的输入下有相同的输出，但是次状态不相同，则此二状态等价与否还得视它们的次状态是否等价而定。
化简的方法：隐含表法
S 2
S 6S 5S 4S 3S 2S 1
S 7
S 6
S 5
S 4
S 3
S 1 S 3
S 7 S 6
S 5 S 3
S 7 S 6
S 2
S 6S 5S 4S 3S 2S 1
S 7
S 6
S 5
S 4
S 3
1,输出不同，肯定不等价，在相应的小方格中记以,×,号。
2,输出相同，并且在相同的输入下次态相同，或者仍为原状态对。肯定等价，在对应的小方格中记以,√”号 。
状态 次态 输出X=0 X=1 X=0 X=1
S1 S1 S7 0 1
S2 S2 S4 0 0
S3 S4 S5 1 0
S4 S7 S5 1 1
S5 S5 S7 0 1
S6 S6 S4 0 0
S7 S3 S6 0 13,输出相同，次态不同，记录次态对。
4,观察该次态对是否等价（等价传递）。若是则钩，若非则叉。
最后将所有等价态合并，就得到化简后的状态表。
对于上例，由于状态 S1 与 S5 等价，状态 S2 与 S6 等价，所以可以将这 4 个状态化简成 2 个状态，而其余 3个状态则无法进一步化简。
原状态 化简后 状态 次态 输出X=0 X=1 X=0 X=1
S1,S5 SA SA SE 0 1
S7 SE SC SB 0 1
S2,S6 SB SB SD 0 0
S3 SC SD SA 1 0
S4 SD SE SA 1 1
二、不完全描述状态表的化简不完全描述状态表：
表中某些状态在某些输入情况下的次态或输出没有确定的值，它们可以取 0也可以取 1，
状态 次态 输出X=0 X=1
S1 S2 S4 0
S2 S1 S4 d
S3 S3 S5 1
S4 d S5 1
相容：
1,输出相容,
如果两个输出序列的每一对有确定值的对应输出均相同，则称此两输出相容。
例,
00111
01110
11010
dZ
dZ
dZ
k
j
i
Zi与 Zj相容,Zj与 Zk也相容 。 而 Zi与 Zk则不相容。可见，相容不具有传递性 。
2,状态相容,
两个状态 Si 和 Sj，如果用任意序列的输入加到此系统上，从 Si 或 Sj 出发所得到的输出序列都相容，则称状态 Si 和状态 Sj 相容。
简单不相容,
在相同输入下，状态 Si 和 Sj 输出不相容。
简单相容,
对于任意输入，输出相容，有确定值的次状态相等或者仍为原状态。
状态 次态 输出X=0 X=1
S1 S3 d 1
S2 d S3 d
S3 d S2 d
S4 S4 d 0
S5 S5 S4 d
例：用 隐含表化简简单不相容简单相容简单相容简单相容简单相容简单相容简单相容
S 2
S 4S 3S 2S 1
S 5
S 4
S 3
S 3 S 5 S 2 S 4S 3 S 4
步骤 1、寻找相容关系打钩的为简单相容，打叉的为简单不相容。
其余三个状态对，既不是简单相容，也不是简单不相容。写上它们 有确定值的次态对 。
由于相容不具有传递性，所以不能简单地由简单相容外推两个不简单相容的状态是否相容。
例如上表中,S1与 S3相容,S3与 S4相容，但是 S1与 S4简单不相容。
同样，也不能推断上表中写上次态对的 3个方格,S1与 S5、
S2与 S5以及 S3与 S5的相容性。
若两个状态的输出相容，有确定值的次态不同，但是该次态对是简单相容的，则此两个状态仍然可能相容。我们称此两个状态 潜在相容 。
考察上述 3个状态对的次态对是否相容：其中两个次态对简单相容，一个次态对的次态对简单相容（潜在相容），所以上述 3个状态对均潜在相容。
步骤 2、寻找最大相容类集合所谓最大相容类集合，是含有不被其它相容类集合所覆盖的相容的一组状态或状态对。寻找最大相容类集合的目的是要将全体状态划分为尽可能少的组，每组内的状态都彼此相容。
利用合并图来寻找最大相容类集合：
合并图是将状态表中所有的状态以点的形式画在一个圆周上，然后将所有的相容状态对（包括潜在相容对）用直线连接起来。若在一组状态点中两两之间都有连线，
表示该组状态中所有状态两两相容，可以形成最大相容类。在图形上，它们将形成一个 内部两两相连的最大的多边形，该多边形的各个顶点就形成一个最大相容类集合。
S1
S5
S4S3
S2
在本例题中，共有 5个状态，构成的相容状态对有：
{S1,S2},{S1,S3},{S1,S5}
{S2,S3},{S2,S4},{S2,S5}
{S3,S4},{S3,S5}
{S4,S5}
最大相容类集合：
{ S1,S2,S3,S5 } 和 { S2,S3,S4,S5 }
S 2
S 4S 3S 2S 1
S 5
S 4
S 3
S 3 S 5 S 2 S 4S 3 S 4
潜在相容步骤 3、构成简化状态表由上面得到的最大相容类集合 {A},{B},…,{K} 可能有状态重叠，所以可以用其中的一部分作为一个简化状态。若用 {A'} 表示 {A} 的一个子集,{B'} 表示 {B} 的一个子集，等，则可以用 {A'},{B'},…,
{K'} 中的一部分 {A'},{B'},…,{N'}作为化简后的状态。其中
{A'},{B'},…,{N'} 应满足下列三个条件：
1,覆盖化,{A'},{B'},…,{N'}中必须包含原状态表中所有的状态。
2,最小化,由 {A'},{B'},…,{N'}构成的状态数目最少。也就是说，若在第一步得到 k个最大相容类集合，最后的简化状态个数可以小于 k。
3,闭合性,{A'},{B'},…,{N'}中任何一个新状态，它所包含的几个原来的状态在一定的输入下对应的次状态必须属于合并后的同一状态。否则简化表的次状态无法确定。
根据上述规则从最大相容类中选择化简后的状态集合来构成简化状态表，
其方法不是唯一的，部分地要凭经验进行试验。
回到原来的例子：
已经得到 2个最大相容类集合，分别是
{ S1,S2,S3,S5 } { S2,S3,S4,S5 }
根据前面所说的三个条件中的前面二个 —— 覆盖性 和 最小化考虑，选取上述 2个最大相容类集合中的部分子集，可以按下面的组合来选取简化后的状态组合：
(1) { S1,S5 } { S2,S3,S4 }
(2) { S1 } { S2,S3,S4,S5 }
(3) { S1,S2 } { S3,S4,S5 }
(4) { S1,S2,S3 } { S4,S5 }
上述 4个组合，每个组合中都包含了原来的所有状态，所以都满足覆盖性要求。这样组合以后的简化状态只有 2个，并且不可能进一步减少，所以满足最小化要求。
但是，方案 (1)和 (3)均不满足 闭合性 。
以方案 (1)为例，原始问题 S1,S5在输入 X = 0时对应的次状态分别为 S3和 S5。但如果按照 方案 (1)简化以后,S1和 S5将合并成一个状态，而它们的次状态 S3和 S5将分属于化简后的两个不同状态，这样一来，在化简后的状态表中新状态 { S1,S5 }
在输入 X = 0时的次态将无法选择。
状态 次态X=0
S1 S3
S5 S5
化简后的状态 次态X=0
SA={S1,S5} SA(S5)? SB(S3)?
SB={S2,S3,S4}
原始的状态转换关系 方案（ 1）的状态转换关系反之，方案 (2)和 (4)则可以满足上述三个条件。所以这两种简化方案是可取的。假定取第二种方案，以 SA代替 { S1 }而以 SB代替 { S2,S3,S4,S5 }，于是本问题的状态转换表便简化成只有两个状态，如下表所示。
状态次态输出X=0 X=1
SA SB d 1
SB SB SB 0
