《数字逻辑及试验》PPT课件

2010,华东师范大学计算机系,1,倒数行6：C211=（S2，S3）C211=（S1，S3）,本章错误,P286倒数行8：C111=（S0，S1）C111=（S0，S2）,2010,华东师范大学计算机系,2,本章错误,P294表7-1910列：S2/1S2/0S1/1S1/0S0/0S0/0,2010,华东师范大学计算机系,3,本章错误,P295行3：F2F1XF2F1,表7-21，X=1D1列：1/01/00/00/01/01/00/11/0,2010,华东师范大学计算机系,4,本章错误,P297表7-23行5：DB/0E/1DB/0E/0,P306行1、行2、倒数行3：10001.000,2010,华东师范大学计算机系,5,本章错误,P311行15：=(F3F2)=(F3F2),图7-47a)改为：,图7-47b)改为：,2010,华东师范大学计算机系,6,本章错误,P318右矩形1：CTLNCTCN,右菱形3：TCHRTCRH,P325倒数行7：U6B(LS112)=22nsU6B(LS112)=20ns,2010,华东师范大学计算机系,7,同步时序电路的设计：,（1）根据需求状态图、状态表（2）状态分配状态转移表（3）状态转移表激励表触发器特征表（4）卡诺图化简激励函数表达式输出函数表达式（5）电路实现,2010,华东师范大学计算机系,8,同步时序电路设计的进一步优化：,（1）根据需求状态图、状态表（2）状态化简最小化状态表（3）状态分配得状态转移表（4）状态转移表激励表触发器特征表（5）卡诺图化简激励函数表达式输出函数表达式（6）电路实现,2010,华东师范大学计算机系,9,7时序电路设计,状态化简状态分配复杂时序电路的设计,2010,华东师范大学计算机系,10,7时序电路设计,7.1状态等价7.2状态化简7.3不完全定义状态表的状态化简7.4状态分配方法7.5算法状态机7.6链接时序机,2010,华东师范大学计算机系,11,7时序电路设计,7.1状态等价,2010,华东师范大学计算机系,12,7.1状态等价,设计步骤：根据功能要求构成状态图原始状态图,构成最小化状态表状态化简消除冗余状态，降低成本,状态化简是建立在状态等价基础上的,2010,华东师范大学计算机系,13,7.1状态等价,1状态等价定理S1与S2等价：当且仅当两状态每种可能的输入序列其输出相等且次态等价，则称：S1与S2等价，记作（S1、S2）。,2010,华东师范大学计算机系,14,1状态等价定理,等价条件：输出相同次态等价（满足下列条件之一）：次态相同次态交替：S1的次态为S2S2的次态为S1次态循环：S1和S2的次态为S3和S4S3和S4的次态为S1和S2,2010,华东师范大学计算机系,15,7.1状态等价,2等价性质：对称性：若S1=S2，则S2=S1自反性：对任何状态，S1=S1传递性：若S1=S2，且S2=S3，则S1=S3,2010,华东师范大学计算机系,16,7.1状态等价,3等价类等价类是若干状态的集合，在此集合中，任何两个状态都是相互等价的。（S1，S2）（S1，S3）（S1，S2，S3）利用等价定理可进行状态化简,2010,华东师范大学计算机系,17,7时序电路设计,7.1状态等价7.2状态化简,2010,华东师范大学计算机系,18,7.2状态化简,方法：等价类表隐含表,一、等价类表化简法：教材P286讨论,2010,华东师范大学计算机系,19,7.2状态化简,二、隐含表化简法提供一种识别冗余状态的图形化方法隐含表：图7-1每个方格代表一对隐含的等价可能性,2010,华东师范大学计算机系,20,二、隐含表化简法,1化简步骤：作隐含表，寻找等价对根据等价性质，构成最大等价类将最大等价类中的状态合并，得到最小化状态表,2010,华东师范大学计算机系,21,二、隐含表化简法,2化简举例例7-1）化简P288图7-4状态图,作隐含表,填隐含表（图7-5),对所有状态进行比较：状态等价，打“”输出不同，打“”输出相同，但次态不同，将次态填入，以便进一步判别,列出状态表（表7-7）,2010,华东师范大学计算机系,22,例7-3）化简原始状态表,对所有状态进行比较，找出等价状态对,BCDE,ABCD,BCAE,AEBC,CDBE,AC,BCDC,AB,DC不等价AD不等价,AE、BC次态循环AE、BC等价,CD不等价DE不等价,归纳等价状态对为：（A,E）（B,C）,2010,华东师范大学计算机系,23,例7-1）化简图7-4状态图,状态合并，作:最小化状态表（表7-9）状态图（图7-7）,归纳最大等价类：（A，E），（B，C），（D）S0S1S2,2010,华东师范大学计算机系,24,2化简举例,例7-2）化简P290表7-10状态表,进一步比较隐含表中尚未确定项逐个比较，除去不等价状态对归纳等价状态对为：（0）（1，2）（3，6）（4，7）（5，8）ABCDE,逐行比较原始状态表填隐含表（图7-8）,最小化状态表（表7-12）,2010,华东师范大学计算机系,25,2化简举例,例1）化简如下原始状态表：,2010,华东师范大学计算机系,26,例1）化简原始状态表,作隐含表，找出等价状态对,BCDEFG,ABCDEF,CF,BE,AECF,CDED,CF等价AB等价,AE、BE次态循环,CD不等价,归纳等价状态对为：(A,B)(A,E)(B,E)(C,F),2010,华东师范大学计算机系,27,例1）化简原始状态表,归纳等价状态对为：(A,B)(A,E)(B,E)(C,F),构成最大等价类根据传递性：(A,B)(A,E)(B,E)(A,B,E)最大等价类为：(A,B,E)(C,F)(D)(G),2010,华东师范大学计算机系,28,例1）化简原始状态表,构成最小化状态表：(A,B,E)(C,F)(D)(G),2010,华东师范大学计算机系,29,7时序电路设计,7.1状态等价7.2状态化简7.3不完全定义状态表的状态化简,2010,华东师范大学计算机系,30,7.3不完全定义状态表的状态化简,特点：状态表中存在不完全确定的次态或输出不完全确定状态表的化简是建立在相容状态基础上的,2010,华东师范大学计算机系,31,7.3不完全定义状态表的状态化简,一、状态相容1.相容状态：对于所有的有效输入序列，分别从状态SA和SB出发，所得到的输出响应序列是完全相同的（不确定状态可任意指定），那么状态SA和SB是相容的，即SA和SB为相容对，记作：SA，SB。,2010,华东师范大学计算机系,32,一、状态相容,相容条件：（不确定状态可任意指定）输出相同次态满足下列条件之一：次态相同次态交替次态循环,2010,华东师范大学计算机系,33,一、状态相容,2.相容类状态相容与状态等价性质一样，具有相容类和最大相容类的性质不同点：不具备传递性，即在相容类中所有状态之间都分别是两两相容的；,不具备传递性若干个最大相容类可能包含公共状态,2010,华东师范大学计算机系,34,一、状态相容,3.相容性质相容类集合必须满足覆盖、闭合和最小三个条件覆盖指相容类集合中包含了原状态表的全部状态闭合指在一个相容类集合中，任一相容类在各种输入取值下的次态组合，都必须属于该集合中某一相容类最小指满足覆盖和闭合的相容类数目达到最少,2010,华东师范大学计算机系,35,一、状态相容,4.化简步骤：作隐含表寻找相容状态对利用状态合并图寻找最大相容类作最小化状态表,状态合并图以点表示状态，均匀分布在圆周上将各相容对用线段连接找出所有点之间都有连线的多边形构成一个最大相容类,2010,华东师范大学计算机系,36,7.3不完全定义状态表的状态化简,二、化简举例例2）化简状态表,作隐含表,BCDE,ABCD,CD,AE,CB,ABDE,AB,DB,CBAE,归纳相容状态对：A，BA，CD，C,2010,华东师范大学计算机系,37,例2）化简状态表,作状态合并图A，BA，CD，C,最大相容类：A，BD，CE,2010,华东师范大学计算机系,38,例2）,作最小化状态表A，BD，CE,S0S1S2,2010,华东师范大学计算机系,39,二、化简举例,例7-3）化简状态表,作隐含表,BCDEFG,ABCDEF,CD,ADEF,CFCG,CF,BDCE,AF,AEAC,DG,ACDF,相容状态对：A,BC,DC,ED,EG,F,CE,CE,GF,GE,ACCG,DECE,2010,华东师范大学计算机系,40,例7-3）化简状态表,作状态合并图A,BC,DC,ED,EG,F,最大相容类：A,BC,E,DF,G,作最小化状态表（表7-19）,2010,华东师范大学计算机系,41,二、化简举例,例3）化简状态表,作隐含表,BCDEF,ABCDE,CD,ABDE,DE,相容状态对：A,BA,FB,CB,DB,EB,FC,DC,EC,FD,ED,FE,F,CE,AF,CE,BF,CD,2010,华东师范大学计算机系,42,例7-3）化简状态表,作状态合并图A,BA,FB,CB,DB,EB,FC,DC,EC,FD,ED,FE,F,最大相容类：B,C,D,E,FA,B,F,2010,华东师范大学计算机系,43,例7-3）化简状态表,作最小化状态表A,B,FB,C,D,E,F,ab,2010,华东师范大学计算机系,44,7时序电路设计,7.1状态等价7.2状态化简7.3不完全定义状态表的状态化简7.4状态分配方法,2010,华东师范大学计算机系,45,7.4状态分配方法,一、状态分配为状态分配唯一的二进制编码设：二进制码位数为M状态数为N则：2M-1N2M,二、状态分配的合理性状态分配不会影响电路的逻辑功能，但影响电路实现的复杂度。寻找较为合理的分配方案,2010,华东师范大学计算机系,46,7.4状态分配方法,三、状态分配算法1.状态分配规则如下情况，应分配相邻的二进制代码规则1：同一输入值下，次态相同的现态规则2：同一状态在相邻输入下的不同次态规则3：在所有输入取值下均有相同输出的现态,2010,华东师范大学计算机系,47,三、状态分配算法,2.状态分配实例例4）为如下状态表建立状态转移表,确定状态变量位数22=4取2位状态变量,应分配相邻代码的状态：规则1：A,BA,C规则2：C,DA,C、B,DA,B规则3：A,B,C,2010,华东师范大学计算机系,48,A：00，B：10，C：01，D：11,例4）,状态分配,规则1：A,B、A,C规则2：C,D、A,C、B,D、A,B规则3：A,B,C,A,B,C,D,状态转移表,2010,华东师范大学计算机系,49,2.状态分配实例,例7-4）考察表7-24所示状态表,应分配相邻代码的状态：规则1：A,C、B,E、A,E、D,F规则2：A,C、C,D、A,F、B,E、D,EA,CB,E出现2次，优先考虑,多种分配方案：方案一：图7-18(a)表7-25方案二：(b)方案三：(c),2010,华东师范大学计算机系,50,例7-4）考察表7-24所示状态表,采用D触发器实现各方案P299例，方案一：,激励表：,卡诺图化简：,D3=F3F2X+F3F2X+F1,2010,华东师范大学计算机系,51,例7-4）考察表7-24所示状态表,卡诺图化简：,D2=F2F1X+F2F1X+F3F2X,D1=F3F2+F2F1X,2010,华东师范大学计算机系,52,例7-4）考察表7-24所示状态表,状态分配方案不同，实现成本略有不同方案一：28门方案二：27门方案三：27门不考虑状态分配原则：35门,状态分配规则不一定能产生最佳方案，但能产生状态分配的较好方案,2010,华东师范大学计算机系,53,同步时序电路的设计：,（1）根据需求状态图、状态表（2）状态分配状态转移表（3）状态转移表激励表触发器特征表（4）卡诺图化简激励函数表达式输出函数表达式（5）电路实现,2010,华东师范大学计算机系,54,同步时序电路设计的进一步优化：,（1）根据需求状态图、状态表（2）状态化简最小化状态表（3）状态分配得状态转移表（4）状态转移表激励表触发器特征表（5）卡诺图化简激励函数表达式输出函数表达式（6）电路实现,2010,华东师范大学计算机系,55,状态图,同步时序电路设计,例5）试设计一个同步时序电路，接收串行二进制代码，输入代码每三位为一组，当输入的三位二进制代码为011时，电路输出为“1”。,A,B,C,D,E,F,G,0/0,1/0,0/0,0/0,1/0,1/0,0/01/0,0/01/1,0/01/0,0/01/0,初态,0,1,00,01,10,11,X/Z,2010,华东师范大学计算机系,56,例5）,状态表,A,B,C,D,E,F,G,0/0,1/0,0/0,0/0,1/0,1/0,0/01/0,0/01/1,0/01/0,0/01/0,初态,0,1,00,01,10,11,B,0C,0,D,0E,0,F,0G,0,A,0A,0A,0A,1A,0A,0A,0A,0,2010,华东师范大学计算机系,57,例5）,最小化状态表,BCDEFG,ABCDEF,BDCE,BFCG,ABAC,ABAC,ABAC,DFEG,ADAE,ADAE,ADAE,AFAG,AFAG,AFAG,X,X,X,X,X,X,等价类:(D,F)(D,G)(G,F)(D,F,G),2010,华东师范大学计算机系,58,例5）,最大等价类:(A)(B)(C)(D,F,G)(E)abcde,最小化状态表：,b,0c,0,d,0e,0,d,0d,0,a,0a,0,a,0a,1,2010,华东师范大学计算机系,59,例5）,状态分配22523用三位二进制代码表示一个状态,根据：规则1：b,cd,e应分配相邻编码规则2：b,cd,e应分配相邻编码,a:000b:001c:011d:010e:110,a,b,c,d,e,2010,华东师范大学计算机系,60,例5）,状态转移表：a:000b:001c:011d:010e:110,2010,华东师范大学计算机系,61,例5）,激励函数：激励表：（D触发器实现）,D3=F2F1X,D2=F2X+F1,2010,华东师范大学计算机系,62,例5）,D1=F2F1,Z=F3X,2010,华东师范大学计算机系,63,例5）,逻辑图：D3=F2F1XD2=F2X+F1D1=F2F1Z=F3X,3QDCP,Q2QDCP,Q1QDCP,Z,F3,F2,F1,CLK,X,2010,华东师范大学计算机系,64,例5）,分析讨论根据激励函数画出包含所有状态的状态图,000,0/0,0/0,1/1,0/0,0/01/1,0/01/1,1/1,0/01/0,0/0,修改输出函数：Z=F3F2F1X,D3=F2F1XD2=F2X+F1D1=F2F1Z=F3X,2010,华东师范大学计算机系,65,例5）,修改输出函数：Z=F3F2F1X,3QDCP,Q2QDCP,Q1QDCP,Z,F3,F2,F1,CLK,X,2010,华东师范大学计算机系,66,例5）,状态图：,2010,华东师范大学计算机系,67,7时序电路设计,7.1状态等价7.2状态化简7.3不完全定义状态表的状态化简7.4状态分配方法7.5算法状态机,2010,华东师范大学计算机系,68,7.5算法状态机,算法状态机（ASM）是一种描述时序系统控制过程的算法流图,其结构形式类似于计算机中的程序流程图特点：可准确地描述控制器的功能和状态变化条件描述控制器的控制状态及其转换关系精确地表示状态转换的时间关系描述符号：ASM流程图,2010,华东师范大学计算机系,69,7.5算法状态机,一、ASM符号1.主要符号状态符号表示系统状态图724,OUT1OUT2,A,00,状态,状态进入,状态退出,无条件输出,Moore型,2010,华东师范大学计算机系,70,一、ASM符号1.主要符号,条件选择符号图725,X,判定标准,入口,0,1,退出路径,2010,华东师范大学计算机系,71,一、ASM符号1.主要符号,条件输出符号图726,输出变量,mealy型,2010,华东师范大学计算机系,72,一、ASM符号,2.ASM块由一个状态符号（条件选择符号）（条件输出符号）组成图727、图728,O1,A,XY,O2,C,B,1,0,00,01,10,2010,华东师范大学计算机系,73,一、ASM符号,3.构造ASM图注意避免不确定性图7-30转换条件未确定,例：构造如下状态图的ASM图,正确吗？,2010,华东师范大学计算机系,74,例7-6,2010,华东师范大学计算机系,75,一、ASM符号3.构造ASM图,例：图7-33采用并行路径描述不确定描述改串行路径描述：图7-34,4.简单例子：模4计数器的ASM图图7-37模4可逆计数器ASM图图7-38,选择块可由ASM块共享：图7-35ASM图的循环描述：图7-36,2010,华东师范大学计算机系,76,7.5算法状态机,二、ASM设计实例例7-7）测量超声波发生器发射端到目的地（障碍物）的距离,1.方法：超声波测量计算出从发送（XMIT）到收到有效回波信号（ECHO）的时间图7-40,2010,华东师范大学计算机系,77,例7-7）测量超声波发生器发射端到目的地的距离,采用类似P260例6-2）“计时器”的方法，获得计数值，送计算机处理。计数时钟取1MHz（1us)计数最大值设为21616位计数值送计算机处理控制时序：图7-41,计数值送计算机接口电路,向CPU发中断请求,在中断处理程序中,CPU读取接口的数据,2010,华东师范大学计算机系,78,例7-7）测量超声波发生器发射端到目的地的距离,2.设计框图,定时信号（超时复位）。当出现故障，无ECHO信号返回时，利用该信号复位系统。图7-43,2010,华东师范大学计算机系,79,例7-7）测量超声波发生器发射端到目的地的距离,3.时序电路模块设计（1）输入信号：XMIT超声波发送脉冲ECHO回波信号ERST定时信号输出信号：CEN计数使能CRST复位ABSTB数据锁存,2010,华东师范大学计算机系,80,例7-7）测量超声波发生器发射端到目的地的距离,（2）ASM图：图7-42,初始态,清零态,就绪态,发送超声波,计数态,超时，系统复位,回波信号未到，继续计数,回波信号到,CRST,2010,华东师范大学计算机系,81,例7-7）测量超声波发生器发射端到目的地的距离,（2）ASM图：图7-42,CEN,D,回波信号到,XMIT,发送信号仍有效,继续计数,避免寄生ECHO信号,停止计数,ECHO,置数并返回,等待回波信号结束,F,2010,华东师范大学计算机系,82,例7-7）测量超声波发生器发射端到目的地的距离,（3）状态表：表7-28,（4）状态化简隐含表化简法：图7-44无等价状态，表7-28即为最小化状态表,2010,华东师范大学计算机系,83,例7-7）测量超声波发生器发射端到目的地的距离,（5）状态分配规则1：B,C4D,F4D,EC,D2规则2：C,DA,DEE,F规则3：A,C,E利用卡诺图分配图7-45,（6）状态转移表表7-29,（7）激励表（用J-K触发器实现）略,2010,华东师范大学计算机系,84,例7-7）测量超声波发生器发射端到目的地的距离,（8）卡诺图化简激励函数表达式输出函数表达式分析表7-29：J1K1：现态011：XMITF1F1+011110,图7-46(b)K1卡诺图：011小格填入XMIT,2010,华东师范大学计算机系,85,例7-7）测量超声波发生器发射端到目的地的距离,J2K2：现态010：ERSTF2F2+J2K2MEV011d0110d1ERST图7-46(d)K2卡诺图：010小格填入ERST,现态110：ECHOF2F2+J2K2MEV010d1111d0ECHO图7-46(d)K2卡诺图：110小格填入ECHO,2010,华东师范大学计算机系,86,例7-7）测量超声波发生器发射端到目的地的距离,J3K3：现态010：F3F3+J3K3XMITECHOERST011d(XMITECHOERST)000d图7-46(e)J3卡诺图：010小格填入XMITECHOERST,化简，得激励函数和输出函数表达式P311,（9）电路图图7-48,（10）时序图图7-49,2010,华东师范大学计算机系,87,7时序电路设计,7.1状态等价7.2状态化简7.3不完全定义状态表的状态化简7.4状态分配方法7.5算法状态机7.6链接时序机,2010,华东师范大学计算机系,88,7.6链接时序机,链接时序机：一个电路的输出成为另一个电路的输入；而另一个电路的输出又成为第一个电路的输入，则该时序机称为链接时序机。,2010,华东师范大学计算机系,89,7.6链接时序机,类型：接口式将机器内的某些状态链接到另一机器上，即为接口链接。串行链接：图7-50并行链接图7-51,交互式解释式阵列式软件式,2010,华东师范大学计算机系,90,7.6链接时序机,设计：1.任务：计算机模拟器设计绘图仪接口电路设计,实例：例7-8）设计绘图仪接口，并模拟计算机进行调试。,2010,华东师范大学计算机系,91,例7-8）设计绘图仪接口，并模拟计算机进行调试。,2.设计框图图7-52交互信号：计算机接口CTH送绘图仪设备码RPYH回答DSH接口数据选通RPYH回答,计算机送往接口接口回答,2010,华东师范大学计算机系,92,例7-8）设计绘图仪接口，并模拟计算机进行调试。,计算机接口TCH接口缓存满TCRHCPU回答INTH中断请求CIH中断响应接口绘图仪DOSH绘图仪数据选通DRH回答,接口送往计算机计算机回答,接口送往绘图仪绘图仪回答,2010,华东师范大学计算机系,93,例7-8）设计绘图仪接口，并模拟计算机进行调试。,计算机模拟器与绘图仪接口链接关系：（部分ASM图）图7-57工作波形：图7-53设备码译码电路图7-54,2010,华东师范大学计算机系,94,例7-8）设计绘图仪接口，并模拟计算机进行调试。,3.计算机模拟器设计图7-52输入信号：XFR启动（模拟中断处理程序入口）INTH中断请求RPYH接口应答TCH缓冲区满（要求CPU停止送数）输出信号：CTH设备号选通DSH数据选通TCRH回答CIH中断响应,2010,华东师范大学计算机系,95,例7-8）设计绘图仪接口，并模拟计算机进行调试。,建立ASM图图7-58送设备号，选中接口工作送数据，直到缓冲区满停止送数，等待中断请求,2010,华东师范大学计算机系,96,例7-8）设计绘图仪接口，并模拟计算机进行调试。,建立状态表状态化简（本例无冗余状态）建立最小化状态表,2010,华东师范大学计算机系,97,例7-8）设计绘图仪接口，并模拟计算机进行调试。,状态分配7个状态需3位状态变量：F3F2F1方法一：分析状态表规则1：A,G4C,D4E,F4F,G8C,E4A,B4B,C,D8利用卡诺图分配图7-60,2010,华东师范大学计算机系,98,例7-8）设计绘图仪接口，并模拟计算机进行调试。,状态分配方法二：分析ASM图图7-58规则1：AA（XFR=0）GA（INTH=0）A,G4BB（RPYH=0）AB（XFR=1）A,B4BC（RPYH=1）CC（RPYH=1）DC（RPYH=1）B,C,D8,2010,华东师范大学计算机系,99,例7-8）设计绘图仪接口，并模拟计算机进行调试。,CD（RPYH=0,TCH=0）DD（RPYH=0）C,D4CE（RPYH=0,TCH=1）EE（TCH=1）C,E4EF（TCH=0）FF（INTH=0）E,F4FG（INTH=1）GG（INTH=1）F,G8利用卡诺图分配图7-60,2010,华东师范大学计算机系,100,例7-8）设计绘图仪接口，并模拟计算机进行调试。,建立状态转移表,J3K3：现态011：RPYHTCHF3F3+J3K3MEV0000d1011dRPYHTCH图7-61J3卡诺图：011小格填入RPYHTCH,现态100：INTHF3F3+J3K3MEV010d1111d0INTH图7-61K3卡诺图：100小格填入INTH,2010,华东师范大学计算机系,101,例7-8）设计绘图仪接口，并模拟计算机进行调试。,建立激励表（选用J-K触发器）（略）卡诺图化简（采用MEV方法）图7-61，62，63，64，65写出激励函数表达式P320输出函数表达式画出逻辑电路图图