第5讲 设计方法.

1、2022-5-301第第5 5讲讲 设计方法设计方法设计步骤设计步骤系统设计系统设计算法设计算法设计几种常用算法几种常用算法算法结构算法结构并行设计技术并行设计技术系统同步系统同步2022-5-3025.1 5.1 设计步骤设计步骤l 数字系统设计基本步骤 l 系统设计：对系统功能进行模块划分，落实系统功能和技术指标的分配，同时确定各功能模块之间的接口关系。运用框图与层次的方法自顶向下进行设计。l 算法设计：确定实现系统要求的算法。l 电路设计：确定电路形式，在电路级描述系统功能。l 芯片设计：按照确定的算法和电路形式，通过设计芯片内部的逻辑功能来实现这些算法和电路。l PCB设计：实现系统整

2、体功能，同时进行初步的工艺和机械结构的设计。l 结构设计：包括机箱和面板设计，属工艺和工业造型的问题。l 电路调试：检查设计中存在的问题。2022-5-3035.1 5.1 设计步骤（续）设计步骤（续）l 数字系统设计基本准则 l 分割准则l 最底层的逻辑块适合用基本逻辑电路来实现，或用逻辑语言进行表达；l 相似功能的模块应该设计成共享的基本模块；l 接口信号线最少结构均称，同层次的模块之间在资源和I/O分配上，不应出现悬殊的差异，没有明显的结构和性能上的瓶颈；l 通用性好，易于移植。l 系统的可观测性：在设计系统的同时设计观测电路。l 系统的关键点信号，如时钟、同步信号和状态信号；l 具有代

3、表性的节点和线路上的信号；l 具备简单的“系统工作是否正常”的判断能力l 同步和异步电路2022-5-3045.1 5.1 设计步骤（续）设计步骤（续）l 尽可能采用同步电路进行设计，避免使用异步电路；l 在必须使用异步电路的场合，应采取措施来避免竞争、增加稳定性。l 最优化设计l 器件资源利用率最高；l 系统工作速度最快，即延时最小；l 布线最容易，即可实现性最好。l 理想的设计l 设计流畅、无拖泥带水的感觉；l 资源分配、IO分配合理，没有任何设计上和性能上的瓶颈；l 具有良好的可观测性；l 易于修改和移植；l 电路器件的特点得到充分的发挥。2022-5-3055.2 5.2 系统设计系统

4、设计l 对系统功能进行模块划分，落实系统功能和技术指标的分配，同时确定各功能模块之间的接口关系。系统设计的好坏直接决定系统的整体性能。例5.1 乘法器设计l 迭代方式：成本低l 阵列方式：速度快l 流水方式：浮点运算l 大数乘法器：算很大的数l 低功耗方式：功耗低迭代式乘法器2022-5-3065.2 5.2 系统设计（续）系统设计（续）阵列式乘法器2022-5-3075.2 5.2 系统设计（续）系统设计（续）流水式乘法器2022-5-3085.2 5.2 系统设计（续）系统设计（续）大整数乘法器控制器数据通路2022-5-3095.3 5.3 算法设计算法设计l FPGA的作用l 简化：简

5、化硬件设计与制作l 提速：提高算法执行速度l 通用CPU与FPGA差别l 通用CPU通过“很细小”的机器指令串行地执行程序，每次执行都要“取指”、“分析”、“执行”、“保存”；l FPGA只执行与系统速度相关的、规模较大的“特殊”操作，这些操作往往可由多个电路模块并行执行。l “硬件”算法最终由硬件来实现，其设计要求与硬件结构良好对应；软件算法则完全用程序来实现，形式多样。2022-5-30105.3 5.3 算法设计（续）算法设计（续）l 采用器件的结构、规模、性质不同时，将用不同的算法设计l 若使用通用芯片，则考虑系统结构尽量简单，少用芯片；l 若采用单片机或DSP，则因为器件相当丰富，算

