FFT快速傅里叶变换23文档

1、快速傅里叶变换 （英语：Fast Fourier Tra nsform, FFT ），是离散傅里叶变换的快速算法，也可用于计算离散傅里叶变换的逆变换。快速傅里叶 变换有广泛的应用，如数字信号处理、计算大整数乘法、求解偏微分方程 等等。本条目只描述各种快速算法。对于复数序列工1|r工离散傅里叶变换公式为：直接变换的计算复杂度是。（刊（参见大0符号）。快速傅里叶变换可以 计算出与直接计算相同的结果，但只需要Onlogn）的计算复杂度。通常，快速算法要求n能被因数分解，但不是所有的快速傅里叶变换都要求n是合数，对于所有的整数n,都存在复杂度为O（nggn）的快速算法。除了指数的符号相反、并多了一个1

2、/n的因子，离散傅里叶变换的正变换与逆变换具有相同的形式。因此所有的离散傅里叶变换的快速算法同时适 用于正逆变换。目录隐藏?1 一般的简化理论? 2快速傅里叶变换乘法量的计算?3 Cooley-Tukey 算法o 3.1设计思想? 4其他算法?5实数或对称资料专用的算法?6复杂度以及运算量的极限?7参考资料?8参阅般的简化理论编辑假设一个M*N Sub-rectangular matrixS可分解成列向量以及行向量相乘：若蹩业 鸟乐有/心:个相异的non-trivialvalues(漏丰2ft, %丰土2九where“ |有 :个相异的 non-trivial values则S共需要打m我P：

3、个乘法Step 1 ：二 I . q.vStep 2 : ?1=血乙寸 Z 2=他乙、 j Z冈=简化理论的变型：一也是一个M*N的矩阵。若|有厂个值不等于0,则的乘法量上限为。快速傅里叶变换乘法量的计算编辑假设- 汽，其中訥込雄彼此互质it点DFT的乘法量为LS，则、点DFT的乘法量为：假设、 r，P是一个质数。若Ni =泛点的DFT需要的乘法量为Bl且Hi x 当中（斤= El， 1, 比龙=0,1 1的情形下，其需要4 log2 N 一 6A + 8个乘法运算以及加法运算。最近有人导出更低的运B4p_ n lo 雲丁 N算量：9 & 亠。(Johnson and Frigo, 2007;

4、 Lundy and Van Buskirk,2007)大多数尝试要降低或者证明FFT复杂度下限的人都把焦点放在复数资料输入的情况，因其为最简单的情形。但是，复数资料输入的FFT算法，与实数资料输入的FFT算法，离散余旋转换(DCT)，离散哈特列转换(DHT)，以 及其他的算法，均有很大的关连性。故任何一个算法，在复杂度上有任何的改善的话，其他的算法复杂度也会马上获得改善（Duhamel & Vetterli,1990）。快速傅里叶变换中文名称：快速傅里叶变换英文名称：fast Fourier tran sform;FFT定义：离散傅里叶变换的一种快速算法，能克服时间域与频率域之间相互转换的计

5、算障碍，在光谱、大气波谱分析、数字信号处理 等方面有广泛应用。应用学科：大气科学（一级学科）；动力气象学（二级学科）以上内容由全国科学技术名词审定委员会审定公布快速傅里叶变换计算离散傅里叶变换 的一种快速算法，简称FFTo快速傅里叶变换是1965 年由J.W.库利和T.W.图基提出的。采用这种 算法能使计算机计算 离散傅 里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。简要介绍有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化快速傅里叶变换成有限长序列。但其计算量太大，很难实时地处理问题，因此引出了快速傅里叶变换(FFT). 1965年，

6、Cooley和Tukey提出了计算离散傅里叶变换(DFT的快速算法，将 DFT的运算量减少了几个数量级。从此，对快速 傅里叶变换(FFT)算法的研究便不断深入，数字信号处理 这门新兴学科 也随FFT的出现和发展而迅速发展。根 据对序列分解与选取方法的不同而 产生了 FFT的多种算法，基本算法是基 2DIT和基2DIF。FFT在离散傅里 叶反变换、线性卷积和线性相关等方面也有重要应用。快速傅氏变换(FFT)，是离散傅氏变换的快速算法，它是根据离散傅氏 变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。 它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字 系统中应用离

7、散傅立叶变换，可以说是进了一大步。设快速傅里叶变换x(n )为N项的复数序列，由DFT变换，任一 X (m)的计算都需要N次复 数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数 加法，一次复数加法等于两次实快速傅里叶变换数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”(四次 实数乘法和四次实数加法)，那么求出N项复数序列的X( m ,即N点DFT变换大约就需要NT次运算。当N=1024点甚至更多的时候，需要 N2=1048576次运算，在FFT中，利用 WN的周期性和对称性， 把一个N项 序列(设N=2k,k为正整数)，分为两个 N/2项的子序列，每个 N/2点DF

8、T 变换需要(N/2)A2次运算，再用N次运算把两个N/2点的DFT变换组合 成一个N点的DFT变换。这样变换以后，总的运算次数就变成N+2*(N/2)八2二N+NA2/2。继续上面的例子，N=1024时，总的运算次数就变成了 525312 次，节省了大约50%勺运算量。而如果我们将这种“一分为二”的思想不 断进行下去，直到分成两两一组的DFT运算单元，那么N点的DFT变换就只需要Nlog2N次的运算，N在1024点时，运算量仅有10240次，是先前 的直接算法的1%点数越多，运算量的节约就越大，这就是FFT的优越性。编辑本段计算方法计算离散傅里叶变换的快速方法，有按时间抽取的FFT算法和按频

9、率抽取的FFT算法。前者是将时域信号序列按偶奇分排，后者是将频域信号序列 按偶奇分排。它们都借助于的两个特点：一是的周期性；另一是的对称性， 这里符号*代表其共轭。这样，便可以把离散傅里叶变换的计算分成若干 步进行，计算效率大为提高。时间抽取算法令信号序列的长度为N=2,其中M是正整数，可以将时域信号序列x(n)分解成两部分，一是偶数部分 x (2n),另一是奇数部分x(2n+1)，其中。于是信号序列 x( n)的离散傅里叶变换可以用两个N2抽样点的离散傅里叶变换来表示和计算。考虑到和离散傅里叶变换的周期性，式可以写成其中(4a)( 4b)由此可见，式是两个只含有 N/2个点的离散傅里叶 变换

10、，Qk)仅包括原信号序列中的偶数点序列， H；k)则仅包括它的奇数 点序列。虽然k=0，1, 2，NN1，但是Qk)和H(k)的周期都是 N2， 它们的数值以N/2周期重复。因为于是由式和式得到(5a)( 5b)因此，一个抽样点数为 N的信号序列x(n)的离散傅里叶变换，可以由两 个N2抽样点序列的离散傅里叶变换求出。依此类推，这种按时间抽取算法是将输入信号序列分成越来越小的子序列进行离散傅里叶变换计算，最 后合成为N点的离散傅里叶变换。通常用图1中蝶形算法的信号流图来表示式的离散傅里叶变换运算。例如，N=8=2的抽样点的信号序列x(n)的离散傅里叶变换，可用如图 2所 示的FET算法的信号流

