下载文档原格式
简述fft原理和算法FFT（快速傅里叶变换）是一种高效的算法，用于将一个复杂的信号分解成一系列简单的正弦波分量。
它在信号处理、图像处理、通信等领域得到广泛应用。
本文将简述FFT的原理和算法。
傅里叶变换是一种将时域信号转换为频域信号的数学工具，可以将信号表示为一系列正弦波的叠加。
傅里叶变换的计算复杂度较高，特别是对于大规模的信号处理任务来说，计算成本非常高昂。
FFT 算法的出现解决了这个问题，它通过利用信号的对称性质和复数运算的性质，大大减少了计算所需的时间。
FFT算法通过逐步将信号分解为越来越短的子序列，最后得到每个子序列的傅里叶变换。
具体来说，FFT算法首先将信号分成偶数和奇数下标的两个子序列，然后对这两个子序列分别进行FFT计算。
接着将得到的两个子序列的傅里叶变换重新组合，得到原始信号的傅里叶变换。
为了更好地理解FFT算法的原理，可以将其比喻为一棵二叉树。
树的根节点表示原始信号，每个节点表示一个子序列。
通过不断地将子序列分解为更小的子序列，直到只剩下一个元素为止。
树的叶子节点表示最终的傅里叶变换结果。
在每一层的计算中，FFT算法利用了信号的对称性质，将计算量减半。
最后，将每个子序列的傅里叶变换结果按照规定的顺序重新组合，得到原始信号的傅里叶变换。
FFT算法的时间复杂度为O(NlogN)，其中N表示信号的长度。
相比于传统的傅里叶变换算法，FFT算法的计算速度得到了极大的提升。
这使得FFT算法成为了信号处理领域中最重要的算法之一。
除了傅里叶变换，FFT算法还具有许多其他应用。
例如，FFT算法可以用于信号滤波，通过将信号变换到频域进行滤波操作，然后再将信号变换回时域。
此外，FFT算法还可以用于频谱分析、图像处理、通信等领域。
总结起来，FFT算法是一种高效的计算傅里叶变换的算法。
通过将信号分解为子序列并利用对称性质，FFT算法大大减少了计算所需的时间。
它在信号处理、图像处理、通信等领域得到广泛应用。
2.3 快速傅立叶变换问题1) 问题背景在数值电路的传输中，为了避免信号干扰，需要把一个连续信号 x(t)先通过取样离散化为一列数值脉冲信号x(0), x(1), …… ,然后再通过编码送到传输电路中。
如果取样间隔很小，而连续信号的时间段又很长，则所得到的数值脉冲序列将非常庞大。
因此，传输这个编码信号就需要长时间的占用传输电路，相应地也需要付出昂贵的电路费用。
那么能否经过适当处理是使上述的数值脉冲序列变短，而同时又不会丧失有用的信息？的经过研究，人们发现，如果对上述数值脉冲序列作如下的变换处理：∑-=--=-==1/21,1,...,1,0,)()(N k Nnki i N n ek x n X π (1)则所得到的新序列X(0), X(1) , ……将非常有序，其值比较大的点往往集中在某一很狭窄的序列段内，这将非常有利于编码和存储，从而达到压缩信息的目的。
公式（1）就是所谓的离散傅立叶变换，简称DFT 。
现在我们来分析一下计算DFT 所需要的工作量。
如果我们不考虑公式（7.1）中指数项的运算，那么计算其每一个点X (n) 需要N 次复数乘法和N-1次的复数加法。
显然当N 很大时，这个工作量也非常巨大。
正是由于这个原因，使得DFT 的应用范围在过去很长的时间里受到了严格的限制。
注意到公式（1）是非常有规律性的，那么能否利用这种规律性来降低DFT 的计算时间？1965年，凯莱和塔柯的提出了一种用于计算DFT 的数学方法，大大减少了DFT 的计算时间，同时又特别适用于硬件处理，这就是所谓的快速傅里叶变换，简称FFT 。
鉴于DFT 的数据结构可以通过傅立叶变换的离散化获得，亦可通过三角插值得到，而本质上又同连续傅里叶分析有着极为密切的关系。
下面我们从傅立叶级数级数和傅立叶积分入手，导出DFT 结构的来源和FFT 的工作原理。
2） 傅立叶变换如果x(t)是定义在整个实轴上的实值或复值函数，则其傅立叶变换可由下式给出：⎰∞∞---==1,)()(/2i dt et x f X Tnift （2）若对任意参数f ，上述积分都存在，则（2）式确定了一个函数X(f)，称为x(t) 的傅立叶变换。
傅里叶分析的发展与现状作者：曾海东韩峰刘瑶琳来源：《现代电子技术》2014年第03期摘要：在计算机技术的支持下傅里叶分析得到了充分的发展。
离散傅里叶变换（DFT）奠定了工程应用的基础；快速傅里叶变换（FFT）使其进入到了实用阶段。
21世纪以来，高速微处理器使得速度不再是制约傅里叶分析的主要因素。
由于高端科技对高准确度分析的需求，解决非同步采样条件下频谱误差问题成了现阶段最为迫切的任务。
已有频谱校正成果采用了基本傅里叶理论以外的技术方法，开启了一个以寻求普适性频谱分析方法为目标、DFT后方法为主的发展方向。
关键词：傅里叶分析； DFT/FFT； DFT频谱校正；参数估计中图分类号： TN911.7⁃34 文献标识码： A 文章编号： 1004⁃373X（2014）03⁃0144⁃04Development and current situation of Fourier analysisZENG Hai⁃dong， HAN Feng， LIU Yao⁃lin（Collage of Mechanical Engineering， Inner Mongolia University of Technology， Huhhot 010051， China）Abstract： With the support of computer technology， Fourier analysis has been fully developed. Discrete Fourier transform （DFT） lays the foundation of engineering application. The fast Fourier transform （FFT） lead it to applicable stage. Since 21st century， speed is no longer the main factor restricting the application of Fourier analysis owing to the development of high speed microprocessor. In order to satisfy the requirement of sophisticated techniques for high accuracy analysis， solving spectrum error under asynchronous sampling has become the most urgent task at present. Some techniques beyond the basic Fourier theory have been adopted in current spectrum correction works，which implies a post⁃DFT developing direction for seeking universal spectrum analysis method.Keywords： Fourier analysis； DFT/FFT； DFT spectrum correction； parameter estimation0 引言傅里叶分析已有200多年的历史，目前FFT及其校正算法在工程实际中仍在广泛应用，展现了其不竭的生命力。
数字信号处理FFT数字信号处理中的FFT算法数字信号处理（Digital Signal Processing, DSP）是一门研究如何以数字方式对信号进行处理和分析的学科。
其中，FFT（Fast Fourier Transform）算法是数字信号处理中最为重要和常用的算法之一。
本文将介绍FFT算法的原理、应用以及一些常见的优化方法。
一、FFT算法原理FFT算法是一种高效地计算离散傅里叶变换（Discrete Fourier Transform, DFT）的方法。
DFT是将一个离散信号从时域（time domain）变换到频域（frequency domain）的过程。
在频域中，我们可以分析信号的频率成分和振幅，从而得到信号的频谱图。
FFT算法的原理是利用对称性和重复计算的方式，将一个需要O(N^2)次乘法运算的DFT计算降低到O(N*logN)的时间复杂度。
通过将N个点的DFT分解成多个规模较小的DFT计算，最终得到原始信号的频域表示。
二、FFT算法应用FFT算法在信号处理领域有着广泛的应用，其中包括但不限于以下几个方面：1. 信号的频谱分析：通过FFT算法，可以将时域信号转化为频域信号，进而分析信号的频率成分和振幅，为后续的信号处理提供依据。
例如，在音频处理中，我们可以通过FFT算法分析音频信号的频谱，用于音乐合成、音频降噪等应用。
2. 图像处理：图像信号也可以看作是一种二维信号，通过对图像的行、列分别进行FFT变换，可以得到图像的频域表示。
在图像处理中，FFT算法被广泛应用于图像增强、滤波、压缩等方面。
3. 通信系统：FFT算法在OFDM（正交频分复用）等通信系统中被广泛应用。
在OFDM系统中，多个子载波信号通过FFT变换合并在一起，实现信号的同时传输和接收。
4. 音频、视频压缩：在音频、视频等信号的压缩算法中，FFT算法也扮演着重要的角色。
通过对音频、视频信号进行频域分析，可以找到信号中能量较小的部分，并将其抛弃从而达到压缩的效果。
快速傅里叶变换发展史快速傅立叶变换(FFT)个人日记2010-04-16 12:24:48 阅读163 评论0 字号：大中小订阅近十多年来数字信号处理技术同数字计算机、大规模集成电路等先进技术一样，有了突飞猛进的发展，日新月异，已经形成了一门具有强大生命力的技术科学。
由于它本身具有一系列的优点，所以能有效地促进各工程技术领域的技术改造和学科发展，应用领域也更加广泛、深入，越来越受到人们的重视。
在数字信号处理中，离散傅里叶变换(Discrete Fourier Transform,DFT)是常用的变换方法，它在各种数字信号处理系统中扮演着重要的角色。
傅里叶变换已有一百多年的历史了，我们知道频域分析常常比时域分析更优越，不仅简单，且易于分析复杂信号。
但用较精确的数字方法，即DFT进行谱分析，在FFT出现以前是不切实际的。
这是因为DFT计算量太大。
直到1965年出现了DFT]运算的一种快速方法以后，情况才发生了根本的变化。
快速傅里叶变换〔Fast Fourier Transfonn,FFT〕并不是与离散傅里叶变换不同的另一种变换，而是为了减少DFT计算次数的一种快速有效的算法。
当时Garwin在自己的研究中极需要一个计算傅立叶变换的快速方法，而正在写有关傅里叶变换的文章，Tukey概括地对Garwin介绍了一种方法，它实质上就是后来著名的Cooley-Tukey算法。
在Garwin的迫切要求下，1963年，IBM公司的Cooley根据Tukey的想法编写了第一个FFT算法程序。
在FFT算法中，Tukey主要利用了旋转因子的周期性和对称性。
这两个性质使DFT运算中的某些项可以合并，使DFT运算尽量分解为更少点数的DFT运算。
因为DFT的运算量与Pow(N,2)成比例，所以如果将一个大点数的DFT分解为若干个小点数的DFT 的组合，将有效地减少运算量。
Cooley在计算机上实现该算法时，为节省存储空间和减少寻址时间，采用了3维标号映射方法和在算法内部的循环结构，这些结构和技巧对后来的FFT算法研究及实现同样产生了很大影响。
现代通信中的FFT算法现代通信技术的发展离不开算法的支持，其中FFT算法是通信领域中最重要的数学算法之一。
在通信领域，FFT算法通过将连续时间函数转化为离散时间函数，大大地提高了通信的速度和效率。
本文将介绍FFT算法的基本原理、应用场景以及优化对策。
一、FFT算法基本原理FFT算法是快速傅立叶变换（Fast Fourier Transform）的缩写，是一种高效的信号处理算法，在信号压缩、遥感等领域有着广泛的应用。
FFT算法的基本原理是把连续的信号在一定的时间间隔内取样，然后用傅里叶变换公式将其转化为频域上的信息，再通过逆傅里叶变换将其转换回时域信号。
在通信领域，我们通常使用的是离散傅立叶变换（DFT），即将连续信号按照时间间隔取样，然后再进行傅立叶变换。
然而，直接通过DFT计算机算量巨大，效率低下。
FFT算法通过巧妙地将DFT分解为多个小的子问题，从而减少计算量，提高了算法的效率。
二、FFT算法的应用场景FFT算法广泛应用于数字信号处理、信道估计、多载波调制等领域。
以OFDM（Orthogonal Frequency-Division Multiplexing）技术为例，OFDM技术中的多载波信号可以通过FFT算法实现快速的频域处理，从而实现多载波信号的调制和解调。
此外，FFT算法还广泛应用于卫星遥感、医学影像处理等领域。
三、FFT算法的优化对策虽然FFT算法在通信领域中十分重要，但是其高算法复杂度限制了其在实际中的应用。
为了提高FFT算法的效率和性能，研究人员提出了许多优化对策。
以下是一些优化对策的介绍。
1.快速傅立叶变换算法：FFT算法的核心是快速傅立叶变换算法，其中最知名的是Cooley-Tukey算法。
该算法通过将DFT分解为多个小的子问题，在一定的时间复杂度内实现快速傅立叶变换。
2.算法并行化：随着计算机硬件性能的提高，通过并行化算法可以充分利用计算机多核CPU或GPU的并行计算能力，从而提高FFT算法的运算速度。
FFT算法的历史及发展现状——《数字信号处理》结课论文学院通信工程学院专业信息工程摘要传统的算W变换(哈特1设x(n)是一个长度为N的有限长序列，定义x(n)的N点离散傅立叶变换为其中，k=0,1,2,...,N-1.X?(k)?的傅立叶反变换为其中，n=0,1,2,...,N-1.2传统快速傅里叶变换（FFT）FFT(快速傅里叶变换)算法与DFT(离散傅里叶变换)算法比较，其运算量显着减少，用计算机实现时速度大为提高。
其思想是利用2点DFT运算无需乘法的特点，以减少过程在乘法运算上的时间开销。
在FFT被提出的这50年中，最为人所熟知的FFT算法有基2、基4等。
下面为就以这两种FFT算法为例，简要介绍传统FFT的思路与大致算法。
2.1基2FFT正如上文所说，直接计算DFT的算法，对于X（K）的每个K值，需要进行4N次实数相乘和（4N-2）次相加，对于N个k值，共需N*N乘和N（4N-2）次实数相加。
改进DFT算法，减小它的运算量，利用DFT中的周期性和对称性，使整个DFT的计算变成一系列迭代运算，可大幅度提高运算过程和运算量，这就是FFT的基本思想。
设N点序列x(n),.将x(n)按奇偶分组，公式如下改写为：，一个N点DFT分解为两个N/2点的DFT，继续分解，迭代下去，其运算量约为。
下图为按时间抽取的8点的FFT蝶形图：2.2基4FFT当N等于4时的四点DFT运算为：可以看到，类似2点DFT，4点DFT运算也无需乘法，可以简少运算量。
对式进行分解：由上式可得如下矩阵变换过程：可以看到，第一步先对最开始的采样点矩阵每一行进行K点DFT，然后第二步每项对应乘以旋转因子，n0为行（0到3行），m 为列（0到K-1列），最后按列做4点DFT，得到一个按行顺序排列的最终结果。
于是我们可以得到如下信号流图：3当今流行的FFT算法虽然传统的FFT算法已经能解决大多数数字信号的频谱分析问题，但是随着图像处理技术发展，传统的算法在处理新的数字信号频谱问题时已显得有所不足。
FFT的算法原理应用FFT（Fast Fourier Transform）是一种高效计算离散傅里叶变换（Discrete Fourier Transform，DFT）的算法。
通过使用FFT算法，可以将DFT的计算时间从O(N^2)降低到O(NlogN)，其中N是离散序列的长度。
FFT的算法原理基于Radix-2分治策略，将一个长序列分解为两个较短序列，并重复此过程，直到仅剩两个元素相乘为止。
FFT的算法主要应用于信号处理和频谱分析等领域。
其在频谱分析中的应用可以帮助我们了解信号的频率内容以及频率分量的强度。
在信号处理中，FFT可以用于将时域数据转换为频域数据，使得信号处理更加简化和高效。
下面将详细介绍FFT的算法原理和主要应用。
1.FFT算法原理：具体步骤如下：1）通过对输入序列进行重新排列，将序列按照奇偶位进行分组，分为两个长度为N/2的子序列。
2）对这两个子序列分别进行DFT计算，得到两个长度为N/2的频域序列。
3）将这两个序列分别与旋转因子进行乘积，得到两个长度为N/2的频域子序列。
4）将这两个频域子序列连接起来，得到长度为N的频域序列。
5）递归地将这个过程应用于每个子序列，直到序列长度为2，此时不需要再进行分解。
6）将分解后的频域序列进行合并和重排，得到最终的频域序列。
通过这种分治策略，FFT能够将DFT的复杂度从O(N^2)降低到O(NlogN)，大大提高了计算效率。
2.FFT的应用：（1）频谱分析：FFT算法可以将时域信号转换为频域信号，分析信号的频率成分和强度。
通过FFT，可以得到信号的频谱信息，帮助我们了解信号的频率特点和分布情况。
常见的应用包括音频分析、图像处理、通信信号分析等。
（2）信号处理：FFT在信号处理中广泛应用，例如滤波、模式识别、降噪等。
通过将信号转换为频域，在频域进行处理后再进行逆变换，可以实现对信号的特定频率的增强或者抑制。
（3）图像处理：FFT在图像处理中的应用主要是基于频率域滤波。
声波通信傅里叶变换(fft)算法声波通信是一种通过声波传输信息的通信方式。
在这种通信中，声波被用作信息的载体，可以通过声音的频率、振幅等特征来传递信息。
声波通信广泛应用于无线通信、水声通信和生物通信等领域。
为了实现高效、可靠的声波通信，傅里叶变换算法（Fast Fourier Transform，简称FFT）被广泛应用于声波信号的处理和分析。
傅里叶变换是一种将时域信号转换为频域信号的数学工具。
它可以将一个连续信号或离散信号表示为一组正弦和余弦函数的线性组合。
通过对信号进行傅里叶变换，我们可以得到信号的频谱信息，包括频率成分和振幅强度等。
在声波通信中，傅里叶变换通常用于对声音信号进行频谱分析和滤波处理。
FFT算法是一种高效地计算傅里叶变换的方法。
传统的傅里叶变换算法需要O(N^2)的计算复杂度，而FFT算法可以将计算复杂度降低到O(NlogN)，大大提高了计算效率。
FFT算法的基本思想是将一个长序列的傅里叶变换分解为若干个较短序列的傅里叶变换，然后再将得到的结果进行组合。
通过迭代的方式，可以逐步将一个复杂的傅里叶变换分解为多个简单的傅里叶变换的组合，从而实现了高效的计算。
在声波通信中，FFT算法可以用于多个方面。
首先，它可以用于声波信号的频谱分析。
通过对声音信号进行傅里叶变换，我们可以将声音信号表示为频率成分和振幅强度的形式。
这样可以帮助我们了解声音信号的频率分布和特征，进而判断信号的来源和内容。
例如，可以用FFT算法对音乐信号进行频谱分析，从而识别出音乐中的各个音调和乐器声音。
另外，FFT算法还可以用于声波信号的滤波处理。
通过对声波信号进行傅里叶变换，我们可以将信号从时域转换为频域。
然后，可以对频谱进行操作，例如提取感兴趣的频率成分、去除噪声成分等。
最后，再将得到的频谱信号进行傅里叶逆变换，将信号重新转换为时域。
通过这样的滤波处理，可以提高声波通信的质量和可靠性。
例如，在语音通信中，可以使用FFT算法对语音信号进行降噪处理，去除背景噪声，提高语音的清晰度。
knN W N N第四章 快速傅里叶变换有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长 序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换 (FFT). 1965 年，Cooley 和 Tukey 提出了计算离散傅里叶变换（DFT ）的快 速算法，将 DFT 的运算量减少了几个数量级。
从此，对快速傅里叶变换（FFT ） 算法的研究便不断深入，数字信号处理这门新兴学科也随 FFT 的出现和发 展而迅速发展。
根据对序列分解与选取方法的不同而产生了 FFT 的多种算 法，基本算法是基２DIT 和基２DIF 。
FFT 在离散傅里叶反变换、线性卷积 和线性相关等方面也有重要应用。
快速傅里叶变换（FFT ）是计算离散傅里叶变换（DFT ）的快速算法。
DFT 的定义式为N −1X (k ) = ∑ x (n )W NR N (k )n =0在所有复指数值 W kn 的值全部已算好的情况下，要计算一个 X (k ) 需要 N 次复数乘法和 N －1 次复数加法。
算出全部 N 点 X (k ) 共需 N 2次复数乘法和 N ( N − 1) 次复数加法。
即计算量是与 N 2成正比的。
FFT 的基本思想：将大点数的 DFT 分解为若干个小点数 DFT 的组合， 从而减少运算量。
W N 因子具有以下两个特性，可使 DFT 运算量尽量分解为小点数的 DFT运算：（1） 周期性：( k + N ) nN= W kn= W ( n + N ) k（2） 对称性：W( k + N / 2 )= −W kNN利用这两个性质，可以使 DFT 运算中有些项合并，以减少乘法次数。
例子：求当N＝4 时，X(2)的值4 NNN3∑44444X (2) = n =0x (n )W 2 n = x (0)W 0 + x (1)W 2 + x (2)W 4 + x (3)W 6= [ x (0) + x (2)]W 0 + [ x (1) + x (3)]W 2(周期性)4＝[ x (0) + x (2)]－[ x (1) + x (3)]W 04(对称性)通过合并，使乘法次数由 4 次减少到 1 次，运算量减少。
数字信号处理期末大作业FFT的发展史、现状及典型算法班级学号：姓名：FFT的发展史、现状及典型算法傅里叶分析已有200多年的历史，目前FFT及其校正算法在工程实际中仍在广泛应用，展现了其不竭的生命力。
本次作业我们论述FFT的现状，发展史以及一些算法，去详细了解、扩展这一算法，巩固所学知识。
一．FFT的简介傅里叶变换是一种将信号从时域变换到频域的变换形式，然而当N很大的时候，求一个N点的DFT要完成N*N次复数乘法和N*（N-1）次复数加法，计算量非常大，所以人们开始探索一种简便的算法对于一个较大的N进行傅里叶变换。
在20世纪60年代由Cooley和Tukey提出了快速傅里叶变换算法，它是快速计算DFT的一种简单高效的方法。
关于何为FFT，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。
举个例子，设x(n)为N项的复数序列，由DFT 变换，任一X（m）的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出N项复数序列的X（m）,即N点DFT变换大约就需要N^2次运算。
当N=1024点甚至更多的时候，需要N2=1048576次运算，在FFT中，利用WN的周期性和对称性，把一个N项序列（设N=2k,k为正整数），分为两个N/2项的子序列，每个N/2点DFT变换需要（N/2）2次运算，再用N次运算把两个N/2点的DFT变换组合成一个N点的DFT变换。
这样变换以后，总的运算次数就变成N+2*（N/2)^2=N+（N^2）/2。
继续上面的例子，N=1024时，总的运算次数就变成了525312次，节省了大约50%的运算量。
而如果我们将这种“一分为二”的思想不断进行下去，直到分成两两一组的DFT运算单元，那么N点的DFT变换就只需要Nlog2N次的运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算量的节约就越大，这就是FFT的优越性。
所以使用FFT算法，可以大大提高傅里叶变换的运算速度，运算时间缩短一到两个数量级，从而使DFT变换应用迅速普及，不仅在频谱分析，而且在线性卷积、线性相关等方面得到广泛应用。
二．FFT的现实意义随着计算机技术的发展，离散傅里叶变化的出现使得傅里叶变换在工程中进入实际应用阶段。
在信号处理中，DFT的计算具有举足轻重的作用，信号的相关、滤波、谱估计等都要通过DFT来实现，但必须减少它的运算量，DFT才能在工程计算中具有实用价值。
所以，FFT的出现提高了它的实用价值。
而FFT成为数字信号处理的关键技术，在信号处理领域扮演的角色越来越重要。
高效率的快速傅立叶变换(FFT)算法是雷达信号处理、卫星通讯、生物医学和多媒体信号处理等基础和核心算法。
提高FFT处理速度满足对雷达信号处理实时性的，要求在EW接收机高速数据处理方面将有广泛的应用前景。
随着科学技术的不断进步，相控阵体制已广泛应用于各种星载、机载、舰载和地面雷达。
对于电尺寸较大几十甚至几百个波长的相控阵天线，(如高分辨率星载，SAR天线、大型稀布阵天线等)，用公式按级数求和计算阵列天线方向图的方法效率甚低。
FFT的引入将从根本上解决这一难题。
平面近场测量方法是天线测量的常规手段而FFT技术加快了天线参数评估的速度。
三．傅里叶变换的发展历程对于发展史，我们由记载可知，离散傅里叶变换DFT是数字信号处理最重要的基石之一，也是对信号进行分析和处理时最常用的工具之一。
在200多年前法国数学家、物理学家傅里叶提出后来以他名字命名的傅里叶级数之后，用DFT 这个工具来分析信号就已经为人们所知。
历史上最伟大的数学家之一。
欧拉是第一个使用“函数”一词来描述包含各种参数的表达式的人，例如：y = f(x)。
他是把微积分应用于物理学的先驱者之一。
给出了一个用实变量函数表示傅立叶级数系数的方程；用三角级数来描述离散声音在弹性媒介中传播，发现某些函数可以通过余弦函数之和来表达。
但在很长时间内，这种分析方法并没有引起更多的重视，最主要的原因在于这种方法运算量比较大。
直到1965年，Cooley和Tukey在《计算机科学》发表著名的《机器计算傅立叶级数的一种算法》论文，FFT才开始大规模应用。
那个年代，有个肯尼迪总统科学咨询委员会。
其中有项研究主题是，对苏联核测试进行检测，Tukey就是其中一员。
美国/苏联核测试提案的批准，主要取决于不实地访问核测试设施而做出检测的方法的发展。
其中一个想法是，分析离海岸的地震计情况，这种计算需要快速算法来计算DFT。
其它应用是国家安全，如用声学探测远距离的核潜艇。
所以在军事上，迫切需要一种快速的傅立叶变换算法，这也促进了FFT的正式提出。
FFT的这种方法充分利用了DFT运算中的对称性和周期性，从而将DFT运算量从N2减少到N*log2N。
当N比较小时，FFT优势并不明显。
但当N大于32开始，点数越大，FFT对运算量的改善越明显。
比如当N为1024时，FFT的运算效率比DFT提高了100倍。
在库利和图基提出的FFT算法中，其基本原理是先将一个N点时域序列的DFT分解为N个1点序列的DFT，然后将这样计算出来的N 个1点序列DFT的结果进行组合，得到最初的N点时域序列的DFT值。
实际上，这种基本的思想很早就由德国伟大的数学家高斯提出过，在某种情况下，天文学计算（也是现在FFT应用的领域之一）与等距观察的有限集中的行星轨道的内插值有关。
由于当时计算都是靠手工，所以产生一种快速算法的迫切需要。
而且，更少的计算量同时也代表着错误的机会更少，正确性更高。
高斯发现，一个富氏级数有宽度N=N1*N2，可以分成几个部分。
计算N2子样本DFT的N1长度和N1子样本DFT的N2长度。
只是由于当时尚欠东风——计算机还没发明。
在20世纪60年代，伴随着计算机的发展和成熟，库利和图基的成果掀起了数字信号处理的革命，因而FFT发明者的桂冠才落在他们头上。
之后，桑德-图基等快速算法相继出现，几经改进，很快形成了一套高效运算方法，这就是现在的快速傅立叶变换（FFT）。
这种算法使DFT的运算效率提高1到2个数量级，为数字信号处理技术应用于各种信号的实时处理创造了良好的条件，大大推进了数学信号处理技术。
1984年，法国的杜哈梅和霍尔曼提出的分裂基块快速算法，使运算效率进一步提高。
库利和图基的FFT算法的最基本运算为蝶形运算，每个蝶形运算包括两个输入点，因而也称为基-2算法。
在这之后，又有一些新的算法，进一步提高了FFT 的运算效率，比如基-4算法，分裂基算法等。
这些新算法对FFT运算效率的提高一般在50%以内，远远不如FFT对DFT运算的提高幅度。
从这个意义上说，FFT 算法是里程碑式的。
可以说，正是计算机技术的发展和FFT的出现，才使得数字信号处理迎来了一个崭新的时代。
除了运算效率的大幅度提高外，FFT还大大降低了DFT运算带来的累计量化误差，这点常为人们所忽略。
以上为FFT的发展史，在整个发展历程中，傅里叶的发明作用尤为重要，后人的推动，改良在发展史上也起到了至关重要的作用。
四．FFT的现状、发展热度对于傅里叶变换的现状，我们分为国内国外两部分进行讨论：首先介绍国外现状，国外围绕快速傅立叶变换的并行计算进行了多项研究和开发。
美国新墨西哥大学Vasilios Georgitsis等人设计了2-DFFT程序，可处理512*512个点的图像，其底层通信基于PVM，将2-DFFT转化成1-DFFT并行计算，完成了二维图像的变换。
目前最新的研究成果是由麻省理工学院计算机科学实验室超级计算技术组开发的FFTW。
FFTW是计算离散傅里叶变换DFT的快速C程序的一个完整集合，它可计算一维或多维、实数据和复数据以及任意规模的DFT。
在FFTW中，DFT的计算由执行器完成。
执行器是由许多高度优化的、可组装的子代码模块组成的。
FFTW有一个规划器。
规划器用以根据具体机器的体系结构特点和具体的DFT宽度N。
在运行时寻找一种有效的子代码块组装方式，因此使得FFTW具有很好的自适应性和很快的运行速度。
FFTW还包含对共享和分布式存储系统的并行变换。
对于国内现状，在我国80年代初就开展了并行算法研究。
快速傅立叶变换的并行算法主要包括基于SIMD-MC2、SIMD-BF、SIMD-CC、MIMD-DM四种体系结构上的FFT算法，它们都是基-2FFT算法，算法各有利弊，受体系结构影响较大。
SIMD-MC2上的FFT算法是按频率抽取的快速傅立叶变换在网孔结构上的具体实现。
假设将n个处理器P0，P1，PN-1排成的方阵。
初始序列开始时已处于阵列的各处理器中，即ak处于Pk中。
算法结束时，Pk保存bk。
SIMD-BF上FFT算法是在一个n=2k的蝶形网络，简记为BF。
将(k+1)、2k个节点布局成(k+1)行，每行有n个节点。
令(r，i)表示第r行和第i列的坐标，0，i，n-1，exp(r，i)表示在BF中坐标点(r，i)处的w的指数，它等于字长为k的整数j，即exp(r，i)=j。
使得如果i的二进制表示为a1，a2，ar-1，ar，ak，则j的二进制为ar，ar-1……a1，00……0。
也就是说将i的前r位取位反，即倒序，后面其余位补零就可以得到j。
因为蝶形网络第r-1行和第r行之间的连接，正好能满足直接将dr-1，i和dr-1，j传到P(r，j)和P(r，j)，所以无需考虑选路时间。
算法时间除计算w、exp(r，i)的时间外，主要是算法第2步进行复数运算的时间。
它等于0( )，显然优于SIMD-MC2上的FFT算法，这也说明算法和体系结构的密切关系。
西安电子科技大学信息科学研究所提出了一种基于共享存储的多机系统并行计算FFT算法。
中国科学院计算技术研究所利用星型互联网的递归可分解性的多样性，提出了一种基于星型互联网络的并行快速傅立叶变换算法。
星图具有层次型结构，可由许多低维的子星图组成。
国防科大就向量机上的FFT并行算法作了系统的研究，并就离散变换、卷积和滤波的并行算法，用多项式变换计算离散卷积以及短卷积嵌套计算长卷积的并行算法，并研究了离散卷积的并行计算下界，对一维和二维滤波给出了用变换法及递推公式计算的并行算法。
可见无论在与国内还是国外，FFT算法都是研究的热点，有着广阔的发展前景。
五．基4FFT算法原理及介绍基4FFT算法是把长度N=4的序列一分为四，将N点DFT表示为4个N/4点DFT的线性组合。
然后再把N/4点DFT一分为四，表示为四个N /16点的DFT。
如此重复下去直至分解成两点DFT的运算。
多基时分蝶式运算定理在形式上比基2时分碟式运算定理复杂，但在本质上是一致的。
