1. 研究目的与意义（文献综述）

快速傅氏变换（fft），是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它在物理学、电子类学科、数论、组合数学、信号处理、概率论、统计学、密码学、声学、光学、海洋学、结构动力学等领域都有着广泛的应用。例如在语音信号处理方面，可以用来做语音识别（刑侦、门禁系统等）、声音模拟（候鸟、鱼群的迁徙引导等）、话音伪装（tom猫等）；而在图像处理中的应用主要体现在图像保存和图像滤波。
有限长序列可以通过离散傅里叶变换(dft）将其频域也离散化成有限长序列。但其计算量太大，很难实时地处理问题，因此引出了快速傅里叶变换(fft). 1965年，cooley和tukey提出了计算离散傅里叶变换（dft）的快速算法，将dft的运算量减少了几个数量级。从此，对快速傅里叶变换（fft）算法的研究便不断深入。
在国内，曹英立等教[1]发表过一篇文章，是关于在分析现有谐波检测方法的基础上,研究了基于全相位快速傅里叶变换和人工神经网络的谐波和间谐波检测算法，进一步提高了谐波检测的精度。 陈杰男等教授[2]发布过一篇文章，关于超高速全并行快速傅里叶变换器，设计和实现超高速快速傅里叶变换器(fft)在雷达与未来无线通信等系统中具有重要意义。在国外，garrido等教授[3]研究出了一个新的类型的快速傅里叶变换（fft）的硬件架构，称为串行转换器（sc）的fft。 ali等教授[4]研究出了64 / 128 / 256 / 512点快速傅里叶反变换（ifft）/单用户和多用户多输入多输出正交频分复用fft处理器在基于ieee 802.11ac无线局域网收发器。
目前，国内外有很多实现快速傅里叶变换的方法，例如在matlab上实现fft的仿真，用verilog语言实现fft，并利用fpga进行仿真，或者用c语言编写程序来实现fft的算法等等。谭子尤教授[18]发表过一篇文章，比较全面地叙述各种快速傅里叶变换算法原理、特点,并完成了基于matlab的实现。
快速傅立叶变换是数字信号处理的一种重要的算法。本课题要求对快速傅立叶变换算法进行分析与优化，并在quartusii平台完成设计与仿真。分析和优化快速傅里叶算法可以让计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数n越多，fft算法计算量的节省就越显著。研究快速傅立叶变换(fft)的fpga实现既可以减少国外对fft实现上采用固核或硬核的技术封锁的限制，又可灵活的为各种工程应用提供满足要求的fft处理，也为更高效率的fft芯片的设计和实现打下基础。

2. 研究的基本内容与方案

本次研究的基本内容主要是分析研究现在流行的fft算法，包括基2快速傅里叶算法和基4快速傅里叶算法。

然后设计fft的总体结构来实现这两种算法，包括蝶形运算单元，地址产生单元，功能切换单元，存储单元，浮点单元和程序控制元，其中, 地址产生单元生成ram读写地址, 使信号以及相关模块启动、控制信号, 是系统的控制核心; 旋转因子产生单元生成复乘运算中的旋转因子的角度数据; 旋转因子rom中预置了每一级运算中所需的旋转因子。

最后基于quartusii平台完成设计与仿真，并分析两种算法的优缺点以及不同旋转因子存储器对运算速率的影响。

3. 研究计划与安排

第1-3周：熟悉毕业论文的题目，查阅相关文献资料，明确研究内容，了解研究所需用到的技术方案和工具。

确定方案，完成开题报告和外文文献翻译。

第4-5周：完成fft总体框架的设计。

4. 参考文献（12篇以上）

[1]曹英立，尹希哲.基于BP神经网络和全相位快速傅里叶变换的电力系统谐波检测技术研究[J].现代电子技术，2017,40（1）：125-128
[2]陈杰男，费超，袁建生，曾维棋，卢浩，胡剑浩.超高速全并行快速傅里叶变换器[J].电子科技大学通信抗干扰国家级重点实验室,2016,38(9)
[3] 李静梅，郑超峰，金玉苹.基于FPGA算法实现[J].应用科技，2009，36（2）：38—41
[4] 李全利，李静.基于FPGA的FFT算法研究[J].自动化技术与应用，2007，26（10）：32-35
[5] 童庆为，陈建春.基于FPGA的FFT算法实现[J].电子科学，2010，23（11）:113-115
[6] 赵敏玲，葛立敏，李文辉.基于FPGA的块浮点FFT的实现[J].兰州理工大学学报，2009，35（4）：103-106
[7] 潘明海，刘英哲，于维双.一种基于FPGA实现的FFT结构[J]微计算机信息，2005，21（9）：156-158
[8] 刘朝晖,韩月秋.用FPGA实现FFT的研究[J].北京理工大学学报,1999,第19卷,第2期
[9] 余景华,郭亨群.OFDM系统中64点FFT的FPGA设计[J].通信技术,2008,第41卷,第12期
[10] 陈永东.一种基于FPGA的DFT算法实现的研究[J].遥测遥控,2005,第26卷,第4期
[11] 王旭东,刘渝.全并行结构FFT的FPGA实现[J].南京航空航天大学学报,2006,第38卷,第1期
[12] 杨兴,谢志远.OFDM中FFT处理器的设计及FPGA实现[J].电测与仪表,2008,第45卷,第7期
[13]Garrido,Mario,Huang,Shen-Jui,Chen,Sau-Gee,Gustafsson,Oscar.The Serial Commutator FFT,IEEE Transactions on Circuits and Systems II: Express Briefs,2016,63(10)
[14]Ali, A, Hamouda, W.A multi-mode IFFT/FFT processor for IEEE 802[J].11ac: design and implementation,2016,16(13),1713-1725
[15] Wang Qi.GA-based Digital Signal Processing Algorithm Research[J]. IEEE Transon Signal Processing, 2010,978(9):910-912
[16] Fast Fourier transform using matrix decomposition[J].INFORMATION SCIENCES, 2015,Vol.291,No.10
[17] James W. Cooley;John W. Tukey.An Algorithm for the Machine Calculation of Complex Fourier Series[J].Mathematics of Computation,1965,Vol.19,No.90
[18]谭子尤, 张雅彬. 离散傅里叶变换快速算法的研究与MATLAB算法实现[J]. 中国科技信息, 2006(22):316-317.
[19] Graham, JT; Rollett, AD; LeSar, R.Fast Fourier transform discrete dislocation dynamics[J].MODELLING AND SIMULATION IN MATERIALS SCIENCE AND ENGINEERING,2016,Vol.24,No.8
[20]时方,谢志远.快速离散傅里叶变换算法研究与FPGA实现[J].电测与仪表,2015,52(5);15-19
[21]赵莹,李云.快速傅里叶变换（FFT）的ASIC实现及现场可编辑门阵列（FPGA）验证[J].科学技术与工程,2015,0(4);243-246
[22]张志娟.基于VHDL语言的DIT—FFT算法设计.常州信息职业技术学院学报[J],2013,(1);14-18