[硕士论文精品]基于fpga的32位浮点数据fft及ifft的设计与实现

中山大学硕士学位论文基于FPGA的32位浮点数据FFTIFFT的设计与实现专业电路与系统硕士生宋军江指导教师黄以华副教授摘要FFTIFFT是时域信号与频域信号之间转换的基本运算，是数字信号处理的核心工具之一，因此，它广泛地应用于许多领域。在数字化的今天，不论是在通信领域还是在图像处理领域，对数字信号处理的速度、精度和实时性要求不断提高。为满足不断提高的要求，国内外不断地推出各种FFTIFFT处理器，主要处理器有ASIC、DSP芯片、FPGA等。由于FPGA具有可反复编程的特点及丰富资源，所以它受到广泛的关注。本论文就是一种基于FPGA实现浮点型数据的FFT及IFFT处理器，该处理器使用ALTERA公司的STRATIXII系列的FPGA芯片。它主要采用流水线结构，这种结构可以使各级运算并行处理，对输入进来的数据进行连续处理，提高了运算速度，满足了系统的实时性要求；另外处理器所处理的数据是32位浮点型的，因此它同时提高了运算的精度。关键词FI丌，IFFT，FPGA，流水线，浮点型数据。中山大学硕士学位论文DESIGNANDIMPLEMENTATIONFOR32BITFLOATINGPOINTFFTIFFTBASEDONFPGAMAJORCIRCUITSANDSYSTEMSNAMESONGJUNJIANGSUPERVISORHUANGYILHAASSOCIATEPROFESSORF】同FFTPROCESSORSARETHEBASICOPERATIONSOFTHETRANSFORMINGBETWEENSIGNALSOFTIMEFIELDANDFREQUENCYFIELDANDITISONEOFTHEMAINTOOLSFORDI舀MLSIGNALPROCESSINGASARESUIT,ITISWIDELYUSEDBYMANYFIELDSBUTINNOWADAYS，THEDEMANDSOFSPEEDANDPRECISIONANDREALTIMEBECOMEMOREANDMOREHEAVIERNOTONLYINCOMMUNICATIONBUTALSOIMAGEPROCESSINGANDSOONTOSATISFYTHEHEAVYDEMAND。MANYFNN叩PROCESSORSHAVEBEENINVENTEDCONSTANTLYATHOMEANDABROADITCONCLUDESASICPROCESSOR，DSPCHIPSET,FPGAANDSOONBUTFPGAHASBEENWIDELYUSEDFORITSFLEXIBLEPROGRAMMABLELOGICANDPLENTYOFSOURCESTHISTHESISSTUDYAKINDOFHIGLLSPEEDFFLWPROCESSORBASEDONFPGAOFSTRATIXIISETOFALTERACOMPANYITADOPTSPIPELINETOREALIZETHEPROCESSORSOTHATTHEOPERATIONSOFEVERYSTAGERUNATTHESAMETIMETHANKSTOTHATTHEPROCESSORCANDEALWITHTHEINPUTDATACONTINUOUSLYANDSATISFYTHEREALTIMEDEMANDINADDITION，THEDATAPROCESSEDIS32BITSFLOATINGPOINTTYPEANDITIMPROVESTHEPRECISIONOFPROCESSINGRESULTKEYWORDFF嘎IFFT,FPGA,PIPELINE，FLOATINGPOINT中山大学硕士学位论文第1章绪论11研究的背景与意义快速傅里叶变换，反变换阡T腰FR是DFTIDFT的快速算法，是把数据从时域到频域从频域到时域变换的基本运算它是数字谱分析的必要前提，是数字信号处理的核心工具之一因此它在通信等数字信号处理领域乃至其他众多学科领域中都有着广泛的应用。IT】随着计算机科学的高速发展，很多领域对FFTIFFR运算速度、精度及实时性的要求越来越高。如数字语音编码、雷达信号处理、声纳信号分析、数字滤波、射电干涉等应用领域。传统的FFRIFFR运算已不能满足系统的更高要求由软件实现的FFTIFFR运算速度慢，不能满足实时高速的系统性能要求，而专用的DSP芯片由于处理速度慢也不能满足某些更高速的要求，如AD公司的2106X系列DSP实现1024点基2复数FFR运算大约需时0SINS，已不能满足高速的要求。因此必须开发出能够实现高速FFTIFFR的专用硬件，以满足不断提高的系统要求。而现在高速发展的现场可编程逻辑阵列器件FPGA，使得硬件实现FFRIFFT运算变为可能。本论文研究一种FFRIFFR专用硬件的具体实现方法，并设计一个硬件系统，即FFTIFFF处理器。该FFRIFFR处理器整体结构采用流水线型，进行32位浮点型数据的复数运算。采用流水线结构可以提高运算速度，32位的浮点型复数运算可以提高运算的精度，从而满足系统要求。12国内外的研究现状中山大学硕士学位论文自从20世纪60年代COOLEYTUKEY快速傅里叶变换FFT算法发表以来，国际上对数字信号处理理论的研究已经非常成熟，但实现的方法多是以软件为主；而到了20世纪70、踯年代，随着集成电路和计算机科学技术的发展，使数字信号处理的硬件实现变为可能，从而使数字信号处理有了更快的发展目前国际上，以FPGA芯片生产商为主的公司在基于FPGA设计FFT的综合研究方面处于领先地位。如XILINX公司推出了140MHZ时钟频率下处理速度达到1US的1024点FFT处理模块，采用800万门VHTEXII器件实现；ALTERA公司2005年推出了FFT的坤核，使用此口核计算16位1024点的FFT仅需要663US。嘲但是这些口核售价很高，还不能在我国得到广泛应用而我国的FPGA起步较晚，和国外相比有一定差距，但进入21世纪以来，发展也非常迅速。我国的科研人员通过对先进的DSP芯片的研究，已经研制出一些高性能处理设备的解决方案，并在板级PCB设计方面取得一定的成果，积累了宝贵的经验如我国某电子技术研究所研制的DSP雷达数字信号处理通用模块，是采用6片ADSF21060和大规模可编程器件构成通用处理模块L国内某所大学所研制的基于TMS320C强201的高速实时数字信号处理平台，实现了基2的复数FFT，允许输入数据的动态范围16BIT,可以实现59US内完成512点的FFT，130US内可以完成1024点的FFR随着集成电路和计算机科学技术的不断发展，对数字信号处理系统的要求也会不断的提高，因此，作为数字信号处理核心工具之一的FFTIFFR也会不断地向前发展。13本论文的研究内容本论文主要研究基2浮点型数据FFFIFFT的FPGA实现，包括浮点型数据运算标准与运算实现，FFRIFFR设计与实现，以及C语言的实现及验证。各章内容分别为第一章概论第二章FPGA技术概述；2中山大学硕士学位论文第三章快速傅里叶变换的算法研究第四章浮点运算标准及实现第五章N啊唧整体结构设计第六章FFTIFFT的FPGA设计与实现14本章小结本章从研究快速傅里叶变换的背景及国内外研究现状来提出本论文的实际意义。随着计算机科学及信息化的高速发展，在数字化的今天，对信号处理的要求不断提高，尤其是对数字信号处理的要求，更是如此为满足这些不断提高的要求，国内外都不断地研究实现数字信号处理的新方法，本论文试图利用FPGA实现FFRAFFR。3中山大学硕士学位论文第2章FPGA技术概述FPGA是现场可编程逻辑门阵列FIELDPROGRAMMABLEGATEARRAY，与之相似的是CPLD，复杂可编程逻辑器件COMPLEXPROGRAMMABLELOGICDEVICE，它们的功能基本相同，只是内部结构及实现原理略有不同。因此它们都可叫做可编程逻辑器件PRO。ILD是一种专用的集成电路，内部有大量的门电路，可以通过软件编程来实现内部门电路的不同连接，从而整个PLD对外就可以实现一定的功能，而且还可以通过软件编程来改变内部门电路的连接关系而改变PLD的功能。使用PLD来进行数字电路的开发，不仅可以大大缩短设计的开发周期，减少PCB的面积，而且还可提高系统的可靠性。因此，PLD是电子设计领域里最有发展前途的一项技术。22FPGACPLD的发展历程当今社会是数字化的社会，是数字集成电路广泛应用的社会。而数字集成电路本身也在随着社会的不断发展而不断的更新换代，已由早期的电子管、晶体管、小中规模集成电路，发展到现在的超大规模集成电路VLSIC，VERYLARGESCALEINTEGRATEDCIRCUIT，几万门以上以及许多具有特定功能的专用集成电路。但是随着微电子技术的发展，设计与制造集成电路的任务已不完全由半导体厂商独立承担。而系统设计师们更愿意自己设计专用集成电路ASIC芯片，而且希望AISC的设计周期尽可能短，最好是在实验室里就能设计出合适的AISC芯片，并且立即投入实际应用之中，因而出现了现场可编程逻辑器件FPLD，其中应用最广4中山大学硕士学位论文泛的当是现场可编程门阵列FPGA和复杂可编程逻辑器件CPLD。早期的可编程逻辑器件可分为三种可编程只读存贮器PROM、紫外线可擦除只读存贮器EPROM和电可擦除只读存贮器EEPROM。由于它们结构上的限制，它们只能完成简单的数字逻辑功能。随后，开始出现了结构上稍复杂的可编程芯片，即可编程逻辑器件PLD，它可以完成各种逻辑功能这种可编程逻辑器件主要有可编程阵列逻辑PAL和通用阵列逻辑GAL。它们都是由“与”门和“或”门阵列组成，任意组合逻辑都可以用“与一或”表达式来描述，所以PLD可以以“积一和”的形式完成大量的组合逻辑功能。这个时期的PLD器件有一个共同的特点，就是可以实现速度特性较好的逻辑功能，但其过于简单的结构使它们也只能实现规模较小的电路为了弥补这一缺陷，20世纪年代中期，ALTERA和XINLINX分别推出了类似于PAL结构的扩展型CPLDCOMPLEXPROGRAMMABLEIJOGICDEVICE和与标准门阵列类似的FPGAFIELDPROGRAMMABLEGATEARRAY，它们都具有体系结构和逻辑单元灵活、集成度高以及适用范围宽等特点。这两种器件兼容了PLD和通用门阵列的优点，可实现较大规模的电路，编程也很灵活。与门阵列等其它ASICAPPLICATIONSPECIFICIC相比，它们又具有设计开发周期短、设计制造成本低、开发工具先进、标准产品无需测试、质量稳定以及可实时在线检验等优点，因此被广泛应用于产品的原型设计和产品生产一般在10000件以下之中。几乎所有应用门阵列、PLD和中小规模通用数字集成电路的场合均可应用FPGA和CPLD器件。47123FPGACPLD的概述锐，嘲FPGA和CPLD都是可编程逻辑器件，它们是PAL和GAL等逻辑器件的基础上发展起来的，同以往的PAL和GAL等相比较，FPGACPLD的规模比较大，它可以替代几十甚至几千块通用IC芯片，因此它受到广泛的关注和普遍的欢迎。在全球范围内有很多公司开发生产FPG和CPLD，但主要的有AITERA和XILINX公司，5中山大学硕士学位论文此外还有LATTICE，ACTEL，QUICKLOGIC等。尽管FPGA和CPLD和其他类型的PLD的结构各有其特点和长处，但它们主要都是由三大部分组成1一个二维的逻辑块阵列，构成了PLD器件的逻辑组成核心。2输入输出模块；3连接逻辑块的互连资源。边线资源由各种长度的边线线段组成，其中也有一些可编程的连接开关，它们用于逻辑块之间、逻辑块输入输出之间的连接。典型的PLD的框图如图21示图21典型PLD的框图FPGACPLD都是特殊的ASIC芯片，除了具有ASIC的特点外，还有以下的优点1随着VLSIVERYLARGESCALEIC，超大规模集成电路工艺的不断提高，单一芯片内部可以容纳上百万个晶体管，FPGACPLD芯片的规模也越来越大，其单片逻辑门数已达上百万门，它所能实现的功能也越来越强，同时也可以实现系统集成。2FPGACPLD的资金投入小，节省了许多潜在的花费。6中山大学硕士学位论文3用户可以反复地编程、擦除、使用，或者在外围电路不动的情况下用不同软件就可实现不同的功能。24FPGACPLD的内部结构矧241基于乘积项PRODUCTTERM的PLD结构CPLD主要采用这种结构，它的内部结构主要可分为三部分宏单元MACROCELL，可编程连线PIA和IO控制块。宏单元是PLD的基本结构，由它来实现基本的逻辑功能。如图22中蓝色的多个宏单元的集合。可编程连线负责信号传递，连接所有的宏单元；IO控制块负责输入输出的电气特性控制。图22基于乘积项的PLD内部结构而宏单元的结构如图23所示，其左侧是乘积项阵列，实际就是一个与或阵列，每一个交叉点都是一个可编程熔丝，如果导通就是实现“与”逻辑，后面的乘积项选择矩阵是一个“或”阵列。两者一起完成组合逻辑。图的右侧是一个可7中山大学硕士学位论文编程D触发器，它的时钟、清零输入都可以编程选择，可以使用专用的全局清零和全局时钟，也可以使用内部逻辑产生的时钟和清零。如果不需要触发器，也可以将此触发器旁路，信号直接输给PIA或输出到IO脚。H。I7P蛔HLO出自晴M相瞎RNL阳M甜L向D口，N_柚龟叫IZMN矧BL蟛鲥J1一釉广、卜一铆P讳UI拱乃N汗如U，溉厂奄广、秉蹶垌盥曼JL，选择矩阵可捕程NU1必L删姨墨F广、A彭LU”。S棚1冷一_FJL。、Z。枷B幽絮WPLA一一VS枷10卧DM蛔嘲NP“嘶峨砸糟图23宏单元的内部结构图242乘积项结构PLD的逻辑实现原理_OC删蛳吐我们以图24中所示的电路为例具体说明PLD是如何利用乘积项结构实现逻辑的，电路如下O2A日CDCU图24示例电路假设组合逻辑的输出AND3的输出为F，则8中山大学硕士学位论文FAB粑宰DA托奉DB粑木D我们以D表示D的“非”PLD将以图25中所示的方式来实现组合逻辑F、R、，一、，旷、，一一一五暑BCC卫面，、月砬。图25实现逻辑功能的电路A，B，C，D都是由PLD芯片的管脚输入后进入可编程边线阵列PIA，在内部会产生A，1A，B，1B，C，1C，D，1D8个输出。图中每一个叉表示相连可编程熔丝导通，所以得到FFLF2A托奉LDB托奉D。这样逻辑功能就实现了。而图23中的触发器的实现比较简单，直接利用宏单元中的可编程D触发器来实现。时钟信号CLK由IO脚输入后进入芯片内部的全局时钟专用通道，直接连接到可编程触发器的时钟端。可编程触发器的输出与IO引脚相连，把结果直接输出到芯片的管脚。从而实现了图23中的电路所示的功能。上例中所示的电路是一个简单电路，因此所需要的内部单元也不多。但是对于一个复杂的逻辑电路，简单的内部电路是不能实现的，因此需要通过将多个宏单元相连来实现复杂的功能。243查找表LOOKLII，TABLE的原理与结构FPG是采用这种结构的PLD芯片，如ALTERA的ACEX，AP既，STRATIXII系列，XILINX的SPARTAN，VIRTEX系列等。查找表LOOKUPTABLE简称为LUT，LUT本质上就是一个RAILI目前FPGA中多使用4输入的LUT，所以每一个LUT可以看成一个有4位地址线的16X1的RAM，当用户通过原理图或HDL语言描述了一个逻辑电路后，PLDFP6A开发软件9中山大学硕士学位论文会自动计算逻辑电路的所有可能的结果，并把结果事先写入RAG。这样，每输入一个信号进行逻辑运算就等于输入一个地址线进行查表，找出地址对应的内容，然后再输出。我们举一个4输入的与门的例子来说明以上的所介绍的工作原理实际逻辑电路LLRR的实现方式B卜F、5习兰IC亡叫，一D_J逻辑输RAM中存储的内A，B，C，D输入地址出容000000000O000100001O001LLLL1111L1、ALTERA公司的FPGA的内部结构ALTERA公司的FPGA都采用基于SRAM的查找表结构形式，主要由嵌入式阵列块EMBEDDEDARRAY，EAB、逻辑阵列块LOGICARRAY，LAB、快通道互连FASTTRACK，FT、I，O单元INPUTOUTPUTCELL，IOC四部分组成，其结构如图26所示。中山大学硕士学位论文嵌入式阵列IOE10E图26ACFX1K器件的内部结构框图1嵌入式阵列块EAB嵌入式阵列块EAB是在输入输出口上的RAM块，在实现存储功能时每个EAB可以提供2048位，可单独使用或组合使用2逻辑阵列块LAB逻辑阵列块是FPGA内部的主要组成部分，LAB通过快通道互连FR相互连接，典型结构如图27所示。LAB是由若干个逻辑单元再加上相连的进位链和级联链输入输出及LAB控制信号、LAB局部互连等构成。逻辑单元LE是FPGA的基本结构单元，主要由一个4输入LUT、一个进位链CARRYM、一个级联链CASCADEIN和一个带同步使能的触发器组成，可编程实现各种逻辑功能。每个LE有两个输出，分别驱动局部互连和快通道互连逻辑单元LE的LUT用于组合逻辑，实现逻辑函数。逻辑单元LE中的可编11中山大学硕士学位论文程触发器用于时序逻辑，可通过编程配置为带可编程时钟的D、T、JK、SR触发器或被旁路实现组合逻辑。寄存器的时钟清0、置位可由全局信号、通用I0引脚或任何内部逻辑驱动。图27ACEXLKLAB结构图进位链和级联链是专用高速数据通道，用于不通过局部互连的通路，连接相邻的LE。进位链用于支持高速计数器和加法器，提供LE之间快速向前进位功能，可使FPGA适用于高速计数器、加法器；级联链用于实现多输入逻辑函数。3快通道互连FT快通道互连FT用于LE和器件I0引脚间的连接，快通道互连是一系列水平FF互连和垂直列互连走向的连续式布线通道。行互连可以驱动I0引脚，或馈送到其它LAB，列互连接各行，也能驱动I0引脚。4IO单元10CFPGA的IO引脚由I0单元驱动，UO单元位于快通道的行或列的末端，由一个双向三态缓冲器和一个寄存器组成，可编程配置成输入、输出或输入输出双向口IO单元的清0、时钟、时钟使能和输出使能控制均由IO控制信号网络采用高速驱动。中山大学硕士学位论文2、XILINX公司的FPGA的基本结构XILINX公司的FPGA产品结构与ALTERA公司的FPGA有较大的差异，其内部结构为逻辑单元阵列LOGICCELLARRAY，LCA，主要由可配置逻辑块CONFIGURABLELOGICBLOCK，CLB或可配置逻辑单元CONFIGURABLELOGICCEL、各模块互连资源PROGRAMMABLEINTERCONNECT和输入输出模块INPUTOUTPUTBLOCK，LOB组成。XILINX公司的FPGA内部的结构如图28所示。可配置逻辑图28XC3000系列FPGA内部结构图1可配置逻辑块CLBCLB主要由组合逻辑功能发生器、D触发器2个和内部控制部分组成。组合逻辑功能发生器有5个逻辑变量输入端和两个反馈输入端，可以作为查找表的地址输入，两个输出端。因此逻辑功能发生器可以配置成321或16X2的查13中山大学硕士学位论文找表。CLB的两个D触发器共享一个时钟信号，D触发器的复位由全局复位信号或RD输入信号驱动。2输入输出模块LOB输入输出模块IOB为外部封装引脚与内部逻辑之间提供一个可编程的接口。3配置存储单元基本的存储单元由2个CMOS反相器和一个用于读写数据的开关晶体管组成。该存储单元具有高可靠性和抗干扰能力。4可编程互连可编程互连是连接各模块的通道，将CLB、10B连接起来形成功能电路。25本章小结本章回顾了CPLD与FPGA的发展历程、并介绍了主要生产商生产的FPGA的内部结构及工作原理等，主要有ALTERA公司和XILINX公司，它们的内部结构有不少的差异，但它们都是基于查找表的PLD。14中山大学硕士学位论文第3章快速傅里叶变换及反变换的算法研究31离散傅里叶变换的原理嘲信号的傅里叶变换建立了信号的时域与频域之间的一一对应关系，拓展了信号的表达空间，为信号与系统的频域分析奠定了理论基础。从而使我们在分析信号与系统时，既可以对信号的时域进行分析也可以对信号的频域进行分析，而且信号的频域分析具有更清晰的物理概念和深刻含义，因此在信息领域有了广泛的应用。对信号进行频域的分析，首先要对时域的信号进行傅里叶变换得到对应的频谱函数。而在数字信号处理中，我们考虑对时域中有限长度的离散信号进行傅里叶变换得到频域有限长度的离散信号，即离散傅里叶变换。离散傅里叶变换的定义如下对时域的有限长序列XN毒OO“ONSN一1的傅里叶变换对定义为X一DFRXN一2XN嘴0SKN一131U一IDFTXKA专薹X肘SN一1一R啊其中昭1E，由式中可以看出傅里叶变换与反变换都是旋转因子赠或降IH的线性组合，因此时域离散信号有限长度序列石O与频域的离散信号Z唯一确定的对应关系。在时域里确定了的离散信号，也就确定了它在频域里对应的频谱函数，从而使我们能够对其频谱函数进行分析。中山大学硕士学位论文32快速傅里叶变换及反变换的原理F1叫【912，毖捌321快速傅里叶交换算法的提出若直接按照式3一1和式32求长度为的时域信号的傅里叶变换，那么，对每一频率分TXT1，都需要进行次复数乘法运算和一1次复数加法运算。因此计算个不同频率分量XT共需要2次复数运算，一I次复数加法运算。而进行傅里叶变换的反变换具有相同的运算量。显然，随着信号的长度的不断增加，则进行变换的运算量将是成级数倍的增加。因此，虽然傅里叶变换在信号与系统的分析中具有非常重要的作用，但由于它的巨大的运算量，使它在一段时间内不能得到广泛的应用。直到1965年COOLEY和TUKEY提出了一种快速运算的算法，即COOLEYTUKEY算法，才使得傅里叶变换的运算量大大的降低，在很大程度上提高了运算效率，从而使傅里叶变换得到广泛应用。322按时域抽取的基2快速傅里叶变换的算法原理我们以长度为2UM为正整数的时间序列XO的基2DFT为例，推导说明快速傅里叶变换的算法原理。COOLEYTUKEY快速算法是利用旋转因子嘴的特殊性质通过在时域内将序列逐次分解为一组子序列进行运算的。2X旋转因子F哮E一7可H具有周期性，对称性及可约性。1旋转因子以N为周期，即中山大学硕士学位论文唠蝶肌4睇仲圳咛了一一时，吩陈H陟方仰篇，仰穸_I，T，ZKN，。MNM为正整数首先把序列工0分解为两组，偶数项为一组，奇数项为一组，可得到两个XIRX2R，KR，X2，1，O，1要一1墨一胛“R一墨，形移，3372筋XZKDFTX2RX2RW毳，P42筋、7石一DFTXN一工渺方N一1一1X哪。为ZO肘N为删以1噘一12荟Z2R孵打荟Z2，1磁犯H。N一1NZ。12磊X，咙昧乏XZ，吃其中OSK墨要一1。由旋转因子的特性可得。17中山大学硕士学位论文XKX1噼X2，36XKN一五一嘭X37其中七一O，1，等一1，式36表示了前半部分。七S等一1Z的组合方式，式37表法了后半部分鲁七墨一1X僻的组合方式，信号流图如图31示。二瑟二二力图3一L蝶形运算削由于信号流图形如蝴蝶，因此称为蝶形运算由蝶形运算图可以看出，每一个蝶形运算需要一次复数乘法，两次复数加减法运算。因此前半部分的组合共需要竺次复数乘法，后半部分也需要旦次复数乘法运算，所以两个掣点的DFT442共需譬次复数相乘运算。而组合运算共需等次蝶形运算，需等次复数相乘运算，因而共需里2丝2搿NF2次复数相乘，与直接运算相比节省了近一半运算。由于等2U1仍然是偶数，可依此推理得继续分解为等个点的序列，依此分解下去，直到最后是二点的DFT运算为止，两点的DFT同样可以用一个蝶形运算表示，例长度为8点的时间序列最后可以分解到XO和X4为一组，X2和X6为一组蝶形运算。由于这种算法是在时域上按偶数和奇数抽取的，且每一次是一分为二的，所以称为按时域抽取的基2算法。长度为8点的时间序列的蝶形运算数据流图如图32所示。X0一一，X0XL二一W0“，W。X4二一W；、X2一。_X2X31一OJ一17、1W2一一X6X4黔JI，L，XLX5。WIIIT,0I一7，W1_X5】6W。JO。|W2I7“_一，X3X7_7、O_W3一X7图32N8按时域抽取的蝶形流程图3,23按时间抽取的基4算法的数学推论基4算法与基2算法的基本原理大致相同，都是将长序列的DFT分解为短序列的DFT，然后再根据短序列的DFT表示长序列对应的DFT。它们都利用了旋转原子陟穷的特性，使DFT的运算结构简单化。按时域抽取的基4算法是将长度为N。4琳的序列X0分解为学个短序列，即4而0X4N，工20X4N1，而0X4N2，X4X4N3剃_O，1，等10下面推导由短序列的DFT表示长序列的DFT。长度为N的序列XO的DFT可以稀到中山大学硕士学位论文；警1Z4，暇庸警1Z4厂1哦M2薹坩，暇薹水，1哦和1冲一1N41罗X4R2WXT4”2弘X4R3嘴”3冲劁岗LN41五，暇砖孵乏ZZ，崂砖一一T睇X3R暇睹孵X4，孵埔38筋筋、7由于昨砖。P一，警打，E一，南H。略。，所以式可以表示为以一1一1Z。荟_，嚼聪荟ZZ，略以一一1孵ZX3，嚼。暇芝X4R嘴。39箭衢、进一步整理得XKX。七W公X七蝶七X3嵋七X4310其中五、X、墨、蜀分别是、X2N、屯OX4N对应的鲁点。FT，频率变量的七的取值为七一O，1，等一1。FLQ式3一LO可知，长度为N的序列X0的DFTXK可由而0、X2、加嘴OXV知昌”R卯暑X中山大学硕士学位论文毛O、砀0对应的DFTX。、X七、X，、X。七来表示，由于_O、X2N、屯O、_都是长度为等的序列，因此，XDK、X2、邑、X4七也都是长度为芸的序列。所以，要想全部的表达X七，就要利用互、X2、Z3、X4七和矽4的特性，即满足。X。七X。七，X“2X2七，X3七3一X3七，X。七4X七，其中七地1，等10而旋转因子咛存在性质嘭；E一，瞄一_噼，咙2E一加孵；一1噼，嘭3；P，瞄；J碟，形4；形1形茹。因此，由式310可得X一五嘭Z嚼X3嘴Z。，311XK仫五一蛾五一略鼍JWYX4K，312X吆五一嘭五畔墨一嘴墨，313X3墨J碟五一畔五一J孵邑314中山大学硕士学位论文中七一O，1，。IN一1。式3一11，312，313，314是按照基4分解的子序列对应的DFT来合成原序列X0DFT计算公式，其实现过程可用信号流程图33表示XLKX2KX3KX4KXKX时2N4XK3N4图33按时间抽取的基4FFT蝶形运算图33FFT算法的规律对于长度为一矿的基2算法，我们可以从中了解它的规律。第一，蝶形运算的规律。整个流图都是由蝶形运算单元组成，因此，蝶形运算是FFT及IFFT运算的核心，是最基本的运算。1矿点序列共需要M级蝶形运算，每级都有冬个蝶形运算；2第L级的要个蝶形运算中，共有2工N个不同的蝶形运算组，即旋转因子不相同；3每个蝶形运算组中有矿_工个蝶形运算；4蝶距，第L级的运算中，参加每个蝶形运算的两个数相距矿4。第二，顺序与倒序。按时间顺序输入的序列，输出时为倒序。按时间输入倒序的序列，输出为顺序。也可以对蝶形运算进行变形，使得输入和输出都为顺序，但它的控制结构不易实现。倒序的规律可以由肼一1位的二进制数加1再倒序的输出结果的次序来定。例如，当N8时，NL的二进制数为001，倒序结果为100，对应的十进制数为4。依此类推，其他的倒序数都可一一求出。中山大学硕士学位论文第三，同址存储。由蝶形运算流图可以看出，参加蝶形运算的两个数，在运算结束后就不再参加下一次的运算，即不需要再保存，而蝶形运算后的结果可以分别存放在存储原来两个数据的存储单元中。这样可以节省硬件资源，降低成本。第四，旋转因子的规律。由第一个规律可得，在第级运算中，共有2工1个不同的蝶形组，因此有4个不同的旋转因子，即矸孽KO12L11，且每级中的旋转因子都是从孵开始的，K依次加L，即为下一个蝶形组的旋转因子，周期为矿4。34算法的选择由前面的推导可知，基2和基4算法都大大的降低了运算量，从而很大程度上提高了傅里叶变换的运算速度。相比较基2算法和基4算法，基2算法的蝶形运算需要一次复数乘法和两次复数加法，而基4算法的蝶形运算需要三次复数乘法和十二次复数加法由于在硬件实现时，乘法器所需的资源比加法运算所消耗的资源多，大大的增加了成本，因此，在实现FFT时我们采用基2算法。35本章小结由于快速傅里叶变换的算法原理是实现FFT的前提，因此，必须对快速傅里叶变换的算法要有非常的了解本章就是针对快速傅里叶变换的基2算法和基4算法原理进行了研究，并得出了一些算法的规律，这些规律在实现的过程有很大的帮助。最后，根据实际的需要及对比两个算法优缺点的比较，我们选择其中的基2算法作为本论文的算法依据，在后面章节的实现过程中都是基于这种基2算法原理的。中山大学硕士学位论文第4章浮点处理器的硬件电路的设计与实现41定点、浮点数据N钉在数字系统中表示数据的方法主要有两种定点型和浮点型。定点型数据是小数点位置固定不变的数，小数点的位置按照约定可以在数的最高有效位的左边或最低有效位的右边，即化为纯小数或纯整数。在计算机中一般采用纯小数的表示方法，纯小数表示是小数点按约定在符号位之后，在最高数值位之前，它表示格式为其中最高位是符号位，即XO是符号位，X0为L时为表示数值为负，为0时表示数值为正；其它为数值部分，即尾数部分，小数点在X0与X1之间。浮点型数据是由两部分组成E阶码和M尾数。其表示格式为其中MS是尾数的符号位，也是整个浮点数的符号位，表示该浮点数的正负，当MS是1时，表示浮点数为负；当MS为0时，表示该浮点数为正。ES，E1，E2EN为阶码EEXPONENT，即指数部分，ES是阶码的符号位，即指数部分的符号位。当ES是1时，则阶码为负，当ES是0时，则阶码为正。M1，姚为尾数部分MMANTISSA，是有效数字，通常是纯小数，用原码表示。因此浮点数表示的数据的真值为。R一1肼尺茸M其中R是阶码的底，也是尾数M的基数相同而在本论文中所采用的数据是32位单精度浮点型二进制数据，它与前面所述的浮点型数据略有不同，即尾数部分M和指数部分E，它的具体表示格式为中山大学硬士学位论文其中31是浮点数的符号位，即若A31是I，则所表示的数为负，若为0，则所表示的数为正A30，A29，A23八位是阶码，即指数部分，表示正或负指数，但是负指数不是用有符号数来表示的，而是将一个偏移量加到实际的指数上，生成一个正数。对于IEEE754标准中的单精度数，该偏移量为127十进制，即把127存储到指数域，这个偏移量加到一切指数上，不管符号。A22，A21A0表示的是尾数或小数部分，即有效位尾数用规格化后的形式存放。规格化一个数即将小数点放在第一个非零位后，即小数点在左边第一个“1”后，而在存储时，小数点前的。L”缺省，所以在单精度浮点型数据的尾数的分辨率为23位。42浮点加法、减法运算规则及硬件电路的实现N施加穑”蜘根据前面介绍的浮点型数据的表示方法，我们可以得出浮点型数据的加法运算规则第一，首先给两个数的尾数部分加上缺省的“1”和小数点，得到两个新的尾数ML，舵第二，比较进行加法运算的两个数的指数部分EL和E2的大小，即阶码的大小若两者相等，则比较两个数的尾数部分的大小；若两者不等，则求出差值。第三，根据上一步得到的阶码的差值，来调整较小的阶码，使之与较大阶码一样大，再对较小的阶码对应的尾数进行相应的移位。而较大的阶码作为运算结果的阶码。第四，判断进行加法运算的两个数的符号位是否相同，若相同，则对前三步得到的尾数部分进行加法运算，得到和的尾数；若不相同，则用较大数减去较小的数，这个结果即为加法运算结果的尾数部分，同时较大数的符号即为最终运算中山大学硕士学位论文结果的符号。第五，对所得的尾数部分规格化。即把小数点移位到第一个非零位之后，小数点前的。1”为缺省，再取小数点后23位，不足位补“0”第六，根据规格小数时移位的位数修正第三步得到的阶码。规格小数时左移N位，则阶码加上N；规格小数时右移N位则阶码减去N，得到的阶码为最终结果的阶码。这样，就得到了两个浮点型数据加法运算结果的符号、阶码尾数，即是运算的结果。减法运算实际与加法运算相同，只需要把减数的符号位取反，就变成了加法运算加法运算单元综合后的电路图如图41所示图41加法处理器电路图减法运算单元综合后的电路图如图4_2所示图42减法处理器电路图中山大学硕上学位论文43浮点乘法、除法运算规则及硬件电路的实现浮点乘法处理器可以采用流水线结构实现，在本论文里没有采用流水线结构。根据浮点型数据的表达格式，进行浮点乘法运算的规则为第一，首先判断在两个乘数中有没有为“O”的，若有0乘数，则结果输出为。0”第二，判断两个浮点数的符号位是否相同，以确定乘积结果的符号位。若相同，则结果的符号位为“0若不同，则结果的符号位为“1第三，将两个阶码部分相加，再减去一个偏移量两个乘数都有偏移量，相加后多了一个偏移量，得到的结果为乘法结果的阶码第四，将两个乘数的尾数部分加上缺省的L和小数点后相乘，得到结果的尾数。第五，将第四步得到的尾数再规格化，对尾数移位，再根据移位的位数对第三步所得阶码进行调整，得到最终结果的阶码。由第一步至第五步可得最终的浮点乘法结果。综合后的乘法运算电路图为如图43所示中山大学硕士学位论文L一一一。一IIT7一I一士譬L拦三蚕_一JE三三茸_I铲，_|苎C、乒。一3乘法处理器综合电路图文所用到的除法器是用在傅里叶反变换的计算中，是一个简单的除法器是对被除数除以2或2的乘方，所以只需对被除数的阶码部分减I或减去除阶码即可，在此不做详细讨论。4旋转因子乘法单元的设计与实现36和式37，即石一X。七形0Z七，XKINX。七一噼X2七可对于参加每一组蝶形运算的两个复数墨和X2，首先求出X2与旋子噼的乘积，然后再与五相加减得到蝶形这算的结果。实现时，乘法运算要比加法运算消耗的资源大，因此我们要尽可能的中山大学硕士学位论文减少乘法的运算。在旋转因子相乘运算单元中，是两个复数相乘，若直接进行复数相乘，则需要4次实数相乘，两次加法运算。我们可以根据以下公式推导，减少乘法运算，以节省资源。设XL七ML口YT,，X2七一CIA，矽夕一E一等HC。S等KN一SIN等KN；X一抄则X2七H葛4一C_D工一痧一CXYDJXACYCXYDZDZDJXAZCXCCYXCD一D一YJXCD一CZY】41由公式4一1可以看出，蝶形运算只需要三次乘法运算，5次加法运算即可。其整体结构图如图44所示。综合后的电路图如图45所示。旋转因子乘法单元除了由上述单元构成以外，还有一个控制单元和八个寄存器单元。控制单元是用来控制旋转因子在不同的时钟周期内完成不同的运算，在第一个时钟周期内完成加法和减法运算，输出图中的S1，S2，S3，经过寄存器后输入到乘法运算单元，在下一个时钟周期内完成乘法运算，输出结果S7，S8，S9，再经过寄存器输出到下一级的加减运算单元，在第三个时钟周期完成加减运算，输出旋转因子相乘，输出的结果再经过寄存器输出。因此，旋转因子运算单元需要在三个时钟周期完成运算。中山大学硕士学位论文图44旋转因子乘法单元结构图啊蠢L4抖刍BI4_邛H鐾十|L0L4HJEIL邑_一邛“4恐图45旋转因子乘法单元综合后的电路图45蝶形运算单元的设计与实现蝶形运算单元是FFT和IFFR运算中的核心单元，它主要由前面介绍的几个运算处理器构成。由式36和式37可知，对于FFT的旋转因子乘法单元得出的结果再与五的实部和虚部分别相加、减即可得到蝶形运算的结果其结构图如图46所示，蝶形运算单元综合后的电路图如图47所示。中山大学硕士学位论文1R1。R“11I一廿酣廿砌伫口S一“J眦WNX20WN习SUN她TOR1S。B鼢毒1图46蝶形运算单元结构图图47蝶形运算单元综合后的电路图蝶形运算单元运算的时序图如图48所示。厂广厂厂厂厂厂N厂厂厂图48蝶形运算单元的时序图由时序图中可以看出，完成一个蝶形运算需要四个时钟周期，前三个时钟周期完成旋转因子乘法运算，输出的结果在第四个时钟周期完成最后的加减法运算，得到蝶形运算的结果。46本章小结本论文所实现的处理器是对32位单精度的浮点型数据进行运算，我们根据IEEE754橼准定义的浮点型数据，进行了蝶彤运算单元所用到的一系列运算模块，它识惫舔嬲减法运舞，乘法模涎和除法模块，滚及由这些模决稳成蝶形运算鹧元等。而这些单元是设计FFT及IFFT的基本模块中山大学硕士学位论文第5章FFTIFFT整体结构的设计51FFT算法的硬件结构根据FFT和IFFR算法的特点，硬件实现的结构基本可以分为四种递归型、级联型、并联型、和阵列型四种结构1、递归型结构由一个蝶形运算单元作为运算单元，采用原址存储，每一级的蝶形运算以及每一级内部各个不同的蝶形运算都由控制单元控制循环使用蝶形运算单元。所谓的原址存储是指，每一个蝶形运算的输入数据经过蝶形运算后，原来的数据就不再参与运算，不用存储，因此，蝶形运算的结果可以存储在输入数据对应的存储单元中。因此，递归型主要由蝶形运算单元，控制单元，地址生成单元，旋转因子存储单元，寄存器单元等部分组成。其结构图如图5一L所示。豳G刮蝶形运算单元|N二回塞JJ,一J圣NY二FFR完成图6一LO基2FFT流程图其中流程图中的W、U都是存放复数旋转因子的，所进行的乘法运算也是复数相乘。最后处理的结果还要把十进制数与32位浮点型二进制数据进行相互转化，然后与硬件实现的结果相比较。中山大学硕士学位论文63FFT综合后的电路分析我们采用ALTERA公司的QUARTUSII对FFT及IFFT进行全编译的报告如图61L及图612所示。图61LFFT全编译报告中山大学硕士学位论文图612IFFT全编译报告本设计中采用了ALTERA公司的STRATIXII系列的EP2S90H484C4器件，所用资源总数及占器件总资源的比例已详细列在报告中。由报告可以看出，系统满足时序的要求，FFT和IFFT分别消耗芯片22和21的自适应查找表ALUT资源，所用到的寄存器总数分别为2361和1534个，总引脚数都为132个，占总引脚的42，DSP块个数同为72个，占总资源的18。FFT及IFFT综合报告分别如图613和614所示。报告中列出了本设计中所用到的总的逻辑单元数、寄存器数及引脚个数等信息，与总编译报告中所列信息基本相同，除此还列出了FFT和IFFT系统所用到的组合功能模块总数分别为14214和14845。中山大学硕士学位论文图6_13FFT的综合报告图614IFFT综合报告FFT和IFFT的静态时序分析报告分别如图615和616所示。由图中可以看出静态时序分析分别列出了系统的建立时间、保持时间，在该系统中，建立时中山大学硕士学位论文间和保持时间没有时序违背的路径，即“FAILEDPATHS”为0，说明系统符合时序要求，与系统的全编译报告中相一致。图615FFT的静态时序分析报告图616IFFT的静态时序分析报告64软、硬件仿真结果对比及误差分析长度为8点的时间序列及其二进制数如下REALPART0335600111L1010101011110L0011110000LLIMAGINEPART048530011111011111000011LL0010011110LREALPART043200111110110111010010111100011010IMAGINEPART068060011111100101110001L101111001101REALPARTT0037600111101000110100000001001110101IMAGINEPART0189100111L10010000011010001101101110REALPART0140600111110000011111111100101110010IMAGINEPART01669001LLL1000101010LL1001111101010L中山大学硕士学位论文为REALPART06528OOLIIILL001001110001110111100110IMAGINEPART0981400111111011110110011110100000111REALPART081420011111101010000011011110110100LIMAGINEPART0951700111111011100111010001010011100REALPART0841I001IIILL010101110101001001010100IMAGINEPART0286300IIII10100100101001010111101001REALPART03674001111101011LLOOOOOLLOLLLL011010IMAGINEPART0269500111110100010011111101111100111把这八点浮点型数据作为输入数据，由C十代码进行F盯运算处理后的结果REALPART36213IMAGINEPART40108REALPART00656386101111011000011001101101100001IIIMAGINEPART一184938101IIIIIILL01100101110000111101IREALPART一10862IMAGINEPART17295101LL1L11000101100001000100L1010REALPART00402698101111010010010011LLO00111110010IMAGINEPART00040805410111011100001011011011000001100REALPART01129IMAGINEPARTO1266001111011110011100111000000111011011111000000001LOL0001101101110REALPART一0374361101111LOLOLLIIILL0101100001ILLL0中山大学硕士学位论文IMAGINEPART一074982410111111001111111111010001110111REALPART13056IMAGINEPART02531REALPART一078853IMAGINEPART0618881001111111010011100011101111001100011111010000001100101100101001010