1、1 第 五 章第五章同步时序逻辑电路同 步 时 序 逻 辑 电 路 2 第五章同步时序逻辑电路本章知识要点: 时序逻辑电路的基本概念; 同步时序逻辑电路的分析和设计方法; 典型同步时序逻辑电路的分析和设计。 3 第五章同步时序逻辑电路5 1概述5.1.1 时序逻辑电路的定义、结构和特点若逻辑电路在任何时刻产生的稳定输出信号不仅与电路该时刻的输入信号有关，还与电路过去的输入信号有关，则称为时序逻辑电路。一定义 4 二结构 时序逻辑电路由组合电路和存储电路两部分组成，通过反馈回路将两部分连成一个整体，一般结构框图如下图所示。 图中，x1，xn为输入信号；Z1，Zm为输出信号；y1，ys为时序逻辑电
2、路的“状态” ；Y1，Yr为时序逻辑电路中的激励信号，它决定电路下一时刻的状态；CP为时钟脉冲信号，它是否存在取决于时序逻辑电路的类型。5 第五章同步时序逻辑电路时序逻辑电路的状态y1，ys是存储电路对过去输入信号记忆的结果，它随着外部信号的作用而变化。次态与现态的概念： 在对电路功能进行研究时，通常将某一时刻的状态称为“现态”，记作yn，简记为 y； 将在某一现态下，外部信号发生变化后到达的新的状态称为 “次态”，记作 y(n+1) 。6 第五章同步时序逻辑电路三特点时序逻辑电路具有如下特征：电路由组合电路和存储电路组成，具有对过去输入进行记忆的功能； 电路中包含反馈回路，通过反馈使电路功能
3、与“时序”相关； 电路的输出由电路当时的输入和状态(对过去输入的记忆)共同决定。7 第五章同步时序逻辑电路5. 1 .2时序逻辑电路的分类 时序逻辑电路通常可以按照电路的工作方式、电路输出对输入的依从关系或者输入信号的形 式进行分类。一按电路的工作方式分类按照电路的工作方式，时序逻辑电路可分为同步时序逻辑电路和异步时序逻辑电路两种类型。本章讨论同步时序电路。1. 同步时序电路 （1）特点：电路中有统一的定时信号，存储器件采用时钟控制触发器，电路状态在时钟脉冲控制下同时发生转换，即电路状态的改变依赖于输入信号和时钟脉冲信号。具体说： 状态如何变？ 取决与输入信号； 状态何时变？取决于时钟信号；每
4、个状态维持多久？取决于时钟脉冲的周期。 8 第五章同步时序逻辑电路（2）现态与次态 同步时序电路中的现态与次态是针对某个时钟脉冲而言的。现态-指时钟脉冲作用之前电路所处的状态。次态-指时钟脉冲作用之后电路到达的状态。注意：前一个脉冲的次态即后一个脉冲的现态！如（3）对时钟的要求脉冲的宽度：必须保证触发器可靠翻转；脉冲的频率：必须保证前一个脉冲引起的电路响应完全结束后，后一个脉冲才能到来。2. 异步时序逻辑电路异步时序逻辑电路的存储电路可由触发器或延时元件组成，电路中没有统一的时钟信号同步，电路输入信号的变化将直接导致电路状态的变化。123次态=现态 次态=现态cp9 第五章同步时序逻辑电路二按
5、电路输出对输入的依从关系分类根据电路的输出是否与输入直接相关，时序逻辑电路可以分为Mealy型和Moore型两种不同的 模型。 1Mealy型电路：若时序逻辑电路的输出是电路输入和电路状态的函数，则称为Mealy型时序逻辑电路。 2Moore型电路：若时序逻辑电路的输出仅仅是电路状态的函数，则称为Moore型时序逻辑电路。 Mealy型电路的输入和输出之间存在直接联系，而Moore型电路则是将全部输入转换成电路状态后再和输出建立联系。即：状态 yMealy型电路过去的输入当前的输入Z状态 yMoore型电路所有的输入Z10 第五章同步时序逻辑电路 若一个时序逻辑电路没有专门的外部输出信号，而是
6、以电路状态作为输出，则可视为Moore型电路的特殊情况。 无论是同步时序逻辑电路或是异步时序逻辑电路，均有Mealy型和Moore型两种模型。同步时序逻辑电路中两种模型的结构框图如下图所示。11 第五章同步时序逻辑电路三按输入信号形式分类时序逻辑电路的输入信号可以是脉冲信号也可以是电平信号。根据输入信号形式的不同，时序逻辑电路通常又被分为脉冲型和电平型两种类型。 下图所示为不同输入信号的波形图。12 第五章同步时序逻辑电路5.1.3 同步时序逻辑电路的描述方法同步时序电路可采用逻辑表达式、状态表、状态图进行描述。状态表和状态图是同步时序逻辑电路分析和设计的重要工具。此外，必要时还可以通过时间图
7、加以描述。一逻辑函数表达式 同步时序电路的结构和功能，可用三组逻辑函数表达式描述。1输出函数表达式：是一组反映电路输出Z与输入x和状态y之间关系的表达式。 Zi = fi(x1，xn ,y1,，ys)i=1,2,m（Mealy型电路) Zi = fi(y1，ys)i=1,2,m（Moore型电路）13 第五章同步时序逻辑电路2激励函数表达式： 激励函数又称为控制函数，它反映了存储电路的输入Y与外部输入x和电路状 态y之间的关系。其函数表达式为 Yj = gj(x1，xn,y1,，ys)j =1,2,r3次态函数表达式：次态函数用来反映同步时序电路的次态y(n+1)与激励函数Y和电路现态y之间的
8、关系，它与触发器类型相关。其函数表达式为 y l(n+1) = kl(Yj，yl)j=1,2,r ；l =1,2 ,，s14 第五章同步时序逻辑电路二状态表状态表：反映同步时序电路输出Z、次态y(n+1)与电路输入x、现态y之间关系的表格，又称为状态转移表。 Mealy型同步时序电路状态表的格式如作下表所示。表格的上方从左到右列出一位输入x的全部取值组合，表格左边从上到下列出电路的全部状态y，表格的中间列出对应不同输入组合和现态下的次态y(n+1)和输出Z。表中，列数 = 一位输入的所有取值组合数；行数 = 触发器的状态组合数。15 第五章同步时序逻辑电路状态表是同步时序电路分析和设计中常用的
9、工具，它非 常清晰地给出了同步时序电路在不同输入和现态下的次态和 输出。Moore型电路状态表的格式如左下表所示。考虑到Moore型电路的输出Z仅与电路的现态y有关，为了清晰起见，将输出单独作为一列，表示其值完全由现态确定。16 第五章同步时序逻辑电路三状态图 状态图：是一种反映同步时序电路状态转换规律及相应输入、输出取值关系的有向图。 在状态图中，用圆圈表示电路的状态，连接圆圈的有向线段表示状态的转换关系，箭头的起点表示现态，终点表示次态，当箭头起止于同一状态时，表明在指定输入下状态保持不变。 Mealy型电路状态图的形式如图(a)所示。图中，在有向箭头的旁边标出发生该转换的输入条件以及在该
10、输入和现态下的相应输出。x/zxMoore型电路状态图的形式如图(b) 所示，电路输出标在圆圈内的状态右下方，表示输入只与状态相关。17 第五章同步时序逻辑电路 用状态图描述同步时序电路的逻辑功能具有直观、形象等优点。 状态图和状态表示是同步时序电路分析和设计的重要工具，相比之下， 状态表更规范，状态图更形象。四时间图时间图是用波形图的形式来表示输入信号、输出信号和电路状态等的取值在各时刻的对应关系，通常又称为工作波形图。在时间图上，可以把电路状态转换的时刻形象地表示出来。18 第五章同步时序逻辑电路5.2同步时序逻辑电路分析同步时序逻辑电路分析的关键是找出电路状态和输出随输入变化而变化的规律
11、，以便确定其逻辑功能。5.2.1分析的方法和步骤常用方法有表格法和代数法。一. 表格分析法的一般步骤 1写出输出函数和激励函数表达式。 2借助触发器功能表列出电路次态真值表。 3作出状态表和状态图（必要时画出时间图）。 4归纳出电路的逻辑功能。19 第五章同步时序逻辑电路二. 代数分析法的一般步骤 由分析步骤可知，两种方法仅第二步有所不同，分析中可视具体问题灵活选用。1写出输出函数表达式和激励函数表达式。 2把激励函数表达式代入触发器的次态方程，导出电路的次态方程组。 3作出状态表和状态图（必要画出时间图）。 4归纳出电路的逻辑功能。 20 第五章同步时序逻辑电路5.2.2分析举例例1 用表格
12、法分析下图所示同步时序逻辑电路。解：该电路由两个J-K触发器和一个异或门组成，电路的输入为x，电路的状态(即触发器状态)用y2、y1表示。电路的输出即状态变量，因此，该电路属于Moore型电路的特例。1.写出输出函数和激励函数表达式 该电路的输出即为状态，各触发器的激励函数表达式为J1=K1=1；J2=K2=xy121 第五章同步时序逻辑电路2列出电路次态真值表 列次态真值表时，首先列出激励函数（此例 J1 = K1 = 1；J2 = K2 = xy1）的真值表，然后根据现态和激励函数值以及相应触发器的功能表填出每一组输入和现态取值下的次态。 J KQ(n+1)0 0 0 1 1 0 1 1
13、Q 0 1 Q22 第五章同步时序逻辑电路3作出状态表和状态图 根据次态真值表，可作出该电路的状态表和状态图如下。现态y2 y1次态y2(n+1)y1(n+1） X=0 X=10 0 0 1 1 0 1 10 1 1 0 1 1 0 01 1 0 0 0 1 1 0状态表23 第五章同步时序逻辑电路4描述电路的逻辑功能。 由状态图可知，该电路是一个2 位二进制数可逆计数器。当输入x=0 时，可逆计数器进行加1计数，其计数序列为 00011011 当输入x=1时，可逆计数器进行减1计数，其计数序列为 00011011在时序逻辑电路分析中，除了状态图和状态表之外，通常还用到时间图。时间图能较形象、
14、生动地体现时序电路的工作过程，并可和实验观察的波形相比较，是描述时序电路工作特性的一种常用方式。24 第五章同步时序逻辑电路作时间图的一般步骤： 假设电路初始状态，并拟定一典型输入序列； 作出状态和输出响应序列； 根据响应序列画出波形图。 本例设电路的初始状态y2y1=00,输入x为电平信号，典型输入序列为111100000，根据状态图可作出电路的状态响应序列如下： CP:123456789 x : 111100000 y2 : 011000110 y1 : 010101010 y2(n+1): 110001100 y1(n+1): 10101010125 第五章同步时序逻辑电路 根据状态响应
15、序列，可作出时间图如下图所示。由于前一个时钟脉冲的次态即为后一个时钟脉冲的现态，所以，时间图中可以将现态和次态共用一个波形表示。CP: 123456789 x : 111100000 y2 : 011000110 y1 : 010101010 y2(n+1):110001100 y1(n+1):101010101 26 第五章同步时序逻辑电路例2分析下图所示的同步时序电路。解：该电路有一个输入x和一个输出Z。输出Z与输入x及电路状态均有直接联系，因此属于Mealy型。1写出输出函数和激励函数的表达式 27 第五章同步时序逻辑电路2. 列出电路次态真值表 根据激励函数表达式和D触发器的功能表，可
16、作出该电路的次态真值表如下表所示。28 第五章同步时序逻辑电路3.作出状态表和状态图 根据输出函数表达式和次态真值表，可作出该电路的状态表和状态图如下。29 第五章同步时序逻辑电路4.说明电路的逻辑功能CP:123456789 x:010110100 y2:000100101 y1:001011010 y2(n+1): 001001010 y1(n+1): 010110100 Z：000100100 设电路初始状态为“00”，输入x为脉冲信号，其输入序列为010110100。根据状态图可作出电路的状态响应序列和输出响应序列如下: 由输入、输出序列可以看出，一旦输入x出现信号“101”，输出Z便
17、产生一个相应的1，其他情况下输出Z为0。因此，该电路是一个“101”序列检测器。30 第五章同步时序逻辑电路例3：试用代数法分析下图所示同步时序逻辑电路的逻辑 功能。 解：该电路由一个J-K触发器和四个逻辑门构成，电路有两个输入端x1和x2，一个输出端Z。输出Z与输入和状态均有直接联系，属于Mealy型电路。 用代数法分析该电路的过程如下。1写出输出函数和激励函数表达式31 第五章同步时序逻辑电路2把激励函数表达式代入触发器的次态方程，得到电路的次态方程组 该电路的存储电路只有一个触发器，因此，电路只有一个次态方程。 根据J-K触发器的次态方程和电路的激励函数表达式，可导出电路的次态方程如下：
18、32 第五章同步时序逻辑电路3根据次态方程和输出函数表达式作出状态表和状态图根据次态方程和输出函数表达式，可以作出该电路的状态表和状态图如下。0133 第五章同步时序逻辑电路4 画出时间图，并说明电路的逻辑功能时钟节拍：12345678 输入x1： 00110110 输入x2： 01011100 状态y： “0” 0001111 输出Z ： 0110010101 设电路初态为“0”，输入x1为00110110，输入x2为01011100，根据状态图可作出电路的输出和状态响应序列如下：34 第五章同步时序逻辑电路根据状态响应序列可作出时间图如下：分析时间图可知，该电路实现了串行加法器的功能。其中
19、x1为被加数，x2为加数，它们按照先低位后高位的顺序串行地输入。每位相加产生的进位由触发器保存下来参加下一位相加，输出Z从低位到高位串行地输出“和”数。该时间图给出了两个二进制数x1=01101100, x2=00111010相加得到“和”数Z=10100110的过程。状态y=11110000是由低位到 高位依次产生的进位信号。时钟节拍：12345678 输入x1：00110110 输入x2：01011100 状态 y： “0” 0001111 输出Z ： 0110010135 第五章同步时序逻辑电路为了使逻辑功能更清晰， 亦可按照左高右低的顺序将输入输出序列表示如下： 时钟节拍： 8 7 6
20、 5 4 3 2 1 x1(被加数)：0 1 1 0 1 1 0 0 x2 (加数)：0 0 1 1 1 0 1 0 y (进位)：1 1 1 1 0 0 0 0 Z (和数)：1 0 1 0 0 1 1 0 上面举例介绍了采用两种方法分析同步时序逻辑电路的全过程。实际问题分析时，可视具体情况灵活运用，根据给定逻辑电路的复杂程度不同，通常可以省去某些步骤。例如，列次态真值表或画时间图等。36 第五章同步时序逻辑电路5.3 同步时序逻辑电路的设计 同步时序逻辑电路的设计是指根据特定的逻辑要求，设计出能实现其逻辑功能的时序逻辑电路。显然， 设计是分析的逆过程，即： 同步时序逻辑电路设计追求的目标是
21、，使用尽可能少的触发器和逻辑门实现预定的逻辑要求！逻辑电路逻辑功能分析设计37 第五章同步时序逻辑电路设计的一般步骤如下：1形成原始状态图和原始状态表； 2状态化简，求得最小化状态表； 3状态编码，得到二进制状态表；4选定的触发器类型，并求出激励函数和输出函数最简表达式； 5画出逻辑电路图。38 第五章同步时序逻辑电路5.3.1建立原始状态图和原始状态表原始状态图和原始状态表是对设计要求的最原始的抽象。建立正确的原始状态图和状态表是同步时序电路设计中最关键的一步。 由于状态图比状态表更形象、灵活，一般先画状态图后作状态表；其次，由于在开始时往往不知道描述一个给定的逻辑问题需要多少状态，因此，一
22、般用字母或数字表示状态。 一.确定电路模型 设计成Mealy型？Moore型？ 将电路设计成哪种模型? 有的问题已由设计要求规定，有的问题可由设计者选择。不同的模型对应的电路结构不同，设计者在选择时，应根据问题中的信号形式、电路所需器件的多少等综合考虑。 形成原始状态图时一般应考虑如下几个方面问题：39 第五章同步时序逻辑电路二. 设立初始状态 时序逻辑电路在输入信号开始作用之前的状态称为初始状态。 在建立原始状态图时，应首先设立初始状态，然后从初始状态出发考虑在各种输入作用下的状态转移和输出响应。三. 根据需要记忆的信息增加新的状态 同步时序电路中状态数目的多少取决于需要记忆和区分的信息量。
23、 一般来说，若在某个状态下出现的输入信号能用已有状态表示，则应转向已有状态。仅当某个状态下出现的输入信号不能用已有状态表示时，才令其转向新的状态。40 第五章同步时序逻辑电路四确定各时刻电路的输出 时序逻辑电路的功能是通过输出对输入的响应来体现的。在建立原始状态图时，必须确定各时刻的输出值。在Moore型电路中，应指明每种状态下对应的输出；在Mealy型电路中应指明从每一个状态出发，在不同输入作用下的输出值。注意：在描述一个逻辑问题的原始状态图和原始状态表中，状态数目不一定能达到最少，这一点无关紧要，因为可以对它再进行状态化简。设计者应把清晰、正确地描述设计要求放在第一位。41 第五章同步时序
24、逻辑电路 例1：某模5加1、加2计数器有一个输入x和一个输出Z。输入x为加1、加2控制信号，当x=0时，计数器在时钟脉冲作用下进行加1计数；当x=1时，计数器在时钟脉冲作用下进行加2计数。当电路计满5个状态后，输出Z产生一个1信号作为进位输出，平时Z输出为0。 试建立该计数器的Mealy型原始状态图和状态表。 解：该问题已指定电路模型为Mealy型，且输入和状态、输出之间的关系也非常清楚，所以状态图的建立很容易。42 第五章同步时序逻辑电路 假设模5计数器的5个状态分别用0、1、2、3、4表示，其中0为初始状态。根据题意可作出原始状态图和原始状态表如下。43 第五章同步时序逻辑电路 例2：某序
25、列检测器有一个输入端x和一个输出端Z。输 入端 x 输入一串随机的二进制代码，当输入序列中出现“011” 时，输出Z产生一个1输出，平时Z输出0 。典型输入、输出序列如下。输入x:101011100110 输出Z: 000001000010 试作出该序列检测器的原始状态图和原始状态表。解：1.假定用Mealy型同步时序逻辑电路实现该序列检测器的逻辑功能.设: 状态A-电路的初始状态； 状态B-表示收到了序列“011”中的第一个信号“0”； 状态C-表示收到了序列“011”中的前面两位“01” ； 状态D-表示收到了序列“011”。44 第五章同步时序逻辑电路该序列检测器Mealy型状态图的构造
26、过程如下。相应的原始状态表如右下表所示。45 第五章同步时序逻辑电路从上述过程可知，一个序列检测器所需要的状态数与要识别的序列长度相关，序列越长，需要记忆的代码位数越多，状态数也就越多。 2假定用Moore型同步时序逻辑电路实现该序列检测器的逻辑功能。 由于电路输出完全取决于状态，而与输入无直接联系。在作状态图时，应将输出标记在代表各状态的圆圈内。设电路初始状态为A，并用状态B、C、D分别表示收到了输入x送来的0、01、011。显然，根据题意，仅当处于状态D时电路输出为1，其他状态下输出均为0。46 第五章同步时序逻辑电路构造Moore型原始状态图的过程如下：相应的原始状态表如下表所示。147
27、 第五章同步时序逻辑电路例3设计一个代码监测器，该同步时序电路用于检测串行输入的8421码，其输入的顺序是先低位后高位，当出现非法数字(即输入1010，1011，1100，1101，1110，1111)时，电路的输出为1。试作出该时序电路的Mealy模型状态图和状态表。解根据题意，电路有一个输入和一个输出。设输入为x，输出为Z。由于输入的8421码是先低位后高位，因此，判断输入是否为非法数字时，应从低位到高位查看各位输入值。设：状态A-起始状态； 状态B和C-表示最低一位代码的两种不同取值0和1； 状态D，E，F，G-表示低两位的码的四种不同取值0011； 状态H，I，J，K，L，M，N，P-
28、表示低三位代码的八种取值000111。 当x输入的第四位代码到来时，即可对输入代码进行判断，若出现非法数字，电路的输出为1，否则为0，并返回到起始状态A。48 第五章同步时序逻辑电路根据以上分析，可以得到下图所示的原始状态图。注意：图中，当4位代码检测完后，应转向初始状态A，以便检查下一组代码。49 第五章同步时序逻辑电路由原始状态图转换后的原始状态表如下表所示。思考： 1.代码检测器与序列检测器的主要区别是什吗？ 2. 若将该代码检测器设计成Moore型同步时序电路，该如何建立原始状态图？需增加几个状态？50 第五章同步时序逻辑电路若将该代码检测器设计成Moore型同步时序电路，则电路输出只
29、与状态相关。 令： 状态A-初始状态； 状态B和C-表示代码最低位的取值0和1； 状态D、E、F、G-分别表示代码低二位的4种取值组合0011； 状态H、I、J、K、L、M、N、P-分别表示低三位的8种取值组合00 0111； 状态X-表示4位代码中的10种合法码； 状态Y-表示4位代码中的6种非法码。 显然，电路仅当处于状态Y时输出为1，其他状态下均输出0。51 第五章同步时序逻辑电路 原始状态图如下图所示，原始状态表略。从该例可以看出，实现同一逻辑功能的Moore型电路比Mealy型电路需要的状态数多。思考： 1.该Moore型状态图在Mealy状态图的基础上增加了两个状态，请问是否能只增
30、加一个状态？ 2.该Moore型状态图中，从状态X、Y出发输入0或1时，为什么不转向初始状态A?52 第五章同步时序逻辑电路上述各例所建立的原始状态图和原始状态表中，对于所 设立的每一个状态，在不同输入取值下都有确定的次态和输 出。通常将这类状态图和状态表称为完全确定状态图和状态 表，由它们所描述的电路称为完全确定电路。实际应用中，根据某些设计要求建立的原始状态图和原 始状态表中往往存在不确定的次态或输出，即某些状态在某 些输入取值下的次态或输出是随意的。这种状态图和状态表 被称为不完全确定状态图和状态表，所描述的电路称为不完 全确定电路。53 第五章同步时序逻辑电路例4：设计一个用于引爆控制
31、的同步时序电路，该电路有一 个输入端 x 和一个输出端Z。平时输入 x 始终为0，一旦需要引爆，则从 x 连续输入4个1信号(不被0间断)，电路收到第四个1后在输出端Z产生一个1信号点火引爆，该电路连同引爆装置一起被炸毁。试建立该电路的Mealy型状态图和状态表。 （该问题的实际意义？-施工的安全性！） 解 分析：该电路实际上是一个用于特殊场所的“1111”序列检测器。它与一般序列检测器有两点不同： 1.输入带有约束条件，即一旦输入出现1，则一定是不被0间断的连续4个1； 2.收到4个1后，输出产生的引爆信号使电路自毁，故此时不再存在次态问题。54 第五章同步时序逻辑电路设：状态A-电路初始状
32、态； 状态B-表示收到了第一个1输入； 状态C-表示收到了连续2个1输 入； 状态D-表示收到了连续3个1输入。 根据题意，可得到该电路的Mealy型原始状态图和原始状态表如下。图、表中用“d”表示不确定次态或不确定输出。55 第五章同步时序逻辑电路注意: 在时序电路设计中，利用不完全确定状态表中不确定次态和不确定输出的随意性，通常可使 设计方案变得更简单。这一点类似包含无关最小项的组合电路设计，只不过在处理上要复杂一些。56 第五章同步时序逻辑电路5.3.2状态化简 什么叫状态化简？ 所谓状态化简，是指采用某种化简技术从原始状态表中消去多余状态，得到一个既能正确地描述给定的逻辑功能，又能使所
33、包含的状态数目达到最少的状态表，通常称这种状态表为最小化状态表。目的：简化电路结构。状态数目的多少直接决定电路中所 需触发器数目的多少。设状态数目为n，所需触发器数目为m，则应满足如下关系： 2m n 2 m-1 为了降低电路的复杂性和电路成本，应尽可能状态表中包含的状态数达到最少。方法：常用方法有观擦法、输出分类法、隐含表法等。下面讨论最常用的一种方法-隐含表法。57 第五章同步时序逻辑电路利用隐含表进行化简时，对于完全给定原始状态表和不完 全给定原始状态表引用了不同的概念，并且处理过程有所不同。一. 完全确定状态表的化简1几个概念(1)等效状态定义 设状态Si和Sj是完全确定状态表中的两个
34、状态，若对于所 有可能的输入序列，分别从状态Si和状态Sj出发，所得到的输 出响应序列完全相同，则状态Si和Sj是等效的，记作(Si，Sj)， 又称状态Si和Sj 为等效对。请注意掌握三点：定义、判断方法和性质。58 判断方法 若状态Si和Sj 是完全确定的原始状态表中的两个现态，则Si和Sj 等效的条件可归纳为在一位输入的各种取值组合下满足如下两条： 第一，输出相同； 第二，次态属于下列情况之一： a.次态相同； b.次态交错或为各自的现态； c.次态循环或为等效对。现态 次态/输出 X=0 X=1 A B C D C/1 D/1 A/0 B/0 B/0 B/0 D/0 C/0什么叫交错、循
35、环呢？例如,在 右表中当X=0时，现态A、B的次态相 同，现态C、D的次态交错；当X=1时， 现态A、B的次态为C、D,而现态C、D 的次态为A、B，构成次态循环，即 AB CD第五章同步时序逻辑电路59 第五章同步时序逻辑电路 性质 等效状态具有传递性。即假若S1和S2等效，S2和S3等效,那 么，一定有S1和S3等效。记作 (S1，S2)，(S2，S3)(S1，S3)(2)等效类 等效类：由若干彼此等效的状态构成的集合。在同一个等 效类中的任意两个状态都是等效的。 例如，由(S1，S2)和(S2，S3)可以推出(S1，S3)，进而可知 S1、S2、S3属于同一等效类，记作 S1，S2，S3
36、，即 (S1，S2) ，(S2，S3) S1，S2，S3等效类是一个广义的概念，两个状态或多个状态均可以组 成一个等效类，甚至一个状态也可以称为等效类，因为任何状 态和它自身必然是等效的。60 第五章同步时序逻辑电路(3) 最大等效类 所谓最大等效类，是指不被任何别的等效类所包含的等效类。 注意：这里所指的最大，并不是指包含的状态最多，而是指它的独立性，即使是一个状态，只要它不被包含在别的等效类中，也是最大等效类。换而言之，如果一个等效类不是任何其他等效类的子集， 则该等效类称为最大等效类。完全给定原始状态表的化简过程，就是寻找出表中的所有最大等效类，然后将每个最大等效类中的状态合并为一个新的
37、状态，从而得到最小化状态表。 简化后的状态数等于最大等效类的个数！61 第五章同步时序逻辑电路2状态化简(1)隐含表化简法的一般步骤 作隐含表 隐含表是一个直角三角形阶梯网格，横向和纵向的网格数等于原始状态表中的状态数n减1。表的横向从左到右依次标上原始状态表中的前n-1个状态，纵向自上到下依次标上原始状态表中的后n-1个状态。表中每个方格代表一个状态对。作隐含表 找等效对 求最大等效类 状态合并作最简状态表1234562 第五章同步时序逻辑电路 顺序比较：按照隐含表中从上至下、从左至右的顺序，对照原始状态表依次对所有“状态对”进行逐一检查和比较，并将检查结果标注在隐含表中的相应方格内。比较结
38、果标注如下： 等效 - 在相应方格内填上“”； 不等效- 在相应方格内填上“”； 与其他状态对相关 - 在相应方格内填上相关的状态对。关联比较：指对那些在顺序比较时尚未确定是否等效的状态对作进一步检查。直到判别出状态对等效或不等效为止。寻找等效对 利用隐含表寻找 “等效对”一般需要进行两轮比较，首 先进行顺序比较，然后进行关联比较。63 第五章同步时序逻辑电路求出最大等效类 在找出原始状态表中的所有等效对之后，可利用等效状态的传递性，求出各最大等效类。确定各最大等效类时应注意两点：各最大等效类之间不应出现相同状态； 原始状态表中的每一个状态都必须属于某一个最大等效类，否则，化简后的状态表不能描
39、述原始状态表所描述的功能。状态合并，作出最小化状态表 将每个最大等效类中的全部状态合并为一个状态，即可 得到和原始状态表等价的最小化状态表。64 第五章同步时序逻辑电路(2)化简举例例化简下表所示原始状态表。解 作隐含表 给定原始状态表具有7个状态，根据画隐含表的规则，可画出隐含表框架如下。65 第五章同步时序逻辑电路 寻找等效对 根据等效状态的判断标准，依次检查每个状态对，可得到顺序比较结果如图 (a)所示。 关联比较的结果如图 (b)所示。 图(a) 图(b)66 第五章同步时序逻辑电路图中，由于状态C和F等效，故可判断出状态A和B等效。检查状态A、E的次态对时，出现如下所示关系： AE
40、BE CF由于已知状态C和F是等效的，而状态BE又与状态AB构成 循环，所以，状态A和E是等效状态对，B和E也是等效状态对。状态D、G对应的方格中含有CD和DE，由于状态CD不等效， 因此状态D和G不等效，故在对应的方格中加记号“/”。由判断结果可知，原始状态表中的7个状态共有四个等效对：(A，B)，(A，E)， (B，E)，(C，F)。67 第五章同步时序逻辑电路状态合并，作出最小化状态表 令A,B,E-a、C,F-b、D-c、G-d，并代入原始状态表中，即可得到化简后的状态表如下边右表所示。 求出最大等效类 由所得到的等效对和最大等效类的定义可知，原始状态表中的7个状态共构成A,B,E,C
41、,F,D,G四个最大等效类。68 第五章同步时序逻辑电路二.不完全确定状态表的化简 化简不完全确定原始状态表时，将引入一个新的概念相容状态。1相容状态和相容类 （1）相容状态 相容状态的定义 假定状态Si 和Sj 是不完全确定状态表中的两个状态，若对于所有的有效输入序列，分别从状态Si和Sj出发，所得到的确定输出响应序列是完全相同的，则状态Si和Sj是相容的，又称为相容对，记作(Si，Sj )。 有效输入序列：若从状态S出发，某输入序列作用下所得到的状态响应序列除最后一个次态外，其他次态都是确定的，则该输入序列对状态S是有效的。69 第五章同步时序逻辑电路例如，对如下状态表而言，序列00001
42、1、01111示有效的，而序列011010、11001示无效的。思考：为什么？70 第五章同步时序逻辑电路 相容状态的判断 假定状态Si 和Sj是不完全确定状态表中的两个现态，状态Si 和Sj 相容的条件可归纳为在一位输入的各种取值组合下满足如下两条。 第一，输出相同，或者其中的一个(或两个)输出不确定。 第二，次态属于下列情况之一： a .次态相同； b. 次态交错或为各自的现态； c. 次态循环或为相容对； d. 其中的一个(或两个)为不确定状态。71 第五章同步时序逻辑电路注意! 相容状态不具备传递性！这是因为判断两个状态是否相容时，对于不给定的输出和不给定的次态可以随意指定的缘故。例如
43、，在下表中，有状态A、B相容，状态B、C相容,但状态A、C不相容。现态 次态 / 输出 X=0 X=1 A B C D C/1 d/d C/0 B/0 B/0 A/0 A/0 d/d72 第五章同步时序逻辑电路(2)相容类 相容类是由彼此相容的状态构成的集合。处于同一相容类中的所有状态之间都是两两相容的。 例如，若有相容对(S1,S2)、(S2,S3)和(S1,S3)，则可构成相容类S1,S2,S3。(3)最大相容类 若一个相容类不是任何其他相容类的子集，则该相容类称为最大相容类。 注意：由于相容状态无传递性，所以，同一原始状态表的各最大相容类之间可能存在相同状态，即同一状态可能出现在不同的最
44、大相容类中。73 第五章同步时序逻辑电路2. 不完全确定状态表的化简(1)化简步骤 作隐含表，寻找相容状态对 利用隐含表寻找相容对的过程与化简完全确定状态表时寻找等效对的过程是相同的，仅仅是状态相容与状态等效的标准有所不同而已。 作隐含表，寻找相容状态对； 利用状态合并图，求出最大相容类； 利用闭覆盖表，求最小闭覆盖； 状态合并，作出最小化状态表 。 74 第五章同步时序逻辑电路利用状态合并图，求出最大相容类 状态合并图：是求最大相容类工具。它将状态表的所有状态以“点”的形式均匀地绘在圆周上，然后把所有相容对用线段连接起来。若某些顶点任意两点之间都有连线，则这些顶点状态的集合构成一个最大相容类
45、。图（a）、（b）、（c）分别表示包含3个、4个和5个状态的最大相容类状态合并图。75 第五章同步时序逻辑电路利用闭覆盖表，求最小闭覆盖 最小闭覆盖-是从最大相容类(或相容类)中选出一 个相容类的集合，该相容类集合满足以下3个条件： a. 覆盖-即所选相容类集合应包含原始状态表的全部 状态。 b. 最小-即所选相容类集合中相容类个数应最少。 c. 闭合-即所选相容类集合中的任一相容类，在原始 状态表中任一输入条件下产生的次态组合应该属于该集合中 的某一个相容类。（思考：为什么要满足覆盖？为什么要满足闭合？）化简不完全确定状态表的关键，就是寻找一个最小闭覆 盖。76 第五章同步时序逻辑电路闭覆盖
46、表：闭覆盖表反映相容类集合对状态的覆盖情况和相容类的闭合关系。 表的左边自上而下列出所选相容类，表的中间覆盖部分列出各相容类对原始状态表中状态的覆盖情况，表的右边闭合部分列出各相容类在一位输入各种取值组合下的次态组合。 注意：这里所说的相容类包括最大相容类和它们的子集。状态合并，作出最小化状态表 将最小闭覆盖中的每个相容类用一个新的状态符号表示，再将其代入原始状态表中，即可得到与原始状态表功能相同的最小化状态表。77 第五章同步时序逻辑电路(2)化简举例 解该原始状态表中存在不确定的次态和输出，属于不完全确定状态表。例化简如下原始状态表。 次/出 x=0 x=1 A A/d d/d B C/1
47、 B/0 C D/0 d/1 D d/d B/d E A/0 C/178 第五章同步时序逻辑电路作隐含表，寻找相容状态对 作出隐含表，并根据相容状态的判断标准对各状态对进行顺序比较和关联比较后的结果如右下图所示。 次/出 x=0 x=1 A A/d d/d B C/1 B/0 C D/0 d/1 D d/d B/d E A/0 C/1由隐含表可知，该状态表中的相容状态对有：(A,B)、(A,C)、(A,D)、(A，E)、(B，D)、(C，D)、(C，E)。79 第五章同步时序逻辑电路作状态合并图，找出最大相容类 根据相容状态对(A,B)、(A,C)、(A,D)、(A，E)、(B，D)、(C，D
48、)、(C，E)。可作出状态合并图如下图所示。从状态合并图得到最大相容类为A,B,D、A,C,D、A,C,E。80 第五章同步时序逻辑电路作闭覆盖表，求最小闭覆盖 由3个最大相容类，可作出其闭覆盖表如下表所示。由闭覆盖表和选择最小闭覆盖的3个条件可知，该例的最小闭覆盖可由最大相容类A,B,D和A,C,E组成。 思考：若闭覆盖表中A,B,D在X=1时的次态组合为CD,最小闭覆盖由最大相容类A,B,D和A,C,E组成行吗？为什么？相容覆盖 合 A B C D E X=0 X=1 ABD AC B ACD AD B ACE AD C81 第五章同步时序逻辑电路状态合并，作出最小化状态表 令：相容类A,
49、B,D状态a，相容类A,C,E状态b， 将其代入原始状态表中，可得到最小化状态表如右下表所示。 B/d d/d D B/0 C/1 B C/1 A/0 E d/1 D/0 C d/d A/d A x=1 x=0 次态/输出 现态原始状态表 b/1a/0b a/0b/1a X=1 X=0 次态/输出 现态最小化状态表82 第五章同步时序逻辑电路构成最小闭覆盖的相容类并不一定是最大相容类。 例如，本例中选最大相容类A,B,D和相容类C,E作为 最小闭覆盖，可得到相同的结果。 在某些情况下，如果仅仅从最大相容类中去选择最小闭 覆盖，则合并后的状态表不一定是最简的。而如果在满足覆 盖的前提下，在最大相
50、容类和非最大相容类之间作恰当的选 择，却能得到最简的状态表（思考：为什么?）。注 意： 状态合并时，若存在确定的次态和不确定的次态，则应取确定的次态；若存在确定的输出和不确定的输出，则应取确定的输出值。 例如，原始状态表中的状态A、B、D在输入x=0时的输出有1和d两种，合并后的状态a在x=0时的输出应为1。83 第五章同步时序逻辑电路5.3.3状态编码状态编码：是指给最小化状态表中用字母或数字表示的状态，指定一个二进制代码，形成二进制状态表。状态编码也称状态分配，或者状态赋值。状态编码的任务是： 确定状态编码的长度(即二进制代码的位数，或者说所需触发器个数)； 寻找一种最佳的或接近最佳的状态
