1. 研究目的与意义
计算离散傅里叶变换的一种快速算法，简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。
傅立叶变换是信号处理中一种重要的变换方法，所以其在电气工程、电子工程、信息与通信工程、控制工程、生物医学工程、天文学等理工类学科中的重要性是不言而喻的，它是绝大多数理工类学科的基础课程。
2. 国内外研究现状分析
努斯鲍勃在《快速傅立叶变换和卷积算法》中提过，近几年来，数字卷积和离散傅立叶变换（dft）的实际应用更加广泛，其意义愈来愈重要。其直接原因是由于数字滤波和dft在数字信号处理中的重要作用以及数字硬件的价格迅速下降后使数字信号处理的应用更加普及。促使快速卷积和dft算法发展的主要原因是由于直接计算长度为n的卷积和dft需要正比于的运算次数，因此当数据很多时运算次数将迅速猛增。这意味着在用计算机实现这些算法时将会提出苛刻的要求。计算离散傅里叶变换的快速方法，有按时间抽取的fft算法和按频率抽取的fft算法。前者是将时域信号序列按偶奇分排，后者是将频域信号序列按偶奇分排。它们都借助于的两个特点：一是的周期性；另一是的对称性，这里符号*代表其共轭。这样，便可以把离散傅里叶变换的计算分成若干步进行，计算效率大为提高。实际上，频率抽取算法与时间抽取算法的信号流图之间存在着转置关系，如将流图适当变形，可以得出多种几何形状。除了基2的fft算法之外，还有基4、基8等高基数的fft算法以及任意数为基数的fft算法。
罗纳德博士在《傅立叶变换及其应用》一书中说到，实现快速傅立叶变换的程序里已经考虑到了许多实际问题。对某些应用，速度是首要的考虑；对另一些应用，方便是主要的。如果n不是2的幂，为了方便说的是我们可以对数据补0,；要求速度说的是需要选择一个改进的程序以获得利用这个因子所具有的特点。一些用户从不要求复的输出；另一些用户则需要复输出，但不是实部和虚部的形式。一部分用户可能需要处理二维和三维的数据。一些用户通常不得不将数据进行分段处理，因为n超过了他们的计算机容量。上述这类问题，虽然很重要，但是都能通过一些所给出的原始文献或通过对已有程序的分析来研究。对一些文档的研究也有其重要，因为一些软件包虽然根本不能完成dft操作，但是经过一些修改可能会或多或少带来一些方便。
仇庆九在《傅立叶积分算子理论及其应用》中提到，傅立叶变换在常系数线性偏微分方程理论中起着重要的作用。通过这种变换，原来自变量空间中的微分运算转化到对偶变量空间中进行讨论，所以它能成功的处理常系数方程中许多困难的问题（例如基本解存在定理等）。但是这种方法对变系数方程确实不适用的。处理变系数方程的古典方法之一是（收敛的或渐近的）级数解法。如所周知，级数解法的局限性很大，应用的范围不广。在一定意义上说，傅立叶积分算子以及拟微分算子理论就是为处理变系数方程问题而产生的现代工具。它在变系数方程中所起的作用与傅立叶变换在常系数方程中所起的作用有些相近；同时，它又采纳了幂级数解法的某些思想，并加以改造，使之成为一种博采众长的新理论。计算离散傅里叶变换的快速方法，有按时间抽取的fft算法和按频率抽取的fft算法。前者是将时域信号序列按偶奇分排，后者是将频域信号序列按偶奇分排。它们都借助于的两个特点：一是的周期性；另一是的对称性，这里符号*代表其共轭。这样，便可以把离散傅里叶变换的计算分成若干步进行，计算效率大为提高。按频率抽取的fft算法是将频域信号序列x(k）分解为奇偶两部分，但算法仍是由时域信号序列开始逐级运算，同样是把n点分成n/2点计算fft，可以把直接计算离散傅里叶变换所需的n次乘法缩减到次。其计算量完全和时间抽取算法一样，即只需次乘法运算和nlog2n次加（减）法运算。图3表示n=8=2点的离散傅里叶变换的信号流图。它以三级迭代进行即位计算，输入数据是按自然次序存放，使用的系数也是按自然次序，而最后结果则以二进制反序存放。实际上，频率抽取算法与时间抽取算法的信号流图之间存在着转置关系，如将流图适当变形，可以得出多种几何形状。除了基2的fft算法之外，还有基4、基8等高基数的fft算法以及任意数为基数的fft算法。
3. 研究的基本内容与计划
研究内容：根据已学知识和参考文献进行对快速傅立叶算法的研究
研究计划:13周：收集相关资料，要求中文资料不少于10篇，英文资料不少于两篇，熟悉课题内容，完成开题报告；
45周：研究快速傅立叶算法，并将它应用到常微分方程数值求解；
4. 研究创新点
快速傅氏变换（FFT），是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。为了得到一种较好的FFT算法，可以将FFT中的部分运算通过调用结构简单的基-2FFT算法来完成而其他部分运算通过调用WFTA算法来完成。
