基于FPGA的FFT设计毕业论文(32页).doc

《基于FPGA的FFT设计毕业论文(32页).doc》由会员分享，可在线阅读，更多相关《基于FPGA的FFT设计毕业论文(32页).doc（32页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、-基于FPGA的FFT设计毕业论文-第 25 页诚 信 承 诺 书本人承诺：所呈交的论文是本人在导师指导下进行的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签 名： 日 期： 本论文使用授权说明本人完全了解南通大学有关保留、使用学位论文的规定，即：学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容。（保密的论文在解密后应遵守此规定）学生签名： 指导教师签名： 日期： 摘 要快速傅里叶变换（FFT）是一种为了改进和提高离散傅里叶

2、变换（DFT）运算速度而提出的算法。它是根据已有的DFT的运算特性发展起来的DFT快速算法。快速傅里叶变换的理论在信号处理、数字通信、语音处理和计算机等诸多领域有着广泛的运用。在不同的运用场合，对FFT电路的性能有着不同的要求，但是在很多领域都要求FFT处理器能够具有高速度、高精度和实时性的工作状态。现场可编程门阵列（FPGA）是由许多独立的可编程逻辑模块组成一种新型可编程器件。FFT运算结构相对比较简单和固定，适合使用FPGA进行硬件实现，并且能兼顾速度及灵活性。本文介绍了一种基于FPGA上实现32点FFT变换的设计方案。整个FFT模块采用基-2时域抽取，顺序输入，逆序输出的方法实现。将采集

3、到的数据通过编写串口程序输入，再运用复数乘法器为核心设计了FFT算法中的基-2蝶形运算单元、溢出控制单元和地址与逻辑控制模块等其它模块，并以这些模块和FPGA内部的双口RAM为基础组成了基-2FFT算法模块，将经过处理的数据由串口程序输出，并且对运算结果使用MATLAB软件对比验证。关键词：快速傅里叶变换，FPGA，旋转因子，基-2ABSTRACTFast Fourier Transform (FFT) is a algorithm in order to improve and enhance the computing speed of the Discrete Fourier Trans

4、form (DFT). It is a DFT fast algorithm according to the development of the operational characteristics of the existing DFT. The theory of FFT is widely used in many fields such as signal processing, digital communications, voice processing, and computer. In different applications, the performances o

5、f the FFT circuit have different requirements, but in many areas FFT processor is required with high speed, high accuracy and real-time work status.Field Programmable Gate Array (FPGA) is a new type programmable device which is composed by a number of independent programmable logic module. The struc

6、ture of FFT computation is relatively simple and fixed, suitable for the use of FPGA hardware implementation, and also can take the speed and flexibility into account. This article introduces a 32-point FFT transform design which is based on FPGA. The entire module uses Radix-2 time-domain extractio

7、n, the order of input, output reverse method. Input data using the serial interface program and using a complex multiplier as the core design of FFT algorithm in the Radix-2 butterfly unit, overflow control unit and address and logical control module and other modules, and within these modules and F

8、PGA-based dual-port RAM formed the Radix-2 FFT algorithm module, output the processed data from the serial interface program, and using MATLAB software for comparison and validation of calculation results. Keywords: FFT, FPGA, Rotation factor, Radix-2目 录摘 要IABSTRACTII第一章 绪 论11.1数字信号处理概论11.2数字信号处理的发展

9、趋势11.3 所做的主要工作2第二章 FPGA的基础知识32.1 FPGA的简介32.2 FPGA较其他器件优点32.3 开发软件简介42.3.1 Quartus II软件介绍42.3.2 Quartus II软件设计流程52.4 Verilog HDL的简介52.5 本章小结6第三章 FFT算法原理73.1 快速傅里叶变换73.2 基-2FFT算法73.2.1 基-2FFT算法原理73.2.2 基-2FFT算法特点113.3 本章小结13第四章 FFT的FPGA实现144.1 整体结构设计144.2 蝶形运算单元154.3 逻辑控制及其他辅助单元174.3.1 逻辑控制单元174.3.2 其