11、图来计算。 N=2点的离散傅里叶变换的计算全由蝶形运算组成，需要M级运算，每级包括N2个蝶形运算，总共有 个蝶形运算。所以，总的计算量为次 复数乘法运算和Nlog2 N次复数加法运算。 FFT算法按级迭代进行，计算公式可以写成N抽样点的输入信号具有 N个原始数据x0( n)，经第一级运算后，得出 新的N个数据x1(n),再经过第二级迭代运算，又得到另外N个数据x2(n)， 依此类推，直至最后的结果 x(k)=xM(k)=X(k)在逐级迭代计算中，每个蝶 形运算的输出数据存放在原来存贮输入数据的单元中，实行所谓“即位计算”，这样可以节省大量存放中间数据的寄存器。 蝶形运算中加权系数随迭代级数成倍

12、增加。由图2可以看出系数的变化规律。对于N=8,M=3情况，需进行三级迭代运算。在第一级迭代中，只 用到一种加权系数；蝶形运算的跨度间隔等于1。在第二级迭代中，用到两种加权系数即、；蝶形运算的跨度间隔等于2。在第三级迭代中，用到4种不同的加权系数即、；蝶形运算的跨度间隔等于4。可见，每级迭代的不同加权系数的数目比前一级迭代增加一倍；跨度间隔也增大一倍。 输入数据序列x(n)需重新排列为x(0 )、x、x、x、x(l)、x、x、X(7),这是按照二进制数的码位倒置所得到的反序数，例如N=8中数“ 1”的二进制数为“ 001”，将其码位倒转变为“ 100”，即为十进制数“ 4”。频率抽取算法按频率

