快速傅里叶变换[编辑]
维基百科，自由的百科全书
跳转至：导航、搜索
傅里叶变换
Z变换
傅里叶级数
傅里叶变换
离散傅里叶级数
离散时间傅里叶变换
离散傅里叶变换
快速傅里叶变换
分数傅里叶变换
短时距傅立叶变换
小波变换
离散小波变换
连续小波变换
快速傅里叶变换（英语：Fast Fourier Transform, FFT），是离散傅里叶变换的快速算法，也可用于计算离散傅里叶变换的逆变换。快速傅里叶变换有广泛的应用，如数字信号处理、计算大整数乘法、求解偏微分方程等等。本条目只描述各种快速算法。
对于复数序列，离散傅里叶变换公式为：
直接变换的计算复杂度是（参见大O符号）。快速傅里叶变换可以计算出与直接计算相同的结果，但只需要的计算复杂度。通常，快速算法要求n能被因数分解，但不是所有的快速傅里叶变换都要求n是合数，对于所有的整数n，都存在复杂度为
的快速算法。
除了指数的符号相反、并多了一个1/n的因子，离散傅里叶变换的正变换与逆变换具有相同的形式。因此所有的离散傅里叶变换的快速算法同时适用于正逆变换。
目录
[隐藏]
? 1 一般的简化理论
? 2 快速傅里叶变换乘法量的计算
? 3 Cooley-Tukey算法
o 3.1 设计思想
? 4 其他算法
? 5 实数或对称资料专用的算法
? 6 复杂度以及运算量的极限
?7 参考资料
?8 参阅
一般的简化理论[编辑]
假设一个M*N Sub-rectangular matrix S可分解成列向量以及行向量相乘：
若有个相异的non-trivial
values( where )
有个相异的non-trivial values
则S共需要个乘法。
Step 1：
Step 2：
简化理论的变型：
也是一个M*N的矩阵。
若有个值不等于0，则的乘法量上限为。
快速傅里叶变换乘法量的计算[编辑]
假设，其中彼此互质点DFT的乘法量为，则点DFT的乘法量为：
假设，P是一个质数。
若点的DFT需要的乘法量为
且当中 () 有个值不为及的倍数，
有个值为及的倍数，但不为的倍数，
则N点DFT的乘法量为：
Cooley-Tukey算法[编辑]
主条目：Cooley-Tukey快速傅里叶变换算法
Cooley-Tukey算法是最常见的FFT算法。这一方法以分治法为策略递归地将长度为的DFT分解为长度分别为和的两个较短序列的DFT，以及与个旋转因子的复数乘法。
这种方法以及FFT的基本思路在1965年J. W. Cooley和J. W. Tukey 合作发表An algorithm for the machine calculation of complex Fourier series之后开始为人所知。但后来发现，实际上这两位作者只是重新发明了高斯在1805年就已经提出的算法(此算法在历史
上数次以各种形式被再次提出)。
Cooley-Tukey算法最有名的应用，是将序列长为N的DFT分割为两个长为N/2的子序列的DFT，因此这一应用只适用于序列长度为2的幂的DFT计算，即基2-FFT。实际上，如同高斯和Cooley与Tukey 都指出的那样，Cooley-Tukey算法也可以用于序列长度N为任意因数分解形式的DFT，即混合基FFT，而且还可以应用于其他诸如分裂基FFT等变种。尽管Cooley-Tukey算法的基本思路是采用递归的方法进行计算，大多数传统的算法实现都将显式的递归算法改写为非递归的形式。另外，因为Cooley-Tukey算法是将DFT分解为较小长度的多个DFT，因此它可以同任一种其他的DFT算法联合使用。
设计思想[编辑]
下面，我们用N次单位根来表示。
的性质：
1.周期性，具有周期，即
2.对称性：。
3.若是的约数，
为了简单起见，我们下面设待变换序列长度。根据上面单位
根的对称性，求级数时，可以将求和区间分为两部分：
和是两个分别关于序列奇数号和偶数号序列N/2点变换。由此式只能计算出的前N/2个点，对于后N/2个点，注意和都是周期为N/2的函数，由单位根的对称性，于是有以下变换公式：
这样，一个N点变换就分解成了两个N/2点变换。照这样可继续分解下去。这就是库利-图基快速傅里叶变换算法的基本原理。根据主定理不难分析出此时算法的时间复杂度为
其他算法[编辑]
在Cooley-Tukey算法之外还有其他DFT的快速算法。对于长度N = N1N2且N_1与N_2互质的序列，可以采用基于中国剩余定理的互质因子算法将N 长序列的DFT分解为两个子序列的DFT。与
Cooley-Tukey 算法不同的是，互质因子算法不需要旋转因子。Rader-Brenner 算法是类似于 Cooley-Tukey 算法，但是采用的旋转因子都是纯虚数，以增加加法运算和降低了数值稳定性为代价减少了乘法运算。这方法之后被split-radix variant of Cooley-Tukey所取代，与Rader-Brenner算法相比，有一样多的乘法量，却有较少的加法量，且不牺牲数值的准确性。
Bruun以及QFT算法是不断的把DFT分成许多较小的DFT运算。(Rader-Brenner以及QFT算法是为了2的指数所设计的算法，但依然可以适用在可分解的整数上。Bruun算法则可以运用在可被分成偶数个运算的数字)。尤其是Bruun算法，把FFT看成是，并把它分解成与的形式。
另一个从多项式观点的快速傅立叶变换法是Winograd 算法。此算法把分解成cyclotomic多项式，而这些多项式的系数通常为1，0，-1。这样只需要很少的乘法量(如果有需要的话)，所以winograd 是可以得到最少乘法量的快速傅立叶算法，对于较小的数字，可以找出有效率的算方式。更精确地说，winograd算法让DFT可以用点的DFT来简化，但减少乘法量的同时，也增加了非常多的加法量。Winograd也可以利用剩余值定理来简化DFT。
Rader算法提出了利用点数为N(N为质数)的DFT进行长度为N-1的回旋折积来表示原本的DFT，如此就可利用折积用一对基本的FFT来计算DFT。另一个prime-size的FFT算法为chirp-Z算法。此法也是将DFT用折积来表示，此法与Rader算法相比，能运用在更一般的转换上，其转换的基础为Z转换(Rabiner et al., 1969)。
实数或对称资料专用的算法[编辑]
在许多的运用当中，要进行DFT的资料是纯实数，如此一来经过DFT 的结果会满足对称性：
而有一些算法是专门为这种情形设计的(e.g. Sorensen, 1987)。另一些则是利用旧有的算法(e.g. Cooley-Tukey)，删去一些不必要的演算步骤，如此省下了记忆体的使用，也省下了时间。另一方面，也可以把一个偶数长度且纯实数的DFT，用长度为原本一半的复数型态DFT来表示(实数项为原本纯实数资料的偶数项，虚数项则为奇数项)。一度人们认为，用离散哈特利转换(Discrete Hartley Transform)
来处理纯实数的DFT会更有效率，但接着人们发现，对于同样点数的纯实数DFT，经过设计的FFT，可以比DHT省下更多的运算。Bruun
算法是第一个试着从减少实数输入的DFT运算量的算法，但此法并没有成为人们普遍使用的方法。
对于实数输入，且输入为偶对称或奇对称的情形，可以更进一步的省下时间以及记忆体，此时DFT可以用离散余弦转换或离散正弦转换来
代替(Discrete cosine/sine transforms)。由于DCT/DST也可以设计出FFT的算法，故在此种情形下，此方法取代了对DFT设计的FFT 算法。
DFT可以应用在频谱分析以及做折积的运算，而在此处，不同应用可以用不同的算法来取代，列表如下：
用来做频谱分析的情况下，DFT可用下列的算法代替：
?DCT.
?DST.
?DHT.
?正交基底的扩展(orthogonal basis expantion)包括正交多项式(orthogonal polynomials)以及CDMA.
?Walsh(Hadamard)转换.
?Haar转换
?小波(wavelet)转换.
?时频分布(time-frequency distribution)
用来做折积的情况下，DFT可用下列的算法代替：
?DCT.
?DST.
?DHT.
?直接做折积(direct computing)
?分段式DFT折积(sectioned DFT convolution)
?威诺格拉德快速傅里叶变换算法
?Walsh(Hadamard)转换
?数论转换
复杂度以及运算量的极限[编辑]
长久以来，人们对于求出快速傅里叶变换的复杂度下限以及需要多少的运算量感到很有兴趣，而实际上也还有许多问题需要解决。即使是用较简单的情形，即点的DFT，也还没能够严谨的证明出FFT至少需要(比NlogN大)的运算量，目前也没有发现复杂度更低的算法。通常数学运算量的多寡会是运算效率好坏最主要的因素，但在现实中，有许多因素也会有很大的影响，如快取内存以及CPU均有很大的影响。
在1978年，Winograd率先导出一个较严谨的FFT所需乘法量的下限：。当时，DFT只需要次无理实数的乘法即可以计算出来。更详尽，且也能趋近此下限的算法也一一被提出(Heideman & Burrus, 1986; Duhamel, 1990)。很可惜的是，这些算法，都需要很大量的加法计算，目前的硬件无法克服这个问题。
对于所需加法量的数目，虽然我们可以在某些受限制的假设下，推得其下限，但目前并没有一个精确的下限被推导出来。1973年，Morgenstern在乘法常数趋近巨大的情形下(对大部分的FFT算法为
真，但不是全部)推导出加法量的下限：。Pan(1986)在假设FFT算法的不同步的情形有其极限下证明出加法量的下限
，但一般来说，此假设相当的不明确。长度为的情形下，在某些假设下，Papadimitriou(1979)提出使用Cooley-Tukey 算法所需的复数加法量是最少的。到目前为止，在长度为情况，还没有任何FFT的算法可以让复数的加法量比
还少。
还有一个问题是如何把乘法量与加法量的总和最小化，有时候称作"演算复杂度"(在这里考虑的是实际的运算量，而不是渐近复杂度)。同样的，没有一个严谨下限被证明出来。从1968年开始，点DFT而言，split-radix FFT算法需要最少的运算量，在的情形下，其需要个乘法运算以及加法运算。最近有人导出更低的运算量：。(Johnson and Frigo, 2019; Lundy and Van Buskirk, 2019)
大多数尝试要降低或者证明FFT复杂度下限的人都把焦点放在复数
资料输入的情况，因其为最简单的情形。但是，复数资料输入的FFT 算法，与实数资料输入的FFT算法，离散余旋转换(DCT)，离散哈特列转换(DHT)，以及其他的算法，均有很大的关连性。故任何一个算法，在复杂度上有任何的改善的话，其他的算法复杂度也会马上获得改善(Duhamel & Vetterli, 1990)。
快速傅里叶变换
中文名称：
快速傅里叶变换
英文名称：
fast Fourier transform;FFT
定义：
离散傅里叶变换的一种快速算法，能克服时间域与频率域之间相互转换的计算障碍，在光谱、大气波谱分析、数字信号处理等方面有广泛应用。
应用学科：
大气科学（一级学科）；动力气象学（二级学科）
以上内容由全国科学技术名词审定委员会审定公布
快速傅里叶变换
计算离散傅里叶变换的一种快速算法，简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。
简要介绍
有限长序列可以通过离散傅里叶变换(DFT）将其频域也离散化
快速傅里叶变换
成有限长序列。但其计算量太大，很难实时地处理问题，因此引出了快速傅里叶变换(FFT). 1965年，Cooley和Tukey提出了计算离散傅里叶变换（DFT）的快速算法，将DFT的运算量减少了几个数量级。从此，对快速傅里叶变换（FFT）算法的研究便不断深入，数字信号处理这门新兴学科也随FFT的出现和发展而迅速发展。根据对序列分解与选取方法的不同而产生了FFT的多种算法，基本算法是基2DIT和基2DIF。FFT在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用。
快速傅氏变换（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算法和按频率抽取的FFT 算法。前者是将时域信号序列按偶奇分排，后者是将频域信号序列按偶奇分排。它们都借助于的两个特点：一是的周期性；另一是的对称性，这里符号*代表其共轭。这样，便可以把离散傅里叶变换的计算分成若干步进行，计算效率大为提高。
时间抽取算法令信号序列的长度为N=2,其中M是正整数，可以将时域信号序列x(n)分解成两部分，一是偶数部分x（2n），另一是奇数部分x（2n+1），其中。于是信号序列x(n）的离散傅里叶变换可以用两个N/2抽样点的离散傅里叶变换来表示和计算。考虑到和离散傅里叶变换的周期性，式⑴可以写成
⑶其中（4a）（4b）由此可见，式⑷是两个只含有N/2个点的离散傅里叶变换，G(k）仅包括原信号序列中的偶数点序列，H(k）则仅包括它的奇数点序列。虽然k=0，1，2，…，N-1，但是G(k）和H(k）的周期都是N/2，它们的数值以N/2
周期重复。
因为于是由式⑶和式⑷得到（5a）（5b)
因此，一个抽样点数为N的信号序列x(n）的离散傅里叶变换，可以由两个N/2抽样点序列的离散傅里叶变换求出。依此类推，这种按时间抽取算法是将输入信号序列分成越来越小的子序列进行离散傅里叶变换计算，最后合成为N点的离散傅里叶变换。
通常用图1中蝶形算法的信号流图来表示式⑸的离散傅里叶变换运算。例如，
N=8=2的抽样点的信号序列x(n）的离散傅里叶变换，可用如图2所示的FET算法的信号流图来计算。
①N=2点的离散傅里叶变换的计算全由蝶形运算组成，需要M级运算，每级包括N/2个蝶形运算，总共有个蝶形运算。所以，总的计算量为次复数乘法运算和N log2N次复数加法运算。
②FFT算法按级迭代进行，计算公式可以写成
⑹N抽样点的输入信号具有N个原始数据x0(n），经第一级运算后，得出新的N 个数据x1(n），再经过第二级迭代运算，又得到另外N个数据x2(n），依此类推，直至最后的结果x(k)=xM(k)=X(k）在逐级迭代计算中，每个蝶形运算的输
出数据存放在原来存贮输入数据的单元中，实行所谓“即位计算”，这样可以节省大量存放中间数据的寄存器。
③蝶形运算中加权系数随迭代级数成倍增加。由图2可以看出系数的变化规律。对于N=8,M=3情况，需进行三级迭代运算。在第一级迭代中，只用到一种加权系
数；蝶形运算的跨度间隔等于1。在第二级迭代中，用到两种加权系数即、；蝶形运算的跨度间隔等于2。在第三级迭代中，用到4种不同的加权系数即、、、；蝶形运算的跨度间隔等于4。可见，每级迭代的不同加权系数的数目比前一级迭代增加一倍；跨度间隔也增大一倍。
④输入数据序列x(n）需重新排列为x(0）、x⑷、x⑵、x⑹、x⑴、x⑸、x⑶、x⑺，这是按照二进制数的码位倒置所得到的反序数，例如N=8中数“1”的二进制数为“001”，将其码位倒转变为“100”，即为十进制数“4”。
频率抽取算法按频率抽取的 FFT算法是将频域信号序列X(k）分解为奇偶两部分，但算法仍是由时域信号序列开始逐级运算，同样是把N点分成N/2点计算FFT，可以把直接计算离散傅里叶变换所需的N次乘法缩减到次。
在N=2的情况下，把N点输入序列x(n）分成前后两半
时间序列x1(n）±x2(n）的长度为N/2，于是N点的离散傅里叶变换可以写成（8a)
（8b)
频率信号序列X（2l）是时间信号序列x1(n)+x2(n）的N/2点离散傅里叶变换，频率信号序列X（2l+1）是时间信号序列【x1(n)-x2(n）】的N/2点离散傅里叶变换，因此，N点离散傅里叶变换的计算，通过两次加（减）法和一次乘法，从原来序列获得两个子序列，所以，频率抽取算法也具有蝶形运算形式。以2为基数的FFT基本蝶形运算公式为
其计算量完全和时间抽取算法一样，即只需次乘法运算和N log2N次加（减）法运算。图3 表示N=8=2点的离散傅里叶变换的信号流图。由图可见，它以三级迭代进行即位计算，输入数据是按自然次序存放，使用的系数也是按自然次序，而最后结果则以二进制反序存放。
实际上，频率抽取算法与时间抽取算法的信号流图之间存在着转置关系，如将流图适当变形，可以得出多种几何形状。
除了基2的FFT算法之外，还有基4、基8等高基数的FFT算法以及任意数为基数的FFT算法。
补充：傅里叶变换：
傅里叶变换能将满足一定条件的某个函数表示成三角函数（正弦和/或余弦函数）或者它们的积分的线性组合。在不同的研究领域，傅里叶变换具有多种不同的变体形式，如连续傅里叶变换和离散傅里叶变换。最初傅里叶分析是作为热过程的解析分析的工具被提出的。
概念
定义
f(t）是t的函数，如果t满足狄里赫莱条件：具有有限个间断点；具有有限个极值点；绝对可积。则有下图①式成立。称为积分运算f(t）的傅立叶变换，
②式的积分运算叫做F（ω）的傅立叶逆变换。F（ω）叫做f(t）的像函数，f(t）叫做
F（ω）的像原函数。F（ω）是f(t）的像。f(t）是F（ω）原像。
傅里叶变换
傅里叶逆变换
在信号处理中，傅里叶变换的典型用途是将信号分解成幅值谱——显示与频率对应的幅值大小
离散形式的傅里叶变换可以利用数字计算机快速地算出（其算法称为快速傅里叶变换算法（FFT)).
卷积定理
f(x,y) * h(x,y)<=>F(u,v)H(u,v)
f(x,y)h(x,y)<=>[F(u,v) * H(u,v)]/2π(A * B 表示做A与B的卷积）
连续傅立叶变换
主条目：连续傅立叶变换。
一般情况下，若“傅立叶变换”一词的前面未加任何限定语，则指的是“连续傅立叶变换”。“连续傅立叶变换”将平方可积的函数f(t) 表示成复指数函数的积分或级数形式。
f(t) = \mathcal^[F（ω）] = \frac{\sqrt{2π}} \int\limits_{-\infty}^\infty F（ω）e^{iωt}\,dω.
上式其实表示的是连续傅立叶变换的逆变换，即将时间域的函数f(t）表示为频率域的函数F （ω）的积分。反过来，其正变换恰好是将频率域的函数F（ω）表示为时间域的函数f(t）的积分形式。一般可称函数f(t）为原函数，而称函数F（ω）为傅立叶变换的像函数，原函数和像函数构成一个傅立叶变换对（transform pair）。
一种对连续傅立叶变换的推广称为分数傅立叶变换（Fractional Fourier Transform）。
当f(t）为奇函数（或偶函数）时，其余弦（或正弦）分量将消亡，而可以称这时的变换为余弦转换（cosine transform) 或正弦转换（sine transform)。
另一个值得注意的性质是，当f(t) 为纯实函数时，F(?ω）= F（ω）*成立。
离散傅立叶变换
主条目：离散傅立叶变换。
为了在科学计算和数字信号处理等领域使用计算机进行傅立叶变换，必须将函数xn定义在离散点而非连续域内，且须满足有限性或周期性条件。这种情况下，使用离散傅立叶变换，将函数xn 表示为下面的求和形式：
x_n = \frac1 \sum_{k=0}^ X_k e^{i\frac{2\pi} kn} \qquad n = 0,\dots,N-1
其中Xk是傅立叶振幅。直接使用这个公式计算的计算复杂度为\mathcal(n^2），而快速傅立叶变换（FFT）可以将复杂度改进为\mathcal(n \log n）。计算复杂度的降低以及数字电路计算能力的发展使得DFT成为在信号处理领域十分实用且重要的方法
因为正余弦波被定义成从负无穷大到正无穷大，我们无法把一个长度无限的信号组合成长度有限的信号。面对这种困难，方法是把长度有限的信号表示成长度无限的信号，可以把信号无限地从左右进行延伸，延伸的部分用零来表示，这样，这个信号就可以被看成是非周期性离解信号，我们就可以用到离散时域傅立叶变换的方法。还有，也可以把信号用复制的方法进行延伸，这样信号就变成了周期性离解信号，这时我们就可以用离散傅立叶变换方法进行变换
这里我们要学的是离散信号，对于连续信号我们不作讨论，因为计算机只能处理离散的数值信号，我们的最终目的是运用计算机来处理信号的。
离散傅立叶变换是离散时间傅立叶变换（DTFT）的特例（有时作为后者的近似）。DTFT在时域上离散，在频域上则是周期的。DTFT可以被看作是傅立叶级数的逆。
但是对于非周期性的信号，我们需要用无穷多不同频率的正弦曲线来表示，这对于计算机来说是不可能实现的。所以对于离散信号的变换只有离散傅立叶变换（DFT）才能被适用，对于计算机来说只有离散的和有限长度的数据才能被处理，对于其它的变换类型只有在数学演算中才能用到，在计算机面前我们只能用DFT方法，后面我们要理解的也正是DFT方法。
变换意义
傅立叶变换是数字信号处理领域一种很重要的算法。要知道傅立叶变换算法的意义，首先要了解傅立叶原理的意义。傅立叶原理表明：任何连续测量的时序或信号，都可以表示为不同频率的正弦波信号的无限叠加。而根据该原理创立的傅立叶变换算法利用直接测量到的原始信号，以累加方式来计算该信号中不同正弦波信号的频率、振幅和相位。
和傅立叶变换算法对应的是反傅立叶变换算法。该反变换从本质上说也是一种累加处理，这样就可以将单独改变的正弦波信号转换成一个信号。从现代数学的眼光来看，傅里叶变换是一种特殊的积分变换。它能将满足一定条件的某个函数表示成正弦基函数的线性组合或者积分。在不同的研究领域，傅里叶变换具有多种不同的变体形式，如连续傅里叶变换和离散傅里叶变换。
因此，可以说，傅立叶变换将原来难以处理的时域信号转换成了易于分析的频域信号（信号的频谱），可以利用一些工具对这些频域信号进行处理、加工。最后还可以利用傅立叶反变换将这些频域信号转换成时域信号。
图像傅里叶：设f是一个能量有限的模拟信号，则其傅立叶变换就表示f的谱。从纯粹的数学意义上看，傅立叶变换是将一个函数转换为一系列周期函数来处理的。从物理效果看，傅立叶变换是将图像从空间域转换到频率域，其逆变换是将图像从频率域转换到空间域
中文名称：
[频率]方向谱
英文名称：
directional spectrum
其他名称：
二维谱
FFT是离散傅立叶变换的快速算法，可以将一个信号变换到频域。有些信号在时域上是很难看出什么特征的，但是如果变换到频域之后，就很容易看出特征了。这就是很多信号分析采用FFT变换的原因。另外，FFT可以将一个信号的频谱提取出来，这在频谱分析方面也是经常用的。FFT结果的具体物理意义。一个模拟信号，经过ADC采样之后，就变成了数字信号。采样定理告诉我们，采样频率要大于信号频率的两倍
总结：假设采样频率为Fs，采样点数为N，做FFT之后，某一点n（n从1开始）表示的频率为：Fn=(n-1)*Fs/N；该点的模值除以N/2就是对应该频率下的信号的幅度（对于直流信号是除以N）；该点的相位即是对应该频率下的信号的相位。相位的计算可用函数atan2(b,a)计算。atan2(b,a)是求坐标为(a,b)点的角度值，范围从-pi到pi。要精确到xHz，则需要采样长度为1/x秒的信号，并做FFT。要提高频率分辨率，就需要增加采样点数，这在一些实际的应用中是不现实的，需要在较短的时间内完成分析。解决这个问题的方法有频率细分法，比较简单的方法是采样比较短时间的信号，然后在后面补充一定数量的0，使其长度达到需要的点数，再做FFT，这在一定程度上能够提高频率分辨力。具体的频率细分法可参考相关文
献
傅立叶变换是数字信号处理中的基本操作，广泛应用于表述及分析离散时域信号领域。但由于其运算量与变换点数N的平方成正比关系，因此，在N较大时，直接应用DFT算法进行谱变换是不切合实际的。然而，快速傅立叶变换技术的出现使情况发生了根本性的变化。本文主要描述了采用FPGA来实现2k/4k/8k点FFT的设计方法
快速傅里叶变换 FFT是离散傅立叶变换的快速算法，可以将一个信号变换到频域。有些信号在时域上是很难看出什么特征的，但是如果变换到频域之后，就很容易看出特征了。这就是很多信号分析采用FFT变换的原因。另外，FFT可以将一个信号的频谱提取出来，这在频谱分析方面也是经常用的。 虽然很多人都知道FFT是什么，可以用来做什么，怎么去做，但是却不知道FFT之后的结果是什意思、如何决定要使用多少点来做FFT。 现在圈圈就根据实际经验来说说FFT结果的具体物理意义。一个模拟信号，经过ADC采样之后，就变成了数字信号。采样定理告诉我们，采样频率要大于信号频率的两倍，这些我就不在此罗嗦了。 采样得到的数字信号，就可以做FFT变换了。N个采样点，经过FFT之后，就可以得到N个点的FFT结果。为了方便进行FFT运算，通常N取2的整数次方。 假设采样频率为Fs，信号频率F，采样点数为N。那么FFT之后结果就是一个为N点的复数。每一个点就对应着一个频率点。这个点的模值，就是该频率值下的幅度特性。具体跟原始信号的幅度有什么关系呢？假设原始信号的峰值为A，那么FFT的结果的每个点（除了第一个点直流分量之外）的模值就是A的N/2倍。而第一个点就是直流分量，它的模值就是直流分量的N倍。而每个点的相位呢，就是在该频率下的信号的相位。第一个表示直流分量（即0Hz），而最后一个点N的再下一个点（实际上这个点是不存在的，这里是假设的第N+1个点，也可以看做是将第一个点分做两半分，另一半移到最后）则表示 采样频率Fs，这中间被N-1个点平均分成N等份，每个点的频率依次增加。例如某点n所表示的频率为：Fn=(n-1)*Fs/N。由上面的公式可以看出，Fn所能分辨到频率为为Fs/N，如果采样频率Fs为1024Hz，采样点数为1024点，则可以分辨到1Hz。1024Hz的采样率采样1024点，刚好是1秒，也就是说，采样1秒时间的信号并做FFT，则结果可以分析到1Hz，如果采样2秒时间的信号并做FFT，则结果可以分析到0.5Hz。如果要提高
快速傅里叶变换(FFT)的DSP 实现 (马灿明 计算机学院 计算机应用技术 2110605410) 摘要:本文对快速傅里叶变换(FFT)原理进行简单介绍后，然后介绍FFT 在TMS320C55xx 定 点DSP 上的实现，FFT 算法采用C 语言和汇编混合编程来实现，算法程序利用了CCS 对其结果进行了仿真。 关键字：FFT ，DSP ，比特反转 1.引言 傅里叶变换是将信号从时域变换到频域的一种变换形式，是信号处理领域中一种重要的分析工具。离散傅里叶变换（DFT ）是连续傅里叶变换在离散系统中的表现形式。由于DFT 的计算量很大，因此在很长一段时间内使其应用受到很大的限制。 20世纪60年代由Cooley 和Tukey 提出了快速傅里叶变换（FFT ）算法，它是快速计算DFT 的一种高效方法，可以明显地降低运算量，大大地提高DFT 的运算速度，从而使DFT 在实际中得到了广泛的应用，已成为数字信号处理最为重要的工具之一。 DSP 芯片的出现使FFT 的实现变得更加方便。由于多数的DSP 芯片都能在单指令周期内完成乘法—累加运算，而且还提供了专门的FFT 指令（如实现FFT 算法所必需的比特反转等），使得FFT 算法在DSP 芯片上实现的速度更快。本节首先简要介绍FFT 算法的基本原理，然后介绍FFT 算法的DSP 实现。 2.FFT 算法的简介 快速傅里叶变换（FFT ）是一种高效实现离散傅里叶变换（DFT ）的快速算法，是数字信号处理中最为重要的工具之一，它在声学，语音，电信和信号处理等领域有着广泛的应用。 2.1离散傅里叶变换DFT 对于长度为N 的有限长序列x(n)，它的离散傅里叶变换（DFT ）为 1,1,0, )()(1 0-==∑-=N k W n x k X n n nk N （1） 式中， N j N e W /2π-= ，称为旋转因子或蝶形因子。 从DFT 的定义可以看出，在x(n)为复数序列的情况下，对某个k 值，直接按（1） 式计算X(k) 只需要N 次复数乘法和（N-1）次复数加法。因此，对所有N 个k 值，共需要N 2 次复数乘法和N(N-1)次复数加法。对于一些相当大有N 值（如1024点）来说，直接计算它的DFT 所需要的计算量是很大的，因此DFT 运算的应用受到了很大的限制。 2.2快速傅里叶变换FFT 旋转因子W N 有如下的特性。 。对称性： 2/N k N k N W W +-= 。周期性： N k N k N W W += 利用这些特性，既可以使DFT 中有些项合并，减少了乘法积项，又可以将长序列的DFT
kn N W N N 第四章 快速傅里叶变换 有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长 序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换 (FFT). 1965 年，Cooley 和 Tukey 提出了计算离散傅里叶变换（DFT ）的快 速算法，将 DFT 的运算量减少了几个数量级。从此，对快速傅里叶变换（FFT ） 算法的研究便不断深入，数字信号处理这门新兴学科也随 FFT 的出现和发 展而迅速发展。根据对序列分解与选取方法的不同而产生了 FFT 的多种算 法，基本算法是基２DIT 和基２DIF 。FFT 在离散傅里叶反变换、线性卷积 和线性相关等方面也有重要应用。 快速傅里叶变换（FFT ）是计算离散傅里叶变换（DFT ）的快速算法。 DFT 的定义式为 N ?1 X (k ) = ∑ x (n )W N R 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 ) n N = W kn = W ( n + N ) k （2） 对称性：W ( k + N / 2 ) = ?W k N N 利用这两个性质，可以使 DFT 运算中有些项合并，以减少乘法次数。例子： 求当 N ＝4 时，X(2)的值
#include 实验四 快速傅里叶变换（FFT ） 4.1实验目的 1）加深对快速傅里叶变换（FFT ）基本理论的理解； 2）了解使用快速傅里叶变换（FFT ）计算有限长序列和无限长序列信号频谱的方法； 3）掌握用MATLAB 语言进行快速傅里叶变换时常用的子函数。 4.2实验原理 1）用MATLAB 提供的子函数进行快速傅里叶变换 从理论学习可知，DFT 是唯一在时域和频域均为离散序列的变换方法，它适用于有限长序列。尽管这种变换方法是可以用于数值计算的，但如果只是简单的按照定义进行数据处理，当序列长度很大时，则将占用很大的内存空间，运算时间将很长。 快速傅里叶变换是用于DFT 运算的高效运算方法的统称，FFT 只是其中的一种。FFT 主要有时域抽取算法和频域抽取算法，基本思想是将一个长度为N 的序列分解成多个短序列，如基2算法、基4算法等，大大缩短了运算的时间。 MATLAB 中提供了进行快速傅里叶变换（FFT ）的子函数，用fft 计算DFT ，用ifft 计算IDFT 。 2）用FFT 计算有限长序列的频谱 基本概念： 一个序号从1n 到2n 的时域有限长序列()x n ，它的频谱()j X e ω定义为它的离散时间傅里叶变换，且在奈奎斯特（Nyquist ）频率范围内有界并连续。序列的长度为N ，则211N n n =?+。计算()x n 的离散傅里叶变换（DFT ）得到的是()j X e ω的N 个样本点()k j X e ω。其中数字频率为 k 2πω()d ωk k N == 式中：d ω为数字频率的分辨率；k 取对应－(N －1)/2到(N －1)/2区间的整数。 在实际使用中，往往要求计算出信号以模拟频率为横坐标的频谱，此时对应的模拟频率为 s s 2π2π?ω/T ()()T k k k k kD N L ==== 式中：D 为模拟频率的分辨率或频率间隔；T s 为采样信号的周期，Ts ＝1/Fs ；定义信号时域长度L ＝N T s 。 第一章 快速傅里叶变换（FFT ） 4.1 填空题 （1）如果序列)(n x 是一长度为64点的有限长序列)630(≤≤n ，序列)(n h 是一长度为128点 的有限长序列)1270 (≤≤n ，记)()()(n h n x n y *=（线性卷积），则)(n y 为 点的序列，如果 采用基FFT 2算法以快速卷积的方式实现线性卷积，则FFT 的点数至少为 点。 解：64+128-1＝191点; 256 (2)如果一台通用机算计的速度为：平均每次复乘需100s μ，每次复加需20s μ，今用来计算N=1024点的DFT )]([n x 。问直接运算需（ ）时间，用FFT 运算需要（ ）时间。 解：①直接运算：需复数乘法2 N 次，复数加法） （1-N N 次。 直接运算所用计算时间1T 为 s s N N N T 80864.12512580864020110021==?-+?=μ）（ ② 基2FFT 运算：需复数乘法 N N 2log 2 次，复数加法N N 2log 次。 用FFT 计算1024点DTF 所需计算时间2T 为 s s N N N N T 7168.071680020log 100log 2 222==?+?=μ。 (3)快速傅里叶变换是基于对离散傅里叶变换 和利用旋转因子k N j e π2-的 来减少计算量，其特点是 _______、_________和__________。 解：长度逐次变短；周期性；蝶形计算、原位计算、码位倒置 （4）N 点的FFT 的运算量为复乘 、复加 。 解：N N L N mF 2log 2 2== ；N N NL aF 2log == 4.2 选择题 1．在基2DIT —FFT 运算中通过不断地将长序列的DFT 分解成短序列的DFT ，最后达到2点DFT 来降低运算量。若有一个64点的序列进行基2DIT —FFT 运算，需要分解 次，方能完成运算。 A.32 B.6 C.16 D. 8 解：B 2．在基2 DIT —FFT 运算时，需要对输入序列进行倒序，若进行计算的序列点数N=16，倒序前信号点序号为8，则倒序后该信号点的序号为 。 A. 8 B. 16 C. 1 D. 4 解：C 3．在时域抽取FFT 运算中，要对输入信号x(n)的排列顺序进行“扰乱”。在16点FFT 中，原来x(9) 快速傅里叶变换(FFT)的原理及公式 原理及公式 非周期性连续时间信号x(t)的傅里叶变换可以表示为 式中计算出来的是信号x(t)的连续频谱。但是，在实际的控制系统中能够得到的是连续信号x(t)的离散采样值x(nT)。因此需要利用离散信号x(nT)来计算信号x(t)的频谱。 有限长离散信号x(n)，n=0，1，…，N-1的DFT定义为： 可以看出，DFT需要计算大约N2次乘法和N2次加法。当N较大时，这个计算量是很大的。利用WN的对称性和周期性，将N点DFT分解为两个N／2点 的DFT，这样两个N／2点DFT总的计算量只是原来的一半，即(N／2)2+(N／2)2=N2／2，这样可以继续分解下去，将N／2再分解为N／4点DFT等。对于N=2m点的DFT都可以分解为2点的DFT，这样其计算量可以减少为(N／2)log2N 次乘法和Nlog2N次加法。图1为FFT与DFT-所需运算量与计算点数的关系曲线。由图可以明显看出FFT算法的优越性。 将x(n)分解为偶数与奇数的两个序列之和，即 x1(n)和x2(n)的长度都是N／2，x1(n)是偶数序列，x2(n)是奇数序列，则 其中X1(k)和X2(k)分别为x1(n)和x2(n)的N／2点DFT。由于X1(k)和X2(k)均以N／2为周期，且WN k+N/2=-WN k，所以X(k)又可表示为： 上式的运算可以用图2表示，根据其形状称之为蝶形运算。依此类推，经过m-1次分解，最后将N点DFT分解为N／2个两点DFT。图3为8点FFT的分解流程。 FFT算法的原理是通过许多小的更加容易进行的变换去实现大规模的变换，降低了运算要求，提高了与运算速度。FFT不是DFT的近似运算，它们完全是等效的。 关于FFT精度的说明： 因为这个变换采用了浮点运算，因此需要足够的精度，以使在出现舍入误差时，结果中的每个组成部分的准确整数值仍是可辨认的。为了FFT的舍入误差，应该允许增加几倍log2(log2N)位的二进制。以256为基数、长度为N字节的数 FFT原理与实现 2010-10-07 21:10:09| 分类：数字信号处理 | 标签：fft dft |举报|字号订阅 在数字信号处理中常常需要用到离散傅立叶变换(DFT)，以获取信号的频域特征。尽管传统的DFT算法能够获取信号频域特征，但是算法计算量大，耗时长，不利于计算机实时对信号进行处理。因此至DFT被发现以来，在很长的一段时间内都不能被应用到实际的工程项目中，直到一种快速的离散傅立叶计算方法——FFT，被发现，离散傅立叶变换才在实际的工程中得到广泛应用。需要强调的是，FFT并不是一种新的频域特征获取方式，而是DFT的一种快速实现算法。本文就FFT的原理以及具体实现过程进行详尽讲解。 DFT计算公式 本文不加推导地直接给出DFT的计算公式： 其中x(n)表示输入的离散数字信号序列，WN为旋转因子，X(k)为输入序列x(n)对应的N个离散频率点的相对幅度。一般情况下，假设x(n)来自于低通采样，采样频率为fs，那么X(k)表示了从-fs/2率开始，频率间隔为fs/N,到fs/2-fs/N截至的N个频率点的相对幅度。因为DFT计算得到的一组离散频率幅度值实际上是在频率轴上从成周期变化的，即X(k+N)=X(k)。因此任意取连续的N个点均可以表示DFT的计算效果，负频率成分比较抽象，难于理解，根据X(k)的周期特性，于是我们又可以认为X(k)表示了从零频率开始，频率间隔为fs/N,到fs-fs/N 截至的N个频率点的相对幅度。 N点DFT的计算量 根据(1)式给出的DFT计算公式，我们可以知道每计算一个频率点X(k)均需要进行N次复数乘法和N-1次复数加法，计算N各点的X(k)共需要N^2次复数乘法和N*(N-1)次复数加法。当x(n)为实数的情况下，计算N点的DFT需要2*N^2次实数乘法，2*N*(N-1)次实数加法。 旋转因子WN的特性 1.WN的对称性 2.WN的周期性 3.WN的可约性 根据以上这些性质，我们可以得到式(5)的一系列有用结果 基-2 FFT算法推导 假设采样序列点数为N=2^L，L为整数，如果不满足这个条件可以人为地添加若干个0以使采样序列点数满足这一要求。首先我们将序列x(n)按照奇偶分为两组如下： 于是根据DFT计算公式(1)有： kn N W N N 第四章 快速傅里叶变换 有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长 序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换 (FFT). 1965 年，Cooley 和 Tukey 提出了计算离散傅里叶变换（DFT ）的快 速算法，将 DFT 的运算量减少了几个数量级。从此，对快速傅里叶变换（FFT ） 算法的研究便不断深入，数字信号处理这门新兴学科也随 FFT 的出现和发 展而迅速发展。根据对序列分解与选取方法的不同而产生了 FFT 的多种算 法，基本算法是基２DIT 和基２DIF 。FFT 在离散傅里叶反变换、线性卷积 和线性相关等方面也有重要应用。 快速傅里叶变换（FFT ）是计算离散傅里叶变换（DFT ）的快速算法。 DFT 的定义式为 N ?1 X (k ) = ∑ x (n )W N R 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 ) n N = W kn = W ( n + N ) k （2） 对称性：W ( k + N / 2 ) = ?W k N N 利用这两个性质，可以使 DFT 运算中有些项合并，以减少乘法次数。例子： 求当 N ＝4 时，X(2)的值 快速傅里叶变换的原理及其应用 摘要: 快速傅氏变换（FFT），是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。傅里叶变换的理论与方法在“数理方程”、“线性系统分析”、“信号处理、仿真”等很多学科领域都有着广泛应用,由于计算机只能处理有限长度的离散的序列,所以真正在计算机上运算的是一种离散傅里叶变换. 虽然傅里叶运算在各方面计算中有着 重要的作用，但是它的计算过于复杂，大量的计算对于系统的运算负担过于庞大，使得一些对于耗电量少，运算速度慢的系统对其敬而远之，然而，快速傅里叶变换的产生，使得傅里叶变换大为简化，在不牺牲耗电量的条件下提高了系统的运算速度，增强了系统的综合能力，提高了运算速度，因此快速傅里叶变换在生产和生活中都有着非常重要的作用，对于学习掌握都有着非常大的意义。 关键词：快速傅氏变换；图像处理；matlab 前言： 傅里叶变换在信号处理中具有十分重要的作用，但是基于离散时间的傅里叶变换具有很大的时间复杂度，根据傅里叶变换理论，对一个有限长度且 长度为N的离散信号，做傅里叶变换的时间复杂度为) O，当N很大时τ， (2 N 其实现的时间是相当惊人的（比如当N为4 10 10时，其完成时间为τ8 (τ为计算机的时钟周期）），故其实现难度是相当大的，同时也严重制约了DFT在信号分析中的应用，故需要提出一种快速的且有效的算法来实 现。正是鉴于DFT极其复杂的时间复杂度，1965年..JWCooley 和..JWTukey巧妙地利用 NW因子的周期性和对称性，提出了一个DFT的快速算法，即快速傅里叶变换（FFT），从而使得DFT在信号处理中才得到真正的广泛应用。 傅立叶变化的原理； （1）原理 《测试信号分析及处理》课程作业 快速傅里叶变换 一、程序设计思路 快速傅里叶变换的目的是减少运算量，其用到的方法是分级进行运算。全部计算分解为M 级，其中N M 2log =；在输入序列()i x 中是按码位倒序排列的，输出序列()k X 是按顺序排列；每级包含2N 个蝶形单元，第i 级有i N 2 个群，每个群有12-i 个蝶形单元； 每个蝶形单元都包含乘r N W 和r N W -系数的运算，每个蝶形 单元数据的间隔为12-i ，i 为第i 级； 同一级中各个群的系数W 分布规律完全相同。 将输入序列()i x 按码位倒序排列时，用到的是倒序算法——雷德算法。 自然序排列的二进制数，其下面一个数总比上面的数大1，而倒序二进制数的下面一个数是上面一个数在最高位加1并由高位向低位仅为而得到的。 若已知某数的倒序数是J ，求下一个倒序数，应先判断J 的最高位是否为0，与2 N k =进行比较即可得到结果。如果J k >，说明最高位为0，应把其变成1，即2 N J +，这样就得到倒序数了。如果J k ≤，即J 的最高位为1，将最高位化为0，即2N J -，再判断次高位；与4N k =进行比较，若为0，将其变位1，即4 N J +，即得到倒序数，如果次高位为1，将其化为0，再判断下一位……即从高位到低位依次判断其是否为1，为1将其变位0，若这一位为0，将其变位1，即可得到倒序数。若倒序数小于顺序数，进行换位，否则不变，防治重复交换，变回原数。 注：因为0的倒序数为0，所以可从1开始进行求解。 二、程序设计框图 （1）倒序算法——雷德算法流程图 (2)FFT算法流程 快速傅里叶变换FFT的C语言算法彻底研究LED音乐频谱显示的核心算法就是快速傅里叶变换，FFT的理解和编程还是比较难的，特地撰写此文分享一下研究成果。 一、彻底理解傅里叶变换 快速傅里叶变换（Fast Fourier Transform)是离散傅里叶变换的一种快速算法，简称FFT，通过FFT可以将一个信号从时域变换到频域。模拟信号经过A/D转换变为数字信号的过程称为采样。为保证采样后信号的频谱形状不失真，采样频率必须大于信号中最高频率成分的2倍，这称之为采样定理。假设采样频率为fs，采样点数为N，那么FFT结果就是一个N点的复数，每一个点就对应着一个频率点，某一点n(n 从1开始)表示的频率为：fn=(n-1)*fs/N。举例说明：用1kHz的采样频率采样128点，则FFT结果的128个数据即对应的频率点分别是0，1k/128，2k/128，3k/128，…，127k/128 Hz。这个频率点的幅值为：该点复数的模值除以N/2（n=1时是直流分量，其幅值是该点的模值除以N）。 二、傅里叶变换的C语言编程 1、对于快速傅里叶变换FFT，第一个要解决的问题就是码位倒序。假设一个N 点的输入序列，那么它的序号二进制数位数就是t=log2N.码位倒序要解决两个问题：①将t位二进制数倒序；②将倒序后的两个存储单元进行交换。如果输入序列的自然顺序号i用二进制数表示，例如若最大序号为15，即用4位就可表示n3n2n1n0，则其倒序后j对应的二进制数就是n0n1n2n3，那么怎样才能实现倒序呢？利用C语言的移位功能！ 程序如下，我不多说，看不懂者智商一定在180以下！复数类型定义及其运算#define N 64 //64点 #define log2N 6 //log2N=6 /*复数类型*/ typedef struct { float real; float img; }complex; complex xdata x[N]; //输入序列 /*复数加法*/ complex add(complex a,complex b) { complex c; c.real=a.real+b.real; c.img=a.img+b.img; return c; } /*复数减法*/ complex sub(complex a,complex b) { complex c; c.real=a.real-b.real;实验四 快速傅里叶变换(FFT)
快速傅里叶变换(FFT)试题
快速傅里叶变换(FFT)的原理及公式
快速傅里叶变换FFT原理与实现
详解FFT(快速傅里叶变换FFT
快速傅里叶变换的原理及其应用
快速傅里叶变换(FFT)原理及源程序
快速傅里叶变换fft变换
相关主题
文本预览