数字系统与逻辑设计--第五章(C)

1、电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 5.3.3 序列信号发生器设计序列信号发生器设计 分分 类类 1、计数型、计数型 2、移存型、移存型由由移位寄存器加反馈电路移位寄存器加反馈电路构成。构成。 由由模值为序列信号长度模值为序列信号长度的计数的计数 器器加组合逻辑电路加组合逻辑电路构成。构成。 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 1、计数器型序列信号发生器、计数器型序列信号发生器 计数器的作用是产生节拍计数器的作用是产生节拍 模值等于序列长度模值等于序列长度或或序序 列长度的整数倍列长度的整数倍。 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学

2、院 例例5.3.3 例例5.3.35.3.3：分析图分析图5.3.65.3.6所示电路所示电路Z Z的输出序列，并采用的输出序列，并采用 与非门和同或门增加两个输出序列信号：与非门和同或门增加两个输出序列信号： X=110011,110011,X=110011,110011,和和Y=101101,101101,Y=101101,101101,。 Q2nQ1nQ0nQ2n+1Q1n+1Q0n+1 0 0 0 0 0 1 0 1 1 1 1 1 1 1 01 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1 0 00 0 0 Z 0 0 0 0 0 1 输出序列为输出序列为000001

3、nnnnnn QQQQQQD 01201 20 nn QQZ 12 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 例例5.3.3 Q2nQ1nQ0n 0 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1 0 0 Z 0 0 0 0 0 1 XY 1 1 0 0 1 1 1 0 1 1 0 1 nnnn QQQQX 1010 nnnnnn QQQQQQY 100101 如果计数器的模值能如果计数器的模值能 够被序列信号的长度够被序列信号的长度 整除，则可以用它来整除，则可以用它来 产生长度短于计数器产生长度短于计数器 模值的序列信号。模值的序列信号。 =(0,1,4,6)+

4、 (2,5) =(0,3,4,7)+ (2,5) 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 设计方法设计方法 仿仿真真 确确定定触触发发器器数数K K 给给定定序序列列信信 号号长长度度M M KK M22 1 作作状状态态转转移移表表，为为每每个个 状状态态分分配配一一个个输输出出值值 设设计计计计数数器器并并 检检查查自自启启动动 设设计计组组合合电电路路 画画逻逻辑辑图图 一一般般按按同同步步计计数数器器设设计计 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 确定模值确定模值M和触发器数和触发器数K 举例举例 设计一个计数型序列信号发生器，输出序设计一个计数型

5、序列信号发生器，输出序 列为列为1010010100。 M=5 K=3 作状态转移表作状态转移表 Z=（0,2）+ （ （5,6,7） Z 1 0 1 0 0 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 设计计数器设计计数器 nnn nnnnn nnnn QQQ QQQQQ QQQQ 0 101 02 2 1 0 0 1 1 21 1 nnn QKQJQ 1 JK触发器触发器 特征方程特征方程 1 1 0 20 011 2 012 K QJ QKJ K QQJ n n nn 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 举例（续）举例（续） 检查自启动检查自启动 10

6、0100 101101 111111 010010011011 001001 000000 110110 Q Q2 2Q Q1 1Q Q0 0 设计组合电路设计组合电路 nn QQ 02 能自启动能自启动 Z=（0,2）+ （ （5,6,7） 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 画逻辑电路图画逻辑电路图 1 1J J 1 1J J 1 1J J 1 1K K1 1K K1 1K K & & & & C C1 1C C1 1C C1 1 & & Z Z C CP P Q Q0 0 Q Q1 1 Q Q2 2 1 1 1 2 012 K QQJ nn n QKJ 011 1

7、0 20 K QJ n nn QQZ 02 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 仿真仿真 设计符合要求设计符合要求 1 0 1 0 01 0 1 0 01 0 1 0 0 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 2. 移存型序列信号发生器移存型序列信号发生器 由给定序列信号由给定序列信号 确定循环长度M确定循环长度M 求求最最少少移移位位寄寄存存器器位位数数K K KK M22 1 K K是是否否够够大大K=K+1K=K+1 检检查查自自启启动动 画画逻逻辑辑图图 仿仿真真 Y N 设设 计计 方方 法法 由移位寄存器由移位寄存器 加上反馈构成加上反馈构