6、法设计也不尽相同。l 算法设计中主要考虑的因素l 功能：系统应完成的功能；l 速度：系统要达到的运行速度，在实时系统中显得很重要；l 功耗：手持设备的重要指标；l 成本：几乎是人人关心的问题。l 各因素往往相互制约，必须协调，寻找到最佳方案。2022-5-30115.4 5.4 几种常用算法几种常用算法l 跟踪法：按照确定的系统功能，由控制要求逐步细化、具体化系统的工作过程，从而导出系统的算法。 例5.1：设计一个简单的7位串行数字门锁系统。该锁在输入完0110111时，绿灯亮，可以用钥匙开门。 解：用Mealy机来实现还有其它办法吗？2022-5-3012l 归纳法：从特殊到一般的方法。先将

7、比较抽象、概略的系统功能设计具体化，然后再经过一般规律性的归纳，从而导出系统的算法。5.4 5.4 几种常用算法（续）几种常用算法（续）输入：LEFT，RIGHT，HAZ，（时钟）；输出：LC，LB，LA，RA，RB，RC。 例5.2：雷鸟车尾灯2022-5-30135.4 5.4 几种常用算法（续）几种常用算法（续）共有8个状态，其中IDLE为空闲状态（没有灯发光）。问题：在IDLE状态时，如果LEFT和HAZ同时有效会怎么样？2022-5-30145.4 5.4 几种常用算法（续）几种常用算法（续）l 状态图必须没有二义性，即离开每一个状态的弧线上所标出的转移表达式都是互斥的，并且是完备的

8、。l 互斥性：在离开每一状态的弧线上所标的任意一对转移表达式的逻辑积等于0。l 完备性：在离开每一状态的弧线上所标的所有转移表达式的逻辑和等于1。l 右图无二义性l 有没有更好的改进？2022-5-30155.4 5.4 几种常用算法（续）几种常用算法（续） 初态：000； 左转：Q2=0，Q1 Q0用葛莱码； 右转：Q2=1，Q1 Q0用葛莱码； 全亮：100。一个更好的改进一个更好的改进2022-5-3016l 划分法：把一个复杂系统按一定规则划分成为一系列简单的子系统，而这些子系统可由简单的算术运算和逻辑运算来完成，从而导出系统的算法。5.4 5.4 几种常用算法（续）几种常用算法（续）

9、 例5.3：设计一个时钟同步状态机（“猜谜游戏”机），它有4个按钮输入G1G4和4个灯输出L1L4，按钮和灯都有一个编号。另外，还有一个输出信号ERR与一个红灯相连。4个灯在时钟控制下，轮流地被点亮，时钟频率为4Hz。按下一个按钮，就有一个输入Gi为有效。如果在时钟触发沿所测得Gi与时钟触发沿到来前就有效的灯输出不相同的话，ERR信息有效，红灯被点亮。一旦完成了一次猜测，游戏就停止并且ERR输出会维持1个或多个时钟周期（猜错时），直到输入Gi被取消，游戏又恢复进行。2022-5-30175.4 5.4 几种常用算法（续）几种常用算法（续）?2022-5-30185.4 5.4 几种常用算法（续

10、）几种常用算法（续）2022-5-3019 例5.4：要使得游戏更具有挑战性，可以使时钟频率为原来的2倍或是3倍，并且让灯保持原来状态的时间为任意长（随机的）。这样游戏者就真正要做出判断：某一盏灯在某一状态上保持的时间是否足以让他按下按钮。5.4 5.4 几种常用算法（续）几种常用算法（续） 2022-5-30202022-5-30215.4 5.4 几种常用算法（续）几种常用算法（续）l 解析法：当遇到难以分解的计算过程时，采用数学分析对其进行数值近似，转换成多项式或某种迭代过程，然后画出其算法流程图，从而导出系统的算法。xx 例5.5：设计一个求 y= 的电路。 分析：一种常用的求x的平方

11、根的方法是牛顿逐次逼近法。方法的核心是给出一个 的估算值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.732052022-5-3022 通过解析，将平方根的运算转化成W=x/y，=y+W，U=V/2三种基本运算，由此可设计出如右所示的算法流程图。5.4 5.4 几种常用算法（续）几种常用算法（续）开始