10、他辅助模块184.4 存储单元204.5 串口通信单元224.6 FFT整体实现244.7 本章小结26第五章 系统的仿真与测试275.1 实验结果及分析275.2 本章小结29结束语30参考文献31致 谢32第一章 绪 论1.1数字信号处理概论随着现代计算机与信息技术的不断飞速发展，对数字信号处理系统的运行处理速度要求也越来越高。数字信号处理系统的研究人员一直在寻找各种优化的算法来解决信号处理中遇到的棘手问题。其实质就是通过相应的软件与硬件的结合，将模拟信号或者其他的一些信号转换为数字信号并加以相应的处理。在数字信号处理领域中部分数据可以在完成所有采集之后再进行处理，这些数据对系统的实时性处

11、理要求较低，利用通用的计算机系统既可以完成处理。这一类数字信号处理在计算机上编写程序，修改和运行，并对结果进行分析就能满足要求。还有一类数字信号处理必须在规定的时间内完成，比如手机通话和雷达系统等。有的数字信号处理对时间的要求十分严格，甚至使用高速的通用微处理器芯片也无法满足性能需要，因此在这种情况下就必须为这样的运算设计专用的硬线逻辑电路，通过FPGA器件上实现或者制成高速专用集成电路。因此，对数字信号的实时处理一方面也是建立在高速大规模集成电路不断发展的基础上的。另一方面，对数字信号处理实时性的要求不断提高，也推动了高速大规模集成电路制造技术的进步1。经过几十年的发展，数字信号处理（DSP

12、）作为一项成熟的技术，已经在诸多领域取得了广泛的运用，并且一些方面有逐步取代传统的模拟信号处理系统的趋势。DSP系统具有以下几项优点：如数字元器件对温度变化老化及元件容差不敏感。相比较模拟信号，数字信号在精度、灵活性、线性相位、多维处理等方面具有明显优势。有两个事件加速了DSP技术的发展，其一是Cooley和Tuckey（1956年）揭示了一种计算离散傅里叶变换（Discrete Fourier Transform ，DFT）的有效算法。而另一个重大转折就是在20世纪70年代后期可编程数字信号处理器（Programmable Digital Signal Processor，PDSP）引入。1

13、.2数字信号处理的发展趋势数字信号处理在很多领域运用广泛，比如信号处理、数字通信、语音识别、雷达系统等。传统的使用软件处理来实现这些算法，缺点明显：速度慢、效率低，已经无法满足现代通信中对于信号处理的实时性越来越高的要求。数字信号处理发展的一个明显趋势就是：高速和实时。在一些情况下，即使通用信号处理器（DSP）也无法满足系统的性能要求。近年来，现场可编程门阵列（FPGA）凭借着其更高的集成度、更强的逻辑实现能力和更好的设计灵活性，逐渐在数字信号处理领域获得越来越广泛的应用。它作为专用集成电路（ASIC）中的一种半定制电路，相对于DSP有着成本、性能和灵活性等方面的优点。FPGA是一种直接由硬件

14、实现的器件，它由逻辑功能块排成阵列组成，内部含有很多相同的运算单元，所以当使用FPGA在作数字信号处理时，速度会远远高于通用的DSP芯片。在实现实时处理方案时往往需要使用多个DSP芯片，从而提高了产品的价格、功耗和开发周期。特别是伴随近年来FPGA的集成规模、运算速度不断提高，系统设计和调试方法更加丰富，其在数字信号处理方面应用会更加广泛。1.3 所做的主要工作随着FPGA技术的不断成熟和FFT算法在诸多领域的广泛应用，所以利用FPGA芯片进行FFT系统设计的方案越来越多。因为FPGA芯片的重复可编程特点和具有丰富的逻辑单元，所以非常适合于算法比较固定、运算数据量大的实时数字信号处理。研究是在

15、国内外专家学者的研究基础之上进行的，本论文主要FFT算法的FPGA实现，重点是运用Quartus II软件模拟仿真。全文共分为五章，各章节的主要内容安排如下：第一章为绪论，简要介绍了数字信号处理技术的研究背景、意义和发展趋势。第二章对FPGA的基础知识进行了简单的介绍，以及使用FPGA进行开发的优点。然后对本次研究需要使用的Quartus II软件和Verilog HDL的使用予以介绍。第三章对FFT算法的原理进行介绍。了解快速傅里叶变换的主要内容后，论文着重介绍了FFT算法原理和特点。其中包括理论知识、算法实现和主要特点。第四章介绍FFT的FPGA的实现，首先描述整体的设计思路，再对使用硬件