13、抽取的FFT算法是将频域信号序列 X(k)分解为奇偶两部分，但算法仍是由时域信号序列幵始逐级运算，同样是把N点分成N/2点计算FFT，可以把直接计算离散傅里叶变换所需的N次乘法缩减到次。在N=2的情况下，把N点输入序列x(n)分成前后两半时间序列x1(n) x2(n)的长度为N/2，于是N点的离散傅里叶变换可以 写成(8a)(8b)频率信号序列X (21 )是时间信号序列x1(n)+x2( n)的N2点离散傅里叶 变换，频率信号序列 X (21+1 )是时间信号序列【x1 (n)-x2( n)】的N/2 点离散傅里叶变换，因此，N点离散傅里叶变换的计算， 通过两次加(减) 法和一次乘法，从原来

14、序列获得两个子序列，所以，频率抽取算法也具有 蝶形运算形式。以2为基数的FFT基本蝶形运算公式为其计算量完全和时间抽取算法一样，即只需次乘法运算和Nog2 N次加(减) 法运算。图3表示N=8=2点的离散傅里叶变换的信号流图。由图可见，它 以三级迭代进行即位计算，输入数据是按自然次序存放，使用的系数也是 按自然次序，而最后结果则以二进制反序存放。实际上，频率抽取算法与时间抽取算法的信号流图之间存在着转置关系，如将流图适当变形，可以得出多种几何形状。除了基2的FFT算法之外，还有基4、基8等高基数的FFT算法以及任意 数为基数的FFT算法。补充：傅里叶变换：傅里叶变换能将满足一定条件的某个函数表

15、示成三角函数(正弦和/或余 弦函数)或者它们的积分的线性组合。在不同的研究领域，傅里叶变换具有多种不同的变体形式，如连续傅里叶变换和离散傅里叶变换。最初傅里叶分析是作为热过程的解析分析的工具被提出的。概念定义f(t )是t的函数，如果t满足狄里赫莱条件：具有有限个间断点；具有f(t )的傅有限个极值点；绝对可积。则有下图式成立。称为积分运算 立叶变换，式的积分运算叫做F(3 )的傅立叶逆变换。F(3 )叫做f(t )的像函 数，f(t )叫做F(3 )的像原函数。F(3 )是f(t )的像。f(t )是F(3 )原像。傅里叶变换傅里叶逆变换在信号处理中，傅里叶变换的典型用途是将信号分解成幅值谱

