第2章 数字系统设计.ppt

第2章数字系统的算法设计和硬件实现 2 1算法设计2 2算法结构2 3系统硬件实现概述2 4数据处理单元的设计2 5控制单元的设计 内容 第2章数字系统的算法设计和硬件实现 2 1算法设计 2 1 1算法设计综述 1 算法推导的主要考虑因素 设计者根据用户需求 确定设计者认为可行 用户可以接受的系统主要技术指标 本阶段的中心任务是进行系统的可行性分析 1 逻辑指标 系统应完成的逻辑功能 2 非逻辑指标 其他非逻辑约束因素 2 1算法设计 2 硬件结构对算法推导的影响 1 采用不同器件 将有不同的算法设计对策 常规MSI SSI通用集成电路 要求芯片使用少 而使用PLD设计可以 拼硬件 换取优越性 2 系统算法设计与软件算法设计的区别 系统算法用硬件实现时 算法和系统应有很好的对应性 即有可实现性 2 1算法设计 2 1 2跟踪法跟踪法就是按照已确定的系统功能 由控制要求逐步细化 逐步具体化 从而导出系统算法 例2 2试设计一个简易的5位串行码数字锁 该所在受到5位与规定相符的二进制数码时打开 使相应的灯点亮 试导出该串行码数字锁的算法流程图 SETUP和START是外部输入控制信号 灯LT在操作过程正确且5位串行码正确时燃亮 否则显示错误的灯LF亮 同时喇叭告警 规定时限 2 1算法设计 设计者按照已定的初步思路进一步思考以下问题 1 二进制代码如何送人 2 该数字锁应规定怎样的正确使用规程 3 如果用户送错了代码或者连续不断地送入代码 则锁电路应有如何反应 4 一次开锁结束后 无论正确与否 应如何进入下一次准备开锁状态 2 1算法设计 这些问题把基本的逻辑问题具体化 逐步导出算法 经设计人员与用户反复磋商 假设确定如下方案 1 设置置数开关S以便置0或者置1 又设置读数开关READ 当用户按动一次READ把S所置的二进制数送入数字锁 2 设定正确使用数字锁的规程为 a 锁接通电源后 首先按SETUP键 启动锁电路 b 按下START表示即将送入一组新代码 未按时任何输入数据均无效 c 交替使用S和READ 依次送入正确的代码 如11001 d 按下按钮TRY 则锁打开 正确开锁指示灯LT燃亮 2 1算法设计 3 在START和TRY之间 如果送入的代码与正确代码不符 则错误指示灯LF亮 此后送入的任何代码均无效 4 在按下START之后 如果送入5个以上数字 虽然前5个是正确的 但在第6次按READ时 灯LF亮 出错 5 一次操作过程结束后 灯LT和LF总亮一只 这时按下SETUP 则灯LT或LF熄灭 数字锁又自动进入等待开锁状态 6 喇叭报警可按用户要求执行 本例表明 由比较抽象 概略的系统功能到具体的 详尽的算法流程有一个跟踪控制要求并逐步细化的过程 这就是跟踪法的基本思想 2 1算法设计 开始 WSETUP SETUP 1 WAIT START 1 OPR 数码正确且操作正确 LT点亮 LF点亮 喇叭报警 Y N Y Y N N 2 1算法设计 2 1 3归纳法归纳法就是先把比较抽象的设计要求具体化 而后再进行一般规律的归纳 由此推导出系统算法 具体步骤为 先假设一组特定数据 从解决具体数据处理和数据变换入手 从中发现普遍规律 最后求导待设计系统的完整的算法流程图 例2 3试设计一个顺序排队电路的算法流程图 分析用户需求 我们发现以下问题需要确定 2 1算法设计 1 Di从输入到存放于RAM中某个字 其处理过程要一段时间 为了保证只有当Di存在RAM之后 Di 1才允许到来 建议增加一个应答信号READY 2 一组排队结束后 如果需要对另一组新数据进行排队 系统应如何工作呢 设计者建议 一旦DONE 1 首先判断WRITE 为低时总将地址信息A指定的内容从OUT输出 为高时 电路判别START 若START为高 则开始新一轮数据排队 3 排队算法 当Di RAM j 时 将Di放入RAM j 1 当Di RAM j 时 将RAM j 放入RAM j 1 而将Di放入RAM j 2 1算法设计 开始 i 0DONE 0 READY 1 START READY 0ii 1 i n READY 1对Di排队存入RAM WRITE 0 DONE 1 Y Y N N 接受Di OUTRAM A Y N 2 1算法设计 2 1 4划分法划分法就是把一个运算比较复杂的系统划分成一系列简单的运算 而后通过基本的算术运算和基本的逻辑运算来完成 例2 3试导出实现算式Z a b c d 的算法流程图 2 1算法设计 开始 WAITDONE 1 BEG Y Y N RzR1 R2 RaaRBbRccRdd R1 Ra Rb R2 Rc Rd 2 1算法设计 2 1 5解析法对于一些难以划分的计算过程 往往采用解析法莱进行算法设计 例2 4试设计一个求平方根的电路 其输入为x 输出y的算术表达式是 y x 分析 对于逻辑电路求平方根只能采用牛顿逐次逼近法 核心是 y1 y0 x yo 2 可使y1比y0更接近实际值 只要规定了计算结果的误差要求 通过若干次迭代 总可求足够精确地结果 2 1算法设计 开始 读入x y y0 u y 允许误差 Y N u y w 2 w x y 结束 yu 2 1算法设计 2 1 6综合法综合法就是把上述几种推导算法的方法组合起来应用 例2 4试设计一个人体秤控制装置的算法流程 该人体电子秤控制装置应能有序 正确的管理以下功能的实现 1 进行人体体重的测量 并能以3位十进制数显示体重的千克数 2 进行人体身高的测量 并能以3位十进制数显示高度的厘米数 体重和身高显示器公用 3 由身高和体重的实测信息 根据被测对象的具体状况 男女 成人或儿童等 自动计算并显示被测对象属于偏瘦 适中 偏胖类型的哪一种 4 允许不考虑消除电子秤的自重功能 2 1算法设计 设计按以下步骤进行 荷重传感器 位移传感器 放大器 放大器 体重 身高 A D 信息处理 显示器 打印用户卡片 1 导出逻辑框图 2 1算法设计 2 模数转换器量化和编码的约定 A D转换器把连续的模拟信号转换为数字信号 ADC0809 a 体重量化的单位量为1KG 00 FFH表示0 255KG b 身高量化的单位量为1CM 00 FFH表示0 255CM 3 电子秤控制装置算法流程图 该装置工作过程如下 a 当接收到BEG1 1时 开始一次人体身高和体重的测量 b 当BEG1 1时 首先测量身高 通过A D转换为另一组数字量 经存储码制变换和处理 由8段显示器显示3位十进制的身高数据 c 当BEG2 1时 系统进行体重测量 通过A D转换为另一组数字量 经存储码制变换和处理 显示数据 d 由上述2组数据 进行数据计算和判别 判别出对象胖瘦 并正确显示偏胖 适中或偏瘦3种情况之一 2 1算法设计 计算被测对象体重和身高比例关系 假设L为实测身高的数字量 W为实测体重的数字量 K1和K2为某常数的数字量 K1的取值为 a 男性成人 K1值约为105CM的数字量表示 b 女性成人 K1值约为100CM的数字量表示 c 青少年和儿童 按医学标准确定实际的数值 K2的取值为 a 成人 K2值约为3 8CM的数字量表示 b 青少年和儿童 按医学标准确定实际的数值 2 2算法结构 2 2 1顺序算法结构执行算法的整个过程中 同一时间只进行一种或一组相关的子运算 在顺序算法结构中 若待处理数据是单个元素D 假设它完成算法流程需要经历l段 每段平均时间为 则所需要的运算时间为 t l 若待处理的数据是连续输入的数据流 则含有n个元素的数据流总的运算时间为 Ts n t n l 特点 执行速度较慢 但实现系统的硬件配置简单 成本较低 2 2算法结构 2 2 2并行算法结构执行算法同一时间有多于一条路径在进行运算 而这些同时执行的运算操作之间几乎没有依赖关系 在顺序算法结构中 若待处理数据是单个元素D 假设它完成算法流程需要经历l段 每段平均时间为 则所需要的运算时间为 t l 若待处理的数据是连续输入的数据流 则含有n个元素的数据流总的运算时间为 Ts n t n l 特点 执行速度较慢 但实现系统的硬件配置简单 成本较低 2 2算法结构 例2 9 改进例2 3所述n个排队电路的算法 求出提高排队电路速度的并行算法 对于RAM j 1 而言 归纳为以下3种情况 a Di RAM j 时 则RAM j 1 RAM j b RAM j 1 Di RAM j 时 则RAM j 1 Dic Di RAM j 1 时 则RAM j 1 RAM j 1 2 2算法结构 0M1U2X RAM j Di RAM j 1 C0 C1 RAM j 1 数据选择器MUX的控制信号C1 C0取值为00 01 10分别对应以上3种情况 所以对于存储器RAM n 而言 其硬件结构如上图所示 同时驱动n个MUX工作 完成一个班排队过程 因此属于并行算法结构 2 2算法结构 在并行算法结构中 如果待处理数据是单个元素Di完成运算时间满足 t l 含有n个元素的数据流输入时 并行结构总的运算时间为 Tp n l 例2 10 试计算R个数据排队电路采用顺序结构算法和并行结构算法的运算时间 假设顺序结构中每个Di与一个RAM j 比较且存放需要经历h段 每段平均时间为 2 2算法结构 2 2 2流水线算法结构主要针对连续输入数据流的系统 把整个运算过程分解成若干段 系统在同一时间对先后输入的数据流元素进行不同段的运算 从而大大提高了运算速度 例2 10 试设计一个实现Z AB C 1 2运算的流水线操作算法 其中A B C均是数据流 长度为m 且均是位n 设相乘 相加 开平方需时间 1 2 3 则 整个运算完成时间为3 m 采用流水线设计时间为3 m 1 2 1算法设计 开始 AB C 1 2 A B A B C 2 3硬件系统实现概述 1 用专用SSI MSI LSI构成 2 以微机为核心 辅以必要的辅助器件 在固化于存储器内的软件的控制下实现系统功能 3 将整个系统配置在一片或者数片PLD内 4 研制相应的ASIC 构成单片系统 2 4数据处理单元的设计 数据处理单元又叫受控电路 主要功能 数据存储 算术和逻辑运算 数据传送和变换 2 4 1器件选择1 易于控制2 满足非逻辑的约束要求 1 性能因素 运行速度 ECL最快 可靠性 可测试性 2 物理因素 3 经济因素 2 4 2数据处理单元设计的基本步骤 1 组成数据处理单元逻辑框图根据系统算法和结构选择方案 用抽象的逻辑块组成逻辑框图2 构成数据处理单元详细逻辑电路图选择具体型号的集成器件实现第一步中的抽象模块 3 确定控制信号时序列出控制信号排序表 2 4 3数据处理单元设计实例 例2 11试导出例2 2中5位串行码数字锁的数据处理单元逻辑电路图 1 导出逻辑框图 2 选择器件 3 串行数字锁控制信号序列的确定 2 5控制单元的设计 用硬件电路构成控制时序信号就是控制器的设计 2 5 1系统控制方式1 集中控制 子运算器1 系统控制器 子运算器2 子运算器n 2 5控制单元的设计 2 分散控制 2 5控制单元的设计 1 半集中控制 2 5 2控制器的基本结构和系统同步 1 控制器的基本结构控制器输入信号 外界对系统的输入信号 数据处理单元的条件反馈信息控制器输出信号 对外界的输出信号 对数据处理单元的控制信号 组合逻辑网络 状态寄存器 外界输入 条件反馈输出 控制信号 输出信号 现态信息 次态信息 控制器 CP 2 5 2控制器的基本结构和系统同步 2 系统同步 1 控制器与外部信号之间的同步 即异步输入信号的同步化 异步信号同步化的必要性第一 异步信号的捕获 第二 输入信号有变化时间 同步化电路第一 异步输入信号是短暂的 第二 输入信号的同步化时间发生在时钟的上升沿 2 系统控制器输出同步 状态寄存器的各个状态量不会同时改变 总是有先后的 即时各个状态量同时变化 由于它们从组合网络的输入端到输出端所经途径不同 仍然会出现毛刺 2 5 2算法状态机图 ASM图 1 ASM图概念ASM图用来描述控制器在不同时间内应完成的一系列操作 指出控制器状态转换 转换条件及控制器的输出 ASM图和算法流程图差别 1 算法流程图是事情驱动的流程图规则 ASM图具体为时钟CP驱动的流程图 2 ASM图的状态快 不说明操作 只明确标出应有的输出 确切说 算法流程图规定了系统应进行的操作及操作顺序 ASM图规定了完成这操作顺序所需要的时间 算法流程图 2 5 2算法状态机图 ASM图 2 ASM图和算法流程图的互相关系和转换 例2 12将某算法流程图转换为ASM图 图中RE 16用RE数据左移4次实现 并用计数器CNT记录移位次数 流程图对应的算法和控制信号表如表2 5所示 ROE ROE 1 ROEDATA LD 1CPR 1 LD 0CPR 1 某流程图的局部 对应的ASM图 工作块 状态块 Si011 Sj111 2 5 2算法状态机图 ASM图 3 状态机的VHDL实现为什么要使用状态机 1 高效的顺序控制模型 2 容易利用现成的EDA优化工具 3 性能稳定 4 设计实现效率高 5 高速性能 6 高可靠性能 2 5 2算法状态机图 ASM图 一般有限状态机的结构 1 说明部分 2 主控时序进程 2 5 2算法状态机图 ASM图 一般有限状态机的结构 3 主控组合进程 2 5 2算法状态机图 ASM图 4 辅助进程 接下页 接上页 2 5 4控制器的硬件逻辑设计方法 系统控制器和同步时序电路的差别 1 关于设计依据 2 关于状态化简 3 关于状态分配 4 关于硬