8、成 对给定的序列取对给定的序列取M组组K 位码，每取一组后移位码，每取一组后移 一位，看一位，看M组组K位码中位码中 是否有重复的码，若是否有重复的码，若 没有则没有则K已足够大。已足够大。 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 例例5.3.4 设计一个移存型序列信号发生器设计一个移存型序列信号发生器，输出序列为，输出序列为 1010010100。 M=5，先取，先取K=3 求移存器位数求移存器位数K 101100010001010 重复重复 取取K=K+1=4 1010 0100 1001 0010 0101 无重复无重复 电路中心电路中心 张咏梅张咏梅 电子工程学院电子

9、工程学院 求反馈函数求反馈函数D0 列状态转移表，求反馈函数列状态转移表，求反馈函数D0。 D D0 0 n Q3 n Q2 n Q 1 1 11 1 0 0 1 1 0 0 0 01 1 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 nn QQ 03 1010 0100 1001 0010 0101 0 1 0 1 0 D0=(2,4)+ 0 1 0 DQ n 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 检查自启动检查自启动 作全状态图作全状态图 能自启动能自启动 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院

10、 画逻辑图画逻辑图 C C1 1C C1 1C C1 1 1 1D D1 1D D1 1D D C CP P Q Q0 0Q Q1 1 Q Q2 2 C C1 1 1 1D D 3 Q & & nn QQD 030 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 仿真仿真 设计符合要求设计符合要求 1 0 1 0 0 1 0 1 0 0 仿真波形仿真波形 每个触发器每个触发器 都输出相同都输出相同 的序列的序列 1 0 1 0 0 1 0 1 0 0 nn QQD 030 10100100100100100101 1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1

11、 0 1 1 0 1 0 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 （1）计数型计数型序列信号发生器中的计数器的输出可以序列信号发生器中的计数器的输出可以 供给几个组合电路，供给几个组合电路，产生几种长度相同产生几种长度相同但序列内容不但序列内容不 同的序列信号同的序列信号（如果（如果计数器的模值可以被序列的长度计数器的模值可以被序列的长度 整除时整除时，序列长度也可以短于计数序列长度也可以短于计数器的模值器的模值）。）。 （2）计数型计数型序列信号发生器序列信号发生器所用的触发器比移存型所用的触发器比移存型 的少。的少。 （3）计数型计数型序列信号发生器的序列信号发生器的结构

12、结构一般都比移存型一般都比移存型 序列信号发生器要序列信号发生器要复杂一些复杂一些，设计过程也比较复杂。设计过程也比较复杂。 计数型与移存型序列信号发生器的比较计数型与移存型序列信号发生器的比较 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 5.3.4 M序列发生器序列发生器 M序列序列伪随机信号伪随机信号最长线性序列最长线性序列伪随机码伪随机码 M序列序列：在一个周期内，：在一个周期内，0和和1的数目接近相等，并且有的数目接近相等，并且有 各种长度的各种长度的0或或1的信号组合。看起来就象是的信号组合。看起来就象是0或或1随机出随机出 现的信号序列，而实际上是一个固定的已知序列。

13、现的信号序列，而实际上是一个固定的已知序列。 M序列的用途：序列的用途：测试信道、误码仪测试信道、误码仪/传输特性测试仪、传输特性测试仪、 扰码器扰码器/解扰器解扰器 M序列发生器序列发生器：产生：产生M序列的电路序列的电路 M序列发生器序列发生器实际上是一种实际上是一种移存型序列信号发生器移存型序列信号发生器 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 M序列发生器的特点序列发生器的特点 M序列的长度序列的长度M=2K-1（ K是移存器的位数）。是移存器的位数）。 反馈电路是某些触发器输出的反馈电路是某些触发器输出的异或异或加上加上校正项校正项，校，校 正项是先将正项是先将k个

