基于FPGA数字信号处理.doc

本科生毕业设计（论文）摘 要随着电子技术和集成电路技术的飞速发展，数字信号处理已广泛应用于语音、图像处理，通信和多媒体等领域中。傅立叶变换（DFT）作为其数字信号处理中的基本运算，发挥着重要作用。特别是快速傅立叶变换（FFT）算法的提出，减少了当N很大的时候DFT的运算量，使得数字信号处理的实现和应用变得更加容易，因此对FFT算法及其实现方法的研究具有很强的理论和现实意义，且实际价值不可估量。本文主要探讨了基于FPGA数字信号处理的实现。首先详细阐述了数字信号处理的理论基础，重点讨论了傅立叶变换算法原理，由于快速傅立叶变换算法在实际中得到了广泛的应用，本文给出了基-2 FFT原理、讨论了按时间抽取FFT算法的特点。本论文对硬件描述语言的描述方法和风格做了一定的探讨，介绍了硬件描述语言的开发环境MAX+PLUSII。在此基础上，本论文详细阐述了数字集成系统的高层次设计方法，讨论了数字系统设计层次的划分和数字系统的自顶向下的设计方法，探讨了数字集成系统的系统级设计和寄存器传输级设计，描述了数字集成系统的高层次综合方法。最后本文描述了数字信号处理系统结构的实现方法，指出常见的高速、实时信号处理系统的四种结构：由于FFT算法在数字信号处理中占有重要的地位，所以本文提出了用FPGA实现FFT的一种设计思想，给出了总体实现框图:重点设计实现了FFT算法中的蝶形处理单元，采用了一种高效乘法器算法设计实现了蝶形处理单元中的旋转因子乘法器，从而提高了蝶形处理器的运算速度，降低了运算复杂度。关键词：数字信号处理；VHDL语言；FPGA；FFT算法AbstractWith the rapid development of electronic and integrate circuit technology,digital signal processing has been widely applied in various field, like speechingand graphing processing, communication, multimedia. DFT plays an important part in digital signal processing as a basic calculation. Especially, FFT algorithmreduces the calculation quantity when N is a little great, which makes it much easier for implement and application. It is strongly theory and real signification to research on the FFT algorithm and its method for design and its value cannot be computed.The paper mainly probes into the realization of digital signal processing based on FPGA.At first the fundamental theory of digital signal processing and the DFT algorithm are expounds, then radix-2 FFT and the characteristic of DIT FFT are discussed.In this paper,the description method and style of hardware description language and its development environment MAX+PLUSII are detailed. On the basis of that,the high level design method of integrated digital system and the partition of disign level of digital system are discussed, the top-down design strategy and the high level synthesis method of digital system are also detailed. After doing that, the paper points out the universal architectures of the high-speed real-time signal processing system and describes how to implement them. Since FFT plays an important role in digital signal processing, implementing FFT with FPGA is presented and the total realization graph is designed. For improving speed and decreasing computing complexity, high efficiency multiplier algorithm is used to realizing twiddle factor multiplier of butterfly processing unit.Key words：Digital Signal Processing;VHDL;FPGA;FFT Algorithm目 录第1章 绪 论11.1 数字信号处理概述11.2 FPGA简介21.3 FFT算法的发展31.4 用FPGA实现数字信号处理的特点41.5 本文的主要工作5第2章 数字信号处理的理论基础72.1 离散傅立叶变换72.1.1 傅立叶变换的几种形式72.1.2 离散傅立叶变换算法82.2 快速傅立叶变换92.2.1 FFT算法基本思想92.2.2 按时间抽取基-2FFT算法102.2.3 按时间抽取FFT算法的特点11第3章 硬件描述语言及MAX+PLUS平台143.1 硬件描述语言（HDL）143.1.1 HDL概述143.1.2 HDL设计方法143.2 VHDL语言163.2.1 VHDL语言简介163.2.2 VHDL的优点163.2.3 VHDL设计特点173.2.4 VHDL基本设计流程183.2.5 VHDL设计单元模型183.2.6 VHDL语言中顺序执行语句和并行执行语句223.3 VHDL语言开发环境MAX+PLUS介绍24第4章 用FPGA实现数字信号处理算法264.1 数字信号处理的系统结构的实现方法264.2 基于FPGA的FFT算法实现284.2.1 FFT处理器的实现框图284.2.2 复数乘法器的实现294.2.3 蝶形运算单元的实现314.2.4 数据存储单元RAM的实现324.2.5 旋转因子存储器ROM的实现334.2.6 控制单元的设计344.3 小结34第5章 结 论35参考文献37致 谢39附录40IV第1章 绪 论1.1 数字信号处理概述数字信号处理是利用计算机或专专用处理设备，以数字形式对信号进行采集、变换、滤波、估值、增强、压缩、识别等处理，以得到符合需要的信号形式。数字信号处理技术的实质就是将模拟信号或我们现实生活中的一些信号转化为数字信号并对转换后的数字信号进行相应的处理。字信号处理是从20世纪60年代以来，随着信息科学和计算机学科的高速发展而迅速发展起来的一门新兴学科。70年代以来，随着电子计算机、大规模集成电路、超大规模集成电路以及微处理器技术的迅猛发展，数字信号处理得到了飞速的发展，它的重要性日益在各个领域的应用中表现出来。图1.1给出了数字信号处理系统的简化框图。此系统先将模拟信号变换为数字信号，经数字信号处理后，再变换成模拟信号输出。其中抗混叠滤波器的作用，是将输入信号中高于折叠频率（其值等于采样频率的一半）的分量滤除，以防信号频谱的混叠。随后，信号经采样和A/D变换后，变成数字信号。数字信号处理器对进行处理，得到输出数字信号，经D/A变换器转换成模拟信号，此信号经低通滤波器，滤除不需要的高频分量，最后输出平滑的模拟信号。抗混叠滤波器A/D变换器数字信号处理器D/A变换器低通滤波器图1.1 数字信号处理系统简化框图数字信号处理与模拟信号处理相比具有如下优点：1.数字信号在处理过程中更加稳定数字信号参数不象模拟信号参数那样容易受电阻、电容、运算放大器或是温度变化的影响。一个数字系统也很少受器件使用时间的影响，所以数字系统要比模拟系统稳定得多。这保证了应用系统的稳定性以及较长的使用寿命。2.数字信号处理系统的可预见性当一个数字信号处理系统设计完成后，我们可以通过仿真或是其它手段直接看到结果，而且这与最终应用中出现的情况是一样的：同时，所有拷贝的数字信号处理系统间是没有性能差别的。3.特殊功能数字信号处理可以完成许多模拟信号处理所达不到的功能，如线性相位响应，还有一些模拟信号不能处理的问题如无损压缩、纠错编码等。4.性和可编程能力数字信号处理具有极强的适应能力，可以在多种领域内应用。同时，数字信号处理的设计也相对简单，并且可以根据不同的应用迅速对设计进行改进或重新设计。5.成本低廉数字信号处理器多通过超大规模集成电路实现，相对使用大量的模拟器件完成同一任务来讲，数字信号处理器的成本是很低的。由于数字信号处理具有以上优点，数字信号处理在现实生活中得到了广泛的应用。目前，数字信号处理技术已广泛应用于数字通信、语音合成、图像处理、多媒体技术、高清晰度电视、数字音响、以及机器人等各个领域。1.2 FPGA简介可编程逻辑阵列器件是可以由用户进行编程以实现所需逻辑功能的数字集成电路，利用其内部的逻辑结构实现任何布尔表达式、寄存器函数。和一般的ASIC电路相比，可编程逻辑阵列器件具有设计周期短，修改方便的优点。现场可编程门阵列FPGA是八十年代中期出现的新型高密度可编程逻辑器件，它是在PAL、GAL、EPLD等可编程器件的基础上进一步发展的产物。通过编程可以立刻把一个通用的FPGA芯片配置成用户需要的硬件数字电路，因而大大加快电子产品的研发周期，降低研发成本，缩短产品上市时间。FPGA具有高密度（一个器件内部可用逻辑门可达数万门），运行速度快（管脚间的延时小，仅几个）的特点。用它来设计数字电路可以简化系统设计，缩小数据规模，提高系统的稳定性。ALTERA公司的FPGA器件FLEX 10K 器件内含随机静态存储器，方便数据的暂时存储。FPGA兼有串、并行工作方式和高集成度、高速、高可靠性等明显的特点，其时钟延迟可达纳秒级，同时，在基于芯片的设计中可以减少芯片数量，缩小系统体积，降低能源消耗，提高系统的性能指标和可靠性。正是由于FPGA具有这些优点，FPGA在超高速应用领域和实时测控方面有非常广阔的应用前景。在高可靠应用领域，如果设计得当，将不会存在类似于MCU的复位不可靠和PC可能跑飞等问题。FPGA的高可靠性还表现在，几乎可将整个系统下载于同一芯片中，实现所谓片上系统，从而大大缩小了体积。与AMU设计相比，FPGA显著的优势是开发周期短，投资风险小、产品上市速度快，市场适应能力强和硬件升级回旋硕士学位论文余地大，而且当产品定型和产量扩大后，可将在生产中达到充分检验的VHDL设计迅速实现ASIC投产。随着大规模现场可编程逻辑器件的发展，系统设计进入“片上可编程系统”（SOPC）的新纪元；芯片朝着高密度、低压、低功耗方向挺进：在SOC芯片上可以将微处理器、数字信号处理器、存储器、逻辑电路、模拟电路集成在一个芯片上。而如果将可编程逻辑电路IP核集成到SOC芯片上则会大大提高SOC芯片的灵活性与有效性，并且缩短了SOC芯片的设计周期。因此国际各大公司都在积极扩充其IP库，以优化的资源更好的满足用户的需求，扩大市场。由此可见，FPGA不仅可以解决电子系统小型化、低功耗、高可靠性等问题，而且其开发周期短、开发软件投入少、芯片价格不断降低，这使得FPGA占有越来越多的市场，特别是对小批量、多品种的产品需求，使FPGA成为首选。FPGA普及的另一重要原因是IP（知识产权）越来越被高度重视，带有IP内核的功能块在ASIC设计平台上的应用日益广泛。越来越多的设计人员，采用设计重用，将系统设计模块化，为设计带来了快捷和方便。并可以使每个设计人员充分利用软件代码，提高开发效率，减少上市时间，降低研发费用，缩短研发周期，降低风险。1.3 FFT算法的发展DFT在信号的频谱分析、系统分析、设计和实现中得到了广泛的应用，原因之一就是计算DFT有很多的快速算法，从快速计算DFT的理论观点看，这些快速计算DFT的方法大概可以分为两类。一类是递归型算法，是将一维DFT转化为容易计算的二维或多维DFT,其代表算法Cooley-Tukey算法，Rader-Brenner算法等。例如，分裂基算法、基2、基4、基8、基16及任意组合因子等的组合数FFT算法，利用的周期性和对称性，使长序列的DFT分解为更小点数的DFT，从而大大减少了运算工作量，共同特点是每两级DFF之间需要乘以旋转因子。另一类是将DFT转变为卷积，利用计算卷积的方法计算，其代表是Winograd傅立叶变换算法（WFTA）和素因子（FPA）。这种算法是根据Good-Thomas提出的索引变换，将一个长度的DFT变换成“实际的”二维DFT，也就是说没有Cooley-Tukey中的旋转因子。只要索引映射计算是在线进行的，而且没有预先计算好的表可以使用，那么索引映射就会变得更加复杂。目前，FFT已广泛应用在无线通信、语音识别、图像处理和频谱分析等领域。在不同应用场合，需要不同性能要求的FFT处理器，特别是随着OFDM（正交频分复用）技术的出现，FFT作为OFDM系统中调制解调的关键，如何更快速、更灵活地实现FFT变得越来越重要。到现在为止，FFI的理论研究已经趋于成熟，但是随着通讯技术的飞速发展，很多场合需要快速、高性能的FFT处理器，且随着大容量、高速芯片的出现，自己研发高性能的FFT处理器成为可能，速度可以大大的提高，因此很多人在自己研究的课题领域，对它进行了大量的研究，通过选用不同的硬件，在综合考虑硬件特性和满足系统的前提下，对FFI处理器的流程、算法进行进一步的优化处理，使它的处理速度能有所提高。1.4 用FPGA实现数字信号处理的特点早期的FPGA设计大都是使用FPGA供应商提供的设计软件工具，进行门级设计。而本文的一个特点是首先采用VHDL语言进行电路描述，然后使用高层次的EDA综合工具进行综合，最后使用FPGA供应商提供的布局布线工具进行布局布线。要求在系统设计、综合技巧等方面就要考虑FPGA的特点。在代码设计时，遵从VHDL描述一系统仿真一系统综合一FPGA实现这一高层次设计方法来完成系统的设计与实现。FPGA实现数字信号处理最显著的特点就是高速性能好。以软件方式控制操作和运算的系统速度显然无法与纯硬件系统相比，因为软件是通过顺序执行指令的方式来完成控制和运算步骤的，而用HDL语言描述的系统是以并行方式工作的。以对A/D进行数据采样控制为例，采样周期包括对A/D工作时序的控制和将每一次获得的数据存入RAM（或FIFO）中。工作于12MHz晶振频率的MCS-51系列单片机对A/D控制的采样频率为20KHz上下，即约每秒两万次。但若用FPGA中设计的状态机来完成同样的工作，如对于具有流水线采样工作时序的A/D来说，只需两个状态即可完成一次采样，状态间转换的时间仅为一个时钟周期，而如果FPGA的工作频率是100MHz，则采样频率可达50MHz。这在算法方面同样具有巨大的优势。这里以数字滤波器的设计为例作一比较：表1.1FPGA和DSP芯片实现FIR滤波器的速度对比FIR滤波器阶数FPGA的处理速度（单位：MSPS）DPS芯片的指令执行速度（单位：MIPS）8104832161011616241032472321053360从表1.1可以看出，用FPGA实现32阶8位FIR滤波器的处理速度为105MSPS时，用DSP芯片实现的滤波器要达到相当速度，则需要指令执行速度为3360MIPS。然而目前还没有如此高速的单处理器的DSP芯片。由此可见，在一些DSP芯片不能满足数字信号处理要求的场合，可以采用FPGA来完成数字信号处理。综上所述，与ASIC和通用DSP相比，FPGA器件能够以高速、实时、低成本、高灵活性的优点应用于数字信号处理领域，利用FPGA实现数字信号处理成为数字信号处理领域的一种新的趋势，它可以完全取代通用DSP芯片或作为通用DSP芯片的协处理器进行工作。如果将通用处理器和FPGA融合在一起，把需要多个时钟周期的运算交给FPGA完成，DSP芯片主要完成单时钟的运算和控制FPGA的“可再配置计算”功能，会更好地将两者的优势发挥出来。1.5 本文的主要工作在广泛阅读文献资料的基础上，分析了基2FFT，算法的原理与特性。对FFT算法实现的方式和结构进行了深入的研究，特别对FFT，处理过程中数据的通信进行了研究和分析.整个设计采用了先进的结构化设计思想，针对基-2算法，设计了一种FFT实现方法，主要内容如下：第一章 绪论部分，概要地叙述了数字信号处理的定义以及数字信号处理系统的简化框图，指出了数字信号处理的几种常用方案，简要地介绍了FPGA，就FPGA实现数字信号处理的特点进行了描述。第二章 就数字信号处理的理论基础进行了探讨，首先介绍了傅立叶变换的几种形式，重点探讨了离散傅立叶变换算法原理。由于快速傅立叶变换算法在实际中得到了广泛的应用，本章描述了快速傅立叶变换算法基本思想，给出了按时间抽取基-2 FFT算法实现原理。最后讨论了按时间抽取FFT算法的特点。 第三章 首先介绍了硬件描述语言及其设计方法，其次介绍硬件描述语言中的VHDL语言及其设计优点、设计特点及组成，最后介绍了硬件描述语言的开发环境MAX+PLUSII。第四章 本文提出了用FPGA实现数字信号处理的一种设计思想，首先就数字信号处理系统结构的实现方法进行了描述，指出常见的高速、实时信号处理系统的四种结构，给出了总体实现框图，重点设计实现了FFT算法中的蝶形处理单元，采用了一种高效乘法器算法设计实现了蝶形处理单元中的旋转因子乘法器。第2章 数字信号处理的理论基础2.1 离散傅立叶变换2.1.1 傅立叶变换的几种形式傅立叶变换是信号分析和处理的有力工具，在以快速傅立叶变换算法为代表的一系列有效算法出现后，傅立叶变换不但在信号处理领域起着支柱作用，而且在其它工程领域也获得了广泛的应用。根据信号的连续性、离散性、周期性、非周期性，傅立叶变换可以分为四种不同的形式，形成四种不同的傅立叶变换对，以下分别予以描述。一连续时间非周期信号连续时间非周期信号在频域中得到的是连续非周期的频谱密度函数，傅立叶变换对如下： （2-1） （2-2）这种类型信号的典型信号有指数衰减信号和高斯信号，这种类型信号的变换就称为傅立叶变换。二连续时间周期信号 连续时间周期信号当满足狄里赫利条件时在频域中得到的是离散非周期的傅立叶级数，傅立叶级数的系数为，为离散非周期函数，和组成的变换对如下： （2-3） （2-4）这种类型信号的典型信号有正弦信号和周期方波信号，这种类型信号的傅立叶变换就称为傅立叶级数。三离散时间非周期信号离散时间非周期信号也称为序列，序列的傅立叶变换对如下所示： （2-5） （2-6）这种信号的傅立叶变换称为离散时间傅立叶变换 四离散时间周期信号离散时间周期信号的傅立叶变换有时称为傅立叶级数，但最常被称为离散傅立叶变换。2.1.2 离散傅立叶变换算法上面讨论的四种傅立叶变换对前三种由于至少在时域或频域是离散的，都不适于在计算机上运行。然而、现实世界中的声音图像等各种信号大都为模拟信号，要用计算机对这些信号进行数字信号处理，这些信号必须通过采样量化编码变成有限长的数字信号序列。对于有限长序列，可以得出另外一种傅立叶表示，称为离散傅立叶变换(DFT)。离散傅立叶变换本身是一个序列，而不是一个连续变量的函数，它相应于对信号的傅立叶变换进行频率的等间隔取样的样本。因为存在着计算DFT的高效算法，作为序列的傅立叶表示，DFT除了在理论上十分重要外，在实现各种数字信号处理算法中还起着核心作用。离散傅里叶变换描述分析有限长序列，其本质是建立了以时间为自变量的信号与以频率为自变量的频谱函数之间的变换关系，换言之，离散傅里叶变换定义了时域与频域之间的一种变换或者说是映射。对于DFT时间和频率变量都取离散值。下面讨论一下有限长序列的离散傅立叶变换。对于一个长度为的有限长序列，亦即只在到个点上为非零值，其余皆为零，我们可以把它看成周期为的周期序列中的一个周期即当， 当为其它值， 。 其中 （2-7）从而有限长序列的傅立叶变换定义为正变换： （2-8）反变换： （2-9）其中，由此可见，离散傅立叶变换开辟了频域离散化的道路，使数字信号处理也可以在频域上采用数字运算方法进行，它可以作为一种数学工具来描述离散信号的时域和频域表示的关系，大大增加了数字信号处理的灵活性，特别是它的多种快速算法，使信号的实时处理和设备的简化得以实现，所以离散傅立叶变换不仅在理论上有重要意义，而且在各种数字信号处理中起着核心的作用。2.2 快速傅立叶变换对于式（2.8）DFT的直接计算法。若为复数的话，则计算DFT每一个值就需要次复数乘法和次复数加法。因此计算全部的个值总共需要次复数乘法和次复数加法。而每一个复数乘法需要4次实数乘法和2次实数加法。所以，对于每一个值，直接计算就需要4次实数乘法和次实数加法。除了这些运算量外，通用计算机或专用硬件来做DFT数字计算还需要存储和读取个复数输入序列值以及复系数值的设备。由于计算的总次数以及所需的时间大致上正比于，显然当值很大时直接计算DFT所需要的算术运算的次数就非常大。可见，离散傅里叶变换算法实现了频域离散化，在数字信号处理中起着极其重要的作用，它可以直接用来分析信号的频谱、计算滤波器频率响应、以及实现信号通过线性系统的卷积运算。但对于点DFT运算总共需要4次实数乘法和次实数加法，这样庞大的运算量使得DFT的实际应用特别是实时处理难以实现，直到1965年库利和图基首次提出了计算DFT的一种快速算法，人们开始认识到DFT运算的一些内在规律，发展和完善了一套高效的运算方法，DFT的运算在实际中才得到广泛的应用。继CooleyTukey算法以后，SandeTukey等快速算法相继出现，很快形成了一套高效运算方法，这就是现在的通用快速傅里叶变换，简称为FFT。这种方法使复数乘法的次数从次减少到了次。如时运算量从1048576次减少到5120次，运算效率提高了204.8倍，为DFT乃至数字信号处理技术的实际应用特别是实时处理创造了良好的条件，大大地推动了数字信号处理技术的发展。所以实际工程中用到的都是DFT的快速算法：快速傅里叶变换（FFT）。2.2.1 FFT算法基本思想FFT算法的基本思想：可以将一个长度为的序列的离散傅里叶变换逐次分解为较短的离散傅里叶变换来计算，这些短序列的DFT可重新组合成原序列的DFT，而总的运算次数却比直接的DFT运算少得多，从而达到提高速度的目的。快速傅立叶变换就是利用的特性，逐步地将点序列分解成较短的序列，计算短序列的DFT，然后组合成原序列的DFT，使运算量显著减少。这种分解基本上可分为两类，一类是将时间序列进行逐次分解，称为按时间抽取算法（Decimation In Time）；另一类将傅立叶变换序列进行分解，称为按频率抽取算法（Decimation In Frenquency）。本文主要介绍T按时间抽取基-2FFT算法。2.2.2 按时间抽取基-2FFT算法我们已经知道FFT算法主要是利用的性质，通过把序列逐渐分解为短序列实现运算量的减少。的以下三种性质在FFT运算中得到了应用：性质1：的周期性 性质2：的对称性 性质3：的可约性 ， 由于目前FFT比较普遍使用的算法还是基二算法，本节将讨论基二的按时间抽取算法。基二算法中，序列的长度为2的整数次幂，即，其中为正整数。最初通过将分解为奇数项序列和偶数项序列的形式使FFT运算分为两组。设： （2.10）设为的DFT，为的DFT，利用的性质可得的DFT运算为： （2-11）上面式子的运算可用下图的蝶形信号流图符号表示：图2.1 时间抽取算法蝶形运算图由此可见，一个N点DFT分解为两个点的DFT，从而实现了运算量的减少，再经过逐次分解最终分解为2点的DFT，实现了FFT运算。FFT运算的核心是蝶形运算。通过顺序计算全部蝶形实现FFT算法的实现。下面给出时的按时间抽取FFT流图。图2.2 的时间抽取FFT算法流图对于序列的长度的FFT，共有级蝶形，每级由个蝶形运算组成，每个蝶形包括一次复乘、二次复加，则级运算的运算量为复数乘法：复数加法：由此可见，FFT算法与直接DFT算法相比运算量大为减少，如时，DFT所需的复数乘法运算次数为：次，而FFT所需的复数乘法运算次数仅为次。可见时DFT算法的运算量是FFT算法的运算量的倍。从而可以看出FFT算法的优越性，且当点数N越大越能突出FFT算法的优越性。2.2.3 按时间抽取FFT算法的特点图2.2所示流图描述了计算离散傅里叶变换的一种算法。在图2.2中特别重要的是连接节点的支路和每个支路的传输比。只要节点间的连结和连结的传输比维持不变，则无论在流图中的诸节点如何重新排列，它始终表示相同的计算。由图2.2可以推知按时间抽取算法在运算方式上的特点，主要有以下两种特点：同址运算，倒位序规律。以下分别介绍这两种特点。特点1：同址运算由图2.2看出，对于长度为的序列，每一级计算均需要一组个复数，并通过图2.1形式的基本蝶形把它们变换为下一组的个复数，这种过程重复次，最后得到所要求的离散傅立叶变换。当实现图2.2中描述的运算时，我们可以想象使用两列（复数的）存贮寄存器，一列存贮要计算的数，另一列存贮计算中要用到的数据。例如，当计算图2.2中的第一列时，第一组存贮寄存器应当存放输入数据，而第二组存贮寄存器应当存放第一级计算出的结果。把第级计算得出的复数序列记作，其中，把从第级输入的复数序列记作。对于第级计算，可以认为是输入列，是输出列。这样，对于图2.2中所示的的情况，有 （2-12）利用这种表示法，可将图2.1中蝶形计算的输入和输出标记为图2.3所示的那样，并有相应的方程 （2-13 a） （2-13 b） 图2.3 式（2.11）的流图在式(2.11)中，和从一级到另一级是不同的，从图2.2和图2.3中可以清楚地看出，要计算第m列的和位置上的复数节点值，只需要第(m-1)列在和位置上的复数节点值。因此，若将和分别存放在原存放和的同一存贮寄存器中，则实现全部计算实际上只需要一列存贮个复数的寄存器。这种计算通常称为同址计算。由此可见，采用同址运算只需个存储单元，大大节省了存储单元，从而降低了设计成本。特点2：倒位序规律为了实现同址计算，输入序列不能按照原来的先后顺序存贮（或至少不能这样读取），而应如图2.2的流图那样，实际上，这种输入数据存贮和读取的顺序称为倒位序。我们注意到，对于已经讨论过的8点流图，只需要用三位二进制码来标注整个数据。如果用二进制形式写出式（2.10）中的标号，就得到如下一组式子： （2.14）若为序列中标号的二进制表示，则序列值存放在数列的位置上。也就是说，要确定在输入序列中的位置，我们必须将标号的位序颠倒。表 2.1给出了时的自然顺序二进制数以及相应的倒位序二进制数。表2.1码位的倒位序自然系数二进制码倒位序二进制码倒位序数0000000010011004201001023011110641000011510110156110011371111117实际运算中，总是先按自然顺序将输入序列存入存储单元，要实现FFT算法，首先将按自然顺序存放的序列经变址运算变换得到倒位序的排列。第3章 硬件描述语言及MAX+PLUS平台3.1 硬件描述语言（HDL）3.1.1 HDL概述硬件描述语言（HDL）是相对于一般的计算机软件语言如C，PASCAL而言的。硬件描述语言HDL是一种用形式化方法描述数字电路和系统的语言，它描述电子系统的逻辑功能、电路结构和连接方式。利用这种语言，数字电路系统的设计可以从上层到下层（从抽象到具体）逐层描述自己的设计思想，用一系列分层次的模块来表示极其复杂的数字系统。然后，利用电子设计自动化（EDA）工具，逐层进行仿真验证，再把其中需要变为实际电路的模块组合，经过自动综合工具转换到门级电路网表。接下去，再用专用集成电路ASIC或现场可编程门阵列FPGA自动布局布线工具，把网表转换为要实现的具体电路布线结构。硬件描述语言具有以下几个优点：（1）设计技术齐全，方法灵活；（2）加快了硬件电路的设计周期，降低了硬件电路的设计难度；（3）采用系统早期仿真，在系统设计早期就可发现并排除存在的问题；（4）语言设计可与工艺技术无关；（5）语言标准、规范，易共享和复用。目前，采用硬件描述语言进行数字系统的设计己被广泛采用。据统计，目前在美国硅谷约有90%以上的ASIC和FPGA采用硬件描述语言进行设计。硬件描述语言HDL的发展至今已有20多年的历史，并成功地应用于设计的各个阶段:建模、仿真、验证和综合等。到20世纪80年代，已出现了上百种硬件描述语言，对设计自动化曾起到了极大的促进和推动作用。但是，这些语言一般各自面向特定的设计领域和层次，而且众多的语言使用户无所适从。因此，急需一种面向设计的多领域、多层次并得到普遍认同的标准硬件描述语言。20世纪80年代后期，VHDL和Verilog HDL语言适应了这种趋势的要求，先后成为IEEE标准。就FPGA/CPLD开发而言，VHDL语言是最常用和流行的硬件描述语言之一，在数字信号处理的FPGA设计中得到了广泛的使用。3.1.2 HDL设计方法HDL设计方法基本上包含3方面：（1）设计描述的开发，这种描述必须是有效的；（2）综合，将设计描述转换成优化的门级表示，目前的综合工具只是将输入的寄存器传输级(RTL)的HDL描述转换为门级的网表，再由门级的网表实现互连的门级宏单元结构。因为厂家所支持的各个工艺库中有门级宏单元模块，所以有了门级网表就能按照技术条件进行优化，得到一个优化了的门级结构；（3）对设计加以验证。硬件描述语言RTL级设计的流程框图如图3.1所示，其中的综合部分是HDL设计方法中的关键。RTL VHDL源文件RTL仿真功能仿真转化成门级优化门级仿真工作速度与功能仿真门级结束YNNY综合图3.1 HDL设计方法流程框图HDL综合设计方法优点如下：（1）提高设计效率：设计者不需人工进行门级描述，节省了设计时间；（2）设计是在较高的抽象层次上进行，设计者不用更多地考虑门级，可花费更多的时间考虑概念级方面；（3）利用HDL具有的自动优化和快速探索各种设计方案的能力，可使设计者迅速而成功地得到高质量设计的最终结果，从而改善了设计质量；（4）设计与工艺无关，便于设计的再利用。3.2 VHDL语言3.2.1 VHDL语言简介VHDL的英文全名是Very-High-Speed Integrated Circuit Hardware Description Language（超高速集成电路硬件描述语言)，VHDL语言是美国国防部资助的VHSIC（Very High Speed Integrated Circuit超高速集成电路）项目开发的产品，诞生于1982年。1987年底VHDL被IEEE和美国国防部确认为标准硬件描述语言。自IEEE公布了VHDL的标准版本（IEEE std 1076-1987）之后，各EDA公司相继推出了自己的VHDL设计环境。此后，VHDL在电子设计领域受到了广泛的接受，并逐步取代了原有的非标准HDL。1993年，IEEE对VHDL进行了修订，从更高的抽象层次和系统描述能力上扩展VHDL的内容，公布了新版本的VHDL，即ANSI/IEEE std 1076-1993版本。1996年IEEE 1076.3成为VHDL综合标准。VHDL主要用于描述数字系统的结构、行为、功能和接口，非常适用于可编程逻辑芯片的应用设计。与其它的HDL相比，VHDL具有更强的行为描述能力，从而决定了它成为系统设计领域最佳的硬件描述语言。强大的行为描述能力是避开具体的器件结构，从逻辑行为上描述和设计大规模电子系统的重要保证。就目前流行的EDA工具和VHDL综合器而言，将基于抽象的行为描述风格的VHDL程序综合成为具体的FPGA和CPLD等目标器件的网表文件已不成问题。VHDL语言可以支持自上而下和基于库的设计方法，并支持同步电路、异步电路、FPGA以及其它随机电路的设计。目前大多数EDA工具几乎在不同程度上都支持VHDL语言。这给VHDL语言进一步推广和应用创造了良好的环境。VHDL具有多层次描述系统硬件功能的能力，可以描述系统模型直到门级电路。VHDL语言在硬件设计领域的作用将与C和C+在软件设计领域的作用一样，在大规模数字系统的设计中，它将逐步取代如逻辑状态表和逻辑电路图等级别较低的繁琐的硬件描述方法，而成为主要的硬件描述工具，它将成为数字系统设计领域中所有技术人员必须掌握的一种语言。VHDL和可编程逻辑器件的结合成为一种强有力的设计方式，将为设计者的产品上市带来创记录的速度。3.2.2 VHDL的优点VHDL是一种全方位的硬件描述语言，包括系统行为级、寄存器传输级和逻辑门级多个设计层次，支持结构、数据流和行为三种描述形式的混合描述，因此VHDL几乎覆盖了以往各种硬件描述语言的功能，整个自顶向下或自底向上的电路设计过程都可以用VHDL来完成。VHDL还具有以下优点：（1）VHDL的宽范围描述能力使它成为高层次设计的核心，将设计人员的工作重心提高到了系统功能的实现与调试，而花较少的精力于物理实现。（2）VHDL可以用简洁明确的代码描述来进行复杂控制逻辑的设计，灵活且方便，而且也便于设计结果的交流、保存和重用。（3）VHDL的设计不依赖于特定的器件，方便了工艺的转换。（4）VHDL是一个标准语言，为众多的EDA厂商支持，因此移植性好。VHDL通常由以下几部分组成：（1）实际用的VHDL语言。（2）含有STANDARD包和TEXTIO包的STD库。在STANDARD包内存有一些预定义的数据类型说明和函数；在TEXTIO包内含有支持格式化ASCII I/O操作的数据和子程序的说明。（3）买方专用的库和程序包。（4）用户专用的库和程序包。（5）保存用户设计用的WORK库。3.2.3 VHDL设计特点VHDL语言只所以在电子设计领域应用广泛与它的设计特点是密不可分的。总的来说，VHDL语言具有如下三个设计特点:（1）VHDL描述就是将一个待设计系统的部件和互连关系列成网表，并对该系统设计的行为提供证据。VHDL可在各个抽象层次上进行，如算法级、寄存器传输级、具有单位时间延迟的门级和详细定时的门级等。通常在自顶向下（top-down）的设计方法中，设计者首先对所设计的系统提出比较抽象的概念性描述，而后进入到系统的细节考虑。（2）一个用VHDL语言描述的系统模型，通常要在VHDL仿真器上运行，以验证所模拟系统的行为。对一个VHDL设计模型的仿真，需加激励以提供在仿真过程中观察该模型的手段，得到最终所要检查的仿真结果。这就要求设计者给出测试条件（提供一组功能测试向童）作为输入，用以检验所设计系统的功能。（3）VHDL设计可通过逻辑综合工具产生其物理设计，特别是许多生产销售VLSI门阵芯片的厂家，可将VHDL设计描述转换成门级网表，从而可制造出一个专用的集成电路芯片。由此可见，VHDL的应用可对一个设计提供文档、对所设计系统的行为进行仿真、继而直接进行逻辑综合。总之，VHDL语言不但可用于对一电子系统的行为特征和元件间的互连关系建立文档；也可将一个VHDL设计描述输入到仿真器中，在给定的测试条件下运行，以检验设计的正误；还可将VHDL设计输入到逻辑综合工具中，产生所要设计的电路结构；VHDL也可将设计分成若干个抽象层次加以描述。3.2.4 VHDL基本设计流程用VHDL/Verilog HDL开发CPLD/FPGA的完整流程为：（1）文本编辑：用任何文本编辑器都可以进行，也可以用专用的文本编辑环境。通常VHDL文件保存为.vhd文件，Verilog文件保存为.v文件。（2）功能仿真：将文件调入HDL仿真软件进行功能仿真，检查逻辑功能是否正确（也称为前仿真，对简单的电路可以跳过这一步，只在布线完成后进行时序仿真）。（3）逻辑综合：将源文件调入逻辑综合软件进行综合，即把语言综合成最简的布尔表达式和信号的连接关系。逻辑综合软件会生成.edf的EDA工业标准文件。（4）布局布线：将.edf文件调入PL D厂家提供的软件中进行布线，即把设计好的逻辑安放到CPLD/FPGA内。（5）时序仿真：需要利用在布局布线中获得的精确参数，用仿真软件验证电路的时序。（也称为后仿真）。（6）仿真下载：确认仿真无误后，将文件下载到芯片中。3.2.5 VHDL设计单元模型VHDL设计可由4个分立的设计单元组成，每个设计单元经编辑后保存在WORK库中。这4个可编辑的源设计单元分别是：实体（entity）、结构体（architecture）、配置（configuration）和程序包（package）。下面逐一介绍这4个设计单元。1实体实体是用来描述一个设计对外部的接口信号、端口数目、端口的方向和数据类型等，还包括一些其它的信息，如属性等。一切通信均由实体中的端口说明来产生。实体定义了硬件的输入输出端口，定义了硬件与外部环境的接口。从这种意义上来讲，实体定义的其实是一个黑盒子，黑盒子上带有输入和输出的端口说明，但并不包含如何将输入映射到输出的信息。下面的 VHDL源代码定义了一个实体BUBBLE，它的输入端口为DATA_IN，DATA_ READY和START，输出端口为DATA_OUT。它定义了图3.2所示的一个硬件模块，但没有定义输入信号和输出信号之间的关系。简单地讲，实体定义了一个“插座”，这个插座只定义了硬件的端口，可以在这个插座上插上任何端口匹配的硬件。图3.2实体BUBBLE定义的硬件模块entity bubble isport(data_ready: in boolean; data in: in integer; start: in std_logic; data_ out: out inteager);end bubble;2结构体结构体定义了硬件设计的输入端口和输出端口之间的映射关系，用来说明相应的硬件的行为。换句话说，结构体定义了插座（实体）上插入了什么器件。设计者可以在任何层次定义结构体，算法级、RTL级或者逻辑门级都可以写出相应的结构体。结构体通常由说明部分和算法部分组成，算法部分通常是一些并发执行的语句。下面的VHDL源代码是实体BUBBLE的一种行为描述。结构体BEHAVIOR中的算法部分只有一个并发执行的进程语句SORT。其中，进程实际上是包含在begin和end之间的无限循环语句。architecture behavior of bubble is -结构体的说明部分 type memory is array(1 to 256) of integer; procedure read_mem(data_ready: in boolean; data_in: in inteager; ram: out memory) is begin for i in 1 to 256 loop wait until data_ready; ram(i):=data_in; end loop; end read_mem; procedure write_mem(data_ready: in boolean; data_out: out inteager; ram: in memory) is begin for i in 1 to 256 loop wait until data_ready; data_outi loop t2:=t1-2; t1:=t1-1; if ram(t1)ram(t2) then tmp:=ram(t 1); ram(t1):=ram(t2); ram(t2):=tmp; end if; end loop end loop; write_mem(data_ready, data_out, ram); end process sort;end behavior;结构体有三种描述方法：Netlist（网表描述）、Equation（方程描述）和Behave（行为描述），有时将它们称之为：Structural（结构描述），Data flow（数据流描述）和Behavior（行为描述）。下面分别进行说明。（1）Structural（结构描述）结构描述最反映一个设计硬件方面的特征，表达了内部元件间连接关系。使用元件例化语句来描述。下面VHDL程序反映了半加器的结构描述。architecture ha-structure of half-adder iscomponent xor2port(x, y: in bit;n: out bit)end component;component and2port(l, m:in bit; n: out bit);end component;beginx1:xor2 port map (a,b,sum);a1:and2 port map (a,b, carry);end ha-structure;（2）Data flow（数据流描述）数据流描述反映一个设计中数据从输入到输出的流向，使用并发语句描述。下面代码给出了半加器的数据流描述。architecture dataflow of half-adder isbegin sum=a xor b after 8ns; carry=a and b after 4ns;end dataflow;（3）Behavior（行为描述）行为描述反映一个设计的功能或算法，一般使用进程PROCESS，用顺序语句表达。下面程序描述半加器的行为描述。architecture behavior of half-adder isbeginprocess(a,b) variable x,y: bit;begin x:=a; y:=b; sum=x xor y; carry=x and y; end process;end behavior;上面介绍了VHDL的三种不同的描述风格：行为级描述、数据流描述和结构级描述。在一个系统中三种描述风格基本上都可能用到。在主模块与子模块调用时一般采用结构化描述：在一般模块的设计时，根据具体情况，可以用行为级描述，又可以用数据流描述。对于一个复杂系统的描述来讲，单用一种描述方法来描述是不现实的，通常是几种描述方法混合使用。3配置一个实体可用多个结构体描述，由配置来决定选择哪一个结构体来综合。配置语句基本语法格式如下：configuration配置名of实体名is f