第四章 同步时序逻辑电路.

Presentation on theme: "第四章 同步时序逻辑电路."— Presentation transcript:

1 第四章 同步时序逻辑电路

2 学习要求： 了解时序电路的基本结构、分类和常用的描述方法； 熟悉各种触发器的功能和使用； 熟练掌握同步时序电路分析和设计的基本方法； 熟悉状态图的建立，状态简化和状态分配的各个重要环节。

3 4.1 时序逻辑电路模型 时序电路：一个电路在任何时刻的稳定输出不仅与该时刻电路的输入信号有关，而且与该电路过去的输入有关，这样的电路称为"时序电路"。 时序电路由组合电路和存储(记忆)器件及反馈回路三部分组成，见下图. x1 z1 组合电路 存储器件 xn … zm yr y1 Y1 Yl x1 . xn：时序电路的输入或外部输入； z1 . zm：时序电路的输出或外部输出； y1.. yr：时序电路的状态或内部输入； Y1 . Yl：时序电路的激励或内部输出；

4 状态：过去的输入已不存在，但可以通过存储器件把它们记录下来，称之为状态。记录下来的信息可能和过去的输入完全一样，也可能是经过了组合电路加工处理后的结果。我们把某一时刻之前的状态称为"现态"，把这一时刻之后的状态称为"次态"，"现态"和"次态"是一个相对的概念，分别用y(n)(或y)和y(n+1)表示。 时序电路的逻辑函数由下列方程组成： Zi= fi (x1,…， xn ; y1,…， yr ) , i=1, …, m Yj= gj (x1,…， xn ; y1,…， yr ) , j=1, …, l

5 两种时序电路类型见下图： x1 z1 组合电路 存储器件 xn … zm yr y1 Y1 Yl 时钟 x1 z1 组合电路 xn … zm
存储器件或延时器件 xn … zm yr y1 Y1 Yl (a) 同步时序电路 (b) 异步时序电路

6 时序电路输入信号的波形图： 时钟脉冲 (CP) 同步脉冲 1 异步脉冲 1 同步电平 1 异步电平 1

7 4.2 状态表和状态图 4.2.1 Mealy 型状态表和状态图
4.2 状态表和状态图 状态表与状态图是用来表示同步时序电路的输入、输出、现态、次态之间转移关系的两种常用工具。 Mealy 型状态表和状态图 如果同步时序电路的输出是输入和现态的函数，即Zi= fi (x1,…， xn ; y1,…， yr ) , i=1, …, m ，则称该电路为Mealy型电路。

8 一、状态表 Mealy 型电路状态表 现态 次态 / 输出 输入x y y(n+1)/Z 该表表明：处在状态y的同步时序电路，当输入为x时，输出为z，且在时钟脉冲作用下，电路进入次态y(n+1)。

9 某Mealy 型电路状态表 现 态 次态 / 输出(y(n+1)/Z) x = 0 y A / 0 B / 0 x = 1 C / 0 A / 1 A B C

10 二、状态图 状态图是一种反映同步时序电路状态转移规律和输入、输出取值关系的有向图。 A C B 0/0 1/0 1/1 y x/z y(n+1) Mealy型电路状态图 某Mealy型电路状态图

11 Moore 型状态表和状态图 如果同步时序电路的输出仅是现态的函数, 即Zi= fi (y1,…, yr ) , i=1, …, m , 则称电路为Moore型电路。它的电路结构图可表示为: x1 组合电路 xn … yr y1 Y1 Yl 存储器件 z1 zm

12 一、状态表 Moore 型电路状态表 现 态 次 态 输入x y y(n+1) Z 输 出 该表表明：当电路处于状态y时，输出为z，若输入为x，则在时钟脉冲作用下，电路进入次态y(n+1)。

13 某Moore 型电路状态表 现 态 次 态 y(n+1) x = 0 y C B x = 1 A 输 出 Z 1

14 二、状态图 C/0 A/0 B/1 1 y/z x y(n+1) Z' Moore型电路状态图 某Moore型电路状态图

15 4.3 触发器 触发器是一种存储元件，在电路中用来"记忆"电路过去的输入情况。
4.3 触发器 触发器是一种存储元件，在电路中用来"记忆"电路过去的输入情况。 一个触发器具有两种稳定的状态,一个称之为 "0"状态，另一种称之为"1"状态。在任何时刻,触发器只处于一个稳定状态,当触发脉冲作用时,触发器可以从一种状态翻转到另一种状态。 常用的触发器有R–S触发器, D触发器J – K触发器和T触发器。

16 4.3.1 基本R－S触发器 基本R－S触发器可 由两个"与非"门交叉耦合组成，其逻辑图和逻辑符号如下： & G1 R Q G2 S Q R
1 1 1

17 基本R－S触发器的输入与状态之间的逻辑关系可用触发器的功能表来描述。
Q(n+1) 功能说明 d 1 Q 不定 置 0 置 1 不变