16、描述语言实现的各个模块进行介绍和分析。第五章为通过使用Quartus II软件对FFT系统进行编译、仿真和测试，对输入的数据进行处理后再输出，并且和理论值进行比较验证设计的正确性。第二章 FPGA的基础知识2.1 FPGA的简介FPGA（Field Programmable Gate Array，现场可编程门阵列）是在可编程逻辑阵列（PAL）、通用逻辑阵列（GAL）、复杂可编程逻辑器件（CPLD）等可编程器件的基础上进一步发展的产物，相对于其他的可编程器件，FPGA在系统集成度、逻辑实现和设计能力等诸多方面有着明显的优势。它能够根据用户的编程实现某种逻辑功能，而不需要前期的大量硬件开发投入。这

17、使得FPGA在满足专用的、个性化的设计要求方面无疑将拥有更大的灵活性和竞争力2。近年来，随着FPGA的性能不断快速发展，它的广泛使用不仅简化了电路的设计复杂程度，降低了设计成本，提高了系统的可靠性，而且给整个数字电路系统的设计和实现带来了革命性的变化，使更低成本、更短周期的复杂数字系统开发成为可能。正是由于FPGA上述的优点，使得其在在数字信号处理、工业控制、数据处理等诸多领域的运用越来越广泛。而随着微电子制造技术的发展和市场的需要，各种大容量、高性能、低功耗的FPGA不断推出，新一代的FPGA不仅包含可编程逻辑模块，更集成了微处理器芯片（CPU）和其他各种外接端口，方便与外部设备的连接使用，

18、从而能够实现软硬件的协同工作，为数字系统设计提供更为强大的硬件支持。所以FPGA的发展前景必将十分的广阔。2.2 FPGA较其他器件优点经过二十多年的不断发展，现在工程中使用的可编程逻辑器件主要包括两大类：CPLD和FPGA。虽然FPGA和CPLD都是可编程的ASIC器件，它们之间有着很多的共同点，但是由于FPGA和CPLD在结构上的差异，使得它们都具有各自的特点。通常CPLD的特点有：（1） CPLD不需要另外配置加载芯片。（2） CPLD的运算速度比FPGA快，并且具有较大的时间上的可预测性。（3） 在编程存储方式上，CPLD使用E2PROM或Flash作为编程存储器，即使系统断电后存储器

19、内容不会丢失。FPGA则是使用SRAM的存储，系统断电时存储器中的编程信息丢失。（4） CPLD的保密性比FPGA好。（5） 通常情况下，CPLD的功耗比FPGA大，而且随着集成度的提高而增大。FPGA中包含数量丰富的可编程逻辑模块，但是CPLD通常情况下却只能做到512个逻辑单元。除此之外，FPGA的平均逻辑单元成本也大大低于CPLD。所以，FPGA和CPLD相比较而言，具有一下的优点：（1） I/O数量多。同CPLD一样，FPGA同样具有众多的用户可定义的I/O资源，支持多种I/O标准，且数据传输的速率非常高。（2） 时序更容易满足要求。与CPLD相比FPGA的内部布线资源更加丰富，更容易

20、实现用户的时序设计要求。（3） 细粒FPGA结构的优点。FPGA是细粒结构，这就意味着每个单元间存在细粒延迟。如果将少量的逻辑紧密排列在一起，FPGA的速度会相当的快。（4） 内部资源丰富。与CPLD相比，FPGA除了具有丰富的布线资源外，其内部逻辑资源也要丰富的多。（5） 容量大、功能强。一般来说，FPGA器件的容量比CPLD器件更容易做大，其内部资源更加的丰富，甚至可以把整个系统放在一块FPGA芯片上实现。（6） 可任意次数的编程。FPGA器件的编程数据是存放在片外的RAM上，当系统上电时才将数据导入FPGA芯片的内部存储单元中，理论上的编程次数是无限的，而CPLD的稳定可编程次数一般不超

21、过1万次。正是因为FPGA具有的以上特点，利用FPGA设计的FFT系统相对于传统软件或者DSP实现FFT具有以下优点：（1） FPGA芯片运行速度快能够很好的满足实时处理的要求，而单纯靠软件或者DSP进行处理速度通常比较慢。（2） FPGA的可编程特性使得其灵活性很强，可以根据需要再次修改程序算法，而且降低了开发成本和设计周期，这是DSP无法比拟的。2.3 开发软件简介2.3.1 Quartus II软件介绍Quartus II软件是Altera公司主推的FPGA设计软件，其前身是大家熟悉的MaxPlus II软件，Quartus II软件集设计输入、编译、综合、仿真、布线布局和下载等功能于一

