6.5 同步 时序逻辑电路的设计同步时序逻辑电路设计又称 同步时序逻辑电路综合,其基本指导思想是用尽可能少的触发器和门电路来完成设计。
6.5.1 同步时序电路设计的一般步骤
1,作原始状态图和状态表；
2,对原始状态表化简；
3,状态分配；
4,选定触发器； 5.求出输出函数和激励函数表达式；
6,画出逻辑电路图。
6.5.2 建立原始状态图状态图是同步时序电路设计的依据,它必须正确反映设计要求 。 状态图的构成没有统一的方法,关键是要充分正确地理解设计要求,明确电路的输入条件和输出要求,输入和输出关系,以及状态的转换关系 。
原始状态图建立的一般过程为：
假定一个初始状态,由此出发,每加入一个输入信号,则记忆其次态,并标出其相应的输出值 。 次态可能为现态,已有状态或新的状态,直到没有新的状态为止 。 每个状态的各种可能的输入值都要考虑到 。
例,某序列检测器有一个输入端 x和一个输出端 Z。 从 x端输入一组按时间顺序排列的串行二进制码 。 当输入序列中出现 101时,
输出 Z＝ 1,否则 Z＝ 0。 试作出该 序 列 检 测 器 的 Mealy 型和
Moore型原始状态图和状态表 。
S0 S1
S2S3
1/1
1/0
0/0
0/0
0/0 1/00/0
1/0
电路的 Mealy 型状态表现态次态 /输出
x=0 x=1
S0
S1
S2
S3
S0/0
S2/0
S0/0
S2/0
S1/0
S1/0
S3/1
S1/0
电路的 Moore 型状态表现态次 态
x=0 x=1
S0
S1
S2
S3
S0
S2
S0
S2
S1
S1
S3
S1
输 出
Z
0
0
0
1
S0/0 S1/0
S2/0S3/1
1
0
1
0
0
10
1
例,假设某同步时序电路,用于检测串行输入的 8421BCD码,其输入的顺序是先高位后低位,
当出现非法数字 (即输入
1010,1011,1100，
1101,1110,1111)时,
电路的输出为 1。 试作出该时序电路的 Mealy型原始状态图和状态表 。
F
D
A
B C
E
G
0/0
1/00/0
1/0
0/0 1/0
0/0
1/0
解：
H
D
A
B
1/00/0
C
E
I
0/0
0/0
1/0
1/0
F G
0/0 1/0
N
J K
P
0/0
0/0
1/0
1/0
L M
0/0 1/0
0/01/0 0/01/0 0/0
1/0 0/01/0 0/01/0 0/11/1 0/11/1 0/11/1
电路的原始状态图现态 次态 /输出x=0 x=1
A
B
C
D
E
F
G
H
I
J
K
L
M
N
P
B/0
D/0
J/0
F/0
H/0
A/0
A/0
A/0
A/0
L/0
N/0
A/0
A/1
A/1
A/1
C/0
E/0
K/0
G/0
I/0
A/0
A/0
A/0
A/0
M/0
P/0
A/0
A/1
A/1
A/1
电路的原始状态表例,假设有一个三位二进制加、减法器（模 8计数器）
，当 X输入为 1时，实现加 1计数；当 X为 0时，实现减 1
计数，试作出该电路的 Moore型原始状态图和状态表。
解：
000 111 110 101 100 011 010 001
000 001 010 011 100 101 110 111
当 X为 0时：
当 X为 1时：
计数器的输出可为状态本身，亦可看作外部输出。
1
000
110
001
101
010111
100
011
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
原始状态图现态 次态 /输出x=0 x=1
000
001
010
011
100
101
110
111
111
000
001
010
011
100
101
110
001
010
011
100
101
110
111
000
原始状态表
6.5.3 状态简化一般情况下,原始状态图和原始状态表中存在着多余的状态 。 状态个数越多,电路中所需的触发器的数目也越多,制造成本就越高 。 为降低制造成本,需要去掉多余的状态,即要进行 状态简化 。
所谓 状态简化,就是要获得一个最小化的状态表 。 这个表不仅能正确地反映设计的全部要求,
而且状态的数目最少 。
完全确定状态表,状态表中的 次态和输出都有确定的状态和确定的输出值。
等效状态,设状态 S1和 S2是完全确定状态表中的两个状态,如果对于所有可能的输入序列,分别从状态
S1 和状态 S2出发,所得到的输出响应序列完全相同,则状态 S1和 S2是等效的,记作 (S1,S2),或说,
状态 S1和 S2是等效对 。 等效状态可以合并 。
一,完全确定状态表的简化
S1
S'1
S2
S'2
S3
S'3
S4
S'4
0/0
0/0
0/1
0/1
1/1
1/1
…
…
等效状态传递性,(S1,S2),(S2,S3)→ (S1,S3)
等效类,彼此等效的状态集合
最大等效类,不被其它等效类所包含的等效类 。
一个状态也可能是一个最大等效类 。
状态简化的任务是要在原始状态表中找出全部最大等效类 (最大等效类集合 ),并将每一个最大等效类用一个状态来表示 。
判别方法：
第一,它们的输出完全相同；
假定状态 S1和 S2是完全确定原始状态表中的两个现态,那么 S1和 S2等效的条件可归纳为在输入的各种取值组合下：
(1) 次态相同；
第二、它们的次态满足下列条件之一，即
(2) 次态交错；
(3) 次态循环； (4) 次态对等效。
Si
Sj
1/0
Sl
0/1
0/1
Sk
1/0
次态相同次态相同或交错
Si
Sj
0/0
1/0 1/0 Sk
0/0
次态交错或相同或循环
Si
Sj
1/0 1/0
Sk
Sl
0/0
0/0
0/1
0/1
Sm
1/0
1/0
次态交错或等效 (Sk,Sl等效 )
Si
Sj
1/01/0
Sl
Sk
0/1
0/1
1,观察法化简例,简化下表所示的状态表现态次态 /输出
x=0 x=1
A
B
C
D
A/0
A/0
A/0
A/0
B/0
C/0
D/1
D/1
解,? A和 B,C和 D的输出完全相等；
C和 D在输入的各种取值组合下，次态相同，因此 C和 D等效；
最大等效类为 {A},{B}，
{C,D},分别用 A',B',C'表示；
A和 B在 x=1时的次态不满足四条件之一，因此 A
和 B不等效 ;
现态次态 /输出
x=0 x=1
A
B
C
D
A/0
A/0
A/0
A/0
B/0
C/0
D/1
D/1
最小化状态表为：
现态次态 /输出
x=0 x=1
A'
B'
C'
A'/0
A'/0
A'/0
B'/0
C'/0
C'/1
现态次态 /输出
x=0 x=1
A
B
C
D
A/0
A/0
A/0
A/0
B/0
C/0
D/1
D/1
2,隐含表法化简例,简化下表所示的状态表现态 次态 /输出x=0 x=1
A
B
C
D
E
F
G
C/0
F/0
D/0
D/1
C/0
D/0
C/1
B/1
A/1
G/0
E/0
E/1
G/0
D/0
解,? 作隐含表? 顺序比较，寻找等效状态对
状态对等效，打
,√,；
状态对不等效，打
,╳,；
状态对是否等效需进一步检查，则标记次态对。
A B C D E F
G
F
E
D
C
B CF
BE AECF
CD
DE
现态 次态 /输出x=0 x=1
A
B
C
D
E
F
G
C/0
F/0
D/0
D/1
C/0
D/0
C/1
B/1
A/1
G/0
E/0
E/1
G/0
D/0
A B C D E F
G
F
E
D
C
B CF
BE AECF
CD
DE
处于循环链中的每一个状态对都是等效状态对,
一共 四个等效对 (A,B),(A,E),(B,E),(C,F)。
关联比较,
确定等效状态对
AE→ BE→ CF√
AB→CF √
现态次态 /输出
x=0 x=1
a
b
c
d
b/0
c/0
c/1
b/1
a/1
d/0
a/0
c/0
确定最大等效类，作最小化状态表,
四个等效对 (A,B),(A,E),(B,E),(C,F)
四个最大等效类 (A,B,E),(C,F),(D),(G)
令以上四个最大等效类依次为 a,b,c,d.
现态 次态 /输出x=0 x=1
A
B
C
D
E
F
G
C/0
F/0
D/0
D/1
C/0
D/0
C/1
B/1
A/1
G/0
E/0
E/1
G/0
D/0
二,不完全确定状态表的简化不完全确定状态表,状态表中存在不确 定 的次态或输出,这些不确定的次态或输出将有利于状态简化 。
相容状态：设状态 S1和 S2是不完全确定状态表中 的两个状态,如果对于所有的有效输入序列,
分别从状态 S1和 S2出发,所得到的输出响应序列
(除不确定的那些位之外 )是完全相同的,那么状态 S1和 S2是相容的,或者说状 态 S1和 S2是相容对,
记作 (S1,S2)。 相容状态可以合并 。
例,设计一个,1111”序列检测器，使其成为爆炸装置的引爆控制器。假定工作条件为：平时无 1输入，
Z一直处于 0状态；当连续输入 4个 1时（不允许出现
0）,Z=1引爆，整个装置不存在。
A
D
B
C
1/0
1/0
1/0
0/0
0/d
0/d
0/d
1/1
d d d
d
现态次态 /输出
x=0 x=1
A
B
C
D
A/0
d/d
d/d
d/d
B/0
C/0
D/0
d/1
相容状态无传递性：
Si
Sj
1/1
0/0
0/0
0/0
Sk
0/0
Sl
1/0
1/d
Si和 Sj相容；
Sj和 Sk相容；
但 Si和 Sk不相容。
最大相容类：不被其它相容类所包含的相容类
相容类：彼此相容的状态集合判别方法：
在不完全确定状态表中判断两个状态是否相容也是根据表中给出的次态和输出来决定的 。
假定状态 Si和 Sj是不完全确定状态表中的两个现态,那么状态 Si和 Sj相容的条件可归纳为在输入的各种取值组合下,
第一,它们的输出完全相同,或者其中的一个 (或两个 ) 输出为任意值 。
第二、它们的次态满足下列条件之一：
(1) 次态相同； (2) 次态交错； (3) 次态循环；
(4) 其中的一个 (或两个 )为任意状态 ; (5) 次态相容；
例,简化下表所示的状态表现 态次 态
x=0 x=1
A
B
C
D
E
F
B
B
A
d
F
d
D
D
E
E
d
C
输 出
0
d
1
1
1
d
解,? 作隐含表；? 顺序比较，
寻找相容对；
AB
DE
A B C D E
F
E
D
C
B
DE
BF AF
CE CECDCD
现 态次 态
x=0 x=1
A
B
C
D
E
F
B
B
A
d
F
d
D
D
E
E
d
C
输 出
0
d
1
1
1
d
CE→AF √
CF→CE √
DF→CE √
以上三步与确定状态表的化简相同
关联比较，确定相容对；
AB
DE
A B C D E
F
E
D
C
B
DE
BF AF
CE CECDCD
AF→ CD √
BC→ AB √
DE √
BD→DE √
BE→BF→CD √
全部相容对,(A,B),(A,F),(B,C),(B,D),(B,E),
(B,F),(C,D),(C,E),(C,F),(D,F),(D,E),(E,F)。
作状态合并图，求最大相容类。
S1
S2 S3
3状态相容
S4
S1
S2
S3
4状态相容
S1
S2
S3S4
S5
5状态相容
A
B
C
D
F
E
本例状态合并图，最大相容类是 (A,B,F),(B,C,D,E,F)。
全部相容状态对：
(A,B),(A,F),(B,C),
(B,D),(B,E),(B,F),
(C,D),(C,E),(C,F),
(D,F),(D,E),(E,F)。
作最小化状态表,最小化状态表 (又称最小闭覆盖 )
应满足下列三个条件：
覆盖性－－所选相容类集合应包含原始状态表中的全部状态。
最小性－－所选相容类集合中相容类的个数应最少。
闭合性－－所选相容类集合中的任一相容类，在原始状态表中任一输入条件下产生的次态应该属于该集合中的某一个相容类。
采用闭覆盖表来反映所选相容类集合的覆盖和闭合情况。本例的闭覆盖表为
CDE
最大相容类
ABF
BCDEF
A B C D E F
√ √
√ √ √ √
√
√
覆 盖 闭 合
x=0 x=1
B
ABF
CD
现态次态
x=0 x=1
A
B
C
D
E
F
B
B
A
d
F
d
D
D
E
E
d
C
输出
0
d
1
1
1
d
所 选 相 容 类 集 合 {(A,B,F),
(B,C,D,E,F)} 满足最小闭覆盖条件,令 A表示 (A,B,F)，
C表示 (B,C,D,E,F)可得：
现 态 次 态x=0 x=1
A
C
A,C
A
C
C
输 出
0
1
现 态 次 态x=0 x=1
A
C
d
A
C
C
输 出
0
1
由于该表中只有两个状态,进一步可以得到：
现态次态
x=0 x=1
A
B
C
D
E
F
B
B
A
d
F
d
D
D
E
E
d
C
输出
0
d
1
1
1
d
CDE
最大相容类
ABF
BCDEF
A B C D E F
√ √
√ √ √ √
√
√
覆 盖 闭 合
x=0 x=1
B
ABF
CD
例,化简下表所示的状态表现态次态 /输出
x=0 x=1
A
B
C
D
E
D/d
E/0
D/0
C/d
C/1
A/d
A/d
B/d
C/d
B/d
解,作隐含表，寻找相容状态对
A B C D
E
D
C
B
AB
DEAC
CE
CD
AC
AB
CD
AB
DE
BC
BC
由上图得相容状态对为 (A,B),(A,C),(A,D),(A,E),
(B,C),(C,D),(D,E)
AB→DE→BC √
AC→AB √
BD→ AC √CE ╳
AE→ ABCD√√
AD→ →BC √CDAC √
现态次态 /输出
x=0 x=1
A
B
C
D
E
D/d
E/0
D/0
C/d
C/1
A/d
A/d
B/d
C/d
B/d
作状态合并图，寻找最大相容类
A
B
CD
E
得最大相容类为 (A,B,C),(A,C,D),(A,D,E)
作最小化状态表若选相容类集合为 {(A,B,C),
(A,D,E)}则下表表明它不满足闭合要求相容类
ABC
ADE
A B C D E
√
√
√ √
√ √
覆 盖 闭 合
x=0 x=1
DE
CD ABC
AB
A
B
CD
E
现态次态 /输出
x=0 x=1
A
B
C
D
E
D/d
E/0
D/0
C/d
C/1
A/d
A/d
B/d
C/d
B/d
(A,B,C),(A,C,D),(A,D,E)
但如果选相容类 (A,B,C)和
(D,E)则能满足最小闭覆盖的要求相容类
ABC
DE
A B C D E
A B C
D E
覆 盖 闭 合
x=0 x=1
DE
C BC
AB
A
B
CD
E
现态次态 /输出
x=0 x=1
A
B
C
D
E
D/d
E/0
D/0
C/d
C/1
A/d
A/d
B/d
C/d
B/d
令 A'=(A,B,C),B'=(D,E),进一步可得：
现态次态 /输出
x=0 x=1
A'
B'
B' /0
A' /1
A'/d
A'/d
寻找最小闭覆盖通常不是一件容易的事情，其结果往往不唯一。
现态次态 /输出
x=0 x=1
A
B
C
D
E
D/d
E/0
D/0
C/d
C/1
A/d
A/d
B/d
C/d
B/d
6.5.4 状态编码 (状态分配 )
给最小化状态表中的每一个状态指定一个二进制代码,形成二进制状态表 。
通常情况下,状态编码的方案不一样,所得到的输出函数和激励函数的表达式也不同,由此而设计出来的电路复杂度也不同 。 状态分配的任务是,决定编码的长度；寻找一种最佳的或接近最佳的状态分配方案 。
设最小化状态表中的状态数为 N,编码长度为 n,N和 n的关系为 2n-1<N?2n
用 2n种组合来对 N个状态进行分配时，可能出现的分配方案的总数 Ks为
!)2(
!2AK
Nn
n
N
ns －
例如,n=2,N=4时 有方 案状态 1 2 3 4 5 6 7 8 9 10 11 12
A
B
C
D
00 10 01 11 00 01 10 11 00 10 01 11
01 11 00 10 10 11 00 01 11 01 10 00
11 01 10 00 11 10 01 00 01 11 00 10
10 00 11 01 01 00 11 10 10 00 11 01
方 案状态 13 14 15 16 17 18 19 20 21 22 23 24
A
B
C
D
00 01 10 11 00 10 01 11 00 01 10 11
11 10 01 00 10 00 11 01 01 00 11 10
10 11 00 01 01 11 00 10 10 11 00 01
01 00 11 10 11 01 10 00 11 10 01 00
但是，在 Ks种方案中只有三种是独立的 (真正不相同的 )方案
!)!2(
)!12(
=K nNn
n
u
－
－
然而,当 n较大时,Ku仍然很大,要真正找到最佳的分配方案是十分困难的,况且分配方案的好坏还与所采用的触发器的类型有关 。 因此,
实际应用时都是采用工程的方法,依据以下四条件原则来进行状态分配 。
状态分配的基本原则有四条：
(1) 在相同输入条件下具有相同次态的现态,应尽可能分配相邻的二进制代码；
(2) 在相邻输入条件,同一现态的次态应尽可能分配相邻的二进制代码；
(3) 输出 完全相同 的现态应尽可能分配相邻的二进制代码；
(4) 最小化状态表中出现次数最多的状态或初始状态应分配逻辑 0。
一般情况下,第一条原则较为重要,需优先考虑,其次要考虑由前三条原则得到的应分配相邻代码的状态对出现的次数,次数多的状态对应优先分配相邻的二进制代码 。
例,对下表所示的状态表进行状态分配现态次态 /输出
x=0 x=1
A
B
C
D
C/0
C/0
B/0
A/1
D/0
A/0
D/0
B/1
解,? 确定 n=2
确定 分配由规则 (1)得 A和 B,A和 C
应相邻；
由规则 (2)得 C和 D,C和
A,B和 D,A和 B应相邻；
由规则 (3)得 A,B,C 三者应相邻,即 AB,AC,BC应相邻；
由规则 (4)得 A分配为逻辑 0。
现态次态 /输出
x=0 x=1
A
B
C
D
C/0
C/0
B/0
A/1
D/0
A/0
D/0
B/1
A B
DC
0 1
0
1
y2
y1 A:
B:
C:
D:
y2 y1
0 0
1 0
0 1
1 1
由规则 (1)得
A和 B,A和 C应相邻；
由规则 (2)得
C和 D,C和 A,B和
D,A和 B应相邻；
由规则 (3)得
A,B,C 三者应相邻,即 A和 B,A和
C,B和 C应相邻；
由规则 (4)得
A分配为逻辑 0。
最后我们可以得到二进制状态表现态
y2 y1
次态 y2(n+1)y1(n+1)/输出
x=0 x=1
0 0
0 1
1 1
1 0
01/0
10/0
00/1
01/0
11/0
11/0
10/1
00/0
注意,有时满足分配原则的分配方案不唯一，
这时可任选一种。
现态次态 /输出
x=0 x=1
A
B
C
D
C/0
C/0
B/0
A/1
D/0
A/0
D/0
B/1
确定激励函数和输出函数
1,触发器的激励表触发器的激励表反映触发器从某种现态转换到某种次态时,对触发器输入 (激励 )的要求 。 在这种表中,现态和次态作为自变量,输入 (激励 )
作为因变量 。 触发器的激励表可由触发器的状态表直接推出 。
Q Q(n+1) R S
d 0
0 1
1 0
0 d
0 0
0 1
1 0
1 1
Q Q(n+1) D
0
1
0
1
0 0
0 1
1 0
1 1
R-S触发器激励表 D触发器激励表
Q Q(n+1) J K
0 d
1 d
d 1
d 0
0 0
0 1
1 0
1 1
Q Q(n+1) T
0
1
1
0
0 0
0 1
1 0
1 1
J-K触发器激励表 T触发器激励表
2,确定激励函数两种方法,根据次态方程来确定和通过激励表来确定 。
例,若用 J-K触发器实现下表所示的二进制状态表,试写出激励和输出函数。
现 态
y2 y1
次态 y2(n+1)y1(n+1)/输出 Z
x=0 x=1
0 0
0 1
1 1
1 0
11/0
00/0
00/1
01/0
01/0
00/1
10/1
11/0
解,确定激励函数现态
y2 y1
次态
y2(n+1) y1(n+1)
0 0
0 1
1 1
1 0
0 0
0 1
1 1
1 0
输入
x
激励函数
J2K2J1K1
1 1
0 0
0 0
0 1
0 1
0 0
1 0
1 1
1 d 1 d
0 d d 1
d 1 d 1
d 1 1 d
0 d 1 d
0 d d 1
d 0 d 1
d 0 1 d
0
0
0
0
1
1
1
1
现态
y2 y1
y2(n+1)y1(n+1)/输出 Z
x=0 x=1
0 0
0 1
1 1
1 0
11/0
00/0
00/1
01/0
01/0
00/1
10/1
11/0
Q Q(n+1) J K
0 d
1 d
d 1
d 0
0 0
0 1
1 0
1 1
J1=1
12J yx＝
现态
y2 y1
次态
y2(n+1) y1(n+1)
0 0
0 1
1 1
1 0
0 0
0 1
1 1
1 0
输入
x
激励函数
J2K2J1K1
1 1
0 0
0 0
0 1
0 1
0 0
1 0
1 1
1 d 1 d
0 d d 1
d 1 d 1
d 1 1 d
0 d 1 d
0 d d 1
d 0 d 1
d 0 1 d
0
0
0
0
1
1
1
1
xy2
1 d
d0
00 01
0
1
y1 11 10
d 0
d 0J2
xy2
d 1
1d
00 01
0
1
y1 11 10
0 d
0 dK2
xy2
1 1
dd
00 01
0
1
y1 11 10
1 1
d dJ1
xy2
d d
11
00 01
0
1
y1 11 10
d d
1 1K1
x＝2K
K1=1
Z=y2y1+xy1
0 0
10
00 01
0
1
y1
xy2
11 10
0 0
1 1
Z
确定输出函数现态
y2 y1
y2(n+1)y1(n+1)/输出 Z
x=0 x=1
0 0
0 1
1 1
1 0
11/0
00/0
00/1
01/0
01/0
00/1
10/1
11/0
画出逻辑电路图先画出触发器并给触发器编号,再根据激励函数和输出函数画出组合逻辑部分的电路,最后画出同步时钟信号线 。
1
D1 CD2 C
y2
CP
x
&
y1
z
1
y2
1&
y1
11D y?
2122122 +++=+D xyyyxyxyyx＝
)+(=+ =Z 21121 yxyyyxy
例如：
6.5.1 同步时序电路设计的一般步骤
1,作原始状态图和状态表；
2,对原始状态表化简；
3,状态分配；
4,选定触发器； 5.求出输出函数和激励函数表达式；
6,画出逻辑电路图。
6.5.2 建立原始状态图状态图是同步时序电路设计的依据,它必须正确反映设计要求 。 状态图的构成没有统一的方法,关键是要充分正确地理解设计要求,明确电路的输入条件和输出要求,输入和输出关系,以及状态的转换关系 。
原始状态图建立的一般过程为：
假定一个初始状态,由此出发,每加入一个输入信号,则记忆其次态,并标出其相应的输出值 。 次态可能为现态,已有状态或新的状态,直到没有新的状态为止 。 每个状态的各种可能的输入值都要考虑到 。
例,某序列检测器有一个输入端 x和一个输出端 Z。 从 x端输入一组按时间顺序排列的串行二进制码 。 当输入序列中出现 101时,
输出 Z＝ 1,否则 Z＝ 0。 试作出该 序 列 检 测 器 的 Mealy 型和
Moore型原始状态图和状态表 。
S0 S1
S2S3
1/1
1/0
0/0
0/0
0/0 1/00/0
1/0
电路的 Mealy 型状态表现态次态 /输出
x=0 x=1
S0
S1
S2
S3
S0/0
S2/0
S0/0
S2/0
S1/0
S1/0
S3/1
S1/0
电路的 Moore 型状态表现态次 态
x=0 x=1
S0
S1
S2
S3
S0
S2
S0
S2
S1
S1
S3
S1
输 出
Z
0
0
0
1
S0/0 S1/0
S2/0S3/1
1
0
1
0
0
10
1
例,假设某同步时序电路,用于检测串行输入的 8421BCD码,其输入的顺序是先高位后低位,
当出现非法数字 (即输入
1010,1011,1100，
1101,1110,1111)时,
电路的输出为 1。 试作出该时序电路的 Mealy型原始状态图和状态表 。
F
D
A
B C
E
G
0/0
1/00/0
1/0
0/0 1/0
0/0
1/0
解：
H
D
A
B
1/00/0
C
E
I
0/0
0/0
1/0
1/0
F G
0/0 1/0
N
J K
P
0/0
0/0
1/0
1/0
L M
0/0 1/0
0/01/0 0/01/0 0/0
1/0 0/01/0 0/01/0 0/11/1 0/11/1 0/11/1
电路的原始状态图现态 次态 /输出x=0 x=1
A
B
C
D
E
F
G
H
I
J
K
L
M
N
P
B/0
D/0
J/0
F/0
H/0
A/0
A/0
A/0
A/0
L/0
N/0
A/0
A/1
A/1
A/1
C/0
E/0
K/0
G/0
I/0
A/0
A/0
A/0
A/0
M/0
P/0
A/0
A/1
A/1
A/1
电路的原始状态表例,假设有一个三位二进制加、减法器（模 8计数器）
，当 X输入为 1时，实现加 1计数；当 X为 0时，实现减 1
计数，试作出该电路的 Moore型原始状态图和状态表。
解：
000 111 110 101 100 011 010 001
000 001 010 011 100 101 110 111
当 X为 0时：
当 X为 1时：
计数器的输出可为状态本身，亦可看作外部输出。
1
000
110
001
101
010111
100
011
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
原始状态图现态 次态 /输出x=0 x=1
000
001
010
011
100
101
110
111
111
000
001
010
011
100
101
110
001
010
011
100
101
110
111
000
原始状态表
6.5.3 状态简化一般情况下,原始状态图和原始状态表中存在着多余的状态 。 状态个数越多,电路中所需的触发器的数目也越多,制造成本就越高 。 为降低制造成本,需要去掉多余的状态,即要进行 状态简化 。
所谓 状态简化,就是要获得一个最小化的状态表 。 这个表不仅能正确地反映设计的全部要求,
而且状态的数目最少 。
完全确定状态表,状态表中的 次态和输出都有确定的状态和确定的输出值。
等效状态,设状态 S1和 S2是完全确定状态表中的两个状态,如果对于所有可能的输入序列,分别从状态
S1 和状态 S2出发,所得到的输出响应序列完全相同,则状态 S1和 S2是等效的,记作 (S1,S2),或说,
状态 S1和 S2是等效对 。 等效状态可以合并 。
一,完全确定状态表的简化
S1
S'1
S2
S'2
S3
S'3
S4
S'4
0/0
0/0
0/1
0/1
1/1
1/1
…
…
等效状态传递性,(S1,S2),(S2,S3)→ (S1,S3)
等效类,彼此等效的状态集合
最大等效类,不被其它等效类所包含的等效类 。
一个状态也可能是一个最大等效类 。
状态简化的任务是要在原始状态表中找出全部最大等效类 (最大等效类集合 ),并将每一个最大等效类用一个状态来表示 。
判别方法：
第一,它们的输出完全相同；
假定状态 S1和 S2是完全确定原始状态表中的两个现态,那么 S1和 S2等效的条件可归纳为在输入的各种取值组合下：
(1) 次态相同；
第二、它们的次态满足下列条件之一，即
(2) 次态交错；
(3) 次态循环； (4) 次态对等效。
Si
Sj
1/0
Sl
0/1
0/1
Sk
1/0
次态相同次态相同或交错
Si
Sj
0/0
1/0 1/0 Sk
0/0
次态交错或相同或循环
Si
Sj
1/0 1/0
Sk
Sl
0/0
0/0
0/1
0/1
Sm
1/0
1/0
次态交错或等效 (Sk,Sl等效 )
Si
Sj
1/01/0
Sl
Sk
0/1
0/1
1,观察法化简例,简化下表所示的状态表现态次态 /输出
x=0 x=1
A
B
C
D
A/0
A/0
A/0
A/0
B/0
C/0
D/1
D/1
解,? A和 B,C和 D的输出完全相等；
C和 D在输入的各种取值组合下，次态相同，因此 C和 D等效；
最大等效类为 {A},{B}，
{C,D},分别用 A',B',C'表示；
A和 B在 x=1时的次态不满足四条件之一，因此 A
和 B不等效 ;
现态次态 /输出
x=0 x=1
A
B
C
D
A/0
A/0
A/0
A/0
B/0
C/0
D/1
D/1
最小化状态表为：
现态次态 /输出
x=0 x=1
A'
B'
C'
A'/0
A'/0
A'/0
B'/0
C'/0
C'/1
现态次态 /输出
x=0 x=1
A
B
C
D
A/0
A/0
A/0
A/0
B/0
C/0
D/1
D/1
2,隐含表法化简例,简化下表所示的状态表现态 次态 /输出x=0 x=1
A
B
C
D
E
F
G
C/0
F/0
D/0
D/1
C/0
D/0
C/1
B/1
A/1
G/0
E/0
E/1
G/0
D/0
解,? 作隐含表? 顺序比较，寻找等效状态对
状态对等效，打
,√,；
状态对不等效，打
,╳,；
状态对是否等效需进一步检查，则标记次态对。
A B C D E F
G
F
E
D
C
B CF
BE AECF
CD
DE
现态 次态 /输出x=0 x=1
A
B
C
D
E
F
G
C/0
F/0
D/0
D/1
C/0
D/0
C/1
B/1
A/1
G/0
E/0
E/1
G/0
D/0
A B C D E F
G
F
E
D
C
B CF
BE AECF
CD
DE
处于循环链中的每一个状态对都是等效状态对,
一共 四个等效对 (A,B),(A,E),(B,E),(C,F)。
关联比较,
确定等效状态对
AE→ BE→ CF√
AB→CF √
现态次态 /输出
x=0 x=1
a
b
c
d
b/0
c/0
c/1
b/1
a/1
d/0
a/0
c/0
确定最大等效类，作最小化状态表,
四个等效对 (A,B),(A,E),(B,E),(C,F)
四个最大等效类 (A,B,E),(C,F),(D),(G)
令以上四个最大等效类依次为 a,b,c,d.
现态 次态 /输出x=0 x=1
A
B
C
D
E
F
G
C/0
F/0
D/0
D/1
C/0
D/0
C/1
B/1
A/1
G/0
E/0
E/1
G/0
D/0
二,不完全确定状态表的简化不完全确定状态表,状态表中存在不确 定 的次态或输出,这些不确定的次态或输出将有利于状态简化 。
相容状态：设状态 S1和 S2是不完全确定状态表中 的两个状态,如果对于所有的有效输入序列,
分别从状态 S1和 S2出发,所得到的输出响应序列
(除不确定的那些位之外 )是完全相同的,那么状态 S1和 S2是相容的,或者说状 态 S1和 S2是相容对,
记作 (S1,S2)。 相容状态可以合并 。
例,设计一个,1111”序列检测器，使其成为爆炸装置的引爆控制器。假定工作条件为：平时无 1输入，
Z一直处于 0状态；当连续输入 4个 1时（不允许出现
0）,Z=1引爆，整个装置不存在。
A
D
B
C
1/0
1/0
1/0
0/0
0/d
0/d
0/d
1/1
d d d
d
现态次态 /输出
x=0 x=1
A
B
C
D
A/0
d/d
d/d
d/d
B/0
C/0
D/0
d/1
相容状态无传递性：
Si
Sj
1/1
0/0
0/0
0/0
Sk
0/0
Sl
1/0
1/d
Si和 Sj相容；
Sj和 Sk相容；
但 Si和 Sk不相容。
最大相容类：不被其它相容类所包含的相容类
相容类：彼此相容的状态集合判别方法：
在不完全确定状态表中判断两个状态是否相容也是根据表中给出的次态和输出来决定的 。
假定状态 Si和 Sj是不完全确定状态表中的两个现态,那么状态 Si和 Sj相容的条件可归纳为在输入的各种取值组合下,
第一,它们的输出完全相同,或者其中的一个 (或两个 ) 输出为任意值 。
第二、它们的次态满足下列条件之一：
(1) 次态相同； (2) 次态交错； (3) 次态循环；
(4) 其中的一个 (或两个 )为任意状态 ; (5) 次态相容；
例,简化下表所示的状态表现 态次 态
x=0 x=1
A
B
C
D
E
F
B
B
A
d
F
d
D
D
E
E
d
C
输 出
0
d
1
1
1
d
解,? 作隐含表；? 顺序比较，
寻找相容对；
AB
DE
A B C D E
F
E
D
C
B
DE
BF AF
CE CECDCD
现 态次 态
x=0 x=1
A
B
C
D
E
F
B
B
A
d
F
d
D
D
E
E
d
C
输 出
0
d
1
1
1
d
CE→AF √
CF→CE √
DF→CE √
以上三步与确定状态表的化简相同
关联比较，确定相容对；
AB
DE
A B C D E
F
E
D
C
B
DE
BF AF
CE CECDCD
AF→ CD √
BC→ AB √
DE √
BD→DE √
BE→BF→CD √
全部相容对,(A,B),(A,F),(B,C),(B,D),(B,E),
(B,F),(C,D),(C,E),(C,F),(D,F),(D,E),(E,F)。
作状态合并图，求最大相容类。
S1
S2 S3
3状态相容
S4
S1
S2
S3
4状态相容
S1
S2
S3S4
S5
5状态相容
A
B
C
D
F
E
本例状态合并图，最大相容类是 (A,B,F),(B,C,D,E,F)。
全部相容状态对：
(A,B),(A,F),(B,C),
(B,D),(B,E),(B,F),
(C,D),(C,E),(C,F),
(D,F),(D,E),(E,F)。
作最小化状态表,最小化状态表 (又称最小闭覆盖 )
应满足下列三个条件：
覆盖性－－所选相容类集合应包含原始状态表中的全部状态。
最小性－－所选相容类集合中相容类的个数应最少。
闭合性－－所选相容类集合中的任一相容类，在原始状态表中任一输入条件下产生的次态应该属于该集合中的某一个相容类。
采用闭覆盖表来反映所选相容类集合的覆盖和闭合情况。本例的闭覆盖表为
CDE
最大相容类
ABF
BCDEF
A B C D E F
√ √
√ √ √ √
√
√
覆 盖 闭 合
x=0 x=1
B
ABF
CD
现态次态
x=0 x=1
A
B
C
D
E
F
B
B
A
d
F
d
D
D
E
E
d
C
输出
0
d
1
1
1
d
所 选 相 容 类 集 合 {(A,B,F),
(B,C,D,E,F)} 满足最小闭覆盖条件,令 A表示 (A,B,F)，
C表示 (B,C,D,E,F)可得：
现 态 次 态x=0 x=1
A
C
A,C
A
C
C
输 出
0
1
现 态 次 态x=0 x=1
A
C
d
A
C
C
输 出
0
1
由于该表中只有两个状态,进一步可以得到：
现态次态
x=0 x=1
A
B
C
D
E
F
B
B
A
d
F
d
D
D
E
E
d
C
输出
0
d
1
1
1
d
CDE
最大相容类
ABF
BCDEF
A B C D E F
√ √
√ √ √ √
√
√
覆 盖 闭 合
x=0 x=1
B
ABF
CD
例,化简下表所示的状态表现态次态 /输出
x=0 x=1
A
B
C
D
E
D/d
E/0
D/0
C/d
C/1
A/d
A/d
B/d
C/d
B/d
解,作隐含表，寻找相容状态对
A B C D
E
D
C
B
AB
DEAC
CE
CD
AC
AB
CD
AB
DE
BC
BC
由上图得相容状态对为 (A,B),(A,C),(A,D),(A,E),
(B,C),(C,D),(D,E)
AB→DE→BC √
AC→AB √
BD→ AC √CE ╳
AE→ ABCD√√
AD→ →BC √CDAC √
现态次态 /输出
x=0 x=1
A
B
C
D
E
D/d
E/0
D/0
C/d
C/1
A/d
A/d
B/d
C/d
B/d
作状态合并图，寻找最大相容类
A
B
CD
E
得最大相容类为 (A,B,C),(A,C,D),(A,D,E)
作最小化状态表若选相容类集合为 {(A,B,C),
(A,D,E)}则下表表明它不满足闭合要求相容类
ABC
ADE
A B C D E
√
√
√ √
√ √
覆 盖 闭 合
x=0 x=1
DE
CD ABC
AB
A
B
CD
E
现态次态 /输出
x=0 x=1
A
B
C
D
E
D/d
E/0
D/0
C/d
C/1
A/d
A/d
B/d
C/d
B/d
(A,B,C),(A,C,D),(A,D,E)
但如果选相容类 (A,B,C)和
(D,E)则能满足最小闭覆盖的要求相容类
ABC
DE
A B C D E
A B C
D E
覆 盖 闭 合
x=0 x=1
DE
C BC
AB
A
B
CD
E
现态次态 /输出
x=0 x=1
A
B
C
D
E
D/d
E/0
D/0
C/d
C/1
A/d
A/d
B/d
C/d
B/d
令 A'=(A,B,C),B'=(D,E),进一步可得：
现态次态 /输出
x=0 x=1
A'
B'
B' /0
A' /1
A'/d
A'/d
寻找最小闭覆盖通常不是一件容易的事情，其结果往往不唯一。
现态次态 /输出
x=0 x=1
A
B
C
D
E
D/d
E/0
D/0
C/d
C/1
A/d
A/d
B/d
C/d
B/d
6.5.4 状态编码 (状态分配 )
给最小化状态表中的每一个状态指定一个二进制代码,形成二进制状态表 。
通常情况下,状态编码的方案不一样,所得到的输出函数和激励函数的表达式也不同,由此而设计出来的电路复杂度也不同 。 状态分配的任务是,决定编码的长度；寻找一种最佳的或接近最佳的状态分配方案 。
设最小化状态表中的状态数为 N,编码长度为 n,N和 n的关系为 2n-1<N?2n
用 2n种组合来对 N个状态进行分配时，可能出现的分配方案的总数 Ks为
!)2(
!2AK
Nn
n
N
ns －
例如,n=2,N=4时 有方 案状态 1 2 3 4 5 6 7 8 9 10 11 12
A
B
C
D
00 10 01 11 00 01 10 11 00 10 01 11
01 11 00 10 10 11 00 01 11 01 10 00
11 01 10 00 11 10 01 00 01 11 00 10
10 00 11 01 01 00 11 10 10 00 11 01
方 案状态 13 14 15 16 17 18 19 20 21 22 23 24
A
B
C
D
00 01 10 11 00 10 01 11 00 01 10 11
11 10 01 00 10 00 11 01 01 00 11 10
10 11 00 01 01 11 00 10 10 11 00 01
01 00 11 10 11 01 10 00 11 10 01 00
但是，在 Ks种方案中只有三种是独立的 (真正不相同的 )方案
!)!2(
)!12(
=K nNn
n
u
－
－
然而,当 n较大时,Ku仍然很大,要真正找到最佳的分配方案是十分困难的,况且分配方案的好坏还与所采用的触发器的类型有关 。 因此,
实际应用时都是采用工程的方法,依据以下四条件原则来进行状态分配 。
状态分配的基本原则有四条：
(1) 在相同输入条件下具有相同次态的现态,应尽可能分配相邻的二进制代码；
(2) 在相邻输入条件,同一现态的次态应尽可能分配相邻的二进制代码；
(3) 输出 完全相同 的现态应尽可能分配相邻的二进制代码；
(4) 最小化状态表中出现次数最多的状态或初始状态应分配逻辑 0。
一般情况下,第一条原则较为重要,需优先考虑,其次要考虑由前三条原则得到的应分配相邻代码的状态对出现的次数,次数多的状态对应优先分配相邻的二进制代码 。
例,对下表所示的状态表进行状态分配现态次态 /输出
x=0 x=1
A
B
C
D
C/0
C/0
B/0
A/1
D/0
A/0
D/0
B/1
解,? 确定 n=2
确定 分配由规则 (1)得 A和 B,A和 C
应相邻；
由规则 (2)得 C和 D,C和
A,B和 D,A和 B应相邻；
由规则 (3)得 A,B,C 三者应相邻,即 AB,AC,BC应相邻；
由规则 (4)得 A分配为逻辑 0。
现态次态 /输出
x=0 x=1
A
B
C
D
C/0
C/0
B/0
A/1
D/0
A/0
D/0
B/1
A B
DC
0 1
0
1
y2
y1 A:
B:
C:
D:
y2 y1
0 0
1 0
0 1
1 1
由规则 (1)得
A和 B,A和 C应相邻；
由规则 (2)得
C和 D,C和 A,B和
D,A和 B应相邻；
由规则 (3)得
A,B,C 三者应相邻,即 A和 B,A和
C,B和 C应相邻；
由规则 (4)得
A分配为逻辑 0。
最后我们可以得到二进制状态表现态
y2 y1
次态 y2(n+1)y1(n+1)/输出
x=0 x=1
0 0
0 1
1 1
1 0
01/0
10/0
00/1
01/0
11/0
11/0
10/1
00/0
注意,有时满足分配原则的分配方案不唯一，
这时可任选一种。
现态次态 /输出
x=0 x=1
A
B
C
D
C/0
C/0
B/0
A/1
D/0
A/0
D/0
B/1
确定激励函数和输出函数
1,触发器的激励表触发器的激励表反映触发器从某种现态转换到某种次态时,对触发器输入 (激励 )的要求 。 在这种表中,现态和次态作为自变量,输入 (激励 )
作为因变量 。 触发器的激励表可由触发器的状态表直接推出 。
Q Q(n+1) R S
d 0
0 1
1 0
0 d
0 0
0 1
1 0
1 1
Q Q(n+1) D
0
1
0
1
0 0
0 1
1 0
1 1
R-S触发器激励表 D触发器激励表
Q Q(n+1) J K
0 d
1 d
d 1
d 0
0 0
0 1
1 0
1 1
Q Q(n+1) T
0
1
1
0
0 0
0 1
1 0
1 1
J-K触发器激励表 T触发器激励表
2,确定激励函数两种方法,根据次态方程来确定和通过激励表来确定 。
例,若用 J-K触发器实现下表所示的二进制状态表,试写出激励和输出函数。
现 态
y2 y1
次态 y2(n+1)y1(n+1)/输出 Z
x=0 x=1
0 0
0 1
1 1
1 0
11/0
00/0
00/1
01/0
01/0
00/1
10/1
11/0
解,确定激励函数现态
y2 y1
次态
y2(n+1) y1(n+1)
0 0
0 1
1 1
1 0
0 0
0 1
1 1
1 0
输入
x
激励函数
J2K2J1K1
1 1
0 0
0 0
0 1
0 1
0 0
1 0
1 1
1 d 1 d
0 d d 1
d 1 d 1
d 1 1 d
0 d 1 d
0 d d 1
d 0 d 1
d 0 1 d
0
0
0
0
1
1
1
1
现态
y2 y1
y2(n+1)y1(n+1)/输出 Z
x=0 x=1
0 0
0 1
1 1
1 0
11/0
00/0
00/1
01/0
01/0
00/1
10/1
11/0
Q Q(n+1) J K
0 d
1 d
d 1
d 0
0 0
0 1
1 0
1 1
J1=1
12J yx＝
现态
y2 y1
次态
y2(n+1) y1(n+1)
0 0
0 1
1 1
1 0
0 0
0 1
1 1
1 0
输入
x
激励函数
J2K2J1K1
1 1
0 0
0 0
0 1
0 1
0 0
1 0
1 1
1 d 1 d
0 d d 1
d 1 d 1
d 1 1 d
0 d 1 d
0 d d 1
d 0 d 1
d 0 1 d
0
0
0
0
1
1
1
1
xy2
1 d
d0
00 01
0
1
y1 11 10
d 0
d 0J2
xy2
d 1
1d
00 01
0
1
y1 11 10
0 d
0 dK2
xy2
1 1
dd
00 01
0
1
y1 11 10
1 1
d dJ1
xy2
d d
11
00 01
0
1
y1 11 10
d d
1 1K1
x＝2K
K1=1
Z=y2y1+xy1
0 0
10
00 01
0
1
y1
xy2
11 10
0 0
1 1
Z
确定输出函数现态
y2 y1
y2(n+1)y1(n+1)/输出 Z
x=0 x=1
0 0
0 1
1 1
1 0
11/0
00/0
00/1
01/0
01/0
00/1
10/1
11/0
画出逻辑电路图先画出触发器并给触发器编号,再根据激励函数和输出函数画出组合逻辑部分的电路,最后画出同步时钟信号线 。
1
D1 CD2 C
y2
CP
x
&
y1
z
1
y2
1&
y1
11D y?
2122122 +++=+D xyyyxyxyyx＝
)+(=+ =Z 21121 yxyyyxy
例如：