18 01 RS Q Q(n+1) d 1 基本R－S触发器的次态方程为： Q(n+1)＝S＋RQ 其约束条件为： R+S=1 基本R－S触发器的一个重要特性：如果连续出现多个置0或置1信号，只有第一个置0或置1信号起作用。利用这一特性可消除机械开关的触点抖动。 基本R－S触发器也可由"或非"门组成。

19 时钟控制R－S触发器 在数字系统中，通常要求触发器按一定的时间节拍动作，即让输入信号的作用受到时钟脉冲的控制，为此出现了带时钟控制的R－S触发器，其逻辑图和逻辑符号如下： & G1 R Q G2 S CP G3 G4 1 Q R S CP 1 1

20 当CP为0时，不论R，S为何值，触发器的状态保持不变；当CP为1时，触发器的状态取取决于R和S，工作原理与R－S触发器相同。
钟控触发器的功能表和状态表如下： 钟控R－S触发器功能表 R S Q(n+1) 功能说明 Q 1 d 不变 置 1 置 0 不定

21 钟控R－S触发器状态表 现 态 Q 次 态 Q(n+1) 0 1 1 d RS=00 1 1 1 0 钟控R－S触发器状态图 1 00, 10 00, 01 RS 01 10

22 1 01 RS Q d Q(n+1) 钟控R－S触发器的状态方程为： Q(n+1)＝S＋RQ RS = 0 (约束条件) 钟控R－S触发器存在次态不能确定和"空翻"两个问题。

23 D触发器 如果使钟控R－S触发器的R和S端始终处于互补状态, 则可消去次态不能确定的问题, 这就形成了所谓的D触发器, 其逻辑图的逻辑符号如下: & G1 (R) Q G2 D CP G3 G4 (S) 1 1 Q C D 1 1 1 1

24 当CP=0时，D触发器的状态不变；当CP=1时，D触发器的状态取决于D。
Q(n+1) 1 Q Q(n+1) 1 D＝0 D＝1

25 D触发器的次态方程为： Q(n+1)＝D 状态图为： 1 D D触发器结构简单, 但仍然存在"空翻"现象。实际使用的D触发器是一种维持阻塞型D触发器, 可以防止"空翻"的发生。

26 维持阻塞D触发器: Q & RD SD CP CP上升沿将 D可靠置入， 无空翻现象。 D Q SD D CP RD 置”0”阻塞线
置”1”维持线 置”1”阻塞线 置”0”阻塞线 置”0”维持线 & Q SD CP RD D CP上升沿将 D可靠置入， 无空翻现象。

27 4.3.4 J－K触发器 J－K触发器有两个输入端，即克服了R－S触发器的"约束"问题，使用上又比D触发器灵活。其逻辑图与逻辑符号如下：
Q＝1 Q＝0 & G1 K Q G2 J CP G3 G4 Q(n+1)=0 Q(n+1)=1 1 1 1 Q J K C Q 1 Q 1 1

28 当CP＝0时，J－K触发器的状态保持不变；
若J=K=0, 则G3=G4=1, 触发器保持原状态； 若J=1, K=0, 则G3=1, G4=Q, 使触发器置1； 若J=0, K=1, 则G3=Q, G4=1, 使触发器置0； 若J=K=1, 则G3=Q, G4=Q, 使触发器翻转；

29 J－K触发器功能表和状态表如下： J－K触发器功能表 J K Q(n+1) 功能说明 Q 1 不变 置 0 置 1 翻转 J－K触发器状态表 Q Q(n+1) 0 1 1 JK=00 1 1 1 0

30 01 JK Q 1 Q(n+1) J－K触发器的次态方程为： Q(n+1)＝JQ＋KQ 状态图为： 1 00, 01 JK 10, 11 01, 11 00, 10 为防止"空翻"，实际数字电路中使用的J－K触发器是主从式集成J－K触发器，它使用"前沿采样，后沿定局"的方式，无空翻，功能较全，使用灵活。

31 主从J—K触发器: K J CP & Q SD RD 1 （从） （主） CP前沿采样， 后沿定态；无 空翻现象。 SD J CP Q K

32 T触发器 T触发器实际上是J－K触发器的一种特殊形式。如果把J－K触发器的J－K端连在一起就形成了T触发器。因此T触发器的次态方程为： Q(n+1)＝TQ＋TQ 其功能表和状态表是J－K触发器功能表和状态表的一部分。 T触发器又称"计数"触发器。

33 4.4 同步时序逻辑电路的分析 分析的任务：对一个给定的时序逻辑电路，研究在一系列输入信号作用下，电路将会产生怎样的输出，进而说明该电路的逻辑功能。实际上是要求出电路的状态表、状态图或时间图，并作出功能评述。

34 4.4.1 同步时序逻辑电路的分析方法 逻辑电路图 输出函数和激励函数表达式 触发器次态方程 触发器功能表 状态表和状态图
同步时序逻辑电路的分析方法 逻辑电路图 输出函数和激励函数表达式 触发器次态方程 触发器功能表 状态表和状态图 用时间图和文字描述电路逻辑功能 列出状态 转移真值表 电路次态方程组