22、体，是一款功能非常强大的EDA设计软件，对于不是很大的系统设计，完全可以在这个平台上完成所有的设计任务。但是，由于Altera公司毕竟是一家以FPGA芯片为主营业务的公司，且Quartus II软件功能过于庞杂，所以合理的利用FPGA设计第三方软件及其他数据处理软件（如MATLAB软件），将大大提高FPGA的设计效率。2.3.2 Quartus II软件设计流程基于Quartus II进行的EDA设计开发流程如图2.1所示，包括以下步骤：（1）设计输入：包括原理图式设计输入、硬件描述语言文本输入、内存编辑输入及第三方工具输入等几种方式。（2）编译：Quartus II可选的编译方式有综合并输出

23、网表和完全的编译。第二种编译包括，网表输出、综合、器件配置等，并且编译软件根据器件配置设定延时时间。（3）仿真：Quartus II软件支持多种输入的仿真，如.vwf波形文件，.vec向量文件，.tbl列表文件。通过仿真验证设计的逻辑功能和时间延时是否满足要求。（4）下载与检验：当设计经过编译和仿真测试后，如果满足设计要求便可以下载到电路开发板上的FPGA芯片中进行在线测试。修改设计在线测试编程仿真与定时分析编译输入设计文件在设计过程中，如果出现错误，则需要重新回到设计输入阶段，改正错误或调整电路后重复上述过程3。图2.1 Quartus II设计流程2.4 Verilog HDL的简介硬件描

24、述语言（HDL,hardware description language）是一种用形式化方法来描述数字电路和系统的语言。通过硬件描述语言，建立系统行为级的仿真模型，然后利用EDA软件对由硬件描述语言建立的的复杂数字逻辑电路模型进行仿真，然后再进行综合编译，以生成符合要求且在电路结构上可以实现的数字电路逻辑网表（Netlist）。再根据具体器件生成该器件工艺条件下的电路延时配置，经测试验证后，写入FPGA或CPLD的存储器中。在20世纪80年代后期，硬件描述语言的发展趋势就是逐渐实现标准化，经过世界范围内的广泛验证，Verilog HDL和VHDL语言符合了这种趋势的要求，得到越来越多的EDA

25、公司和设计人员的使用和认可。本文采用的是Verilog HDL语言来设计逻辑电路4。Verilog HDL是硬件描述语言的一种，用于数字电子系统的设计。该语言允许设计者进行各种级别的逻辑功能设计和数字逻辑系统的仿真验证，更重要的是进行时序分析和综合测试。在美国、欧洲和我国台湾地区都有大量的设计工程师在使用Verilog HDL进行数字电路设计。一般把功能经过验证的、可综合的、实现后电路结构总门数在5000门以上的Verilog HDL模型称之为“软核”（soft core），而把由软核构成的器件称之为虚拟器件5。Verilog HDL很适合系统级（system）、算法级（algorithem）

26、、寄存器传输级（RTL）、逻辑级（logic）、门级（gate）、电路开关级（switch）设计，而system verilog是verilog语言的延伸和扩展，更适合于可重复使用的可综合的IP核和可重用的验证用IP设计，以及特大型（千万门级以上）基于IP的系统级设计和验证。概括的说，Verilog HDL语言具有以下的一些特点：（1） 既用于可综合的电路设计，也可以用于电路与系统的仿真。（2） 能在不同的层次上对所要设计的系统进行描述，从开关级、门级、寄存器传输级行为级等。（3） 电路结构描述方式灵活，不但可以使用行为级描述或者结构级描述，还可以二者混合描述。（4）内置各种逻辑门，如and、

27、or和nand等，可以方便的进行门级结构描述；内置各种开关级器件，如pmos、nmos和cmos等，可以进行开关级的建模。（5）用户自定义原语（UDP）的灵活性6。2.5 本章小结本章主要对FPGA的相关知识进行了介绍，包括含义、组成和相对于其他可编程器件的优点，最重要的特点是大容量，可重复编程，实时处理能力强。然后对本文研究需要使用的Quartus II软件进行了简单的介绍，着重介绍了其设计流程。最后对所使用的硬件描述语言语言Verilog HDL予以介绍，包括其在世界范围内的发展情况和主要特点。第三章 FFT算法原理3.1 快速傅里叶变换快速傅里叶变换（FFT）是Cooley和Tukey于