16、一一显示与频率对应的幅值大小离散形式的傅里叶变换可以利用数字计算机快速地算出(其算法称为快速傅里叶变换算法(FFT).卷积定理f(x,y) * h(x,y)F(u,v)H(u,v)f(x,y)h(x,y)v=F(u,v) * H(u,v)/2n (A * B 表示做 A 与 B 的卷积)连续傅立叶变换主条目：连续傅立叶变换。一般情况下，若“傅立叶变换” 一词的前面未加任何限定语，则指的是“连续傅立叶变换”。“连续傅立叶变换”将平方可积的函数f(t) 表示 成复指数函数的积分或级数形式。f(t) = mathca|AF ( w )=sqrt2 nintlimits_-inftynfty F(w)

17、eAi w t ,d w .上式其实表示的是连续傅立叶变换的逆变换，即将时间域的函数f(t )表示为频率域的函数F(w )的积分。反过来，其正变换恰好是将频率域的函数F (w )表示为时间域的函数 f(t )的积分形式。一般可称函数f(t )为原函数，而称函数F (w )为傅立叶变换的像函数，原函数和像函数构成一个傅立叶变换对(transform pair)。一种对连续傅立叶变换的推广称为分数傅立叶变换(Fractio nal FourierTransform )。当f(t )为奇函数(或偶函数)时，其余弦(或正弦)分量将消亡，而可以称这时的变换为余弦转换(cosine transform)或

18、 正弦转换(sinetran sform)。另一个值得注意的性质是，当f(t)为纯实函数时，F(- w) = F (w) *成立。离散傅立叶变换主条目：离散傅立叶变换 。为了在科学计算和 数字信号处理 等领域使用计算机进行傅立叶变换，必须 将函数xn定义在离散点而非连续域内，且须满足有限性或周期性条件。这种情况下，使用离散傅立叶变换，将函数 xn表示为下面的求和形式： x_n 二 frac1 sum_k=0A X_k eAifrac2pikn qquad n 二0,dots,N-1其中Xk是傅立叶振幅。直接使用这个公式计算的计算复杂度为 mathcal（n2 ），而快速傅立叶变换（FFT）可以

19、将复杂度改进为mathcal（n log n ）。计算复杂度的降低以及数字电路计算能力的发展使得DFT成为在信号处理领域十分实用且重要的方法因为正余弦波被定义成从负无穷大到正无穷大，我们无法把一个长度无 限的信号组合成长度有限的信号。面对这种困难，方法是把长度有限的信 号表示成长度无限的信号，可以把信号无限地从左右进行延伸，延伸的部 分用零来表示，这样，这个信号就可以被看成是非周期性离解信号，我们 就可以用到离散时域傅立叶变换的方法。还有，也可以把信号用复制的方法进行延伸，这样信号就变成了周期性离解信号，这时我们就可以用离散 傅立叶变换方法进行变换这里我们要学的是离散信号，对于连续信号我们不作

20、讨论，因为计算机 只能处理离散的数值信号，我们的最终目的是运用计算机来处理信号的。 离散傅立叶变换是离散时间傅立叶变换（ DTFT的特例（有时作为后者的 近似）。DTFT在时域上离散，在频域上则是周期的。DTFT可以被看作是傅立叶级数的逆。但是对于非周期性的信号，我们需要用无穷多不同频率的正弦曲线来表 示，这对于计算机来说是不可能实现的。所以对于离散信号的变换只有离 散傅立叶变换（DFT）才能被适用，对于计算机来说只有离散的和有限长 度的数据才能被处理，对于其它的变换类型只有在数学演算中才能用到， 在计算机面前我们只能用 DFT方法，后面我们要理解的也正是DFT方法。变换意义傅立叶变换是数字信

21、号处理领域一种很重要的算法。要知道傅立叶变换算 法的意义，首先要了解傅立叶原理的意义。傅立叶原理表明：任何连续测量的时序或信号，都可以表示为不同频率的正弦波信号的无限叠加。而根 据该原理创立的傅立叶变换算法利用直接测量到的原始信号，以累加方式 来计算该信号中不同正弦波信号的频率、振幅和相位。和傅立叶变换算法对应的是反傅立叶变换算法。该反变换从本质上说也是 一种累加处理，这样就可以将单独改变的正弦波信号转换成一个信号。从 现代数学的眼光来看，傅里叶变换是一种特殊的积分变换。它能将满足一 定条件的某个函数表示成正弦基函数的线性组合或者积分。在不同的研究 领域，傅里叶变换具有多种不同的变体形式，如连

22、续傅里叶变换和离散傅 里叶变换。因此，可以说，傅立叶变换将原来难以处理的时域信号转换成了易于分 析的频域信号（信号的频谱），可以利用一些工具对这些频域信号进行处 理、加工。最后还可以利用傅立叶反变换将这些频域信号转换成时域信号。 图像傅里叶：设f是一个能量有限的模拟信号，则其傅立叶变换就表示 的谱。从纯粹的数学意义上看，傅立叶变换是将一个函数转换为一系列周 期函数来处理的。从物理效果看，傅立叶变换是将图像从空间域转换到频 率域，其逆变换是将图像从频率域转换到空间域 中文名称：频率方向谱英文名称：directi onal spectrum其他名称：二维谱FFT是离散傅立叶变换的快速算法，可以将一个信号变换到频域。有些信 号在时域上是很难看出什么特征的，但是如果变换到频域之后，就很容易 看出特征了。这就是很多信号分析采用FFT变