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

多年来数字信号处理技术同数字计算机、大规模集成电路等先进技术一样，有了突飞猛进的发展，日新月异，已经形成了一门具有强大生命力的技术科学。由于它本身具有一系列的优点，所以能有效地促进各工程技术领域的技术改造和学科发展，应用领域也更加广泛、深入，越来越受到人们的重视。在数字信号处理中，离散傅里叶变换(discrete fourier transform,dft)是常用的变换方法，它在各种数字信号处理系统中扮演着重要的角色。但傅里叶变换用较精确的数字方法，即dft进行谱分析，在fft出现以前是不切实际的。这是因为dft计算量太大。直到1965年出现了dft运算的一种快速方法以后，情况才发生了根本的变化。快速傅里叶变换（fast fourier transform,fft）并不是与离散傅里叶变换不同的另一种变换，而是为了减少dft计算次数的一种快速有效的实现算法。

在garwin的迫切要求下，1963年，ibm公司的cooley根据tukey的想法编写了第一个fft算法程序。在fft算法中，tukey主要利用了旋转因子的周期性和对称性。这两个性质使dft运算中的某些项可以合并，使dft运算尽量分解为更少点数的dft运算。因为dft的运算量与pow(n,2)成比例，所以如果将一个大点数的dft分解为若干个小点数的dft的组合，将有效地减少运算量。cooley在计算机上实现该算法时，为节省存储空间和减少寻址时间，采用了3维标号映射方法和在算法内部的循环结构，这些结构和技巧对后来的fft算法研究及实现同样产生了很大影响。1965年，cooley和tukey在《计算数学》上发表了著名的论文，并立即引起了广泛注意。fft算法将运算量从o (n2)减少为2o( n logn)，运算时间减少1-2个数量级，从理论上解决了数字信号处理运算量大的问题，是数字信号处理发展史上的—块里程，从而使数字信号处理从一个计算数学的分支变为一门应用科学，逐步走向实用技术。

在cooley-tukey算法提出之后，sande提出了按照频率抽取的fft算法，它可以作为按照时间抽取的cooley-tukey算法的对偶形式。bergland提出了采用高基数结构的算法。增大基数虽然可以减少计算量，但同时每个计算单元的结构也更复杂。从七十年代中期开始，基于素因子分解的一种快速算法是由ibm公司的winograd博士提出的，可以称为wfta算法。wfta算法有两个主要思想：一是用rader提出的方法将小n点dft转换为循环卷积，利用多项式理论使卷积计算具有尽可能少的乘法次数;二是将小n点dft运算进行嵌套来完成大n点的dft运算。wfta算法比素因子算法的乘法次数更少，而加法次数差别不大。但wfta算法也有一些突出的问题，如算法不能采用原位运算，需要占用较大的存储空间，更重要的是，随着变换点数n的不同，为使运算所需的加法次数最少，要求采用不同的运算次序，这导致运算过程的规则性较差，且控制过程复杂。但后来发现它们在实际应用中并不理想，尽管在理论上仍是有意义的进展。因此fft的研究重点重又回到了带有与旋转因子相乘运算的共因子算法上，主要的研究成果包括rader和brenner提出的余割因子算法，王中德提出的对称分解法，matens提出的割园分解法，vetlerli和nussbaumer提出的dft dct算法等，其中最具代表性的是法国的duhamel和hollman提出的分裂基算法。分裂基算法的特点是将基-2分解与基-4分解揉和在一起，对序列的不同部分分别实施基-2算法和基-4算法。分裂基算法的运算结构与cooley-tukey算法相似，并且对于长度为n=2m的变换，这一算法已达到了dft运算的最小运算量。

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

基本内容及目标

1) 学习数字信号处理中快速傅里叶变换的各种实现方式。

2) 学习并掌握基本的信号处理相关的c 语言编程方法。

3. 研究计划与安排

1) 第1-3周 完成题目调研，完成文献阅读，进行相关资料的收集，完成文献综述以及开题报告撰写；

2) 第4-6周 学习离散时间信号快速傅里叶变换的基础知识；

3) 第7-12周 完成自适应基底快速傅里叶变换c语言实现；

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

[1] 杨丽娟,张白桦,叶旭桢. 快速傅里叶变换fft及其应用[j]. 光电工程,2004,(s1):1-3 7.

[2] 曹伟丽. 快速傅里叶变换的原理与方法[j]. 上海电力学院学报,2006,(02):192-194.

[3] 郭铁桥,张磊. 快速傅里叶变换的c 实现[j]. 中国新技术新产品,2011,(07):38-39.