12、开始w=x / yREAD x, y=y0u=(y+w)/2u-y=允许的误差允许的误差结束结束Noy = u开始开始w=x / yREAD x, y=y0u=(y+w)/2u-y=允许的误差允许的误差结束结束Yesl 综合法：在实际应用中，大部分数字系统的算法比较复杂，需要综合、全面地考虑，逐步分解逻辑关系，最后获得完整的算法流程图。把跟踪法、归纳法、划分法、解析法等几种设计算法组合起来应用的方法称为综合法。2022-5-30235.5 5.5 算法结构算法结构l 数据依赖性：影响算法执行速度的重要原因之一。OP1OP2OP3OP4OP50t1t2t3t4t5OP1OP2OP3OP4OP5O

13、P6OP7OP80t1t2t3t4t5一组关联的子运算l 顺序算法结构：在执行算法的整个过程中，同一时间只进行一种或一组相关的子运算，前后运算存在相关性。2022-5-30245.5 5.5 算法结构（续）算法结构（续）l 并行算法结构：在同一时间段中，有多条路径在同时进行运算，这些同时执行的子运算操作之间是相互独立的。OP1OP2OP3OP4OP5OP6OP7OP8OP9OP10OP110t1t2t3t4l 从OP1到OP2、OP3、OP4不是顺序算法中的条件转移；l OP2、OP3、OP4之间互不关联；l OP5和OP6、OP10和OP11为顺序运算路径中的一组相关操作。2022-5-30

14、255.5 5.5 算法结构（续）算法结构（续）l 流水线操作结构：针对连续输入数据流的顺序处理结构，与基本的顺序结构相比具有如下特点：l 在流水线中操作运算必须是连续任务，只有连续不断地提供任务才能充分发挥流水线的效；l 把一个运算（操作）分解为几个有联系的子运算（子操作），每个子运算由一个专门的功能部件来实现；l 在流水线的每一个功能部件后面都要有一个缓冲寄存器，用于保存本段的执行结果；l 流水线中各段的时间应尽量相等，否则将引起“堵塞”或“断流”等现象；l 流水线需要有“装入时间”和“排空时间”。只有流水线完全充满时，整个流水线的效率才能得到充分发挥。l 在流水线中操作运算必须是连续任务

15、，只有连续不断地提供任务才能充分发挥流水线的效率；l 把一个运算（操作）分解为几个有联系的子运算（子操作），每个子运算由一个专门的功能部件来实现；l 在流水线的每一个功能部件后面都要有一个缓冲寄存器，用于保存本段的执行结果；l 流水线中各段的时间应尽量相等，否则将引起“堵塞”或“断流”等现象；l 流水线需要有“装入时间”和“排空时间”。只有流水线完全充满时，整个流水线的效率才能得到充分发挥。2022-5-30265.5 5.5 算法结构（续）算法结构（续）l 一个4级流水结构2022-5-30275.5 5.5 算法结构（续）算法结构（续） 例5.6：试用顺序操作和流水操作算法实现 ，其中A、

16、B、C均为数据流，数据流长度为m。CBAl 采用顺序算法结构：在t1，t2，t3分别完成这三种子运算。为方便分析，设t1= t2= t3= t，完成整个运算的时间为： Ts=3 m t2022-5-30285.5 5.5 算法结构（续）算法结构（续）l 采用流水线操作算法结构：为提高运算速度，又不增加运算器的硬件成本，改用流水线操作算法结构。 由图可以看出，完成全部数据计算所需要的时间为： T=3t + (m-1) t显然，流水线结构比顺序结构所需要的运算时间要少（(n-1)(m-1)）。2022-5-30295.6 5.6 并行设计技术并行设计技术l 非相关判别条件：设输入集合为I1、I2，

17、输出集合为U1、U2：l I1U2=；l I2U1=；l U1U2=Y=(A+B(C+DEF)+G 6Y=(A+G)+B(C+DEF) 5Y=(A+G+BC)+BD*EF 3l 并行设计技术l 划分技术：将给定问题分成p个独立的几乎等尺寸的子问题由p个电路求解。如何分组，使得子问题易于求解是关键。2022-5-30305.6 5.6 并行设计技术并行设计技术（续）（续）l 分治设计技术：将一个大而复杂的问题分解成若干特征相同的子问题分而治之，如大整数乘法。l 将输入问题分解成若干特征相同的子问题l 并行地求解各个子问题l 归并各子问题的解称为源问题的解l 缓冲操作技术l 乒乓操作l 串并转换l 流水线设计技术2022-5-30315.7 5.7 系统同步系统同步l