同步时序逻辑电路设计教学PPT.ppt

第五章 同步时序逻辑电路,数字系统逻辑设计Digital System and Logic Design,主编：王维华、曲兆瑞,山东大学出版社,主讲人：李 新 山东大学 计算机科学与技术学院,2,2,内容提要,5.3 同步时序逻辑电路设计概述,5.1 时序逻辑电路概述,5.5 状态化简,5.4 建立状态表,5.2 同步时序逻辑电路分析,5.6 状态分配和网络实现,3,5.3 同步时序逻辑电路设计概述,同步时序逻辑电路设计(又称为同步时序逻辑电路综合)对给定功能要求，做出电路实现时序逻辑电路设计是时序逻辑电路分析的逆过程，设计过程更复杂设计步骤(4步)（1）建立状态表：确定状态及转换关系 建立输入、输出以及状态之间的关系（2）状态化简：消除多余状态（3）状态分配：用二进制编码表示各状态（4）电路实现：由赋值状态表确定各触发器的激励函数和电路输出，做出电路图说明：有的设计可能不需要经过全部步骤，如计数器设计不需要化简、赋值，可以直接写出赋值状态表。下面分别介绍各部的具体做法。,4,5.4 建立状态表,建立状态表就是对给定的设计要求，初步确定所需状态个数及其转换关系，写出描述给定功能要求的状态转换表。两种基本方法信号序列法信号序列是指作用于网络的输入信号序列和相应的网络输出信号序列信号序列法是先确定作用于网络的信号序列，再指定状态，作出状态转换表状态图法先根据设计要求作出状态转换图，再由状态转换图写出状态转换表。作状态转换图可以先设定一个初态，再根据所作用的输入信号和系统的功能要求逐步推导出相继状态及其转换关系，完成状态转换图。比较：状态图法中的各状态可以有特定的含义，比较容易理解和掌握,以下通过例题，介绍用状态图法建立状态转换表的具体做法。,5,5.4 建立状态表,状态图是用从状态引出的有向线段表示状态的转换关系，用标注在有向线段上的数码表示输入信号以及输出信号,这种表示方法在输入信号较多时，从状态引出的线段就比较多，看起来不够清晰,为此我们在建立状态表时采用图b所示的表示方法，即把作用于状态的全部输入信号以及相应的输出信号都列在状态右边的大括号中，括号右边引出的有向线段表示状态的转换关系。,6,5.4 建立状态表,同步时序逻辑电路作用1：进行信号检测序列检测：序列的分组是任意的例如：对信号X101001100011进行序列检测，则可有多种分组，其中有两组“100”序列代码检测：代码的分组是固定的例如：对信号X101001100011进行代码检测，则只有101，001，100，011四个分组，其中有一组“100”代码代码检测器不仅要保存合乎要求的信号，还要“记住”代码的分组情况,7,例1 建立“100”序列检测器的状态表,例4.5-1 建立“100”序列检测器的状态表。该检测器有一个串行输入信号X和一个输出信号Z(由CP脉冲划分节拍)。平时Z0，当输入信号X出现“100”序列时Z1。,分析：序列监测器需要记住前两拍的输入信号，因此该网络是具有存储功能的时序逻辑网络,y x/z,0/0,A(无1),0/1,C(有10),1/0,B(有1),1/0,0/0,1/0,y,x,A/0,ABC,0 1,y/z,C/0,A/1,B/0,B/0,B/0,状态表,状态图,8,例2 建立“100”代码检测器的状态表,例4.5-2 建立“100”代码检测器的状态表。该检测器有一个串行输入端X和一个输出端Z(由CP脉冲划分节拍)，其功能是检测三位二进制代码是否是100。平时Z0，当检测到“100”代码时 Z1。,y x/z,1/0,A(等待首位),0/1,D(有10),1/0,B(有1),0/0,E(有两位),1/0,C(有一位),0/0,0/0,0/0,1/0,1/0,y,x,C/0,ABCDE,0 1,y/z,D/0,E/0,B/0,E/0,E/0,A/1,A/0,A/0,A/0,状态表,状态图,9,例3 建立串行加法器的状态表,例4.5-3 建立串行加法器的状态表。串行加法器有两个串行信号输入端A,B和一个输出信号Z(由CP脉冲划分节拍)。A，B分别串行输入两个二进制数(先送低位)，Z串行输出两数相加的“和”,y AB/Z,00/001/110/111/0,S1(加前无进位),S2(加前有进位),y,AB,S1/0,S1S2,00 01 11 10,y/Z,S2/0,S1/0,S1/0,S1/0,S2/0,S2/1,S2/0,(无进位),(有进位),00/101/010/011/1,(无进位),(有进位),状态表,状态图,10,例4 串行比较器,例4.5-4 建立一个串行数据比较器的状态表。串行数据比较器的功能是比较两个串行二进制数的大小。比较器有三个输入端x3、x2、x1和两个输出端z2、z1(由CP脉冲划分节拍)。当x30时，x2和x1分别串行输入两个二进制数(先送低位)；这时输出z2z100。当x31时，x2和x1分别输入两个二进制数的最高位；这时z2z1输出比较结果。即：若x2x1，则z2z101；若x2x1，则z2z110；若x2x1，则z2z111；,11,例4 串行比较器,当x30时，x2和x1分别串行输入两个二进制数(先送低位)；这时输出z2z100。当x31时，x2和x1分别输入两个二进制数的最高位；这时z2z1输出比较结果。即：若x2x1，则z2z101；若x2x1，则z2z110；若x2x1，则z2z111；,y,ABC,000 001 011 010 110 111 101 100,状态表,状态图,x3x2x1,z2z1,A/00,B/00,A/00,C/00,A/10,A/11,A/01,A/11,B/00,B/00,B/00,C/00,A/10,A/01,A/01,A/01,C/00,B/00,C/00,C/00,A/10,A/10,A/01,A/10,12,12,内容提要,5.3 同步时序逻辑电路设计概述,5.1 时序逻辑电路概述,5.5 状态化简,5.4 建立状态表,5.2 同步时序逻辑电路分析,5.6 状态分配和网络实现,13,5.5 状态化简,合并状态表中外特性相同的状态（消除多余状态)外特性相同的状态常称为“相容状态”外特性是指状态的输入/输出特性化简步骤（1）找相容状态对（可以合并的状态对）（2）找最大相容集合（可以合并的个数最多的状态）（3）找最小闭覆盖（构成简化表的必要最大相容）（4）作简化状态表,14,5.5 状态化简,合并状态表中外特性相同的状态（消除多余状态)外特性相同的状态常称为“相容状态”外特性是指状态的输入/输出特性,15,5.5.1 确定相容状态对（概念定理）,1.概念定理（设yi和yj是状态表M中的状态）,状态相容 对状态表M的任意输入序列X(n)作用下，yi和yj产生的指定输出都相同,则定义yi和yj为状态相容。（对任意输入序列）,状态不相容 如果存在某个输入序列X(n)，使yi和yj产生的某个指定输出不相同,则定义yi和yj为状态不相容。（某个输入序列）,输出相容 对状态表M的全部指定输入，yi和yj产生的指定输出都相同,则定义yi和yj为输出相容。（全部一次输入）,输出不相容 如果在状态表M的某个指定输入作用下，yi和yj产生的指定输出不相同,则定义yi和yj为输出不相容。（某个一次输入）,16,定理5.1 yi和yj状态不相容的充分必要条件是：yi和yj输出不相容或次态不相容。,5.5.1 确定相容状态对（概念定理）,例,AC输出不相容，AB次态不相容。,17,5.5.1 确定相容状态对（隐含表法）,2.找相容对的隐含表法 对状态表中的所有状态对，按定理5.1找出所有的不相容对，其余即为相容对。在查找过程中，用隐含表记录对各状态对的相容情况。,隐含表,是一种阶梯状的表格，其中每个方格对应一个状态对。如,隐含表,B,C的相容状态对,18,5.5.1 确定相容状态对（隐含表法）,确定相容对的隐含表法,填隐含表 将各状态对的相容情况填入 隐含表的相应方格中,查次态对 用“”标出所有不相容次态对,确定相容对 无“”方格所对应的状态对即为相容对,19,5.5.1 确定相容状态对,P151例5.5-1 确定图示状态表的相容状态对,1.填隐含表(按列填表),2.查次态对,3.定相容对,对原始状态表进行顺序比较，1)输出不相同，打，表示不等效 2)输出完全相同，且（次态相同或呈交错），打，表示状态等效 3)输出完全相同，但次态不相同且非交错，将相容状态对填入隐含表以待进一步比较,原始状态表,隐含表,无“”方格所对应的状态对就是相容对,2,6,1,2,1,32,6,3,42,6,4,5,1,5,4,5,1,6,1,51,6,1,4,(1,3),(1,5),(2,4),(3,5),(4,6),不完全指定状态表是指含有任意项的状态表，其中任意项可以是次态或输出。,20,5.5.2 确定最大相容集合,相容状态集合 设Q=y1,y2,.,yk是状态表M的一个状态集合，如果对于每一个状态对(yi,yj)Q，都有yiyj 相容，则称Q为相容状态集合。,用关系图法确定最大相容集合：,1)用分布在圆周上的点表示各状态；2)用直线连接各相容状态对；3)找出各“最大完备多边形”，每个最大完整多边形对应一个最大相容集合。（完备多边形是指各顶点之间均有连线的广义多边形）,最大相容集合 设Q是状态表M的一个相容状态集合，如果不存在一个状态ypM，但yp Q，而yp与Q中的每个状态都相容，则称Q是最大相容集合，简称最大相容。最大相容就是状态个数最多并且相互相容的状态集合。,21,5.5.3 确定最大相容集合,P153例5.5-2 确定下列隐含表的最大相容,步骤：,关系图,隐含表,2,6,1,2,1,32,6,3,42,6,4,5,1,5,4,5,1,6,1,51,6,1,4,1,2,3,4,5,6,1)用分布在圆周上的点表示各状态；2)用直线连接各相容状态对；3)找出各“最大完备多边形”,1,2,3,4,5,6,1,2,6,1,2,3,4,5,6,1,4,1,2,3,4,5,6,2,3,6,1,2,3,4,5,6,2,5,6,1,2,3,4,5,6,3,4,1,2,3,4,5,6,4,5,22,5.5.2 确定简化状态表,从最大相容中找出构成简化状态表的必要最大相容，即最小闭覆盖。简化状态表 如果M是状态表M的简化状态表，则M应满足：(a)覆盖性：对yiM，至少存在一个CjM，使M覆盖了M的全部状态，我们就称M满足覆盖性；(b)闭合性：对yiM，至少存在一个CjM，使Ci的次态Cj，即M中状态的次态仍是M的状态，我们就称M满足闭合性；(c)状态个数最少。,1.完全指定状态表的化简 没有任意项的状态表，即状态表中次态和输出是完全指定的，没有任意项。2.不完全指定状态表的化简 不完全指定状态表是指含有任意项的状态表，其中任意项可以是次态或输出。,23,5.5.2.1 完全指定状态表的化简,定理5.2 设M是完全指定状态表，yi,yj,ykM。如果yi和yk相容,yj和yk相容，则yi和yk相容。即对于完全指定状态表，状态相容具有传递性。定理5.3 对于完全指定状态表，全部最大相容满足最小闭覆盖。即对于构成完全指定状态表的简化状态表，所有的最大相容都是必要的，所以找出最大相容后，就可以作简化状态表了。,24,完全指定状态表的化简举例,P154例5.5-3 简化下图所示的状态表,状态表,关系图和最大相容,简化状态表,最终的简化状态表,步骤1:根据状态表确定隐含表,找相容状态对,步骤3:找最小闭覆盖,步骤2:画出状态图，求最大相容,步骤4:合并状态，做简化状态表,25,25,作业,P167练习五9，10，11 14、15,