14、触发器的输出个触发器的输出 “或非或非”，再将这个或，再将这个或 非结果和原来的反馈输出再次进行非结果和原来的反馈输出再次进行“异或异或”运算：运算： M序列一定包含序列一定包含一组一组K个相连的个相连的1信号信号，一组一组K-1个个 相连的相连的0信号信号以及一些其他组合的以及一些其他组合的1或或0信号。信号。 M序列发生器的设计已经定型化，一般只需查表即可。序列发生器的设计已经定型化，一般只需查表即可。 0122100 QQQQQDD kk 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 M序列发生序列发生 器的设计器的设计 查查表表得得到到反反馈馈 函函数数再再加加上上全全 零

15、零校校正正项项 用用移移位位寄寄存存器器和和 异异或或门门实实现现设设计计 仿仿真真 209715121 3276715 409512 204711 102310 5119 2558 1277 636 315 154 73 反馈函数反馈函数M=2k-1k 2120 QQQQ或 6260 QQQQ或 201 QQ 11530 QQQQ 7210 QQQQ 1413140 QQQQ或 4241 QQQQ或 3230 QQQQ或 50 QQ 83 QQ 96 QQ 101 QQ 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 M序列发生器的自启动序列发生器的自启动 M=15 nn QQD

16、300 不能自不能自 启动启动 当各级触发器输出都为当各级触发器输出都为0时，不能回到正常的序列。时，不能回到正常的序列。 为了能自启动，应加上一个校正项。为了能自启动，应加上一个校正项。 0122100 QQQQQDD kk 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 M序列发生器举例序列发生器举例 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 nn QQD 300 M=15 每个触发器都输出相同的序列每个触发器都输出相同的序列 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 JK触发器构成的触发器构成的M序列发生器序列发生器 移存器可以用移存器可以用D

17、触发器也可以用触发器也可以用JK触发器构成。触发器构成。 nnn QKQJQ 1 当反馈函数是当反馈函数是Q0 Qi时：时： n i nn QQDQ 00 1 0 n i QKJ 00 nn i nn i QQQQ 00 不需要异或门不需要异或门 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 M序列的缩短序列的缩短 当所需要的序列长度为当所需要的序列长度为L（LM），且对于输），且对于输 出什么样的序列没有特别的要求时，可以将出什么样的序列没有特别的要求时，可以将 M序列缩短。序列缩短。 当当M序列发生器进入某一个特定的状态序列发生器进入某一个特定的状态S时，时， 跳过跳过M-L个

18、状态个状态，使循环长度缩短为，使循环长度缩短为L。 方法：方法：预置法预置法 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 M序列的缩短序列的缩短 以全以全“1”状态作为第一个状态状态作为第一个状态，找到，找到第第L+1状态状态 作为特定的起跳状态作为特定的起跳状态S，用与非门检出该状态，用与非门检出该状态 （在在S状态时与非门的输出为状态时与非门的输出为0），并将与非门的），并将与非门的 输出接到所有触发器的输出接到所有触发器的异步置位端异步置位端，使全部触发，使全部触发 器置器置“1”，从而跳过后面的所有状态，即，从而跳过后面的所有状态，即从第从第 L+1状态直接跳回到全状态直

19、接跳回到全“1”状态状态。第。第L+1个状态个状态 时间很短，马上就被全时间很短，马上就被全“1”状态所取代，状态所取代，在时间在时间 上第上第L+1个状态和全个状态和全“1”状态合用一个时钟周期状态合用一个时钟周期。 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 M序列的缩短序列的缩短 例：将例：将M=15的序列缩短为的序列缩短为L=11的序列。的序列。 nn QQD 300 1111 0 1 0 1 1 0 0 1 0 0 0 1 0 0 0 0 1 10001111 1 111 为了保证触发器置位的可靠性，与非门的输出端可为了保证触发器置位的可靠性，与非门的输出端可 增加一个

20、触发器，使置位信号延迟半个时钟周期。增加一个触发器，使置位信号延迟半个时钟周期。 S状态状态 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 M序列的缩短序列的缩短 例：将例：将M=15的序列缩短为的序列缩短为L=11的序列。的序列。 nn QQD 300 1111 0 1 0 1 1 0 0 1 0 0 0 从从4个触发器的输出端得到的输出序列是不一样的。个触发器的输出端得到的输出序列是不一样的。 Q3、Q2、Q1和和Q0输出的序列分别为：输出的序列分别为：11110101100、 11101011001、11010110010和和 10101100100。 电路中心电路中心 张咏

