基于FPGA的FFT算法实现
摘要
随着数字电子技术的发展，数字信号处理技术具有极其广泛的应用，比如视频压缩、数字机顶盒、有线调制解调器、数字多用盘、多媒体与无线通信、语音处理、传输系统、雷达成像、全球定位系统等等。同时，信息技术领域是依赖于数字信号处理及其相应的专用集成电路的，所以对数字信号处理的要求越来越高。因此对数字信号处理中涉及到的有关算法的改进也提出了更高的要求，其中快速傅立叶变换是数字信号处理的一种重要的算法研究。现场可编程门阵列是近年来出现的一种新的可编程逻辑器件，它具有运行速度快、存储容量大、管脚多等特点。
本文研究的是利用现场可编程门阵列来实现快速傅立叶变换算法，快速傅立叶变换算法的实现，大大缩短了运算所需的时间，降低了因计算复杂而导致的计算误差。随着超大规模集成电路技术的不断提高，现场可编程门阵列的规模和集成度越来越大，在电子系统的设计中发挥了更大的作用。主要的设计内容包括现场可编程门阵列的结构与功能、VHDL语言的介绍、算法的实现过程等。本文通过离散傅立叶变换引出快速傅立叶变换算法，提出了快速傅立叶变换的两种抽取方法，重点介绍了基2按时间抽取的快速傅立叶算法，对算法进行了MAX+PLUSⅡ的仿真，再利用现场可编程门阵列来实现，并对仿真结果进行了分析。结果表明快速傅立叶变换的算法结果已达到了一定的精度，运算速度能够满足一般实时信号处理的要求。
关键词：现场可编程门阵列,VHDL,快速傅立叶变换，MAX+PLUSⅡ
Abstract
Withthedevelopmentofdigitalelectronictechnology,digitalsignalprocessingtechnologyhaveanextremelywiderangeofapplications,suchasvideocompression,
digitalset-topboxes,cablemodems,digitalmulti-purposetray,multimediaandwirelesscommunications,voiceprocessing,transmissionsystems,radarimaging,globalpositioningsystemsandsoon.Meanwhile,informationtechnologydependonthedigitalsignalprocessinganditscorrespondingapplicationspecificintegratedcircuit,sothedemandofdigitalsignalprocessinghavebecomemoreandmore.Therefore,thedigitalsignalprocessinginvolvedinthealgorithmisalsoputforwardhigherrequirements,andfastFouriertransformdigitalsignalprocessingisanimportantalgorithm.Fieldprogrammablegatearrayemergedinrecentyears,anditisanewprogrammablelogicdevices.Ithastheoperationalspeed,storagecapacity,muchmorepinsandsoon.
ThispaperstudiestheimplementationofFFTbasedFPGA.TherealizationofFastFourierTransformalgorithmgreatlyreducethecomputationtimewhichrequiredtoanddecreasethecomputationalcomplexitycausedbycalculationerrors.AsVLSItechnologycontinuestoimprove,itssizeandgrowingintegrationplayabiggerroleonthedesignofelectronicsystems.AndthemaindesignelementsincludethestructureandfunctionofFPGA,thedescriptionofVHDLlanguage,algorithmimplementationprocessesandsoon.AccordingtothedescriptionofFouriertransformfastFouriertransformalgorithm,leadingtofastFouriertransformofthetwoextractionmethods.Andthepaperespeciallystudiesthetimetakenbythebase2FastFourieralgorithmandusesMAX+PLUSⅡsimulateit,meanwhileadoptsFPGAtoachieve,andthesimulationresultsareanalyzed.TheresultsshowthattheresultsoffastFouriertransformalgorithmhasreachedacertaindegree,anditsaccuracy,computationspeedcanmeetthegeneralrequirementsofreal-timesignalprocessing.
Keywords:FPGA,VHDL,FFT,MAX+PLUSⅡ
目录
第1章绪论 1
1.1FFT算法的研究现状及应用 1
1.2课题的提出 1
1.3FPGA实现FFT的优势 2
1.4本文的研究工作 2
第2章可编程门阵列与VHDL 3
2.1可编程门阵列 3
2.1.1FPGA的基本结构 3
2.1.2FPGA的基本特点 3
2.1.3FPGA的配置模式与功能 4
2.2VHDL的出现 4
2.2.1VHDL硬件描述语言 4
2.2.2VHDL的基本结构 5
第3章FFT算法研究 6
3.1傅立叶变换 6
3.2离散傅立叶变换 6
3.3FFT的基本思想 6
3.4快速傅立叶变换 7
3.4.1基于时选的快速傅立叶变换 7
3.4.2基于频选的快速傅立叶变换 11
3.5FFT算法的类型 13
第4章FFT算法的软件设计与仿真 15
4.1FFT算法模块设计的层次划分 15
4.2旋转因子 15
4.2.1旋转因子模块 15
4.2.2旋转因子复数乘法器算法研究 15
4.3加/减法器 16
4.3.1端口命名 16
4.3.2加/减法器设计 17
4.4乘法器 18
4.4.1端口命名 18
4.4.2乘法器设计 18
4.5基-2蝶形处理器 19
小结 20
致谢 21
参考文献 22
附录 23
绪论
1.1FFT算法的研究现状及应用
数字信号处理是起源于十七和十八世纪数学的一个学科，当时加文(Garwin)在他的研究中极需要一个计算傅立叶变换的快速方法。他注意到图基(J.W.Turkey)正在写有关傅立叶变换的文章，因此详细询问了图基关于计算傅立叶变换的技术知识。图基概括地对加文介绍了一种方法，它实质上就是后来的著名的库利(CooleyJ.W)图基算法。在加文的迫切要求下，库利很快设计出一个计算机程序。1965年库利--图基在<计算数学>、MathematicofComputation杂志上发表了著名的“机器计算傅立叶级数的一种算法”文章，提出一种快速计算DFT的方法和计算机程序——揭开了FFT发展史上的第一页，促使FFT算法产生原因还有1967年至1968年间FFT的数字硬件制成，电子数字计算机的发明，使DFT的运算大大简化了。后来，经过人们对算法的改进，发展和完善了一套高速有效的运算方法，使得DFT的计算大大简化，运算时间一般可缩减一、二个数量级，从而使得DFT的运算在实际中真正得到了广泛的应用[3]。
现在，它在各个科学和技术领域中，已经成为一种重要的现代化工具。数字信号处理技术及其应用，目前正以惊人的速度向前发展着。快速傅里叶变换作为数字信号处理的一项重要内容，在众多学科领域(如信号处理、图像处理、生物信息学、计算物理、应用数学等)都有着广泛的应用。在高速数字信号处理领域，如雷达信号处理，FFT的处理速度往往是整个系统设计性能的关键所在。
1.2课题的提出
随着半导体集成电路和计算机技术的快速发展，数字信号处理逐渐成为一门具有丰富研究领域和理论体系的新兴学科，成为了整个数字化技术的基础。在信号与系统的分析方法中，除了时域分析方法外，还有变换域分析方法。在连续时间信号与系统中，变换域分析方法是z变换法和傅立叶变换法。同时，在数字信号处理中，有限长序列是很重要的序列，可以用z变换和福利也变化来研究它，但是，需要反应出它的“有限长”特点的一种有用工具就是离散傅立叶变换（DFT）[1]。而快速傅立叶变换（FFT）是DFT的一种快速的算法，所以研究FFT是数字信号处理的一个核心问题。
近年来，现场可编程门阵列(FPGA)以其高性能、高灵活性、友好的开发环境、在线可编程等特点，使得基于FPGA的设计可以满足实时数字信号处理的要求，在市场竞争中具有很大的优势。FPGA是在PAL、GAL、EPLD等可编程器件的基础上进一步发展的产物。它是作为专用集成电路（ASIC）领域中的一种半定制电路而出现的，既解决了定制电路的不足，又克服了原有可编程器件门电路数有限的缺点。在现代数字通信系统中，FPGA的应用相当广泛。尤其是在对基带信号的处理和整个系统的控制中，FPGA不但能大大缩减电路的体积，提高电路的稳定性，而且先进的开发工具使整个系统的设计调试周期大大缩短[2]。基于FPGA的这些特点，对FFT算法实现将有一个很大的帮助。
1.3FPGA实现FFT的优势
由于成本、系统功耗和面市时间的原因，许多通讯设备、视频、图像都不能通过简单地使用DSP处理器实现。现在，FPGA已经广泛地用于各种信号处理领域，它具有的灵活性和较高的性能可以让设计者满足不同方案的要求。
FPGA实现FFT算法的优势：
运行速度大大提高。FPGA有内置的高速加法器和乘法器，对于需要累加和乘法的重复使用效果更加明显。
FPGA存储的容量更大。FPGA芯片具有大量的高速存储器，不需要外接存储器就可以实现FFT的实时处理运算，所以其电路更为简单，集成度和可靠性也大大提高了。
FPGA是硬件可编程的。它不需要外接接口和控制电路的配合，使得硬件更加简单，占用空间更加少。
FPGA的管脚比较多，容易实现大规模系统。FPGA具有丰富的IO接口，使得与外设的连接更加方便[4]。
1.4本文的研究工作
本文主要研究的是FFT算法的FPGA实现，内容主要涉及了FPGA的基本结构与功能特点、VHDL硬件语言的描述、FFT算法的提出与分类、利用MAX+PLUSⅡ对算法进行仿真测试。第一章介绍了课题的引出、算法研究的现状及应用、用FPGA实现此算法的优势。第二章介绍的是可编程们阵列与VHDL的内容，对其基本结构和发展应用进行了系统的描述。第三章研究的是算法的实现，先介绍了离散傅立叶变换（DFT），再论述FFT算法概况和分类。第四章研究的是FFT算法的软件设计与仿真，并对结果进行分析。
可编程门阵列与VHDL
2.1可编程门阵列
随着半导体技术的飞跃发展，数字系统应用基本经历了分立元件、小规模集成电路（SSI）、中规模集成电路（MSI）和大规模集成电路（LSI）乃至超大规模集成电路（VLSI）的应用过程。数字系统应用的基本特征乃由中小规模集成度的标准通用集成电路、向用户定制的专用集成电路（ASIC）过渡。特别对于现代较复杂的数字系统，若采用SSI/MSI器件来设计某个特定的应用，不仅要占用很大的物理空间，反而功耗较大，可靠性差；而采用LSI/VLSI器件的专用电路设计，则具有相当高的系统集成度和相对小的功耗，但其开发周期长，开发费用高，具有较大的投资风险性，且有时仍需SSI/MSI器件来设计实现相应的接口逻辑。80年代出现的可编程逻辑器件（PLD—ProgrammableLogicDevices），在一定的程度上，为数字系统技术工程师的快捷、灵活设计提供了可能性，PLD器件的应用，使一系列功能强、速度高、灵活性大的积木式系统设计得以成功[5]。
但是，随着现代数字系统设计的发展，PLD器件无论在集成容量，功耗，速度乃至逻辑设计的灵活性上、均不能满足现代数字系统的大容量、高速度、现场灵活编程设计的要求。现场可编程门阵列器件的产生正是由此而来，起源于美国Xilinx公司的创造，它的英文是FieldProgrammableGateArray，简写为FPGA。它是在PAL、GAL、EPLD等可编程器件的基础上进一步发展的产物，从而显示了诱人的应用前景。同时，FPGA是作为专用集成电路（ASIC）领域中的一种半定制电路而出现的，既解决了定制电路的不足，又克服了原有可编程器件门电路数有限的缺点。有人预言，九十年代的许多电子系统将以CPU十RAM十FPGA的构成为特征，反映了现代数字系统设计的一种趋势。
2.1.1FPGA的基本结构
FPGA是由若干独立的可编程逻辑模块组成的，用户可以通过编程将这些模块连接成所需要的数字系统。FPGA属于高密度PLD，其集成度可达3万门/片以上。FPGA由三个可编程单元和一个用于存放编程数据的静态存储器组成。这三个可编程单元由可配置逻辑模块CLB（ConfigurableLogicBlock）、输出输入模块IOB（InputOutputBlock）和互连资源IR（InterconnectResourse）3个部分组成。FPGA的工作状态全部由编程数据存储器中数据设定。其中，FPGA的大部分引脚都是与可编程的IOB相连，都可以根据需要设置成输入或输出端。因此，FPGA器件的输入端和输出端要比同等规模的EPLD多，在实际中应用更加广泛。每个CLB中都包含组合逻辑电路和存储电路（触发器）两部分，可以用来设计成规模不大的组合逻辑电路或时序逻辑电路[5]。
2.1.2FPGA的基本特点
FPGA的基本特点主要有：
（1）采用FPGA设计ASIC电路，用户不需要投片生产，就能得到合用的芯片。
（2）FPGA可做其它全定制或半定制ASIC电路的中试样片。
（3）FPGA内部有丰富的触发器和I／O引脚。
（4）FPGA器件内部的CLB、IOB和ICR均可以进行编程，可以实现多个变量的任一逻辑。
（5）FPGA是ASIC电路中设计周期最短、开发费用最低、风险最小的器件之一。
（6）FPGA采用高速CHMOS工艺，功耗低，可以与CMOS、TTL电平兼容。
基于上述的特点，可以说，FPGA芯片是小批量系统提高系统集成度、可靠性的最佳选择之一。同时，FPGA是由存放在片内RAM中的程序来设置其工作状态的，因此，工作时需要对片内的RAM进行编程。用户可以根据不同的配置模式，采用不同的编程方式[14]。
2.1.3FPGA的配置模式与功能
FPGA有多种配置模式：并行主模式为一片FPGA加一片EPROM的方式；主从模式可以支持一片PROM编程多片FPGA；串行模式可以采用串行PROM编程FPGA；外设模式可以将FPGA作为微处理器的外设，由微处理器对其编程。
FPGA芯片在加电时，将EPROM中数据读入片内编程RAM中，配置完成后，FPGA进入工作状态。掉电后，FPGA恢复成白片，内部逻辑关系消失，因此，FPGA能够反复使用。FPGA的编程无须专用的FPGA编程器，只须用通用的EPROM、PROM编程器即可。当需要修改FPGA功能时，只需换一片EPROM即可。这样，同一片FPGA，不同的编程数据，可以产生不同的电路功能。因此，FPGA的使用非常灵活。
2.2VHDL的出现
电子技术的发展，特别是专用集成电路（ASIC）设计技术的日趋进步和完善，推动了数字系统设计的迅猛发展。电子技术自动化（EDA）工具给电子设计带来巨大变革，特别是硬件描述语言的出现和发展，解决了传统的电路原理图设计大系统工程时的诸多不便，成为电子电路设计人员的最得力助手。其实，早在20世纪80年代后期，各个ASIC研制和生产厂商为了缩短产品开发周期，提高产品在市场上的竞争力，就相继开发了用于各自目的的硬件描述语言，如ABEL，AHDL等。但是由于没有统一的标准，这些语言的发展受到了限制。1987年12月，IEEE对美国国防部开发的超高速集成电路硬件描述语言（VHDL，VeryHighSpeedIntegrateCircuitHardwareDescriptionLanguage）进行了标准化的工作，得到广大用户的一致欢迎。自此以后，VHDL成为数字电子系统设计的“世界语”，各个CAD厂商都努力使自己的电子设计软件与VHDL兼容，各高等院校都开设了VHDL设计课程。发展集成电路事业是我国制定的新世纪的重要发展目标，也是经济全球化新形势下的科技挑战[6]。
2.2.1VHDL硬件描述语言
VHDL是面向对象的，可以提高设计者在较高的设计层次上描述模型的能力，帮助设计者实现更复杂设计、更大规模的元件的重用。面向对象的方法在软件开发中已被广泛地接受，它不仅仅是一种新的程序设计技术，而且是一种全新设计和构造软件的思维方法，它是计算机解决问题的方式更加类似于人类的思维方式和更强的管理能力。面向对象的语言必须包含抽象性、可封装性、模块化、层次化及信息机制。抽象性意味着一个对象的特性可以在类描述中文档化。可封装性是指代码和数据必须保存在同一单元中，封装性可有选择性的隐藏信息，使得某些信息对外界不可取。模块化定义了单元的重用。层次化使得对象的行为精炼，不必重复设立前驱中已有的内容[7]。
2.2.2VHDL的基本结构
一个完整的VHDL程序，或者说设计实体，通常要求最低能为VHDL综合器所支持，并能作为一个独立的设计单元，即元件的形式而存在的VHDL程序。在VHDL程序中，通常包含实体（ENTITY）、结构体（ARCHITECTURE）、配置（CONFIGURATION）、包集合（PACKAGE）和库（LIBRARY）5个部分。
实体和构造体这两个基本结构是必须的，它们可以构成最简单的VHDL程序。实体包含了对设计工程的输入和输出的定义说明，而设计实体则包含了实体和结构体两个在VHDL程序中最基本的组成部分。一个实用的VHDL程序可以由一个或多个设计实体组成，可以将一个设计实体作为一个完整的系统直接利用，也可以将它作为其他设计实体的一个低层次结构，即元件例化，就是用实体来说明一个具体的器件。包集合存放各设计模块都能共享的数据类型、常数和子程序等。配置用于从库中选取所需单元来组成系统设计的不同版本。库存放已经编译的实体、构造体、包集合和配置。
VHDL程序的一个显著的特点就是，任何一个完整的设计实体都可以分为内外两个部分：外面的部分称为可视部分，由实体名和端口组成；里面的部分称为不可视的部分，由实际的功能描述组成。一旦对已完成的设计实体定义了它的可视界面后，其他的设计实体就可以将其作为已开发好的结果直接调用，这正是一种基于由上至下多层次的系统设计概念的实现途径。
FFT算法研究
3.1傅立叶变换
傅立叶变换的4种可能形式：（1）连续时间、连续频率；（2）连续时间、离散频率；（3）离散时间、连续频率；（4）离散时间、离散频率。见下表
时间函数 频率函数 连续和非周期 非周期和连续 连续和周期（） 非周期和离散（） 离散（T）和非周期 周期（）和连续 离散（T）和周期（） 周期（）和离散（） 表3.1四种傅立叶变换形式的归纳
3.2离散傅立叶变换
设是长度为N点的有限长信号，即信号仅仅分布在[0，N-1]区间，其余均为0，那么，该信号的离散傅立叶变换的定义如下：
(3-1)
一般情况下，x(n)为复数序列，对每一个k值，计算X（k）需要进行N次复数乘法，次复数加法。因此，对于N个k值，共需计算次复数乘法及次复数加法。即计算全部DFT，需要运算。例如，当N取1024时，共需计算2097152次。可见当时，运算次数是相当大的，要对信号进行DFT分析，不管是软件实现还是硬件实现，要做到实时都是不可能的[8]。
3.3FFT的基本思想
直到1965年发现了DFT的一种快速算法以后，情况才发生了根本的变化。在1965年，基图（J.W.Tuky）和库利（T.W.Coody）在《计算机数学》杂志上发表了著名的《机器计算傅立叶级数的一种算法》论文，之后桑德（G.Sand）-图基等快速算法相继出现，又经人们进行改进，很快形成一套高效运算方法，这就是现在的快速傅立叶变换，简称FFT(FastFourierTransform)。这种算法使DFT的运算效率提高1～2个数量级，为数字信号处理技术应用于各种信号的实时处理创造了良好的条件，大大推动了数字信号处理技术的发展。1984年，法国的杜哈梅尔（P.Dohamel）和霍尔曼（H.Hollamann）提出的分裂基快速算法，使运算效率进一步提高[10]。
FFT算法的基本思想就是：把长度为N的序列分成几个较短的序列，利用旋转因子
的周期性和对称性来减少DFT的运算次数，旋转因子的周期性和对称性如下所示：
(3-2)
(3-3)
(3-4)
基2FFT（即时的FFT）算法可以分为两大类：时域抽取法FFT（Decimation-In-TimeFFT,简称DIT-FFT）和频域抽取法FFT（Decimation-In-FrequencyFFT,简称DIF-FFT）。
3.4快速傅立叶变换
快速傅立叶变换（FFT：FastFourierTransform）是离散傅立叶变换的一种快速算法。在功能上，FFT与DFT完全一致，都是计算有限长离散信号x(n)的离散频谱X(k)，但是，FFT的运算效率比DFT要高很多。例如：计算1024点短时信号的离散频谱，FFT的速度大约比DFT快200倍。另外，FFT算法要求信号长度N是2的整数幂，即，如256、512和1024等[9]。
为了便于分析比较，首先看一下N点有限长信号x(n)的离散傅立叶变换的运算量。根据DFT计算公式，得
（3-5）
尽管实际应用中信号x(n)一般是实信号，这里假设它为一个复数信号，则从式（3-5）可以知道N点DFT的运算量如下：
复数乘法次数：,复数加法次数：
实数乘法次数：,实数加法次数：
在时间计算中，乘法运算所需的指令周期数往往远大于假发所需的指令周期数，因此，在算法的效率分析中主要观察乘法计算次数，加法运算次数一般可以忽略不记。当然，这里有必要指出，对于目前广泛应用的DSP微处理器来说，由于片内有专用乘法累加器，乘法计算所需的指令周期数与加法相差不大，此时，加法运算量的分析与乘法运算量应该同等看待。
3.4.1基于时选的快速傅立叶变换
基于时选的FFT算法通过将时域信号x(n)分成偶数和奇数序列并分别计算离散傅立叶变换来减少计算量。
设信号x(n)的长度是，将它分成偶数序列和奇数序列，这样，求x(n)的离散傅立叶变换X(k)可以转换成求的离散傅立叶变换和的离散傅立叶变换，如下：
(3-6)
定义
(3-7)
则（1.2-2）式可进一步转化为
（3-8）
其中,是偶数序列的点DFT，而是奇数序列的点DFT。但是，是的N点DFT，其k的取值范围是，与和的取值范围有差别。当时，应该利用和的周期性特征计算，即。
（3-8）式说明，一个N点DFT可以分解成两个点的DFT组合。例如，一个8点DFT的分解示意如图1.1。这样做的好处是N点DFT的复数乘法次数从原来的减少为，运算效率提高了一倍。
图3.18点DFT分解成两个4点DFT
显然，（3-8）式中点离散傅立叶变换和可以进一步分解成4个点的DFT，并且，只要N满足2的幂这一条件，这种分解就可以一直进行下去。例如，对于图1.1点DFT，进一步的如图3.2和图3.3所示。
图3.24点DFT分解成两个2点DFT
图3.32点DFT的分解
根据逐步分解原理，一个8点DFT的计算最终可以用图3.4来描述。可以看到，整个DFT的计算被分解成3级，其中每一级的复数乘法计算次数为8，因此，总的复数乘法计算次数是。图1.4所描述的就是8点离散傅立叶变换的FFT算法，它比标准的DFT计算方法减少了40次复数乘法。
仔细分析（3-8）式和图3.4可以发现，因为，所以每次分解奇偶序列的复数因子和是可以公用的。这样，图3.4就可以转化为图1.5，每一级的复数乘法次数为4，总的复数乘法计算量为12，比图3.4中的运算量减小了一半。
图3.4基于时选的8点FFT算法
对于长度为的信号x(n),分解的次数为，每一级的复数乘法次数是，因此，总的复数乘法次数为。所以，基于时选的FFT算法和DFT的运算量之比可以用下式表示：
(3-9)
3.4.2基于频选的快速傅立叶变换
基于频选的FFT算法通过将DFT值分成偶序列
和奇序列,并分别计算，从而进行运算量的简化。
设信号x（n）的长度为，则的点数也是N，其表达式如下：
(3-10)
令，则上式成为
(3-11)
将分成偶序列和奇序列分别计算，则
(3-12)
（3-13）
（312）式和（3-13）式表明，可以转化成两个点的DFT计算。设，则其按照（3-12）和（3-13）分解计算DFT的流程如图3.6所示。
显然，（3-12）式和（3-13）式可以进一步推导，将点偶数DFT和奇数DFT分解成4个点的DFT，并且，这种分解可以一直进行下去，直到全部分解为止。例如，图3.6中的2个4点DFT可以进一步分解成4个2点DFT，其分解的方式仍然是将4点DFT分解为偶数和奇数序列分别计算，如图3.7。最后，4个2点DFT也被进一步细化，形成最终的基于频选的8点FFT流程，如图3.8所示。
从图3.8可以看出，8点FFT也是进行了3次DFT分解计算，每次需要复数乘法的次数是4次，因此，总的复数乘法次数为12
对于长度为的信号，DFT分解将一直进行到2点DFT，共进行级分解，每次需要次复数乘法，因此，总的复数乘法次数为，与基于时选的FFT算法一致。也就是说，无论从哪一种FFT算法，其运算效率都是一样的。实际上，基于频选的FFT算法流程图（如图3.8）和基于时选的FFT算法流程图（如图3.5）是互为转置关系，运算效率理所当然是一致的。
3.5FFT算法的类型
FFT算法有以下几种：（1）N为复合数的FFT算法；（2）基-4FFT算法；（3）分裂基FFT算法[11]。
1.复合数的FFT算法
当N为复合数时，可以把它分解成一些因子的乘积，再用FFT的一般算法来计算，即为混合基FFT算法。需要计算N点的DFT，它的式子如下：
(3-14)
2.基-4FFT算法
当混合基FFT算法中的，即时就是基-4FFT算法。将n和k分别用下面式子代替即可。
(3-15)
(3-16)
3.分裂基FFT算法
分裂基FFT算法的核心思想是对偶序列使用基-2FFT算法，对奇序列使用基-4FFT算法。它是目前针对于的算法中具有最少乘法次数的算法，且具有基-2FFT算法同样好的通知运算结构，因此被认为是比较好的FFT算法。
将分成三个子序列：(3-17)
(3-18)
(3-19)
第4章FFT算法的软件设计与仿真
4.1FFT算法模块设计的层次划分
基-2FFT可以用蝶形处理器来实现。这种处理器除了蝶形本身之外，还包括额外的旋转因子复数乘法器。基-2蝶形处理器是有一个复数加法器、一个复数乘法器和一个旋转因子的复数乘法器组成。但是只用3次实数乘法和3次加/减法运算构造复数乘法器也是可以实现的。
4.2旋转因子
4.2.1旋转因子模块
旋转因子的复数乘法器通常由3次实数加法器和3次加/减法运算实现。旋转因子乘法器的模块框图如下：
图4.1旋转因子乘法器的模块框图
4.2.2旋转因子复数乘法器算法研究
旋转因子复数乘法是可以简化的，因为C和S可以预先计算，并储存在一个表中。而且还可以储存以下的3个系数：C、C+S、C-S。有了这3个预先计算的因子，我们首先可以计算：和。然后用：和计算最后的乘积。
检验：
所以，所设计的算法使用了3次乘法、1次加法和2次减法。
4.3加/减法器
4.3.1端口命名
下表给出了add的所有INPUT端口
端口名称 是否必需 描述 说明
cin
否 到低阶位的进位。如果运算是“ADD”，则低=0，高=+1。如果运算是“SUB”，则低=-1，高=0 如果省略，默认值是0（也就是如果运算是“ADD”，为低，如果运算是“SUB”，为高） dataa 是 被加器/被减器 输入端口LPM_WIDTH宽度 datab 是 加数/减数 输入端口LPM_WIDTH宽度
add_sub
否 如果信号为高电平，则运算=dataa+datab;如果信号为低电平，则运算=dataa-datab。 如果使用了LPM_DIRECTION参数，就不能使用add_sub。如果省略，则默认值是“ADD”。Altera推荐使用LPM_DIRECTION参数来指定add函数的运算，而不是为add端口指定一个常数。 clock 否 用于流水线用法的时钟 时钟端口为add函数提供流水线操作。如果PIPELINE值不为0（默认值），则必须连接clock端口。 clken 否 用于流水线用法的时钟使能端 仅适用于VHDL aclr 否 用于流水线用法的异步清零 流水线初始化成未定义的（X）逻辑电平。使用aclr端口可以在任一时刻将流水线设置成全0，与clock信号异步。 表4.1加/减法器的INPUT端口
下表给出了add的所有OUTPUT端口
端口名称 是否必需 描述 说明 result 是 dataa+或-,datab+或-,cin 输出端口宽度
cout
否
MSB的进位输出或输入 如果使用了overflow，就不能使用cout。cout端口具有作为MSB的进位输出或输入的物理解释。cout对在“UNSIGNED”运算中检测溢出的操作至关重要
overflow
否
结果超出可能的精确度 如果使用了overflow，就不能使用cout。overflow端口具有作为MSB的进位输出与MSB的进位输入的XOR运算的物理解释。只有在REPRESENTATION参数值是“SIGNED”时，才有意义 表4.2加/减法器的OUTPUT端口
4.3.2加/减法器设计
三个加/减法器的设计中，运用了三个不同的位长(17,9,8)来实现。其中以位长为17为例，程序如下：
LIBRARYIEEE;
USEIEEE.STD_LOGIC_1164.ALL;
USEIEEE.STD_LOGIC_UNSIGNED.ALL;
ENTITYadd2IS
GENERIC(
WIDTH:integer:=17);
PORT(dataa,datab:INSTD_LOGIC_VECTOR(WIDTH-1DOWNTO0);
add_sub:inSTD_LOGIC;
result:OUTSTD_LOGIC_VECTOR(WIDTH-1DOWNTO0));
ENDadd2;
ARCHITECTUREyeOFadd2IS
signalresult_tep:STD_LOGIC_VECTOR(WIDTH-1DOWNTO0);
BEGIN
PROCESS(add_sub,dataa,datab)
BEGIN
if(add_sub=''0'')then
result_tep<=dataa-datab;
else
result_tep<=dataa+datab;
endif;
result<=result_tep;
ENDPROCESS;
ENDye;
芯片元器件如下图所示
图4.2ADD2芯片图
4.4乘法器
4.4.1端口命名
下表给出了mult的所有INPUT端口。
端口名称 是否必需 描述 说明 dataa 是 被乘数 输入端口dataa宽度 datab 是 乘数 输入端口datab宽度 sum 否 部分和 输入端口sum宽度 clock 否 用于流水线用法的时钟 时钟端口为mult函数提供流水线操作。如果LPM_PIPELINE值不为0，必须连接clock端口 clken 否 用于流水线用法的时钟使能端 仅适用于VHDL aclr 否 用于流水线用法的异步清除 流水线初始化成未定义的（X）逻辑电平。使用aclr端口可以在任一时刻将流水线设置成全0，与clock信号异步 表4.3乘法器的INPUT端口
下表给出了mult的所有OUTPUT端口。
端口名称 是否必需 描述 说明 result 是 Result=dataadatab+sum, 输出端口result的宽度。 表4.4乘法器的OUTPUT端口
4.4.2乘法器设计
程序如下：
LIBRARYIEEE;
USEIEEE.STD_LOGIC_1164.ALL;
USEIEEE.STD_LOGIC_UNSIGNED.ALL;
ENTITYmultIS
GENERIC(LPM_WIDTHA:POSITIVE;
LPM_WIDTHB:POSITIVE;
LPM_WIDTHS:POSITIVE;
LPM_WIDTHP:POSITIVE;
LPM_REPRESENATION:=STRING:="UNSIGNED";
WIDTH:integer:=17);
PORT(dataa:INSTD_LOGIC_VECTOR(WIDTHA-1DOWNTO0);
datab:INSTD_LOGIC_VECTOR(WIDTHB-1DOWNTO0);
sum:INSTD_LOGIC_VECTOR(WIDTHS-1DOWNTO0);
add_mult:inSTD_LOGIC;
result:OUTSTD_LOGIC_VECTOR(WIDTHP-1DOWNTO0));
ENDmult;
ARCHITECTUREshuOFmultIS
n:veriable:integerWIDTH-1downto0;
signalresult_tep:STD_LOGIC_VECTOR(WIDTH-1DOWNTO0);
BEGIN
PROCESS(add_mult,dataa,datab,sum)
BEGIN
if(n
result_tep<=dataadatab+sum;
n=n+1;
endif;
result<=result_tep;
ENDPROCESS;
ENDshu;
4.5基-2蝶形处理器
基-2蝶形处理器是有一个复数加法器、一个复数乘法器和一个旋转因子的复数乘法器组成。它的实现通过反复调用4.4节中程序来实现。框图如下所示。程序见附录
图4.3基-2蝶形处理器框图
整个程序的实现见附录
小结
数字信号处理技术的研究应用在学术界和工业界一直受到普遍的关注。一方面，对于数字信号处理的应用已经越来越多，比如视频压缩、数字机顶盒、有线调制解调器、语音处理、雷达成像、全球定位系统等等。另一方面，信息技术领域对数字信号处理的要求也越来越高。其中快速傅立叶变换是数字信号处理的一种重要的算法研究。快速傅立叶变换算法的实现，大大缩短了运算所需的时间，降低了因计算复杂而导致的计算误差。FPGA是近年来出现的一种新的可编程逻辑器件，有着运行速度快、存储容量大、管脚多等的特点电子系统的设计中发挥了重要的作用。
本论文是对利用现场可编程门阵列来实现快速傅立叶变换算法进行了详细的说明。较系统地描述了该课题的背景、研究现状、意义等，使读者对本课题有一定的了解与认识。同时，对快速傅立叶变换的两种抽取方法做了较全面的介绍，其中重点介绍了基2按时间抽取的快速傅立叶算法，并介绍了FFT算法的软件实现，并对结果进行了分析。
致谢
本文是在导师冯燕尔的精心指导和严格要求下完成的。导师渊博的知识、严谨求学的治学态度和诲人不倦的学者风范以及她实事求是、认真负责的工作作风鼓励着我。在此衷心感谢冯老师在学业上对我的殷殷教诲。
感谢我的父母和同学，在我求学期间，他们给了我无尽的支持和无私的关爱，使得我可以安心完成学业。
最后，衷心感谢各位专家学者为论文审阅工作付出的辛勤劳动。
【参考文献】
[1]程佩青.数字信号处理教程（第二版）[M].北京：清华大学出版社.2001.8
[2]朱明程.现场可编程逻辑门陈列器件FPGA原理及应用设计[M].1994年
[3]胡广书.数字信号处理-理论、算法与实现[M].北京：清华大学出版社,1997
[4]贝斯著,刘凌、胡永生译.数字信号处理的FPGA实现[M].北京：清华大学出版社，2002
[5]褚振勇,翁木云.FPGA设计及应用[M].西安:西安电子科技大学出版社,2002
[6]辛春燕.VHDL硬件描述语言[M].北京：国防工业出版社，2002.1
[7]赵鑫等.VHDL与数字电路设计.北京：机械工业出版社，2005.4
[8]方勇.数字信号处理——原理与实践[M].北京：清华大学出版社，2006.3
[9]俞一彪,孙兵.数字信号处理——理论与应用[M].南京：东南大学出版社，2005.7
[10]俞卞章.数字信号处理[M].西安：西北工业大学出版社，2002.8
[11]门爱东,杨波,全子一.数字信号处理[M].北京：人民邮电出版社，2003.4
[12]付家才.EDA原理与应用[M].北京：化学工业出版社，2001.5
[13]帕里著,陈弘毅译.VLSI数字信号处理系统设计与实现[M].北京：机械工业出版社，2004.6
[14]http://baike.baidu.com/view/51371.htm
[15]http://translate.google.cn
附录
LIBRARYieee;
USEieee.std_logic_1164.ALL;
USEieee.std_logic_arith.ALL;
PACKAGEmul_packageIS
COMPONENTccmul
GENERIC(W2:INTEGER:=17;--Multiplierbitwidth
W1:INTEGER:=9;--Bitwidthc+ssum
W:INTEGER:=8);--Inputbitwidth
PORT
(clk:INSTD_LOGIC;--Clockfortheoutputregister
x_in,y_in,c_in:INSTD_LOGIC_VECTOR(W-1DOWNTO0);
cps_in,cms_in:INSTD_LOGIC_VECTOR(W1-1DOWNTO0);
r_out,i_out:INSTD_LOGIC_VECTOR(W1-1DOWNTO0));
ENDCOMPONENT;
ENDmul_package;
LIBRARYwork;
USEwork.mul_package.ALL;
LIBRARYieee;
USEieee.std_logic_1164.ALL;
USEieee.std_logic_arith.ALL;
LIBRARYieee;
USEieee.std_logic_1164.ALL;
USEieee.std_logic_arith.ALL;
USEieee.std_logic_unsigned.ALL;
ENTITYbfprocIS
GENERIC(W2:INTEGER:=17;
W1:INTEGER:=9;
W:INTEGER:=8);
PORT
(clk:STD_LOGIC;
Are_in,Aim_in,c_in,--8bitinputs
Bre_in,Bim_in:INSTD_LOGIC_VECTOR(W-1DOWNTO0);
cps_in,cms_in:INSTD_LOGIC_VECTOR(W-1DOWNTO0);
Dre_out,Dim_out,Ere_out,Eim_out:OUTSTD_LOGIC_VECTOR(W-1DOWNTO0));
ENDbfproc;
ASCHITECTUREflexOFbfprocIS
SIGNALdif_re,dif_im:STD_LOGIC_VECTOR(W-1DOWNTO0);
SIGNALAre,Aim,Bre,Bim:integerRANGE-128TO127;
SIGNALc:STD_LOGIC_VECTOR(W-1DOWNTO0);
SIGNALcps,cms:STD_LOGIC_VECTOR(W-1DOWNTO0);
SIGNALCre,Cim:STD_LOGIC_VECTOR(W-1DOWNTO0);
BEGIN
PROCESS--Computetheadditionsofthebutterflyusing
BEGIN--integerandstoreinputsinflip-flops
WAITUNTILclk=''1'';
Are<=CONV_INTEGER(Are_in);
Aim<=CONV_INTEGER(Aim_in);
Bre<=CONV_INTEGER(Bre_in);
Bim<=CONV_INTEGER(Bim_in);
c<=c_in;--Loadfrommemorycos
cps<=cps_in;--Loadfrommemorycos+sin
cms<=cms_in;--Loadfrommemorycos-sin
Dre_out<=CONV_STD_LOGIC_VECTOR((Are+Bre)/2,W);
Dim_out<=CONV_STD_LOGIC_VECTOR((Aim+Bim)/2,W);
ENDPROCESS;
PROCESS(Are,Bre,Aim,Bim)
BEGIN
dif_re<=CONV_STD_LOGIC_VECTOR(Are/2-Bre/2,8);
dif_im<=CONV_STD_LOGIC_VECTOR(Aim/2-Bim/2,8);
ENDPROCESS;
ccmul_1:ccmul
GENERICMAP(W2=>W2,W1=>W1,W=>W)
PORTMAP(clk=>clk,x_in=>dif_re,y_in=>dif_im,
c_in=>c,cps_in=>cps,cms_in=>cms,
r_out=>Ere_out,i_out=>Eim_out);
ENDflex;
东海科学技术学院本科生毕业论文
I
东海科学技术学院本科生毕业论文
I
X1(3)
X1(2)
X1(1)
X1(0)
X0(3)
X0(2)
X0(1)
X0(0)
x(4)（4）
4点
DFT
4点
DFT
x(2)（2）
x(0)（0）
x(6)（6）
x(5)
x(1)
x(3)
x(7)
X(2)
X(0)
X(1)
X(3)
X(4)
X(5)
X(6)
X(7)
加/减法器
2点
DFT
2点DFT
X0(0)
X0(1)
G0(0)
G0(1)
X0(2)
G0(0)
G0(1)
X0(3)
x(2)
x(4)
x(0)
x(6)
加/减法器
x(4)
x(0)
G0(1)
G0(0)
加/减法器
x(0)
x(4)
x(2)
x(6)
x(1)
x(5)
x(3)
x(7)
X(3)
X(0)
X(1)
X(2)
X(4)
X(5)
X(6)
X(7)
实数乘法器
-1
-1
-1
-1
-1
-1
-1
-1
x(0)
x(4)
x(2)
x(6)
x(1)
x(5)
x(3)
x(7)
X(3)
X(0)
X(1)
X(2)
X(4)
X(5)
X(6)
X(7)
-1
-1
-1
-1
图3.5基于时选的FFT算法改进形式
-1
-1
x(6)
x(4)
x(2)
x(0)
x(1)
x(3)
x(5)
x(7)
X(4)
X(3)
X(6)
X(0)
X(2)
X(1)
X(5)
X(7)
4点
DFT
4点
DFT
图3.68点DFT分解成4点DFT
-1
-1
-1
x(6)
x(4)
x(2)
x(0)
x(1)
x(3)
x(5)
x(7)
-1
-1
-1
-1
-1
-1
2点
DFT
2点
DFT
2点
DFT
2点
DFT
X(6)
X(4)
X(2)
X(0)
X(1)
X(3)
X(5)
X(7)
图3.74点DFT的进一步分解
图3.8基于频选的8点FFT算法
-1
X(5)
X(0)
X(4)
X(1)
X(3)
X(7)
X(6)
-1
x(3)
x(1)
x(2)
x(0)
x(4)
x(6)
x(5)
x(7)
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
实数乘法器
输出端
输入端
旋转因子的复数乘法器
复数乘法器
复数加法器
输出端口
输入端口
实数乘法器
|
|
