6.3 复杂时序电路的设计一、同步时序电路的设计
1.设计步骤
(1)建立原始状态表和状态图原始的含义,是指没有经过简化而获得的状态转移表和状态转移图 。
对于 原始状态表 和 状态图 的 要求 是：
保证其绝对的正确性，确保状态无遗漏，
状态转移关系的正确。
时序电路的设计是根据实际提出的逻辑要求,设计出符合逻辑要求的逻辑电路。它是时序电路分析的逆过程。
问题的提出 抽象 原始状态图化简 最简的状态转移图状态分配电路设计,① 选择 FF
② 获得电路方程强调,这一步最重要，并且比较难 。
（ 2）状态化简
（ 3）状态分配
（ 4）电路设计
（ 5） 自启动性检查
（ 6） 作逻辑电路图 。
2.设计举例
(1)建立原始状态表和状态图例 6.3.1 1001序列检测器的功能是每当检测到有序列码 1001输入时，输出为,1”，其余情况下输出均为,0”。试建立该检测器的原始状态转移图和原始状态转移表 。
解：① 输入变量为 X、输出变量为 Z；
② 状态个数的确定；
初态 （没有序列信号输入时电路的状态）
为 S0,设 X恰为 1001。
S2S3
S1S0 1/0
1/1
0/0
图 6.3.2 例 6.3.1的状态转移图
1001001…0/0
③ 状态间的转换关系
S2S3
S1S0 1/0
1/1
0/0
0/0
0/0 1/0
1/00/0
11…
101…
1000…
图 6.3.3 例 6.3.1的原始状态转移图
S(t) N(t)/Z(t)X=0 X=1
S0 S0/0 S1/0
S1 S2/0 S1/0
S2 S3/0 S1/0
S3 S0/0 S1/1
表 6.3.1 图 6.3.3的原始状态转移表
1/0
(2)状态化简原始状态图的建立过程,就是问题分析的过程,因此可能引入多余状态 ;而状态数的增加,
就使电路中存储元件和门的数量增加。为使设计的电路简单?经济?方便可靠。就需要对原始状态图进行化简，这一过程称为 状态化简 。在化简前着重 介绍几个概念,
① 等价状态设状态表中的两个现态 A和 B,对任意的输入序列都有相同的输出序列,则称为 A和 B
等价 。
② 等价状态的传递性若 A和 B等价,B和 C等价，则定有 A和 C等价。记作,A ≈ B,B ≈ C?A ≈ C 。
③ 最大等价类等价状态的集合称为 等价类 。
例如,A ≈ B,B ≈ C,A ≈ C 都是等价类。
可写成,（ A,B），（ B,C），（ A,C）
如上述 A,B,C是三个都互相等价的状态，
若再无其它状态与此三个状态等价，则此三个状态的集合为（ A,B,C），就是一个 最大等价类。
④ 等价状态的判断判断的方法：
1） 在所有输入条件下，输出和次态完全相同。
则两者等价。
强调,即使是 单个状态,如果它不被其它等价类包含，此单个状态也是一个最大等价类。
（ A,B），（ B,C），（ A,C）
2）在所有输入条件下，输出相同，次态是相互交错，则两者等价。
例如：
相互交错，
3）互为隐含条件例如：
若要 A ≈ C 则 B ≈ D ；
因而可判断（ A,C），（ B,D）分别等价。
而 B ≈ D 则 A ≈ C,互为隐含条件。
简化方法,利用隐含表进行简化。
a) 画隐含表方法,把原始状态表中的状态纵横依次排列,呈直角三角形网格，两直角边上的网格数为状态数减 1，即,缺头少尾 。 垂直边由上向下标明的状态号,缺头,,水平边上由左向右标明的状态号,少尾,，这样的表格称为 隐含表 。
建立了这些基本概念后，下面进行简化。
例 6.3.2 化简原始状态转移表 6.3.2。
解：① 作状态对图
S(t) N(t)/Z(t)X=0 X=1
A C/1 B/0
B C/1 E/0
C B/1 E/0
D D/1 B/1
E D/1 B/1
表 6.3.2 例 6.3.2的原始状态转移表
b)进行顺序比较，作隐含表比较方法,A与 B,A与 C,B与 C；
A与 D,B与 D,C与 D ；
A与 E,B与 E,C与 E,D与 E 。
A B C D
E
D
C
B
图 6.3.4 (a)
原始状态转移表② 进行顺序比较，
作隐含表
BE
A B C D
E
D
C
B
BEBC √
√
× ×
× × ×
×
S(t) N(t)/Z(t)X=0 X=1
A C/1 B/0
B C/1 E/0
C B/1 E/0
D D/1 B/1
E D/1 B/1
图 6.3.4 (b)
说明：,√” 表示等价，,×,表示不等价。
③ 再 进行比较
④ 列出等价类
（ B,C），（ D,E）
⑤ 列出最大等价类。
A，（ B,C），
（ D,E）
√
×
×
图 6.3.4 (c)令,A? a ;
(B,C)? b ;
(D,E)? d 。
BE
A B C D
E
D
C
B
BEBC √
√
× ×
× × ×
×
⑥ 进行状态合并，列出最简状态转移表
S(t) N(t)/Z(t)X=0 X=1
a b/1 b/0
b b/1 d/0
d d/1 b/1
表 6.3.5 最简状态转移表
S(t) N(t)/Z(t)X=0 X=1
A C/1 B/0
B C/1 E/0
C B/1 E/0
D D/1 B/1
E D/1 B/1
令,A? a ;
(B,C)? b ;
(D,E)? d 。
c) 状态编码（状态分配）
所谓 状态分配,就是给简化了的状态分配一个二进制代码，以便于用记忆电路来表示时序电路的内部状态。
采用的方法有三种,
按顺序编码按 Gray码独热编码 (One hot)
例 6.3.3 对表 6.3.6进行状态编码。
S(t)
N(t)/Z(t)
X=0 X=1
A A/0 B/0
B A/0 C/0
C A/0 D/0
D A/0 D/1
表 6.3.6 例 6.3.3的状态转移表解,①由状态数 M确定代码位数 n=2
② 状态编码令,A→00,B →01,C →11,D →10 。
③ 作二进制状态转移表
S(t) N(t)/Z(t)X=0 X=1
0 0 00/0 01/0
0 1 00/0 11/0
1 1 00/0 10/0
1 0 00/0 10/1
表 6.3.7 例 6.3.3的二进制状态转移表
d) 电路设计
① 选定触发器类型。
② 根据二进制状态转移表（或称编码后的状态转移表）设计各触发器的激励函数和电路的输出函数。
例 6.3.4 设二进制状态转移表如表 6.3.8所示，试设计实现该表功能的同步时序电路。
解,① 选定触发器类型。
选用两位 DFF进行设计
② 根据二进制状态转移表（或称编码后的状态转移表）设计各触发器的激励函数和电路的输出函数。
表 6.3.18 例 6.3.4的二进制状态转移表
0
1
0
Q2 Q1
01/000/01
01/100/00
10/000/00
X=1X=0
Q2 Q1 / Zn n n+1 n+1
0
1
0
Q2 Q1
01/000/01
01/100/00
10/000/00
X=1X=0
Q2 Q1 / Zn n n+1 n+1
0
1
0
Q2 Q1
01/000/01
01/100/00
10/000/00
X=1X=0
Q2 Q1 / Zn n n+1 n+1
选用两位 JKFF进行设计
0
1
0
Q2 Q1
01/000/01
01/100/00
10/000/00
X=1X=0
Q2 Q1 / Zn n n+1 n+1
K2=1 K1=X
K2=1 K1=X
例一,设计一个序列信号检测器,电路要求连续输入 4个,1”时,输出为 1,并且状态可以 重叠 。
由设计要求可知，待设计电路应有一个输入端 X，一个输出端 Z。
解释,1111111·· ·· 11111111·· ··
0001111·· ·· 00010001·· ··
可以重叠 √ 不可以重叠解,(1)建立原始状态图分析,设 A:初始状态 ;
B:记忆第一个有效输入 ;
C:记忆第二个有效输入 ;
D:记忆第三个有效输入 ;
E:记忆第四个有效输入。
1/0A0/0 B 1/0
0/0
C
1/0
D0/0
E 1/1
0/0
1/1
0/0X/Z
（ 2）作原始状态转移表
（ 3）画隐含表
（ 4）顺序比较
（ 5）再比较
AB,AC,BC不等价
0/0
（ 6）列出最大等价类
A,B,C,（ D,E）
↓ ↓ ↓ ↓
令,a b c d
（ 7）进行状态合并，列出最简状态转移表
A→a,B →b,C→c,(D,E)→d
（ 8）状态编码 （或称为状态分配）
（ 9）电路设计
Z=XQ2Q1
Z=XQ2Q1
例二：设计一个序列信号检测器,电路要求连续输入 4个,1”时,输出为 1,并且状态可以 不重叠 。
解释,1111111·· ·· 11111111·· ··
0001111·· ·· 00010001·· ··
可以重叠 不可以重叠 √
解,(1)建立原始状态图分析,设 A:初始状态 ;
B:记忆第一个有效输入 ;
C:记忆第二个有效输入 ;
D:记忆第三个有效输入 ;
E:记忆第四个有效输入。
分析,设 A:初始状态 ;
B:记忆第一个有效输入 ;
C:记忆第二个有效输入 ;
D:记忆第三个有效输入 ;
E:记忆第四个有效输入。
A0/0 B1/0 C1/0
D
1/0
0/0
0/0
E 1/1
0/0
1/0
0/0
X/Z
（ 2）作原始状态转移表
（ 3）画隐含表
（ 4）顺序比较
（ 5）再比较
AB,AC,BC,BE,CE不等价。
（ 6）列出最大等价类
B,C,D,（ A,E）
（ 7）进行状态合并，
列出最简状态转移表
↓ ↓ ↓ ↓
令,b c d a
（ 7）进行状态合并，列出最简状态转移表
(A,E)→a,B →b,C→c,D→d,
（ 8）状态编码 （或称为状态分配）
（ 9）电路设计
Z=XQ2Q1
Z=XQ2Q1
作业,6.2,6,3
1.设计步骤
(1)建立原始状态表和状态图原始的含义,是指没有经过简化而获得的状态转移表和状态转移图 。
对于 原始状态表 和 状态图 的 要求 是：
保证其绝对的正确性，确保状态无遗漏，
状态转移关系的正确。
时序电路的设计是根据实际提出的逻辑要求,设计出符合逻辑要求的逻辑电路。它是时序电路分析的逆过程。
问题的提出 抽象 原始状态图化简 最简的状态转移图状态分配电路设计,① 选择 FF
② 获得电路方程强调,这一步最重要，并且比较难 。
（ 2）状态化简
（ 3）状态分配
（ 4）电路设计
（ 5） 自启动性检查
（ 6） 作逻辑电路图 。
2.设计举例
(1)建立原始状态表和状态图例 6.3.1 1001序列检测器的功能是每当检测到有序列码 1001输入时，输出为,1”，其余情况下输出均为,0”。试建立该检测器的原始状态转移图和原始状态转移表 。
解：① 输入变量为 X、输出变量为 Z；
② 状态个数的确定；
初态 （没有序列信号输入时电路的状态）
为 S0,设 X恰为 1001。
S2S3
S1S0 1/0
1/1
0/0
图 6.3.2 例 6.3.1的状态转移图
1001001…0/0
③ 状态间的转换关系
S2S3
S1S0 1/0
1/1
0/0
0/0
0/0 1/0
1/00/0
11…
101…
1000…
图 6.3.3 例 6.3.1的原始状态转移图
S(t) N(t)/Z(t)X=0 X=1
S0 S0/0 S1/0
S1 S2/0 S1/0
S2 S3/0 S1/0
S3 S0/0 S1/1
表 6.3.1 图 6.3.3的原始状态转移表
1/0
(2)状态化简原始状态图的建立过程,就是问题分析的过程,因此可能引入多余状态 ;而状态数的增加,
就使电路中存储元件和门的数量增加。为使设计的电路简单?经济?方便可靠。就需要对原始状态图进行化简，这一过程称为 状态化简 。在化简前着重 介绍几个概念,
① 等价状态设状态表中的两个现态 A和 B,对任意的输入序列都有相同的输出序列,则称为 A和 B
等价 。
② 等价状态的传递性若 A和 B等价,B和 C等价，则定有 A和 C等价。记作,A ≈ B,B ≈ C?A ≈ C 。
③ 最大等价类等价状态的集合称为 等价类 。
例如,A ≈ B,B ≈ C,A ≈ C 都是等价类。
可写成,（ A,B），（ B,C），（ A,C）
如上述 A,B,C是三个都互相等价的状态，
若再无其它状态与此三个状态等价，则此三个状态的集合为（ A,B,C），就是一个 最大等价类。
④ 等价状态的判断判断的方法：
1） 在所有输入条件下，输出和次态完全相同。
则两者等价。
强调,即使是 单个状态,如果它不被其它等价类包含，此单个状态也是一个最大等价类。
（ A,B），（ B,C），（ A,C）
2）在所有输入条件下，输出相同，次态是相互交错，则两者等价。
例如：
相互交错，
3）互为隐含条件例如：
若要 A ≈ C 则 B ≈ D ；
因而可判断（ A,C），（ B,D）分别等价。
而 B ≈ D 则 A ≈ C,互为隐含条件。
简化方法,利用隐含表进行简化。
a) 画隐含表方法,把原始状态表中的状态纵横依次排列,呈直角三角形网格，两直角边上的网格数为状态数减 1，即,缺头少尾 。 垂直边由上向下标明的状态号,缺头,,水平边上由左向右标明的状态号,少尾,，这样的表格称为 隐含表 。
建立了这些基本概念后，下面进行简化。
例 6.3.2 化简原始状态转移表 6.3.2。
解：① 作状态对图
S(t) N(t)/Z(t)X=0 X=1
A C/1 B/0
B C/1 E/0
C B/1 E/0
D D/1 B/1
E D/1 B/1
表 6.3.2 例 6.3.2的原始状态转移表
b)进行顺序比较，作隐含表比较方法,A与 B,A与 C,B与 C；
A与 D,B与 D,C与 D ；
A与 E,B与 E,C与 E,D与 E 。
A B C D
E
D
C
B
图 6.3.4 (a)
原始状态转移表② 进行顺序比较，
作隐含表
BE
A B C D
E
D
C
B
BEBC √
√
× ×
× × ×
×
S(t) N(t)/Z(t)X=0 X=1
A C/1 B/0
B C/1 E/0
C B/1 E/0
D D/1 B/1
E D/1 B/1
图 6.3.4 (b)
说明：,√” 表示等价，,×,表示不等价。
③ 再 进行比较
④ 列出等价类
（ B,C），（ D,E）
⑤ 列出最大等价类。
A，（ B,C），
（ D,E）
√
×
×
图 6.3.4 (c)令,A? a ;
(B,C)? b ;
(D,E)? d 。
BE
A B C D
E
D
C
B
BEBC √
√
× ×
× × ×
×
⑥ 进行状态合并，列出最简状态转移表
S(t) N(t)/Z(t)X=0 X=1
a b/1 b/0
b b/1 d/0
d d/1 b/1
表 6.3.5 最简状态转移表
S(t) N(t)/Z(t)X=0 X=1
A C/1 B/0
B C/1 E/0
C B/1 E/0
D D/1 B/1
E D/1 B/1
令,A? a ;
(B,C)? b ;
(D,E)? d 。
c) 状态编码（状态分配）
所谓 状态分配,就是给简化了的状态分配一个二进制代码，以便于用记忆电路来表示时序电路的内部状态。
采用的方法有三种,
按顺序编码按 Gray码独热编码 (One hot)
例 6.3.3 对表 6.3.6进行状态编码。
S(t)
N(t)/Z(t)
X=0 X=1
A A/0 B/0
B A/0 C/0
C A/0 D/0
D A/0 D/1
表 6.3.6 例 6.3.3的状态转移表解,①由状态数 M确定代码位数 n=2
② 状态编码令,A→00,B →01,C →11,D →10 。
③ 作二进制状态转移表
S(t) N(t)/Z(t)X=0 X=1
0 0 00/0 01/0
0 1 00/0 11/0
1 1 00/0 10/0
1 0 00/0 10/1
表 6.3.7 例 6.3.3的二进制状态转移表
d) 电路设计
① 选定触发器类型。
② 根据二进制状态转移表（或称编码后的状态转移表）设计各触发器的激励函数和电路的输出函数。
例 6.3.4 设二进制状态转移表如表 6.3.8所示，试设计实现该表功能的同步时序电路。
解,① 选定触发器类型。
选用两位 DFF进行设计
② 根据二进制状态转移表（或称编码后的状态转移表）设计各触发器的激励函数和电路的输出函数。
表 6.3.18 例 6.3.4的二进制状态转移表
0
1
0
Q2 Q1
01/000/01
01/100/00
10/000/00
X=1X=0
Q2 Q1 / Zn n n+1 n+1
0
1
0
Q2 Q1
01/000/01
01/100/00
10/000/00
X=1X=0
Q2 Q1 / Zn n n+1 n+1
0
1
0
Q2 Q1
01/000/01
01/100/00
10/000/00
X=1X=0
Q2 Q1 / Zn n n+1 n+1
选用两位 JKFF进行设计
0
1
0
Q2 Q1
01/000/01
01/100/00
10/000/00
X=1X=0
Q2 Q1 / Zn n n+1 n+1
K2=1 K1=X
K2=1 K1=X
例一,设计一个序列信号检测器,电路要求连续输入 4个,1”时,输出为 1,并且状态可以 重叠 。
由设计要求可知，待设计电路应有一个输入端 X，一个输出端 Z。
解释,1111111·· ·· 11111111·· ··
0001111·· ·· 00010001·· ··
可以重叠 √ 不可以重叠解,(1)建立原始状态图分析,设 A:初始状态 ;
B:记忆第一个有效输入 ;
C:记忆第二个有效输入 ;
D:记忆第三个有效输入 ;
E:记忆第四个有效输入。
1/0A0/0 B 1/0
0/0
C
1/0
D0/0
E 1/1
0/0
1/1
0/0X/Z
（ 2）作原始状态转移表
（ 3）画隐含表
（ 4）顺序比较
（ 5）再比较
AB,AC,BC不等价
0/0
（ 6）列出最大等价类
A,B,C,（ D,E）
↓ ↓ ↓ ↓
令,a b c d
（ 7）进行状态合并，列出最简状态转移表
A→a,B →b,C→c,(D,E)→d
（ 8）状态编码 （或称为状态分配）
（ 9）电路设计
Z=XQ2Q1
Z=XQ2Q1
例二：设计一个序列信号检测器,电路要求连续输入 4个,1”时,输出为 1,并且状态可以 不重叠 。
解释,1111111·· ·· 11111111·· ··
0001111·· ·· 00010001·· ··
可以重叠 不可以重叠 √
解,(1)建立原始状态图分析,设 A:初始状态 ;
B:记忆第一个有效输入 ;
C:记忆第二个有效输入 ;
D:记忆第三个有效输入 ;
E:记忆第四个有效输入。
分析,设 A:初始状态 ;
B:记忆第一个有效输入 ;
C:记忆第二个有效输入 ;
D:记忆第三个有效输入 ;
E:记忆第四个有效输入。
A0/0 B1/0 C1/0
D
1/0
0/0
0/0
E 1/1
0/0
1/0
0/0
X/Z
（ 2）作原始状态转移表
（ 3）画隐含表
（ 4）顺序比较
（ 5）再比较
AB,AC,BC,BE,CE不等价。
（ 6）列出最大等价类
B,C,D,（ A,E）
（ 7）进行状态合并，
列出最简状态转移表
↓ ↓ ↓ ↓
令,b c d a
（ 7）进行状态合并，列出最简状态转移表
(A,E)→a,B →b,C→c,D→d,
（ 8）状态编码 （或称为状态分配）
（ 9）电路设计
Z=XQ2Q1
Z=XQ2Q1
作业,6.2,6,3