28、1956年提出的一种离散傅里叶变换的快速计算方法，它在理论上并不是一种新的变换，而是一种快速有效地计算DFT的方法。DFT可以为连续信号频谱分析，实现快速线性卷积，计算相关函数等。但是由于DFT的计算量很大，所以其并没有得到真正的运用。直到FFT算法的提出，这种情况才得到根本的改变。FFT算法使得DFT计算量大大降低，运算时间比传统的DFT算法缩短了一到两个数量级，从而有力地推动了数字信号处理技术的运用和发展7。3.2 基-2FFT算法3.2.1 基-2FFT算法原理 基-2FFT算法是最经典而且也是运用最广泛的FFT算法。该算法分按时间抽取（DIT）和按频率抽取（DIF）两种类型，它们两者在

29、原理上是基本相同的。本课题采用的是DIT，下面着重介绍这一算法。已知长度为N的有限长序列x(n)的DFT表达式为： (3-1)当x(n)为复数序列的一般情况时，k为0到N-1的某个整数，根据（3-1）式计算X(k)的DFT值分别需要N次复数乘法和(N-1)次复数加法。 那么直接计算DFT需要N2次复数乘法及N(N-1)次复数加法。因为1次复数乘法中包含4次实数乘法和2次实数加法，1次复数加法中有2次实数加法，所以做1次离散傅里叶变换需要4N2次实数乘法和N(4N-2)次实数加法。当序列的长度N不断增大时，所需要的运算次数也会随着急剧的增加，所以直接用DFT算法进行谱分析和信号的实时处理是不切实

