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

《数字系统设计与PLD应用第二章.ppt》由会员分享，可在线阅读，更多相关《数字系统设计与PLD应用第二章.ppt（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章第二章数字系统的算法设计与硬件实现数字系统的算法设计与硬件实现2021/9/1712.1算法设计算法设计一一.概述概述1.考虑的主要因素考虑的主要因素(1)逻辑功能逻辑功能(2)非逻辑指标非逻辑指标(速度、功耗、成本等速度、功耗、成本等例例2-1：用逐次累加法实现二进制乘法器。：用逐次累加法实现二进制乘法器。AB=ABi=1特点：电路简单、成本低，但速度慢。特点：电路简单、成本低，但速度慢。2021/9/1722.硬件实现对算法设计的影响硬件实现对算法设计的影响(1)中小规模通用器件中小规模通用器件:要求电路尽可能简单要求电路尽可能简单;(2)PLD:硬件资源丰富硬件资源丰富,不一定按最

2、小化设计不一定按最小化设计,可以提高设计效率和可以提高设计效率和电路性能为目标电路性能为目标.(3)ASIC:需兼顾最简与设计效率需兼顾最简与设计效率(重用重用)两个方面两个方面.二二.常用设计方法常用设计方法1.跟踪法跟踪法按功能对控制要求逐步细化按功能对控制要求逐步细化(分解分解),从而导出算法。从而导出算法。例例2-2:五位串行密码锁的设计五位串行密码锁的设计启动锁启动锁开始开始读数读数开启开启2021/9/1732021/9/1742021/9/1752021/9/1762021/9/1772021/9/1782.归纳法归纳法将抽象要求具体化将抽象要求具体化(从具体数据入手从具体数据入

3、手),得出一般规律得出一般规律,再进行算法再进行算法设计设计例例2-3:正数顺序正数顺序(由小至大由小至大)排队电路的设计排队电路的设计设欲写入的数是设欲写入的数是4，6，5，8，9，10方法：首先将方法：首先将RAM中各单元清中各单元清0；然后逐个读入数据，同时按沉然后逐个读入数据，同时按沉底法进行排序。底法进行排序。第第i个数个数Di(i=1n)与与RAM(j)(j=2n)逐个进行比较逐个进行比较:若若DiRAM(j),则则RAM(j-1)-RAM(j)若若DiRAM(j),则则RAM(j-1)-Di2021/9/1792021/9/1710i=n2021/9/17113.划分法划分法将复

4、合运算划分成简单运算将复合运算划分成简单运算,从而得到算法。从而得到算法。例例2-4:设计运算电路设计运算电路z=(a-b)(c+d)2021/9/17124.解析法解析法利用利用“数值分析数值分析”方法方法,将复杂的数学运算分解成一系列简单运算将复杂的数学运算分解成一系列简单运算的迭代的迭代,从而得到算法。从而得到算法。例例2-5:设计运算电路设计运算电路y=x由此，通过解析，将平方根的由此，通过解析，将平方根的计算转换为计算转换为w=x/y、v=y+w和和u=v/2三个基本运算，由此导出三个基本运算，由此导出算法流程图。算法流程图。采用牛顿迭代法采用牛顿迭代法:首先给出一个估算值首先给出一

5、个估算值y。然后通过迭代运算然后通过迭代运算yi+1=(yi+x/yi)/2求求y的近似解的近似解,直到直到|yi+1-yi|e时为止。时为止。2021/9/17135.综合法综合法综合法就是把上述几种推导算法的方法组合起来应用。综合法就是把上述几种推导算法的方法组合起来应用。例例2-6:试设计一个倒数变换器，求数试设计一个倒数变换器，求数A的倒数的倒数1/A的近似值的近似值Z。A的的数值为数值为1/2A1,要求变换结果满足要求变换结果满足|Z-1/A|10-4考虑数的范围和考虑数的范围和精度，需精度，需16位二进位二进制定点数来表示制定点数来表示A、Z和误差和误差E，其中最，其中最高位为高位

6、为1位整数，位整数，其余为小数部分。其余为小数部分。2021/9/1714根据解析式，进而采用划分法，根据解析式，进而采用划分法，把较复杂的算法分解为相乘、相减、把较复杂的算法分解为相乘、相减、比较等简单的子运算，从而得出相比较等简单的子运算，从而得出相应的算法。应的算法。采用牛顿拉夫逊迭代公式：采用牛顿拉夫逊迭代公式：Zi1=Zi(2-AZi)因为因为Z的最小值是的最小值是1，最大值是，最大值是2，为此可令起始值为此可令起始值Z0=1，只要满足，只要满足|AZi-1|0.5E必有必有|Zi-1/A|0.5E/AE2021/9/1715例例2-7:四位二进制乘法器的算法设计。四位二进制乘法器的

7、算法设计。根据第根据第1 1章的讨论知章的讨论知,乘法器乘法器的运算可以分解成多次移位与相的运算可以分解成多次移位与相加运算，也就是说，通过若干次加运算，也就是说，通过若干次移位运算和加法运算的循环，就移位运算和加法运算的循环，就可以实现乘法器的功能可以实现乘法器的功能.2021/9/1716例例2-7:四位二进制乘法器的算法设计。四位二进制乘法器的算法设计。根据第根据第1 1章的讨论知章的讨论知,乘法器乘法器的运算可以分解成多次移位与相的运算可以分解成多次移位与相加运算，也就是说，通过若干次加运算，也就是说，通过若干次移位运算和加法运算的循环，就移位运算和加法运算的循环，就可以实现乘法器的功

8、能可以实现乘法器的功能.2021/9/17172.2算法结构算法结构一一.顺序算法结构顺序算法结构顺序算法是最基本的算法结构。其特点是：在执行算法的整个过顺序算法是最基本的算法结构。其特点是：在执行算法的整个过程中，同一时间只进行一种或一组相关的子运算。程中，同一时间只进行一种或一组相关的子运算。在顺序算法结构中，如果待处理数据是连续输入的数据流，含有在顺序算法结构中，如果待处理数据是连续输入的数据流，含有n个元素，若每个数据元素完成算法流程需经历个元素，若每个数据元素完成算法流程需经历L段，而每段平均时段，而每段平均时间为间为，则所需的运算时间为，则所需的运算时间为TS=n*L*顺序算法结构

9、的工作速度不高。但实现系统的硬件配置简单，成顺序算法结构的工作速度不高。但实现系统的硬件配置简单，成本较低。本较低。2021/9/1718二二.并行算法结构并行算法结构其特点是：执行算法的同一时间有多于一条路径在进行运算，而其特点是：执行算法的同一时间有多于一条路径在进行运算，而这些同时执行的运算与操作之间几乎没有依赖关系。这些同时执行的运算与操作之间几乎没有依赖关系。在并行算法结构中，如果待处理数据是连续输入的数据流，含有在并行算法结构中，如果待处理数据是连续输入的数据流，含有n个元素，若每个数据元素完成算法流程需经历个元素，若每个数据元素完成算法流程需经历L段，而每段平均段，而每段平均时间

10、为时间为，则所需的运算时间为，则所需的运算时间为TP=n*L*其中其中L是并行算法流程经历的运算段数是并行算法流程经历的运算段数.因因L远小于远小于L，故大大提高了速度。，故大大提高了速度。2021/9/1719三三.流水线算法结构流水线算法结构流水线算法结构仅适用于连续输入的数据流。其特点是：把整个流水线算法结构仅适用于连续输入的数据流。其特点是：把整个运算过程分解成若干段，系统在同一时间可对先后输入的数据流元运算过程分解成若干段，系统在同一时间可对先后输入的数据流元素进行不同段的运算。素进行不同段的运算。例如：求例如：求Z=AB+C2021/9/1720在流水线算法结构中，如果待处理数据的

11、连续输入的数据流含有在流水线算法结构中，如果待处理数据的连续输入的数据流含有n个元素，每个数据元素完成算法流程需经历个元素，每个数据元素完成算法流程需经历L段，而每段平均时间段，而每段平均时间为为，则所需的运算时间为，则所需的运算时间为T=L*+(n-1)*流水线算法结构的数据处理效率最高。但它要求流水线算法结构的数据处理效率最高。但它要求:(1)数据流必须连续输入数据流必须连续输入;(2)各处理段的硬件完全独立各处理段的硬件完全独立(不合用不合用);(3)各段的处理时间基本相等。各段的处理时间基本相等。Pentium处理器和最新的处理器和最新的DSP等控制器均采用了流水线结构等控制器均采用了

12、流水线结构,以最以最大限度地提高处理速度大限度地提高处理速度.2021/9/17212.3硬件实现概述硬件实现概述（1）用市售标准的）用市售标准的SSI、MSI和和LSI构成构成,这是最经典的方法。这是最经典的方法。（2）将整个系统配置在一片或数片）将整个系统配置在一片或数片PLD芯片内芯片内,特点是价廉、运特点是价廉、运行速度高、体积小、易于修改设计等。行速度高、体积小、易于修改设计等。（3）研制相应的）研制相应的ASIC，构成单片系统，构成单片系统,在大批量产品中在大批量产品中,应用愈应用愈来愈多。来愈多。（4）以微控制器）以微控制器(嵌入式嵌入式CPU、DSP、单片机等、单片机等为核心、

13、辅以为核心、辅以必要的辅助器件，在软件控制下实现系统功能。特点是价格便宜，必要的辅助器件，在软件控制下实现系统功能。特点是价格便宜，实现方便，适用于处理速度要求不高的场合，也得到广泛应用。实现方便，适用于处理速度要求不高的场合，也得到广泛应用。2021/9/17222.4数据处理单元设计数据处理单元设计一一.器件选择器件选择1、易于控制、易于控制各受控电路的控制方式和控制信号要尽可能简单，从而使产生这各受控电路的控制方式和控制信号要尽可能简单，从而使产生这些控制信号的逻辑也趋简单，以便于实现。些控制信号的逻辑也趋简单，以便于实现。2、满足非逻辑约束的要求、满足非逻辑约束的要求（1）性能因素）性

14、能因素系统性能除了前述的逻辑功能外，还有许多非逻辑因素影响着系系统性能除了前述的逻辑功能外，还有许多非逻辑因素影响着系统的性能。统的性能。a.运行速度运行速度;b.可靠性可靠性(延迟、功耗、电平匹配等延迟、功耗、电平匹配等);c.可测试性。可测试性。2021/9/1723（2）物理因素）物理因素a.器件的温度范围器件的温度范围b.工作电源的电压范围工作电源的电压范围（3）经济因素）经济因素(成本成本)包括设计成本、制造成本、维护成本和运行成本等。包括设计成本、制造成本、维护成本和运行成本等。2021/9/1724二二.设计步骤设计步骤1、组成数据处理单元逻辑框图、组成数据处理单元逻辑框图根据系

15、统算法和结构选择方案，用抽象的逻辑模块组成数据处理根据系统算法和结构选择方案，用抽象的逻辑模块组成数据处理单元逻辑框图。单元逻辑框图。2、构成数据处理单元详细逻辑电路图、构成数据处理单元详细逻辑电路图选择具体型号的集成器件实现第选择具体型号的集成器件实现第1步中的抽象模块，且应力求器件步中的抽象模块，且应力求器件数少，由此得出数据处理单元详细逻辑电路图。明确它们和控制器数少，由此得出数据处理单元详细逻辑电路图。明确它们和控制器之间交换信息的全部特征，包括信号名称、有效作用电平或有效作之间交换信息的全部特征，包括信号名称、有效作用电平或有效作用沿等。用沿等。3、确定控制信号时序、确定控制信号时序

16、在明确各控制信号的基础上，对它们进行排序，列出控制信号排在明确各控制信号的基础上，对它们进行排序，列出控制信号排序表，从而归纳并确定控制信号时序，作为对控制单元设计的技术序表，从而归纳并确定控制信号时序，作为对控制单元设计的技术要求，使系统正确执行算法流程。要求，使系统正确执行算法流程。2021/9/1725三三.设计举例设计举例例例2-8:按照本章例按照本章例2-6所设计的倒数所设计的倒数变换器算法流程图，设计其数据处变换器算法流程图，设计其数据处理单元。理单元。2021/9/1726为实现倒数变换器各子运算，需要为实现倒数变换器各子运算，需要5个存储器，且应分别由相应的个存储器，且应分别由

17、相应的控制信号管理，它们是：控制信号管理，它们是：a.A（16bit），存储待变换数据），存储待变换数据ARG,实现实现AARG。b.E（16bit），存储规定误差数据），存储规定误差数据ERR，实现，实现EERR/2。c.Z（16bit），存储变换结果），存储变换结果Z。实现。实现Z1或或Z（YZ）。）。d.W（16bit），存放运算的中间结果（），存放运算的中间结果（AZ），实现），实现W（AZ）。）。e.Y（16bit），存放中间结果（），存放中间结果（2-AZ）数据，实现）数据，实现Y（2-AZ）。）。第一步第一步导出数据处理单元的逻辑框图导出数据处理单元的逻辑框图（1）存储器的选择。

18、存储器是用以存储待处理的数据、中间结果、）存储器的选择。存储器是用以存储待处理的数据、中间结果、输出数据以及条件反馈信息等。输出数据以及条件反馈信息等。2021/9/1727(2)运算器的选择运算器的选择倒数变换器算法流程图中，包括三种子运算：乘法运算、减法运倒数变换器算法流程图中，包括三种子运算：乘法运算、减法运算和比较运算。为此，运算器和相应的控制信号作如下选择和规定：算和比较运算。为此，运算器和相应的控制信号作如下选择和规定：a.乘法器乘法器MUL。b.减法器减法器SUB1。c.减法器减法器SUB2。d.比较器比较器COMP。由此，可得数据处理单元的逻辑框图由此，可得数据处理单元的逻辑框

19、图.2021/9/17282021/9/1729第二步第二步导出数据处理单元的逻辑电路图。导出数据处理单元的逻辑电路图。根据上述逻辑框图，选择实现数据处理单元各模块的具体器件根据上述逻辑框图，选择实现数据处理单元各模块的具体器件,即即得数据处理单元的逻辑电路图得数据处理单元的逻辑电路图.2021/9/17302021/9/17312021/9/1732第三步第三步确定控制信号的时序确定控制信号的时序在画出数据处理单元逻辑电路图的基础上，列出数据处理单元所在画出数据处理单元逻辑电路图的基础上，列出数据处理单元所需的控制信号的时序表需的控制信号的时序表.2021/9/1733例例2-9:试设计四位

20、乘法器的数据处理单元试设计四位乘法器的数据处理单元.需需3个个寄寄存存器器RA,RB和和RP分分别别存存放放被被乘乘数数A、乘乘数数B和和乘乘积积（部部分分积积P。需要需要1个计数器记录循环次数。个计数器记录循环次数。需要需要1个四位个四位并行加法器。并行加法器。部部分分积积P的的移移位位可可通通过过移移位位寄寄存存器实现。器实现。B1B4的的检检测测也也可可以以采采用用移移位位寄寄存存器器将将4位位并并行行数数据据逐逐位位串串行行移移出出检检查。查。2021/9/1734乘法器数据处理单元的逻辑框图乘法器数据处理单元的逻辑框图2021/9/1735乘法器数据处理单元的逻辑电路图2021/9/

21、1736数据处理单元所需的控制信号及其时序数据处理单元所需的控制信号及其时序步骤步骤操作操作控制信号控制信号1WaitEND=12i0，P0输入输入A,BCR=0CA=CB1=CB0=13ii+1PP+ACC=1CM1=CM0=14右移右移PCM0=CB0=12021/9/1737数据处理单元所需的控制信号及其时序数据处理单元所需的控制信号及其时序步骤步骤操作操作控制信号控制信号1WaitEND=12i0，P0输入输入A,BCR=0CA=CB1=CB0=13ii+1PP+ACC=1CM1=CM0=14右移右移PCM0=CB0=12021/9/17382.5控制单元的设计控制单元的设计一一.系统

22、控制方式系统控制方式系统控制的实质是控制系统中的数据处理单元以预定的时序进行系统控制的实质是控制系统中的数据处理单元以预定的时序进行工作。工作。控制方式有三种类型：集中控制、分散控制和半集中控制控制方式有三种类型：集中控制、分散控制和半集中控制.集中控制方式经常有一个同步时钟信集中控制方式经常有一个同步时钟信号号CP。子运算的执行时间可能只需一。子运算的执行时间可能只需一个时钟信号的周期，也可能需要若干个个时钟信号的周期，也可能需要若干个时钟周期；在某些情况下，子运算执行时钟周期；在某些情况下，子运算执行时间并不固定，而由数据状态来决定。时间并不固定，而由数据状态来决定。1、集中控制、集中控制

23、数字系统中，如果仅有一个控制器，由它控制整个算法的执行，数字系统中，如果仅有一个控制器，由它控制整个算法的执行，则称为集中控制型则称为集中控制型.2021/9/17392、分散控制、分散控制系统中没有统一的控制器，全部控制功能分散在各个子运算器中系统中没有统一的控制器，全部控制功能分散在各个子运算器中完成，称作分散控制型。完成，称作分散控制型。分散控制的时序可以是同步的，也可以是异步的。前者与集中控分散控制的时序可以是同步的，也可以是异步的。前者与集中控制类似，但各子运算器间需交换有关运算进程的信息。制类似，但各子运算器间需交换有关运算进程的信息。分散控制为异步时序时，没有统一的时钟信号，执行

24、顺序由子运分散控制为异步时序时，没有统一的时钟信号，执行顺序由子运算器产生的进程信号控制。算器产生的进程信号控制。2021/9/17403、半集中控制、半集中控制系统中配有系统控制器，但对各子运算器又在各自的控制器控制系统中配有系统控制器，但对各子运算器又在各自的控制器控制下进行工作。系统控制器集中控制各子运算之间总的执行顺序。称下进行工作。系统控制器集中控制各子运算之间总的执行顺序。称为半集中控制型或集散型控制器为半集中控制型或集散型控制器.2021/9/1741二二.控制器的基本结构和信号同步控制器的基本结构和信号同步1、控制器的基本结构、控制器的基本结构控制器的输入信号有：外界对系统的输

25、入（即外输入信号）和数控制器的输入信号有：外界对系统的输入（即外输入信号）和数据处理单元所产生的条件反馈信息。控制器的输出信号有对数据处据处理单元所产生的条件反馈信息。控制器的输出信号有对数据处理单元的控制信号和对外界的输出。理单元的控制信号和对外界的输出。控制器实际上就是一个同步时序电路控制器实际上就是一个同步时序电路(有限状态机有限状态机).2021/9/17422、异步输入信号的同步、异步输入信号的同步信号同步是指控制器与外部输入信号和来自数据处理单元的反馈信号同步是指控制器与外部输入信号和来自数据处理单元的反馈信号之间的同步问题，即异步输入信号的同步化信号之间的同步问题，即异步输入信号

26、的同步化.2021/9/17432021/9/17442021/9/17452021/9/17462021/9/17472021/9/17482021/9/17492021/9/1750三三.算法状态机图算法状态机图(ASM图图)算法流程图，并未严格规定各操作的时间及操作之间的时序关系。算法流程图，并未严格规定各操作的时间及操作之间的时序关系。采用同步时序结构的控制器，在时钟脉冲的驱动下完成各种操作，采用同步时序结构的控制器，在时钟脉冲的驱动下完成各种操作，为此应该对各操作之间的时间关系作出严格的描述。为此应该对各操作之间的时间关系作出严格的描述。算法状态机图算法状态机图(Algorithmi

27、cStateMachineChart，ASM图图)便是一便是一种描述时钟驱动的控制器工作流程的方法。种描述时钟驱动的控制器工作流程的方法。1.ASM图的基本符号图的基本符号(1)状态块状态块对应控制器的一个对应控制器的一个工作状态工作状态,与算法流与算法流程图中工作块的区程图中工作块的区别在于别在于,必须标明需必须标明需要产生的输出控制要产生的输出控制信号信号2021/9/1751(2)判别块判别块对应某个输入条件的判断对应某个输入条件的判断,与算法流程图中判别块的区别与算法流程图中判别块的区别在于在于,必须标明需要判别的输入信号必须标明需要判别的输入信号.(3)条件输出块条件输出块条条件件输

28、输出出块块不不是是一一个个独独立立的的状状态态,其其中中的的输输出出信信号号除除了了与与它它之之前前判判别别块块中中的的输输入入条条件件有有关关外外,还还与与判判别别块块之之前前的的状状态态块块有有关关。因因此此它它相相当当于于米米里里型型输输出出，而而状状态态块块中中的的输输出出相相当当于于莫莫尔型输出。尔型输出。2021/9/17522。由算法流程图导出由算法流程图导出ASM图图算法流程图与算法流程图与ASM图之间存在明确的对应关系。图之间存在明确的对应关系。2021/9/1753例例2-10：根据前述四位乘法器的算法流程图和数据处理单元导出其根据前述四位乘法器的算法流程图和数据处理单元导

29、出其控制器的控制器的ASM图图.步骤步骤操作操作控制信号控制信号1WaitEND=12i0，P0输入输入A,BCR=0CA=CB1=CB0=13ii+1PP+ACC=1CM1=CM0=14右移右移PCM0=CB0=12021/9/1754算法流程图算法流程图ASM图图2021/9/1755算法流程图算法流程图ASM图图2021/9/1756ASM图图算法流程图算法流程图2021/9/1757ASM图图算法流程图算法流程图2021/9/1758四四.基于基于ASM图的控制器设计图的控制器设计一般无需状态化简一般无需状态化简,直接选择核心时直接选择核心时序器件序器件,状态分配状态分配(编码编码),

30、推导激励函推导激励函数和输出函数数和输出函数,从而得出控制器的逻从而得出控制器的逻辑电路辑电路.例例2-11：根据上例的根据上例的ASM图图,以以D触发器为记忆元件触发器为记忆元件,设计四位乘法设计四位乘法器的控制单元器的控制单元.(1)状态分配状态分配共共4个状态，故仅需个状态，故仅需2个触发器。令个触发器。令ASM图图2021/9/1759(2)推导激励函数推导激励函数000110112021/9/176000011011(2)推导激励函数推导激励函数2021/9/176100011011(2)推导激励函数推导激励函数2021/9/176200011011(2)推导激励函数推导激励函数20

31、21/9/176300011011(2)推导激励函数推导激励函数2021/9/1764(3)推导输出方程推导输出方程END=Q1Q0CR=Q1Q0CA=CB1=Q1Q0CB0=Q1Q0+Q1Q0=Q0CC=Q1Q0CM1=Q1Q0BiCM0=Q1Q0Bi+Q1Q02021/9/1765(4)画逻辑电路图画逻辑电路图2021/9/1766例例2-12：根据乘法器的根据乘法器的ASM图图,以多以多D触发器为核心触发器为核心,采用采用“一对一一对一”的状态分配方法的状态分配方法,设计四位乘法器的控制单元设计四位乘法器的控制单元.(1)状态分配状态分配共共4个状态，故需个状态，故需4个触发器个触发器令

32、令:S0Q0(0000)，S1Q1(1100)，S2Q2(1010)，S3Q3(1001)2021/9/1767(2)列出列出ASM图的次态表图的次态表次次态态现态现态输输入入S0S0STARTS3i=4S1S0STARTS2S1S3i=4S3S22021/9/1768(3)推导激励方程推导激励方程D0=Q0START+Q3(i=4)D1=Q0STARTD2=Q1+Q3i=4D3=Q2次次态态现态现态输输入入S0S0STARTS3i=4S1S0STARTS2S1S3i=4S3S22021/9/1769(4)推导输出方程推导输出方程END=Q0CR=Q1CA=CB1=Q1CB0=Q1+Q3CC=Q2CM1=Q2BiCM1=Q2Bi+Q32021/9/1770(5)画出逻辑电路图画出逻辑电路图2021/9/1771