21、梅张咏梅 电子工程学院电子工程学院 M序列的缩短序列的缩短 CLRN D PRN Q DFF inst CLRN D PRN Q DFF inst1 CLRN D PRN Q DFF inst2 CLRN D PRN Q DFF inst3 NOT inst4 NOT inst5 NOT inst6 VCC cp INPUT XOR inst7 NAND4 inst8 Q3 Q0 Q3.0 OUTPUT set set OUTPUT D0 OUTPUT XOR inst9 NOR4 inst13 Q2 Q1 D0 1 1 1 1 0 1 0 1 1 0 0 1 1 1 0 1 0 1 1 0

22、0 1 1 1 0 1 0 1 1 0 0 1 0 1 0 1 0 1 1 0 0 1 0 0 1 0 0 0 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 5.4 一般时序逻辑电路的设计方法一般时序逻辑电路的设计方法 本节介绍稍微复杂一点的、带有某种本节介绍稍微复杂一点的、带有某种“智能智能”的数字的数字 系统的设计方法，即系统的设计方法，即有限状态机有限状态机的设计方法的设计方法 。 以触发器为记忆存储电路的以触发器为记忆存储电路的同步时序电路同步时序电路称为称为有限状有限状 态机态机FSM（finite state machine）。 实现数字系统的主控部件。实现数字系统的主

23、控部件。 检测外部信号，并作出适当的响应。检测外部信号，并作出适当的响应。 发出各种信号，以协调并控制整个系统的工作，完发出各种信号，以协调并控制整个系统的工作，完 成指定的任务。成指定的任务。 “状态机状态机”的作用：的作用： 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 数字系统数字系统 子系统子系统 输入控输入控 制信号制信号 输出控输出控 制信号制信号 信息信息 输入输入 信息信息 输出输出 控 制 器控 制 器 输出输出 接口接口 输出输出 接口接口 输入输入 接口接口 输入输入 接口接口 子系统子系统 子系统子系统 时钟时钟 数据处理器数据处理器 由若干由若干数字电路数

24、字电路和和逻辑逻辑 部件部件构成的能够构成的能够处理处理或或 传送传送数字信息的设备。数字信息的设备。 其它物理量与其它物理量与 数字量的转换数字量的转换 数字量与其它数字量与其它 物理量的转换物理量的转换 使各子系统和使各子系统和 整个系统按规整个系统按规 定顺序工作定顺序工作 完成数字量的运完成数字量的运 算等处理工作算等处理工作 数字系统与功能部件（数字单元电路）的区别：数字系统与功能部件（数字单元电路）的区别：有无控制器有无控制器 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 状态机和状态机和CPU/MCU 许多系统控制器是用微处理器许多系统控制器是用微处理器CPU和微控制

25、器和微控制器MCU实现的。实现的。 但在高速系统中，仍然需要用但在高速系统中，仍然需要用硬件控制器硬件控制器即即状态机状态机。 状态机的特点：状态机的特点： 控制功能单一，用途单一。控制功能单一，用途单一。 控制速度和响应速度快控制速度和响应速度快。 控制逻辑修改较难。控制逻辑修改较难。 CPU/MCU的特点：的特点： 控制功能（算法）可以相控制功能（算法）可以相 当复杂。当复杂。 控制速度和响应速度较慢控制速度和响应速度较慢。 修改逻辑简单，只要改变修改逻辑简单，只要改变 程序即可。程序即可。 用用PLD实现状态机时实现状态机时 逻辑修改变得较容易逻辑修改变得较容易 电路中心电路中心 张咏梅

26、张咏梅 电子工程学院电子工程学院 5.4.1 一般同步时序逻辑电路的设计方法一般同步时序逻辑电路的设计方法 根据给出的具体的逻辑问题，求出实现这一逻根据给出的具体的逻辑问题，求出实现这一逻 辑功能的逻辑电路，且电路简单，工作可靠。辑功能的逻辑电路，且电路简单，工作可靠。 电路最简的标准：电路最简的标准： 小规模电路小规模电路：所用：所用触发器触发器和和门电路门电路的的数目最少数目最少， 且触发器和门的且触发器和门的输入端数目最少输入端数目最少。 中、大规模电路中、大规模电路：所用的：所用的集成电路和外围门集成电路和外围门 电路的数目最少电路的数目最少，器件种类最少器件种类最少，相互间的，相互间

