• 1. 第5讲 设计方法 设计步骤 系统设计 算法设计 几种常用算法 算法结构 并行设计技术 系统同步10/23/20181
  • 2. 5.1 设计步骤 数字系统设计基本步骤 系统设计:对系统功能进行模块划分,落实系统功能和技术指标的分配,同时确定各功能模块之间的接口关系。运用框图与层次的方法自顶向下进行设计。 算法设计:确定实现系统要求的算法。 电路设计:确定电路形式,在电路级描述系统功能。 芯片设计:按照确定的算法和电路形式,通过设计芯片内部的逻辑功能来实现这些算法和电路。 PCB设计:实现系统整体功能,同时进行初步的工艺和机械结构的设计。 结构设计:包括机箱和面板设计,属工艺和工业造型的问题。 电路调试:检查设计中存在的问题。10/23/20182
  • 3. 5.1 设计步骤(续) 数字系统设计基本准则 分割准则 最底层的逻辑块适合用基本逻辑电路来实现,或用逻辑语言进行表达; 相似功能的模块应该设计成共享的基本模块; 接口信号线最少结构均称,同层次的模块之间在资源和I/O分配上,不应出现悬殊的差异,没有明显的结构和性能上的瓶颈; 通用性好,易于移植。 系统的可观测性:在设计系统的同时设计观测电路。 系统的关键点信号,如时钟、同步信号和状态信号; 具有代表性的节点和线路上的信号; 具备简单的“系统工作是否正常”的判断能力 同步和异步电路10/23/20183
  • 4. 5.1 设计步骤(续) 尽可能采用同步电路进行设计,避免使用异步电路; 在必须使用异步电路的场合,应采取措施来避免竞争、增加稳定性。 最优化设计 器件资源利用率最高; 系统工作速度最快,即延时最小; 布线最容易,即可实现性最好。 理想的设计 设计流畅、无拖泥带水的感觉; 资源分配、I/O分配合理,没有任何设计上和性能上的瓶颈; 具有良好的可观测性; 易于修改和移植; 电路器件的特点得到充分的发挥。10/23/20184
  • 5. 5.2 系统设计 对系统功能进行模块划分,落实系统功能和技术指标的分配,同时确定各功能模块之间的接口关系。系统设计的好坏直接决定系统的整体性能。 例5.1 乘法器设计 迭代方式:成本低 阵列方式:速度快 流水方式:浮点运算 大数乘法器:算很大的数 低功耗方式:功耗低迭代式乘法器10/23/20185
  • 6. 5.2 系统设计(续)阵列式乘法器10/23/20186
  • 7. 5.2 系统设计(续)流水式乘法器10/23/20187
  • 8. 5.2 系统设计(续)大整数乘法器控制器数据通路10/23/20188
  • 9. 5.3 算法设计 FPGA的作用 简化:简化硬件设计与制作 提速:提高算法执行速度 通用CPU与FPGA差别 通用CPU通过“很细小”的机器指令串行地执行程序,每次执行都要“取指”、“分析”、“执行”、“保存”; FPGA只执行与系统速度相关的、规模较大的“特殊”操作,这些操作往往可由多个电路模块并行执行。 “硬件”算法最终由硬件来实现,其设计要求与硬件结构良好对应;软件算法则完全用程序来实现,形式多样。10/23/20189
  • 10. 5.3 算法设计(续) 采用器件的结构、规模、性质不同时,将用不同的算法设计 若使用通用芯片,则考虑系统结构尽量简单,少用芯片; 若采用单片机或DSP,则因为器件相当丰富,算法设计也不尽相同。 算法设计中主要考虑的因素 功能:系统应完成的功能; 速度:系统要达到的运行速度,在实时系统中显得很重要; 功耗:手持设备的重要指标; 成本:几乎是人人关心的问题。 各因素往往相互制约,必须协调,寻找到最佳方案。10/23/201810
  • 11. 5.4 几种常用算法 跟踪法:按照确定的系统功能,由控制要求逐步细化、具体化系统的工作过程,从而导出系统的算法。 例5.1:设计一个简单的7位串行数字门锁系统。该锁在输入完0110111时,绿灯亮,可以用钥匙开门。 解:用Mealy机来实现还有其它办法吗?10/23/201811
  • 12. 归纳法:从特殊到一般的方法。先将比较抽象、概略的系统功能设计具体化,然后再经过一般规律性的归纳,从而导出系统的算法。5.4 几种常用算法(续)输入:LEFT,RIGHT,HAZ,(时钟); 输出:LC,LB,LA,RA,RB,RC。 例5.2:雷鸟车尾灯10/23/201812
  • 13. 5.4 几种常用算法(续)共有8个状态,其中IDLE为空闲状态(没有灯发光)。问题:在IDLE状态时,如果LEFT和HAZ同时有效会怎么样?10/23/201813
  • 14. 5.4 几种常用算法(续) 状态图必须没有二义性,即离开每一个状态的弧线上所标出的转移表达式都是互斥的,并且是完备的。 互斥性:在离开每一状态的弧线上所标的任意一对转移表达式的逻辑积等于0。 完备性:在离开每一状态的弧线上所标的所有转移表达式的逻辑和等于1。 右图无二义性 有没有更好的改进?10/23/201814
  • 15. 5.4 几种常用算法(续) 初态:000; 左转:Q2=0,Q1 Q0用葛莱码; 右转:Q2=1,Q1 Q0用葛莱码; 全亮:100。一个更好的改进10/23/201815
  • 16. 划分法:把一个复杂系统按一定规则划分成为一系列简单的子系统,而这些子系统可由简单的算术运算和逻辑运算来完成,从而导出系统的算法。5.4 几种常用算法(续) 例5.3:设计一个时钟同步状态机(“猜谜游戏”机),它有4个按钮输入G1~G4和4个灯输出L1~L4,按钮和灯都有一个编号。另外,还有一个输出信号ERR与一个红灯相连。4个灯在时钟控制下,轮流地被点亮,时钟频率为4Hz。按下一个按钮,就有一个输入Gi为有效。如果在时钟触发沿所测得Gi与时钟触发沿到来前就有效的灯输出不相同的话,ERR信息有效,红灯被点亮。一旦完成了一次猜测,游戏就停止并且ERR输出会维持1个或多个时钟周期(猜错时),直到输入Gi被取消,游戏又恢复进行。10/23/201816
  • 17. 5.4 几种常用算法(续)?10/23/201817
  • 18. 5.4 几种常用算法(续)10/23/201818
  • 19. 例5.4:要使得游戏更具有挑战性,可以使时钟频率为原来的2倍或是3倍,并且让灯保持原来状态的时间为任意长(随机的)。这样游戏者就真正要做出判断:某一盏灯在某一状态上保持的时间是否足以让他按下按钮。5.4 几种常用算法(续) 10/23/201819
  • 20. 10/23/201820
  • 21. 5.4 几种常用算法(续) 解析法:当遇到难以分解的计算过程时,采用数学分析对其进行数值近似,转换成多项式或某种迭代过程,然后画出其算法流程图,从而导出系统的算法。 例5.5:设计一个求 y= 的电路。 分析:一种常用的求x的平方根的方法是牛顿逐次逼近法。方法的核心是给出一个 的估算值y0,用y1=(y0+x/y0)/2,求得y1,同理可求得y2,y3…逐次递进,最后达到精度要求为止。 设x=3,令y0=1,其计算过程为: 序号 y W=x/y V=y+W U=V/2 0 1 3 4 2 1 2 1.5 3.5 1.75 2 1.75 1.714 3.464 1.7321 3 1.7321 1.73200 3.4641 1.7320510/23/201821
  • 22. 通过解析,将平方根的运算转化成W=x/y,V=y+W,U=V/2 三种基本运算,由此可设计出如右所示的算法流程图。5.4 几种常用算法(续)开始w=x / yREAD x, y=y0u=(y+w)/2u-y<=允许的误差结束Noy = u开始w=x / yREAD x, y=y0u=(y+w)/2u-y<=允许的误差结束Yes 综合法:在实际应用中,大部分数字系统的算法比较复杂,需要综合、全面地考虑,逐步分解逻辑关系,最后获得完整的算法流程图。把跟踪法、归纳法、划分法、解析法等几种设计算法组合起来应用的方法称为综合法。10/23/201822
  • 23. 5.5 算法结构 数据依赖性:影响算法执行速度的重要原因之一。OP1OP2OP3OP4OP50t1t2t3t4t5OP1OP2OP3OP4OP5OP6OP7OP80t1t2t3t4t5一组关联的子运算 顺序算法结构:在执行算法的整个过程中,同一时间只进行一种或一组相关的子运算,前后运算存在相关性。10/23/201823
  • 24. 5.5 算法结构(续) 并行算法结构:在同一时间段中,有多条路径在同时进行运算,这些同时执行的子运算操作之间是相互独立的。OP1OP2OP3OP4OP5OP6OP7OP8OP9OP10OP110t1t2t3t4 从OP1到OP2、OP3、OP4不是顺序算法中的条件转移; OP2、OP3、OP4之间互不关联; OP5和OP6、OP10和OP11为顺序运算路径中的一组相关操作。10/23/201824
  • 25. 5.5 算法结构(续) 流水线操作结构:针对连续输入数据流的顺序处理结构,与基本的顺序结构相比具有如下特点: 在流水线中操作运算必须是连续任务,只有连续不断地提供任务才能充分发挥流水线的效; 把一个运算(操作)分解为几个有联系的子运算(子操作),每个子运算由一个专门的功能部件来实现; 在流水线的每一个功能部件后面都要有一个缓冲寄存器,用于保存本段的执行结果; 流水线中各段的时间应尽量相等,否则将引起“堵塞”或“断流”等现象; 流水线需要有“装入时间”和“排空时间”。只有流水线完全充满时,整个流水线的效率才能得到充分发挥。 在流水线中操作运算必须是连续任务,只有连续不断地提供任务才能充分发挥流水线的效率; 把一个运算(操作)分解为几个有联系的子运算(子操作),每个子运算由一个专门的功能部件来实现; 在流水线的每一个功能部件后面都要有一个缓冲寄存器,用于保存本段的执行结果; 流水线中各段的时间应尽量相等,否则将引起“堵塞”或“断流”等现象; 流水线需要有“装入时间”和“排空时间”。只有流水线完全充满时,整个流水线的效率才能得到充分发挥。10/23/201825
  • 26. 5.5 算法结构(续) 一个4级流水结构10/23/201826
  • 27. 5.5 算法结构(续) 例5.6:试用顺序操作和流水操作算法实现 ,其中A、B、C均为数据流,数据流长度为m。 采用顺序算法结构:在⊿t1,⊿t2,⊿t3分别完成这三种子运算。为方便分析,设⊿t1= ⊿t2= ⊿t3= ⊿t,完成整个运算的时间为: Ts=3 • m • ⊿t10/23/201827
  • 28. 5.5 算法结构(续) 采用流水线操作算法结构:为提高运算速度,又不增加运算器的硬件成本,改用流水线操作算法结构。 由图可以看出,完成全部数据计算所需要的时间为: T=3⊿t + (m-1) ⊿t 显然,流水线结构比顺序结构所需要的运算时间要少((n-1)(m-1))。10/23/201828
  • 29. 5.6 并行设计技术 非相关判别条件:设输入集合为I1、I2,输出集合为U1、U2: I1ΛU2=Φ; I2ΛU1=Φ; U1ΛU2=ΦY=(A+B(C+DEF))+G 6 Y=(A+G)+B(C+DEF) 5 Y=(A+G+BC)+BD*EF 3 并行设计技术 划分技术:将给定问题分成p个独立的几乎等尺寸的子问题由p个电路求解。如何分组,使得子问题易于求解是关键。10/23/201829
  • 30. 5.6 并行设计技术(续) 分治设计技术:将一个大而复杂的问题分解成若干特征相同的子问题分而治之,如大整数乘法。 将输入问题分解成若干特征相同的子问题 并行地求解各个子问题 归并各子问题的解称为源问题的解 缓冲操作技术 乒乓操作 串并转换 流水线设计技术10/23/201830
  • 31. 5.7 系统同步 包括控制器与外部输入信号之间的同步(异步输入同步),系统控制器的输出同步。 异步输入同步:对于异步输入信号必须进行同步化处理。 异步信号的捕捉 信号同步 信号清除10/23/201831
  • 32. 5.7 系统同步(续)自动清除?非自动清除?10/23/201832
  • 33. 5.7 系统同步(续) 控制器的输出同步 输出信号通常由组合电路产生,可能出现冒险,因为: 状态寄存器的各个状态变量通常不会同时改变; 从组合电路的输入到输出会有竞争而出现冒险。 在控制器输出端增加缓冲寄存器和合适的选通信号10/23/201833