35 例：用表格法分析下图所示的同步是序逻辑电路
＝1 K1 J1 C K2 J2 Y2 Y1 CP 1 X

36 解： 第一步：写出输出函数和激励函数表达式。 J1=K1=1 J2=K2=x  y1 第二步：列同状态转移真值表。 现 态y2 y1
激 励 函 数 J2 K2 J1 K1 次 态 y2 (n+1) y1 (n+1) 1 0 0 0 1 1 0 1 1 输 入x

37 第三步：作出状态表和状态图。 00 01 10 11 1 x 次 态 y2 (n+1)y1 (n+1) 0 0 0 1 1 0 1 1 现 态 y2 y1 x = 0 x = 1

38 第四步：用时间图和文字描述电路和逻辑功能。
当x=0时,该电路进行加1计数,计数序列为: 00 01 10 11 当x=1时,该电路进行减1计数,计数序列为: 00 11 10 01

39 时间图的作法： 选定一个典型的输入序列； 输入序列为：x= ,初态： y2y1=00 根据选定的典型输入序列，求出状态响应序列(和输出响应序列) CP: x: y2: y1: y2(n+1): y1(n+1):

40 画时间图: 1 y1 y2 x 2 3 4 5 6 7 8 CP

41 例：试有代数法分析下图所示的同步时序逻辑电路。
1 D1 C D2 y2 CP x & y1 z

42 解： 第一步：写出输出函数和激励函数表达式。 Z=x y2 y1 D2 = x + y2 + y1 = x y2 y1 D1 = x 第二步：把激励函数表达式代入触发器的次态方程，得到电路的次态方程组。 Q2(n+1)＝D2＝ x y2 y1 Q1(n+1)＝D1＝ x

43 第三步：根据次态方程组和输出函数表达式作出状态表和状态图。
00 01 10 11 1/0 x/z 0/0 1/1 次态/输出( y2 (n+1) y1 (n+1)/Z) 0 0 0 1 1 1 1 0 现 态 y2 y1 x = 0 x = 1 00/0 10/0 01/0 01/1

44 第四步：作出时间图，并说明电路的逻辑功能。
典型输入序列：x = 初态： y2 y1= 00 状态响应序列和输出响应序列为： CP: x: y2: y1: y2(n+1): y1(n+1): Z:

45 时间图： CP x y2 y1 Z 1 2 3 4 6 7 8 5 功能说明：该电路是一个"101"序列检测器。

46 4.5 同步时序逻辑电路的设计 同步时序逻辑电路设计又称同步时序逻辑电路综合，其基本指导思想是用尽可能少的触发器和门电路来完成设计。
4.5 同步时序逻辑电路的设计 同步时序逻辑电路设计又称同步时序逻辑电路综合，其基本指导思想是用尽可能少的触发器和门电路来完成设计。 同步时序电路设计的一般步骤为： 1. 作原始状态图和状态表； 2. 对原始状态表化简； 3. 状态分配； 4. 选定触发器，求出输出函数和激励函数表达式； 5. 画出逻辑电路图。

47 建立原始状态图 状态图是同步时序电路设计的依据，它必须正确反映设计要求。状态图的构成没有统一的方法，关键是要充分正确地理解设计要求，明确电路的输入条件和输出要求，输入和输出关系，以及状态的转换关系。 原始状态图建立的一般过程为： 假定一个初始状态，由此出发，每加入一个输入信号，则记忆其次态，并标出其相应的输出值。次态可能为现态、已有状态或新的状态，直到没有新的状态为止。每个状态的各种可能的输入值都要考虑到。

48 例: 某序列检测器有一个输入端x和一个输出端Z。从x端输入一组按时间顺序排列的串行二进制码。当输入序列中出现101时，输出Z＝1，否则 Z＝0。试作出该序列检测器的Mealy型和Moore型原始状态图和状态表。 电路的Mealy 型状态表 现态 次态/输出 x=0 x=1 S0 S1 S2 S3 S0/0 S2/0 S1/0 S3/1 1/0 1/0 0/0 S0 S1 0/0 0/0 1/0 0/0 S3 S2 1/1

49 电路的 Moore 型状态表 现态 次 态 x=0 x=1 S0 S1 S2 S3 输 出 Z 1 1 1 S0/0 S1/0 1 S3/1 S2/0 1

50 例: 假设某同步时序电路，用于检测串行输入的8421BCD码，其输入的顺序是先高位后低位，当出现非法数字(即输入1010，1011，1100，1101，1110，1111)时，电路的输出为1。试作出该时序电路的Mealy型原始状态图和状态表。 解： A 0/0 1/0 0/0 1/0 B C 1/0 0/0 D E 1/0 0/0 F G

51 H D A B 1/0 0/0 C E I F G N J K P L M 0/1 1/1 电路的原始状态图

52 电路的原始状态表 现态 次态/输出 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