27、的 连线也最少连线也最少。 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 同步时序电路的设计同步时序电路的设计过程过程 设设 计计 要要 求求 原始状原始状 态图或态图或 状态表状态表 状状 态态 简简 化化 状状 态态 分分 配配 状态方程状态方程 输出方程输出方程 激励方程激励方程 逻辑图逻辑图 选定触发选定触发 器类型器类型 用触发器和用触发器和 门电路实现门电路实现 设计的方法设计的方法 以原因或条件作为输入变量，以结果为输出变量。以原因或条件作为输入变量，以结果为输出变量。 仿真仿真 是是 否否 确定输入、输出确定输入、输出 变量和变量和状态数状态数。 检查自启动检查自启

28、动 根据根据需要需要“记忆记忆” 的的输入输入信息或结果信息或结果 来来确定确定状态数状态数。 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 一、建立原始状态图和状态表一、建立原始状态图和状态表 原始状态图的建立没有严格的步骤，关键是原始状态图的建立没有严格的步骤，关键是根据根据 设计要求，分析清楚电路的输入和输出，设计要求，分析清楚电路的输入和输出，确定有多少确定有多少 种输入信息需要种输入信息需要“记忆记忆”，对每一种需要对每一种需要“记忆记忆”的的 输入信息规定一种状态来表示输入信息规定一种状态来表示，根据输入的条件和输，根据输入的条件和输 出要求确定各状态之间的关系，从而构

29、成原始状态图。出要求确定各状态之间的关系，从而构成原始状态图。 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 例例5.4.1 5.4.1 设计设计一个用来检测二进制输入序列的检测一个用来检测二进制输入序列的检测 电路，当输入序列中连续输入电路，当输入序列中连续输入4 4位数码均位数码均 为为1 1时，电路输出时，电路输出1 1（可重叠可重叠，即当连续输，即当连续输 入到第五个入到第五个1 1时也输出时也输出1 1）。）。 A A A：初始状态：初始状态 B：记忆输入记忆输入1 C：记忆输入记忆输入10 D：记忆输入记忆输入11 B B D D 1/0 1/0 1/1 0/0 0/0

30、 0/0 该电路必须该电路必须“记忆记忆”3 位连续输入序列。位连续输入序列。 以输入序列为输入以输入序列为输入 变量，用变量，用表示。表示。 以检测结果为输出以检测结果为输出 变量，用变量，用Z表示表示 1/0 E：记忆输入记忆输入100 F：记忆输入记忆输入101 G：记忆输入记忆输入110 H：记忆输入记忆输入111 0/0 1/0 1/0 1/0 1/0 0/0 0/0 0/0 0/0 X/Z 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 例例5.4.1 5.4.1 Sn A B C D E F G H X A/0B/0 C/0D/0 E/0F/0 G/0H/0 1 A/0

31、B/0 A/0D/0 A/0B/0 A/0H/1 A A B B D D 1/0 1/0 1/1 0/0 0/0 0/0 1/0 0/0 1/0 1/0 1/0 1/0 0/0 0/0 0/0 0/0 0 Sn+1/Z X/Z 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 序列信号检测器的序列重叠问题序列信号检测器的序列重叠问题 1 1 1 1 1 1 0 1 不可重叠不可重叠 0 0 0 1 0 0 0 1 设计一个用来检测二进制输入序列的检测电路，当输设计一个用来检测二进制输入序列的检测电路，当输 入序列中连续输入入序列中连续输入4 4位数码均为位数码均为1 1时，电路输出时，

32、电路输出1 1（可重可重 叠叠，即当连续输入到第五个，即当连续输入到第五个1 1时也输出时也输出1 1）。）。 输入序列输入序列 可重叠输出可重叠输出 不可重叠输出不可重叠输出 011 0 0 0 0 0 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 二、状态简化二、状态简化 在建立原始状态表时在建立原始状态表时追求的目标是完整准确地反映设计要求追求的目标是完整准确地反映设计要求， 在没有把握时宁可多设一些状态以免遗漏信息。因此作出的状在没有把握时宁可多设一些状态以免遗漏信息。因此作出的状 态表态表可能存在若干多余状态可能存在若干多余状态，应加以简化应加以简化。 1、完全规定状态表

