数字系统设计与PLD应用第二章

第二章数字系统的算法设计与硬件实现2.1算法设计一.概述1.考虑的主要因素(1)逻辑功能(2)非逻辑指标(速度、功耗、成本等〕例2-1：用逐次累加法实现二进制乘法器。A×B=∑ABi=1特点：电路简单、成本低，但速度慢。2.硬件实现对算法设计的影响(1)中小规模通用器件:要求电路尽可能简单;(2)PLD:硬件资源丰富,不一定按最小化设计,可以提高设计效率和电路性能为目标.(3)ASIC:需兼顾最简与设计效率(重用)两个方面.二.常用设计方法1.跟踪法按功能对控制要求逐步细化(分解),从而导出算法。例2-2:五位串行密码锁的设计启动锁开始读数开启2.归纳法将抽象要求具体化(从具体数据入手),得出一般规律,再进行算法设计例2-3:正数顺序(由小至大)排队电路的设计设欲写入的数是4，6，5，8，9，10方法：首先将RAM中各单元清0；然后逐个读入数据，同时按沉底法进行排序。第i个数Di(i=1～n)与RAM(j)(j=2～n)逐个进行比较:若DiRAM(j),则RAM(j-1)-RAM(j)若Di≤RAM(j),则RAM(j-1)-Dii=n3.划分法将复合运算划分成简单运算,从而得到算法。例2-4:设计运算电路z=(a-b)(c+d)4.解析法利用“数值分析”方法,将复杂的数学运算分解成一系列简单运算的迭代,从而得到算法。例2-5:设计运算电路y=x由此，通过解析，将平方根的计算转换为w=x/y、v=y+w和u=v/2三个基本运算，由此导出算法流程图。采用牛顿迭代法:首先给出一个估算值y。然后通过迭代运算yi+1=(yi+x/yi)/2求y的近似解,直到|yi+1-yi|≤e时为止。5.综合法综合法就是把上述几种推导算法的方法组合起来应用。例2-6:试设计一个倒数变换器，求数A的倒数1/A的近似值Z。A的数值为1/2≤A1,要求变换结果满足|Z-1/A|≤10-4考虑数的范围和精度，需16位二进制定点数来表示A、Z和误差E，其中最高位为1位整数，其余为小数部分。根据解析式，进而采用划分法，把较复杂的算法分解为相乘、相减、比较等简单的子运算，从而得出相应的算法。采用牛顿－拉夫逊迭代公式：Zi＋1=Zi(2-AZi)因为Z的最小值是1，最大值是2，为此可令起始值Z0=1，只要满足|AZi-1|≤0.5E必有|Zi-1/A|≤0.5E/A≤E例2-7:四位二进制乘法器的算法设计。根据第1章的讨论知,乘法器的运算可以分解成多次移位与相加运算，也就是说，通过若干次移位运算和加法运算的循环，就可以实现乘法器的功能.例2-7:四位二进制乘法器的算法设计。根据第1章的讨论知,乘法器的运算可以分解成多次移位与相加运算，也就是说，通过若干次移位运算和加法运算的循环，就可以实现乘法器的功能.2.2算法结构一.顺序算法结构顺序算法是最基本的算法结构。其特点是：在执行算法的整个过程中，同一时间只进行一种或一组相关的子运算。在顺序算法结构中，如果待处理数据是连续输入的数据流，含有n个元素，若每个数据元素完成算法流程需经历L段，而每段平均时间为Δ，则所需的运算时间为TS=n*L*Δ顺序算法结构的工作速度不高。但实现系统的硬件配置简单，成本较低。二.并行算法结构其特点是：执行算法的同一时间有多于一条路径在进行运算，而这些同时执行的运算与操作之间几乎没有依赖关系。在并行算法结构中，如果待处理数据是连续输入的数据流，含有n个元素，若每个数据元素完成算法流程需经历L′段，而每段平均时间为Δ，则所需的运算时间为TP=n*L′*Δ其中L′是并行算法流程经历的运算段数.因L′远小于L，故大大提高了速度。三.流水线算法结构流水线算法结构仅适用于连续输入的数据流。其特点是：把整个运算过程分解成若干段，系统在同一时间可对先后输入的数据流元素进行不同段的运算。例如：求Z=AB+C在流水线算法结构中，如果待处理数据的连续输入的数据流含有n个元素，每个数据元素完成算法流程需经历L段，而每段平均时间为Δ，则所需的运算时间为T=L*Δ+(n-1)*Δ流水线算法结构的数据处理效率最高。但它要求:(1)数据流必须连续输入;(2)各处理段的硬件完全独立(不合用);(3)各段的处理时间基本相等。Pentium处理器和最新的DSP等控制器均采用了流水线结构,以最大限度地提高处理速度.2.3硬件实现概述（1）用市售标准的SSI、MSI和LSI构成,这是最经典的方法。（2）将整个系统配置在一片或数片PLD芯片内,特点是价廉、运行速度高、体积小、易于修改设计等。（3）研制相应的ASIC，构成单片系统,在大批量产品中,应用愈来愈多。（4）以微控制器(嵌入式CPU、DSP、单片机等〕为核心、辅以必要的辅助器件，在软件控制下实现系统功能。特点是价格便宜，实现方便，适用于处理速度要求不高的场合，也得到广泛应用。2.4数据处理单元设计一.器件选择1、易于控制各受控电路的控制方式和控制信号要尽可能简单，从而使产生这些控制信号的逻辑也趋简单，以便于实现。2、满足非逻辑约束的要求（1）性能因素系统性能除了前述的逻辑功能外，还有许多非逻辑因素影响着系统的性能。a.运行速度;b.可靠性(延迟、功耗、电平匹配等);c.可测试性。（2）物理因素a.器件的温度范围b.工作电源的电压范围（3）经济因素(成本)包括设计成本、制造成本、维护成本和运行成本等。二.设计步骤1、组成数据处理单元逻辑框图根据系统算法和结构选择方案，用抽象的逻辑模块组成数据处理单元逻辑框图。2、构成数据处理单元详细逻辑电路图选择具体型号的集成器件实现第1步中的抽象模块，且应力求器件数少，由此得出数据处理单元详细逻辑电路图。明确它们和控制器之间交换信息的全部特征，包括信号名称、有效作用电平或有效作用沿等。3、确定控制信号时序在明确各控制信号的基础上，对它们进行排序，列出控制信号排序表，从而归纳并确定控制信号时序，作为对控制单元设计的技术要求，使系统正确执行算法流程。三.设计举例例2-8:按照本章例2-6所设计的倒数变换器算法流程图，设计其数据处理单元。为实现倒数变换器各子运算，需要5个存储器，且应分别由相应的控制信号管理，它们是：a.A（16bit），存储待变换数据ARG,实现A←ARG。b.E（16bit），存储规定误差数据ERR，实现E←ERR/2。c.Z（16bit），存储变换结果Z。实现Z←1或Z←（Y×Z）。d.W（16bit），存放运算的中间结果（A×Z），实现W←（A×Z）。e.Y（16bit），存放中间结果（2-A×Z）数据，实现Y←（2-A×Z）。第一步导出数据处理单元的逻辑框图（1）存储器的选择。存储器是用以存储待处理的数据、中间结果、输出数据以及条件反馈信息等。(2)运算器的选择倒数变换器算法流程图中，包括三种子运算：乘法运算、减法运算和比较运算。为此，运算器和相应的控制信号作如下选择和规定：a.乘法器MUL。b.减法器SUB1。c.减法器SUB2。d.比较器COMP。由此，可得数据处理单元的逻辑框图.第二步导出数据处理单元的逻辑电路图。根据上述逻辑框图，选择实现数据处理单元各模块的具体器件,即得数据处理单元的逻辑电路图.第三步确定控制信号的时序在画出数据处理单元逻辑电路图的基础上，列出数据处理单元所需的控制信号的时序表.例2-9:试设计四位乘法器的数据处理单元.需3个寄存器RA,RB和RP分别存放被乘数A、乘数B和乘积（部分积〕P。需要1个计数器记录循环次数。需要1个四位并行加法器。部分积P的移位可通过移位寄存器实现。B1～B4的检测也可以采用移位寄存器将4位并行数据逐位串行移出检查。乘法器数据处理单元的逻辑框图乘法器数据处理单元的逻辑电路图数据处理单元所需的控制信号及其时序步骤操作控制信号1WaitEND=12i←0，P←0输入A,BCR=0CA=CB1=CB0=13i←i+1P←P+ACC=1CM1=CM0=14右移PCM0=CB0=1数据处理单元所需的控制信号及其时序步骤操作控制信号1WaitEND=12i←0，P←0输入A,BCR=0CA=CB1=CB0=13i←i+1P←P+ACC=1CM1=CM0=14右移PCM0=CB0=12.5控制单元的设计一.系统控制方式系统控制的实质是控制系统中的数据处理单元以预定的时序进行工作。控制方式有三种类型：集中控制、分散控制和半集中控制.集中控制方式经常有一个同步时钟信号CP。子运算的执行时间可能只需一个时钟信号的周期，也可能需要若干个时钟周期；在某些情况下，子运算执行时间并不固定，而由数据状态来决定。1、集中控制数字系统中，如果仅有一个控制器，由它控制整个算法的执行，则称为集中控制型.2、分散控制系统中没有统一的控制器，全部控制功能分散在各个子运算器中完成，称作分散控制型。分散控制的时序可以是同步的，也可以是异步的。前者与集中控制类似，但各子运算器间需交换有关运算进程的信息。分散控制为异步时序时，没有统一的时钟信号，执行顺序由子运算器产生的进程信号控制。3、半集中控制系统中配有系统控制器，但对各子运算器又在各自的控制器控制下进行工作。系统控制器集中控制各子运算之间总的执行顺序。称为半集中控制型或集散型控制器.二.控制器的基本结构和信号同步1、控制器的基本结构控制器的输入信号有：外界对系统的输入（即外输入信号）和数据处理单元所产生的条件反馈信息。控制器的输出信号有对数据处理单元的控制信号和对外界的输出。控制器实际上就是一个同步时序电路(有限状态机).2、异步输入信号的同步信号同步是指控制器与外部输入信号和来自数据处理单元的反馈信号之间的同步问题，即异步输入信号的同步化.三.算法状态机图(ASM图)算法流程图，并未严格规定各操作的时间及操作之间的时序关系。采用同步时序结构的控制器，在时钟脉冲的驱动下完成各种操作，为此应该对各操作之间的时间关系作出严格的描述。算法状态机图(AlgorithmicStateMachineChart，ASM图)便是一种描述时钟驱动的控制器工作流程的方法。1.ASM图的基本符号(1)状态块对应控制器的一个工作状态,与算法流程图中工作块的区别在于,必须标明需要产生的输出控制信号(2)判别块对应某个输入条件的判断,与算法流程图中判别块的区别在于,必须标明需要判别的输入信号.(3)条件输出块条件输出块不是一个独立的状态,其中的输出信号除了与它之前判别块中的输入条件有关外,还与判别块之前的状态块有关。因此它相当于米里型输出，而状态块中的输出相当于莫尔型输出。2。由算法流程图导出ASM图算法流程图与ASM图之间存在明确的对应关系。例2-10：根据前述四位乘法器的算法流程图和数据处理单元导出其控制器的ASM图.步骤操作控制信号1WaitEND=12i←0，P←0输入A,BCR=0CA=CB1=CB0=13i←i+1P←P+ACC=1CM1=CM0=14右移PCM0=CB0=1算法流程图ASM图算法流程图ASM图ASM图算法流程图ASM图算法流程图四.基于ASM图的控制器设计一般无需状态化简,直接选择核心时序器件,状态分配(编码),推导激励函数和输出函数,从而得出控制器的逻辑电路.例2-11：根据上例的ASM图,以D触发器为记忆元件,设计四位乘法器的控制单元.(1)状态分配共4个状态，故仅需2个触发器。令S0S1S3S20101Q1Q0ASM图(2)推导激励函数10Q1Q0010101Q0Q1D1D0END=1START=1?CR=0,CA=1CB0=CB1=1CC=1Bi=1?CM0=1CM1=1CM0=1CB0=1i=4?NYYNNYS3S2S1S00001101110Q1Q001011i=4START0010101Q0Q1D1D0END=1START=1?CR=0,CA=1CB0=CB1=1CC=1Bi=1?CM0=1CM1=1CM0=1CB0=1i=4?NYYNNYS3S2S1S000011011(2)推导激励函数10Q1Q001011i=4START0010101Q0Q1D1D0END=1START=1?CR=0,CA=1CB0=CB1=1C