《数字逻辑及试验》PPT课件.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 F2F1 XF2F1 表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 CTLN CTCN 右菱形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 B A C D C 2010 华东师范大学计算机系 37 例2 化简状态表 作状态合并图 A B A C D C 最大相容类 A B D C E 2010 华东师范大学计算机系 38 例2 作最小化状态表 A B D C E S0S1S2 2010 华东师范大学计算机系 39 二 化简举例 例7 3 化简状态表 作隐含表 BCDEFG ABCDEF CD ADEF CFCG CF BDCE AF AEAC DG ACDF 相容状态对 A B C D C E D E G F CE CE GF GE ACCG DECE 2010 华东师范大学计算机系 40 例7 3 化简状态表 作状态合并图 A B C D C E D E G F 最大相容类 A B C E D F G 作最小化状态表 表7 19 2010 华东师范大学计算机系 41 二 化简举例 例3 化简状态表 作隐含表 BCDEF ABCDE CD ABDE DE 相容状态对 A B A F B C B D B E B F C D C E C F D E D F E F CE AF CE BF CD 2010 华东师范大学计算机系 42 例7 3 化简状态表 作状态合并图 A B A F B C B D B E B F C D C E C F D E D F E F 最大相容类 B C D E F A B F 2010 华东师范大学计算机系 43 例7 3 化简状态表 作最小化状态表 A B F B C D E F ab 2010 华东师范大学计算机系 44 7时序电路设计 7 1状态等价 7 2状态化简 7 3不完全定义状态表的状态化简 7 4状态分配方法 2010 华东师范大学计算机系 45 7 4状态分配方法 一 状态分配 为状态分配唯一的二进制编码设 二进制码位数为M状态数为N则 2M 1 N 2M 二 状态分配的合理性状态分配不会影响电路的逻辑功能 但影响电路实现的复杂度 寻找较为合理的分配方案 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 E A CB E出现2次 优先考虑 多种分配方案 方案一 图7 18 a 表7 25方案二 b 方案三 c 2010 华东师范大学计算机系 50 例7 4 考察表7 24所示状态表 采用D触发器实现各方案P299例 方案一 激励表 卡诺图化简 D3 F3 F2 X F3 F2X F1 2010 华东师范大学计算机系 51 例7 4 考察表7 24所示状态表 卡诺图化简 D2 F2F1 X F2F1X F3F2 X D1 F3F2 F2F1 X 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 状态分配 22 5 23 用三位二进制代码表示一个状态 根据 规则1 b c d e 应分配相邻编码 规则2 b c d 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 F2 F1X D2 F2 X F1 2010 华东师范大学计算机系 62 例5 D1 F2 F1 Z F3X 2010 华东师范大学计算机系 63 例5 逻辑图 D3 F2 F1XD2 F2 X F1D1 F2 F1 Z F3X 3QDCP Q 2QDCP Q 1QDCP 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 F3F2F1 X D3 F2 F1XD2 F2 X F1D1 F2 F1 Z F3X 2010 华东师范大学计算机系 65 例5 修改输出函数 Z F3F2F1 X 3QDCP Q 2QDCP Q 1QDCP 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 主要符号 状态符号 表示系统状态图7 24 OUT1OUT2 A 00 状态 状态进入 状态退出 无条件输出 Moore型 2010 华东师范大学计算机系 70 一 ASM符号1 主要符号 条件选择符号图7 25 X 判定标准 入口 0 1 退出路径 2010 华东师范大学计算机系 71 一 ASM符号1 主要符号 条件输出符号图7 26 输出变量 mealy型 2010 华东师范大学计算机系 72 一 ASM符号 2 ASM块由一个状态符号 条件选择符号 条件输出符号 组成图7 27 图7 28 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 35 ASM图的循环描述 图7 36 2010 华东师范大学计算机系 76 7 5算法状态机 二 ASM设计实例例7 7 测量超声波发生器发射端到目的地 障碍物 的距离 1 方法 超声波测量 计算出从发送 XMIT 到收到有效回波信号 ECHO 的时间图7 40 2010 华东师范大学计算机系 77 例7 7 测量超声波发生器发射端到目的地的距离 采用类似P260例6 2 计时器 的方法 获得计数值 送计算机处理 计数时钟取1MHz 1us 计数最大值设为216 16位计数值送计算机处理控制时序 图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 C 4 D F 4 D E C D 2规则2 C D A DE E 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 J3K3XMIT ECHOERST 011d XMIT ECHOERST 000d 图7 46 e J3卡诺图 010小格填入XMIT ECHOERST 化简 得激励函数和输出函数表达式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 G 4 C D 4 E F 4 F G 8 C E 4 A B 4 B C D 8利用卡诺图分配图7 60 2010 华东师范大学计算机系 98 例7 8 设计绘图仪接口 并模拟计算机进行调试 状态分配 方法二 分析ASM图图7 58规则1 A A XFR 0 G A INTH 0 A G 4 B B RPYH 0 A B XFR 1 A B 4 B C RPYH 1 C C RPYH 1 D C RPYH 1 B C D 8 2010 华东师范大学计算机系 99 例7 8 设计绘图仪接口 并模拟计算机进行调试 C D RPYH 0 TCH 0 D D RPYH 0 C D 4 C E RPYH 0 TCH 1 E E TCH 1 C E 4 E F TCH 0 F F INTH 0 E F 4 F G INTH 1 G G INTH 1 F G 8利用卡诺图分配图7 60 2010 华东师范大学计算机系 100 例7 8 设计绘图仪接口 并模拟计算机进行调试 建立状态转移表 J3K3 现态011 RPYH TCHF3F3 J3K3MEV0000d1011dRPYH TCH 图7 61J3卡诺图 011小格填入RPYH TCH 现态100 INTHF3F3 J3K3MEV010d1111d0INTH 图7 61K3卡诺图 100小格填入INTH 2010 华东师范大学计算机系 101 例7 8 设计绘图仪接口 并模拟计算机进行调试 建立激励表 选用J K触发器 略 卡诺图化简 采用MEV方法 图7 61 62 63 64 65写出激励函数表达式P320输出函数表达式