33、完全规定状态表的简化的简化 完全规定状态表完全规定状态表中每一个中每一个下一状态和输出都有确定的值下一状态和输出都有确定的值。 2、不完全规定状态表不完全规定状态表的简化的简化 不完全规定状态表不完全规定状态表中的中的下一状态或者输出值可以是不确定的下一状态或者输出值可以是不确定的， 甚至两者都可以是不确定的甚至两者都可以是不确定的，需要在设计中逐步加以确定。，需要在设计中逐步加以确定。 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 完全规定状态表的简化完全规定状态表的简化 关键是找关键是找等价状态等价状态，并将它们合并，从而使状态表中的状，并将它们合并，从而使状态表中的状 态数达

34、到最少。态数达到最少。 两个状态若两个状态若同时满足同时满足以下两个条件则称为以下两个条件则称为等价状态等价状态。 1）在同样的输入作用下都有相同的输出在同样的输入作用下都有相同的输出； 2）在同样的输入条件下其相应的下一状态是彼此等价的在同样的输入条件下其相应的下一状态是彼此等价的： 对应的对应的下一状态相同下一状态相同。 其其下一状态就是两个现在状态本身下一状态就是两个现在状态本身。 其其下一状态将被证明是彼此等价的下一状态将被证明是彼此等价的 （条件等价条件等价）。）。 C、D等价等价 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 完全规定状态表的简化完全规定状态表的简化 等

35、价类等价类：互相等价的状态构成的集合。：互相等价的状态构成的集合。 最大等价类最大等价类：不包含在其它等价类之中的等价类。：不包含在其它等价类之中的等价类。 等价状态的传递性等价状态的传递性：若状态：若状态AB等价，状态等价，状态AC也等价，则也等价，则 状态状态BC必然等价。必然等价。 若若某一状态与任何状态都不等价某一状态与任何状态都不等价，则它，则它自己就构成一个最大自己就构成一个最大 等价类等价类。 最大等价类集合最大等价类集合：所有最大等价类构成的集合就是最大等价类：所有最大等价类构成的集合就是最大等价类 集合。最大等价类集合中的集合。最大等价类集合中的每个最大等价类可以合并成每个最

36、大等价类可以合并成最简状最简状 态表中的态表中的一个状态一个状态。最简状态表中。最简状态表中状态的数目状态的数目就就等于等于最大等价最大等价 类集合中类集合中最大等价类的数目最大等价类的数目。 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 完全规定状态表的简化完全规定状态表的简化 化简方法：化简方法：隐含表法隐含表法 隐含表隐含表（Implication table）：）： 一种水平方向无尾一种水平方向无尾，垂直方向垂直方向 无头的直角三角形表格无头的直角三角形表格。 B B C C D D E E A A B B C C D D 例：若某个状态表有例：若某个状态表有A、B、C、D

37、、E五个状态，隐五个状态，隐 含表的含表的水平方向水平方向为为A、B、C、D四个状态（四个状态（无尾无尾），）， 垂直方向垂直方向为为B、C、D、E四个状态（四个状态（无头无头）。）。 电路中心电路中心 张咏梅张咏梅 电子工程学院电子工程学院 完全规定状态表的简化完全规定状态表的简化步骤步骤 1）作隐含表，在每一个小格中填入相应状态对的关系：）作隐含表，在每一个小格中填入相应状态对的关系： A、状态对、状态对肯定不等价肯定不等价，在小格内打，在小格内打“”； B、状态对、状态对肯定等价肯定等价，在小格内打，在小格内打“ ”； C、状态对是、状态对是条件等价条件等价的，的，把所需要的等价条件都填在相把所需要的等价条件都填在相 应的小格内应的小格内。 2）由隐含表寻求所有的等价状态。）由隐含表寻求所有的等价状态。 从确定的不等价状态出发，反复判断状态对是等价还是不等从确定的不等价状态出发