53 例：假设有一个三位二进制加、减法器（模8计数器）
，当X输入为1时，实现加1计数；当X为0时，实现减1 计数，试作出该电路的Moore型原始状态图和状态表。 解： 当X为0时： 000 111 110 101 100 011 010 001 当X为1时： 000 001 010 011 100 101 110 111 计数器的输出可为状态本身，亦可看作外部输出。

54 原始状态图 1 000 110 001 101 010 111 100 011

55 原始状态表 现态 次态/输出 x=0 x=1 000 001 010 011 100 101 110 111

56 状态简化 一般情况下，原始状态图和原始状态表中存在着多余的状态。状态个数越多，电路中所需的触发器的数目也越多，制造成本就越高。为降低制造成本，需要去掉多余的状态，即要进行状态简化。 所谓状态简化，就是要获得一个最小化的状态表。这个表不仅能正确地反映设计的全部要求，而且状态的数目最少。

57 完全确定状态表： 状态表中的次态和输出都有确定的
一、完全确定状态表的简化 完全确定状态表： 状态表中的次态和输出都有确定的 状态和确定的输出值。 等效状态：设状态S1和S2是完全确定状态表中的两个状态,如果对于所有可能的输入序列，分别从状态S1 和状态S2出发，所得到的输出响应序列完全相同， 则状态S1和S2是等效的，记作(S1, S2) . 或说，状态S1和S2是等效对。等效状态可以合并。 0/0 0/1 1/1 S1 S'1 S2 S'2 S3 S'3 S4 S'4 …

58 等效状态传递性：(S1,S2), (S2,S3)→(S1,S3)
等效类： 彼此等效的状态集合 最大等效类： 不被其它等效类所包含的等效类。 一个状态也可能是一个最大等效类。 状态简化的任务是要在原始状态表中找出全部最大等效类(最大等效类集合)，并将每一个最大等效类用一个状态来表示。

59 判别方法： 假定状态S1和S2是完全确定原始状态表中的两个现态，那么S1和S2等效的条件可归纳为在输入的各种取值组合下： 第一、它们的输出完全相同； 第二、它们的次态满足下列条件之一，即 (1) 次态相同； (2) 次态交错； (3) 次态循环； (4) 次态对等效。

60 次态相同 Sl 0/1 Si Sj Sk 1/0 0/1 1/0

61 次态相同或交错 Si Sj Sk 0/0 1/0 1/0 0/0

62 次态交错或相同或循环 0/1 Sk Sl 0/0 Si Sj Sm 1/0 1/0 1/0

63 次态交错或等效(Sk,Sl等效) Sl Sk 0/1 Si Sj 1/0 1/0

64 1. 观察法化简 例：简化下表所示的状态表 现态 次态/输出 x=0 x=1 A B C D A/0 B/0 C/0 D/1

65 A和B，C和D的输出完全相等； 解： C和D在输入的各种取值组合下，次态相同，因此C和D等效； 现态 次态/输出 x=0 x=1 A B C D A/0 B/0 C/0 D/1 A和B在x=1时的次态不满足四条件之一，因此A和B不等效; 最大等效类为{A}，{B}，{C,D},分别用A', B', C'表示；

66 最小化状态表为： 现态 次态/输出 x=0 x=1 A B C D A/0 B/0 C/0 D/1 现态 次态/输出 x=0 x=1 A' B' C' A'/0 B'/0 C'/0 C'/1

67 1. 隐含表法化简 例：简化下表所示的状态表 现态 次态/输出 x=0 x=1 A B C D E F G C/0 F/0 D/0 D/1 C/1 B/1 A/1 G/0 E/0 E/1

68 解： 顺序比较，寻找等效状态对 状态对等效，打“ √”； 作隐含表 现态 次态/输出 x=0 x=1 A B C D E F G C/0
状态对不等效，打 “ ╳”； 状态对是否等效需进 一步检查，则标记次态对。 作隐含表 现态 次态/输出 x=0 x=1 A B C D E F G C/0 F/0 D/0 D/1 C/1 B/1 A/1 G/0 E/0 E/1 A B C D E F G CF AE CF BE CD DE

69 处于循环链中的每一个状态对都是等效状态对,一共四个等效对 (A,B), (A,E), (B,E), (C,F)。
D E F G CF BE AE CD DE 关联比较，确定等效状态对 AE→BE→CF√ AB→CF√ 处于循环链中的每一个状态对都是等效状态对,一共四个等效对 (A,B), (A,E), (B,E), (C,F)。