30、际的8。通过以上分析，N点DFT需要的复数乘法次数为N2次。如果把整个序列分解成几个有规律的短序列，再分别计算其各个短序列的DFT值，就可以使整个运算的乘法次数减少很多；利用旋转因子的周期性、对称性进行合并和归类处理，从而减少DFT的运算量。其对称性为： (3-2)周期性为： (3-3)式中，m为非零整数。对于基-2FFT，由于N=2M，因此可以通过M次的分解最后完全转换成2点的DFT，最终减少DFT的运算量。根据n的值为奇、偶数将序列x(n)分解为x1(n)、x2(n)两组子序列；用2个N/2点的DFT来实现一个N点DFT的运算。 设一个序列x(n)的长度为N，如下式所示， (3-4)， (

31、3-5)所以 (3-6)偶数奇数其中k的取值范围为0，1，N-1。因为 (3-7)所以这样就将N点DFT分解为两个N/2点的DFT。由于X1(k)和X2(k)均以N/2为周期，而且 (3-8)所以又可以将X(k)表示为如下所示的表达式 (3-9) (3-10)对上式的运算用图3.1所示的流图符号来表示 A B A+BCA-BCC图3.1 蝶形运算符号假设对于一个N=8点的DFT运算可以根据式（3-9）、（3-10）和图3-1,表示成图3.2的计算方式。其中式（3-9）和（3-10）分别给出了X(0)-X(3)和X(4）-X(7)的计算方法。图3.2 N=8点DFT一次时域分解图由图3.1和3.

32、2知，在经过一次时域分解后，计算一个N=2M点的FFT的流程图共有M级蝶形运算，每级由N/2个蝶形运算组成，每个蝶形运算需要1次复数乘法和2次复数加法。所以计算N=2M点FFT的共需要2(N/2)2+N/2=N(N+1)/2N2/2(N1)次复数乘法，N(N/2)+2N/2=N2次复数加法运算。与原DFT运算比较而言，复数乘法的运算量减少了一半，这充分说明FFT算法的有效性9。第二次分解：将x1(r)按r取奇、偶可分解成2个长度为N/4的子序列l=0,1,N/4-1 （3-11） x3(l)= x1(2l) x4(l) = x1(2l+1)根据上面推导可得： ,k=0,1,N/2-1 （3-1

33、2）同理将x2(r)按r取奇、偶可分解成2个长N/4的子序列l=0,1,N/4-1 （3-13） x5(l)= x2(2l) x6(l) = x2(2l+1)推导可得： ,k=0,1,N/2-1 （3-14）经过两次分解，可以将一个N/2点的DFT再被拆分成为了两个N/4点的DFT。依次拆分下去，由此可知，对于N=2M点需要经过M-1次分解得到N/2个2点DFT，如图3.3所示。图3.3 N=8点DFT二次时域分解图DITFFT算法与直接计算DFT运算量的比较：整个运算流图中有M级蝶形，每一级运算中包含N/2个蝶形，每个蝶形需一次复数乘和两次复数加运算。所以，直接DFT作N点运算： 复数乘次数

34、：NN=N2 复数加次数：N(N-1) （3-15）用DIT-FFT作N点运算： 复数乘次数：MN/2=N/2log2N 复加次数：2N/2M= Nlog2N （3-16）假设有N=210=1024点数据，按照上面的分析可知直接DFT运算和DIT-FFT运算所需要的乘法次数的比值是 （3-17）很明显运算效率提高了204倍，而且随着数据量越多，FFT算法的优越性越直观。在常规的N数值下，FFT的运算量比DFT降低了12个数量级，可见FFT大大减少了运算次数，提高了运算速度10。3.2.2 基-2FFT算法特点FFT算法流程图具有以下的规律：1. 蝶形运算每一级运算都由N/2个蝶形运算单元组成。

35、2. 原位计算根据旋转因子的对称性、周期性特点，FFT算法通过分解长序列减少了运算时间，原位计算（in-place computation）的运用，使算法的空间复杂度也因为运算存储单元的减少同时得到了降低。这也是FFT算法的另一个大的优点11。通过原位计算，把所有数据输入到存储器中，经过每一级的蝶形运算，把该级的运算结果仍然保存到原来的存储器中，直到所有的数据完成。FFT采用迭代算法进行运算后再实行原位计算。所以，通过原位计算只需要N个复数的存储单元，这些存储单元不仅存放输入的原始数据，而且运算过程中也存储了输出数据，优点是节省系统的了存储资源，降低了整个系统的硬件开发成本12。3. 蝶形类型

36、随迭代次数成倍增加在第一级的蝶形运算中，只需要一个旋转因子，参加蝶形运算的两个数据点之间间隔为1。在第二级蝶形运算中，需要两种旋转因子和，参加蝶形运算的两个数据点之间间隔为2。在第三级蝶形运算中，需要四个旋转因子即，参加蝶形运算的两个数据点之间间隔为4。通过分析可以发现，每一级蝶形运算单元所需要的旋转因子个数增加一倍，参加运算的数据点之间的间隔也同时增大一倍。最后一级需要的旋转因子达到N/2个，参加蝶形运算的两个数据点的间隔也最大的等于N/2。X (5)图3.4 N=8点DIT-FFT运算流图x(0)x(4)x(2)x(6)x(1)x(5)x(3)X1(1)X1(2)X1(3)X2(0)X2(

37、1)X2(2)X2(3)X (0)X (1)X (2)X (3)X (4)X (6)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)x(7)L=1L=2L=3X (7)X3(0)X1(0)对于一个N=8点的DIT-FFT通过图3.4可以发现，第L级共有个不同的旋转因子，分别表示如下：第一级：L=1，有1个旋转因子：，J=0 （3-18）第二级：L=2，有2个旋转因子：，J=0,1 （3-19）第三级：L=3，有4个旋转因子：，J=0,1,2,3 （3-20）对于N的一般情况，第L级共有个不同的旋转因子： ，J=0,1,2,-1 （3-21） （3-22） ，J=0,1,2

38、,-1 （3-23）4. 序数重排输入数据x(n)是按照新的次序重排的。将按照自然顺序输入的数据的次序用二进制表示，从二进制的最高位到最低位依次交换位置，即把一个二进制数实现反转。在实际运算当中，直接将输入数据x(n)按照位反转的顺序排好输入是很不方便的。所以通常情况下是先将数据按自然顺序输入，然后采用变址寻址算法去寻找相应单元的x(n)，这叫做“顺序输入，逆序输出”。现在设计很多FFT的处理器均具有这种按位反转的寻址功能13。表3.1顺序和倒序二进制数对照表顺序倒序十进制数I二进制数二进制数十进制数J0123456700000101001110010111011100010001011000