70 确定最大等效类，作最小化状态表: 四个等效对 (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/1 B/1 A/1 G/0 E/0 E/1 现态 次态/输出 x=0 x=1 a b c d b/0 c/0 c/1 b/1 a/1 d/0 a/0

71 二、不完全确定状态表的简化 不完全确定状态表： 状态表中存在不确定的次态或输出，这些不确定的次态或输出将有利于状态简化。 相容状态：设状态S1和S2是不完全确定状态表中 的两个状态，如果对于所有的有效输入序列，分别从状态S1和S2出发，所得到的输出响应序列(除不确定的那些位之外)是完全相同的，那么状态S1和S2是相容的，或者说状 态S1和S2是相容对，记作(S1,S2)。相容状态可以合并。

72 例: 设计一个“1111”序列检测器，使其成为爆炸装置 的引爆控制器。假定工作条件为：平时无1输入， Z一直处于0状态；当连续输入4个1时（不允许出现 0），Z=1引爆，整个装置不存在。 0/0 0/d d 现态 次态/输出 x=0 x=1 A B C D A/0 d/d B/0 C/0 D/0 d/1 1/0 A B 1/0 1/0 D C 1/1 0/d 0/d d d d

73 相容状态无传递性： Si Sj Sl 1/0 1/d 0/0 0/0 Si和Sj相容； Sj和Sk相容； 但Si和Sk不相容。 0/0 Sk 0/0 1/1 相容类：彼此相容的状态集合 最大相容类：不被其它相容类所包含的相容类

74 判别方法： 在不完全确定状态表中判断两个状态是否相容也是根据表中给出的次态和输出来决定的。假定状态Si和Sj是不完全确定状态表中的两个现态，那么状态Si和Sj相容的条件可归纳为在输入的各种取值组合下: 第一、它们的输出完全相同，或者其中的 一个(或两个) 输出为任意值。 第二、它们的次态满足下列条件之一： (3) 次态循环； (1) 次态相同； (2) 次态交错； (4) 其中的一个(或两个)为任意状态; (5) 次态相容；

75 例：简化下表所示的状态表 现 态 次 态 x=0 x=1 A B C D E F d 输 出 1

76 顺序比较， 寻找相容对； 解： 作隐含表； 现 态 次 态 x=0 x=1 A B C D E F d 输 出 1 A B C D E F AB DE DE BF AF CD CD CE CE

77 AF→CD √ AB DE A B C D E F BF AF CE CD BC→AB √ DE √ BD→DE √ BE→BF→CD √ CE→AF √ CF→CE √ DF→CE √ 关联比较，确定相容对； 以上三步与确定状态表的化简相同 全部相容对：(A,B), (A,F), (B,C), (B,D), (B,E), (B,F), (C,D), (C,E), (C,F), (D,F), (D,E), (E,F)。

78 作状态合并图，求最大相容类。 S1 S2 S3 3状态相容 S4 S1 S2 S3 4状态相容 S1 S2 S3 S4 S5 5状态相容

79 全部相容状态对： (A,B), (A,F), (B,C), (B,D), (B,E), (B,F), (C,D), (C,E), (C,F), (D,F), (D,E), (E,F)。 A B C D F E 本例状态合并图，最大相容类是(A,B,F), (B,C,D,E,F)。

80 作最小化状态表: 最小化状态表(又称最小闭覆盖) 应满足下列三个条件：
覆盖性－－所选相容类集合应包含原始状态表中 的全部状态。 最小性－－所选相容类集合中相容类的个数应最 少。 闭合性－－所选相容类集合中的任一相容类，在 原始状态表中任一输入条件下产生的次态应 该属于该集合中的某一个相容类。

81 采用闭覆盖表来反映所选相容类集合的覆盖和闭合情况。本例的闭覆盖表为
现态 次态 x=0 x=1 A B C D E F d 输出 1 CDE 最大相 容类 ABF BCDEF A B C D E F √ 覆 盖 闭 合 x=0 x=1 CD

82 √ 现态 次态 x=0 x=1 A B C D E F d 输出 1 现 态 次 态 x=0 x=1 输 出 现 态 次 态 x=0 x=1
所选相容类集合{(A,B,F), (B,C,D,E,F)} 满足最小闭覆盖条件，令A表示(A,B,F)，C表示(B,C,D,E,F)可得： CDE 最大相 容类 ABF BCDEF A B C D E F √ 覆 盖 闭 合 x=0 x=1 CD 现态 次态 x=0 x=1 A B C D E F d 输出 1 现 态 次 态 x=0 x=1 A C A,C 输 出 1 由于该表中只有两个状态，进一步可以得到： 现 态 次 态 x=0 x=1 A C d 输 出 1

83 例：化简下表所示的状态表 现态 次态/输出 x=0 x=1 A B C D E D/d E/0 D/0 C/d C/1 A/d B/d

84 解： 作隐含表，寻找相容状态对 AB→DE→BC √ 现态 次态/输出 x=0 x=1 A B C D E D/d E/0 D/0 C/d C/1 A/d B/d A B C D E DE AC→AB √ AB DE AD→ →BC √ CDAC √ AB CD AC AC CE BC AE→ AB CD √ AB CD BC BD→ AC √ CE ╳ 由上图得相容状态对为(A,B), (A,C), (A,D), (A,E), (B,C), (C,D), (D,E)

85 作状态合并图，寻找最大相容类 A B C D E 得最大相容类为(A,B,C), (A,C,D), (A,D,E)

86 作最小化状态表 (A,B,C), (A,C,D), (A,D,E) A B C D E 若选相容类集合为{(A,B,C), (A,D,E)}则下表表明它不满足闭合要求 现态 次态/输出 x=0 x=1 A B C D E D/d E/0 D/0 C/d C/1 A/d B/d 相容类 ABC ADE A B C D E √ 覆 盖 闭 合 x=0 x=1 DE CD AB

87 但如果选相容类 (A,B,C)和 (D,E)则能满足最小闭覆盖的要求
现态 次态/输出 x=0 x=1 A B C D E D/d E/0 D/0 C/d C/1 A/d B/d 相容类 ABC DE A B C D E 覆 盖 闭 合 x=0 x=1 BC AB

88 现态 次态/输出 x=0 x=1 A B C D E D/d E/0 D/0 C/d C/1 A/d B/d 令A'=(A,B,C), B'=(D,E), 进一步可得： 现态 次态/输出 x=0 x=1 A' B' B' /0 A' /1 A'/d 寻找最小闭覆盖通常不是一件容易的事情，其结果往往不唯一。

89 4.5.3 状态编码(状态分配) 给最小化状态表中的每一个状态指定一个二进制代码，形成二进制状态表。
状态编码(状态分配) 给最小化状态表中的每一个状态指定一个二进制代码，形成二进制状态表。 通常情况下，状态编码的方案不一样，所得到的输出函数和激励函数的表达式也不同，由此而设计出来的电路复杂度也不同。状态分配的任务是： 决定编码的长度；寻找一种最佳的或接近最佳的状态分配方案。

90 设最小化状态表中的状态数为N，编码长度为n，N和n的关系为 2n-1<N2n
用2n种组合来对N个状态进行分配时，可能出现的分配方案的总数Ks为 －

91 例如，n=2, N=4时 有 方 案 状态 A B C D

92 但是，在Ks种方案中只有三种是独立的(真正不相同的)方案
－ 然而，当n较大时，Ku仍然很大，要真正找到最佳的分配方案是十分困难的，况且分配方案的好坏还与所采用的触发器的类型有关。因此，实际应用时都是采用工程的方法，依据以下四条件原则来进行状态分配。

93 状态分配的基本原则有四条： (1) 在相同输入条件下具有相同次态的现态，应尽可能分配相邻的二进制代码； (2) 在相邻输入条件，同一现态的次态应尽可能分配相邻的二进制代码； (3) 输出完全相同的现态应尽可能分配相邻的二进制代码； (4) 最小化状态表中出现次数最多的状态或初始状态应分配逻辑0。

94 一般情况下，第一条原则较为重要，需优先考虑，其次要考虑由前三条原则得到的应分配相邻代码的状态对出现的次数，次数多的状态对应优先分配相邻的二进制代码。

95 例：对下表所示的状态表进行状态分配 现态 次态/输出 x=0 x=1 A B C D C/0 B/0 A/1 D/0 A/0 B/1

96 解： 确定n=2 确定分配 现态 次态/输出 x=0 x=1 A B C D C/0 B/0 A/1 D/0 A/0 B/1
由规则(1)得A和B,A和C应相邻； 由规则(2)得C和D,C和A,B和D,A和B应相邻； 由规则(3)得A,B,C 三者应相邻,即A B,AC,BC应相邻； 由规则(4)得A分配为逻辑0。 现态 次态/输出 x=0 x=1 A B C D C/0 B/0 A/1 D/0 A/0 B/1

97 A B D C 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。 A B D C 1 y2 y1 A: B: C: D: y y1 0 0 1 0 0 1 1 1

98 最后我们可以得到二进制状态表 现态 次态/输出 x=0 x=1 A B C D C/0 B/0 A/1 D/0 A/0 B/1 现态 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 11/0 10/1 00/0 注意：有时满足分配原则的分配方案不唯一，这时可任选一种。

99 确定激励函数和输出函数 1. 触发器的激励表 触发器的激励表反映触发器从某种现态转换 到某种次态时，对触发器输入(激励)的要求。在这种表中，现态和次态作为自变量，输入(激励)作为因变量。触发器的激励表可由触发器的状态表直接推出。

100 R-S触发器激励表 D触发器激励表 Q Q(n+1) R S d 0 0 1 1 0 0 d 0 0 1 1 Q Q(n+1) D 1 0 0 0 1 1 0 1 1

101 J-K触发器激励表 T触发器激励表 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 1 0 0 0 1 1 0 1 1

102 2. 确定激励函数 两种方法：根据次态方程来确定和通过激励表来确定。常采用后一种方法。

103 例：若用D触发器实现下表所示的二进制状态表， 试写出激励和输出函数。
现 态 y2 y1 次态y2(n+1)y1(n+1)/输出Z x=0 x=1 0 0 0 1 1 1 1 0 10/0 00/0 01/1 00/1 01/0 10/1 11/1

104 解： 确定激励函数 现态y2 y1 y2(n+1)y1(n+1)/输出Z x=0 x=1 0 0 0 1 1 1 1 0 10/0 00/0
Q Q(n+1) D 1 0 0 0 1 1 0 1 1 解： 确定激励函数 现态y2 y1 y2(n+1)y1(n+1)/输出Z x=0 x=1 0 0 0 1 1 1 1 0 10/0 00/0 01/1 00/1 01/0 10/1 11/1 现态 y2 y1 次态 y2(n+1) y1(n+1) 0 0 0 1 1 1 1 0 输入 x 激励函数 D2 D1 1

105 1 00 01 y1 xy2 11 10 D2 现态 y2 y1 次态 y2(n+1) y1(n+1) 0 0 0 1 1 1 1 0 输入 x 激励函数 D2 D1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 00 01 y1 xy2 11 10 D1

106 确定输出函数 1 00 01 y1 xy2 11 10 Z 现态y2 y1 y2(n+1)y1(n+1)/输出Z x=0 x=1 0 0 0 1 1 1 1 0 10/0 00/0 01/1 00/1 01/0 10/1 11/1 Z=y2+xy1

107 例：若用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 10/1

108 Q Q(n+1) J K 0 d 1 d d 1 d 0 0 0 0 1 1 0 1 1 解： 确定激励函数 现态 y2 y1 次态 y2(n+1) y1(n+1) 0 0 0 1 1 1 1 0 输入 x 激励函数 J2K2J1K1 1 d 1 d 0 d d 1 d 1 d 1 d 1 1 d 0 d 1 d d 0 d 1 d 0 1 d 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 10/1

109 xy2 1 d 00 01 y1 11 10 J2 现态 y2 y1 次态 y2(n+1) y1(n+1) 0 0 0 1 1 1 1 0 输入 x 激励函数 J2K2J1K1 1 d 1 d 0 d d 1 d 1 d 1 d 1 1 d 0 d 1 d d 0 d 1 d 0 1 d 1 xy2 d 1 00 01 y1 11 10 K2 xy2 1 d 00 01 y1 11 10 J1 xy2 d 1 00 01 y1 11 10 K1 J1=1 K1=1

110 确定输出函数 1 00 01 y1 xy2 11 10 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 10/1 Z=y2y1+xy1

111 画出逻辑电路图 先画出触发器并给触发器编号，再根据激励函数和输出函数画出组合逻辑部分的电路，最后画出同步时钟信号线。

112 例如： 1 D1 C D2 y2 CP x & y1 z

113 4.6 同步时序逻辑电路设计举例 例： 设计一个“ 111…”序列检测器，用来检测串行二进制序列，要求每当连续输入3个(或3个以上)1时，检测器输出为1，否则输出为0。其典型输入输出序列如下： 输入x： 输出Z：

114 解： 作状态图和状态表 B 1/0 C 1/0 0/0 0/0 A 0/0 0/0 D 1/1 1/1

115 现 态 次态/输出Z x=0 x=1 A B C D A/0 B/0 C/0 D/1

116 状态化简 用观察法可得最大等效类为：(A), (B), (C,D) 令C＝(C,D),可得下列最简状态表 现 态 次态/输出Z x=0 x=1 A B C D A/0 B/0 C/0 D/1 现 态 次态/输出Z x=0 x=1 A B C A/0 B/0 C/0 C/1

117 AB，BC，AC应相邻 AB，AC应相邻 AB应相邻 A应为逻辑0 状态分配： 现 态 次态/输出Z x=0 x=1 A B C A/0 B/0 C/0 C/1 A C B 1 y1 y2

118 A C B 1 y1 y2 现态 y2 y1 次态y2(n+1)y1(n+1)/输出Z x=0 x=1 0 0 0 1 1 1 00/0 01/0 11/0 11/1 现 态 次态/输出Z x=0 x=1 A B C A/0 B/0 C/0 C/1

119 确定激励函数和输出函数表达式： 选用J－K触发器 现 态 y2 y1 次 态 y2(n+1y1(n+1) 0 0 0 1 1 1 1 0
Q Q(n+1) J K 0 d 1 d d 1 d 0 0 0 0 1 1 0 1 1 现 态 y2 y1 次 态 y2(n+1y1(n+1) 0 0 0 1 1 1 1 0 输 入 x 激励函数 J2 K2 J1 K1 d d 0 d 0 d 0 d d 1 d 1 d 1 d d d d 0 d 1 d 1 d d 0 d 0 d 0 1 输 出 Z d

120 xy2 d 00 01 1 y1 11 10 J2 现态 y2 y1 0 0 0 1 1 1 1 0 输入 x 激励函数 J2 K2 J1 K1 0 d 0 d 0 d d 1 d 1 d 1 d d d d 0 d 1 d 1 d d 0 d 0 d 0 1 输 出 Z d xy2 d 1 00 01 y1 11 10 K2 xy2 d 00 01 1 y1 11 10 J1 xy2 d 1 00 01 y1 11 10 K1 xy2 d 00 01 1 y1 11 10 Z J2=xy1, k2=x J1=x, k1=x Z=xy2

121 J2=xy1, k2=x J1=x, k1=x Z=xy2 画电路图 K1 C K2 y2 CP x y1 z & 1 J1 J2

122 分析： 由于电路有冗余状态“10”，一旦电路进入“10”状态， 不管输入为 0还是1，经过一个时钟周期后，电路应自动 进入有效状态，否则电路存在“挂起”现象。 分析方法为： 确定无效状态的次态，由于无效状态的次态为d， 所以在化简的卡诺图中，被卡诺圈圈起的d为1，没有被 卡诺圈圈起的d为0。然后判断无效状态的次态是否为有 效状态或是否存在“挂起”现象。

123 xy2 d 00 01 1 y1 11 10 J2 xy2 d 1 00 01 y1 11 10 K2 xy2 d 00 01 1 y1 11 10 J1 xy2 d 1 00 01 y1 11 10 K1 xy2 00 01 1 y1 11 10 Z

124 现 态 y2 y1 次 态 y2(n+1y1(n+1) 0 0 0 1 1 1 1 0 输 入 x 激励函数 J2 K2 J1 K1 0 d 0 d 0 d d 1 d 1 d 1 0 d 1 d 1 d d 0 d 0 d 0 1 输 出 Z xy2 d 00 01 1 y1 11 10 Z Z=xy1y2

125 00 0/0 01 1/0 10 1/1 11 现态 y2 y1 x=0 x=1 0 0 0 1 1 1 0 00/0 01/0 11/0 11/1 次态y2(n+1)y1(n+1)/Z

126 修改后的电路图： K1 C K2 y2 CP x y1 z & 1 J1 J2

127 例：设计一个三位串行奇偶校验电路。当电路串行接
收了三位二进制数后，如果1的个数为偶数，则电路输 出为1；否则为0。当接收了三位二进制数后，电路返 回初始状态。 F B A C G 0/0 1/0 D E 0/1 1/1 解： 作状态图和状态表

128 状态化简 现态 次态/输出 x=0 x=1 A B C D E F G B/0 D/0 F/0 A/1 A/0 C/0 E/0 G/0 现态 次态/输出 x=0 x=1 A B C D E B/0 D/0 E/0 A/1 A/0 C/0

129 DE应相邻 BC，DE应相邻 ABC应两两相邻 A应为逻辑0 状态分配： 现态 次态/输出 x=0 x=1 A B C D E B/0 D/0 E/0 A/1 A/0 C/0 y3y2 A B 00 01 1 y1 11 10 C D E

130 y3y2 A B 00 01 1 y1 11 10 C D E 现态 次态/输出 x=0 x=1 A B C D E B/0 D/0 E/0
1 y1 11 10 C D E 现态 次态/输出 x=0 x=1 A B C D E B/0 D/0 E/0 A/1 A/0 C/0 Y3Y2Y1 次态/输出 x=0 x=1 000 010 110 100 101 010/0 100/0 101/0 000/1 000/0 110/0

131 Y3Y2Y1 次态/输出 x=0 x=1 000 001 010 011 100 101 110 111 010/0 ddd/d 100/0 000/1 000/0 101/0 110/0 101/0 000/0 000/1 100/0

132 xy3 y2y1 1 d D3 xy3 y2y1 d D2 1 xy3 y2y1 1 d D1 xy3 y2y1 d 1 Z
00 01 11 10 xy3 y2y1 1 d D3 00 01 11 10 xy3 y2y1 d D2 1 Y3Y2Y1 次态/输出 x=0 x=1 000 001 010 011 100 101 110 111 010/0 ddd/d 100/0 000/1 000/0 101/0 110/0 101/0 000/0 000/1 00 01 11 10 xy3 y2y1 1 d D1 00 01 11 10 xy3 y2y1 d 1 Z

133 列出激励函数和输出函数表达式： D3=Y2+XY3 D2=Y3Y2 D1=XY3Y2+XY3Y2 =Y2(XY3) Z=XY1+XY3Y2Y1 画逻辑电路图：（略）。

134 xy3 y2y1 1 D3 xy3 y2y1 1 D2 分析： xy3 y2y1 1 D1 xy3 y2y1 1 Z 00 01 11 10
00 01 11 10 xy3 y2y1 1 D3 00 01 11 10 xy3 y2y1 1 D2 分析： 00 01 11 10 xy3 y2y1 1 D1 00 01 11 10 xy3 y2y1 1 Z

135 Y3Y2Y1 次态/输出 x=0 x=1 000 001 010 011 100 101 110 111 010/0 100/0 000/1 000/0 101/0 101/0 110/0 110/1 101/1 000/0 000/1 100/0 100/1

136 00 01 11 10 xy3 y2y1 1 Z Z=XY3Y2Y1+XY3Y2Y1 修改后的画逻辑电路图：（略）。