39、1101011111042615373.3 本章小结本章节主要介绍了基-2FFT算法的原理方法。在稍微介绍快速傅里叶变换的概念和内容之后，重点介绍了基-2FFT算法，其中包括算法的原理、算法实现。基-2FFT算法是最经典且最简单的FFT算法。该算法分按时间抽取（DIT）和按频率抽取（DIF）两种类型，两者的基本原理是等价的，可以相互转化得到。本课题采用的是DIT-FFT。然后对FFT算法的主要特点：蝶形运算单元、原位计算、迭代次数和序数重排进行了讨论。通过分析验证FFT算法相对于DFT算法在计算量方面巨大的优越性。FFT算法使DFT得计算量大为降低，有力地推动了傅里叶变换在数字信号处理技术的应

40、用和发展。第四章 FFT的FPGA实现4.1 整体结构设计随着集成电路制造工艺的不断发展，FPGA内部的可编程逻辑资源越来越丰富。特别是RAM和ROM容量的增加，使得系统的可编程设计更加容易，也使得系统的实时处理性能得到了很大的提高。本文中采用的基-2FFT设计主要由以下模块组成：输入输出处理单元、逻辑控制单元、蝶形运算单元、移位处理单元、溢出控制单元、旋转因子存储文件。如图4.114。溢出控制单元FFT运算RAM2蝶形运算单元逻辑控制单元旋转因子ROMFFT运算RAM1输出处理单元输入处理单元图4.1 FFT工作流程图根据FFT的工作流程图，先用硬件描述语言完成各个子模块的功能，测试正确后再

41、设计顶层模块调用已完成的子模块，从而实现整个系统的功能。4.2 蝶形运算单元从第三章FFT算法原理中可以看到，蝶形运算单元是整个FFT算法的核心模块。根据FFT的算法原理公式可以得出图4.2的蝶形单元示意图15。Z=A+BWZ=A-BWABW图4.2蝶形运算单元示意图图中A和B表示两个输入的复数数据，表示旋转因子，和表示蝶形输出。 （4-1） （4-2） （4-3）所以对于两点FFT的计算过程根据复数运算规则，可以得到： （4-4） （4-5）由式（4-4）和（4-5）可以发现，蝶形运算单元将复数的运算最终通过实数的运算来完成。其中涉及到加法器和乘法器的协同工作，实数加法比较简单，所以直接用硬

42、件描述语言中的算术运算符描述，而实数乘法相对比较复杂，但是Quartus II软件中提供了模块化的乘法器可以直接调用，既保证了功能的正确性又提高了运算效率，缩短了设计时间，这在EDA设计中是经常用到的。如图4.3。图4.3 Quartus II软件中的乘法器模块将蝶形运算单元模块的端口定义如下：module bfly_r2dit (rst, clk,din_av,out_enb,ar, ai,br,bi,wr,wi,xr, xi,yr,yi);其中：clk 外部输入时钟信号rst 复位信号din_av 输入使能信号out_enb 输出使能信号ar,ai,br,bi分别是两个输入的复数数据的实部

43、和虚部，wr,wi是旋转因子的实部和虚部xr,xi,yr,yi 分别是蝶形运算单元的两个输出的实部和虚部部分设计代码如下：wire 19:0 cr, ci;assign cr =real_cos_reg - image_sin_reg;assign ci = image_cos_reg +real_sin_reg;wire 20:0 xr_c,xi_c,yr_c,yi_c;assign xr_c = ar_d1t9,ar_d1t9,ar_d1t,9b0_0000_0000 + cr19,cr ;assign xi_c = ai_d1t9,ai_d1t9,ai_d1t,9b0_0000_0000 + ci19,ci ;assign yr_c = ar_d1t9,ar_d1t9,ar_d1t,9b0_0000_0000 - cr19,cr ;assign yi_c = ai_d1t9,ai_d1t9,ai_d1t,9b0_0000_0000 - ci19,ci ;因为运算过程中会出现数据溢出情况，所以在设计中充分考虑了这一点做了适当的处理。最终完成的蝶形运算单元模块如图4.4。图4.4 蝶形运算单元模块图4.5 蝶形运算单元仿真波形图4.5是蝶形运算单元的仿真波形图。其中real_sin，real_cos，image_sin，image_cos分别是四个实数