fft算法原理（FFT算法原理）

本文目录一览：

• 1、FFT算法分几种？
• 2、FFT的公式是什么和算法是怎样实现
• 3、快速傅立叶变换
• 4、FFT原理的FFT基本原理

FFT算法分几种？

FFT算法分析FFT算法的基本原理是把长序列的DFT逐次分解为较短序列的DFT。按照抽取方式的不同可分为DIT-FFT（按时间抽取）和DIF-FFT（按频率抽取）算法。按照蝶形运算的构成不同可分为基2、基4、基8以及任意因子（2n,n为大于1的整数），基2、基4算法较为常用。 网上有帮助文档: (右上角有点击下载)

FFT的公式是什么和算法是怎样实现

二维FFT相当于对行和列分别进行一维FFT运算。具体的实现办法如下：

先对各行逐一进行一维FFT，然后再对变换后的新矩阵的各列逐一进行一维FFT。相应的伪代码如下所示：

for (int i=0; iM; i++)

FFT_1D(ROW[i]，N);

for (int j=0; jN; j++)

FFT_1D(COL[j]，M);

其中，ROW[i]表示矩阵的第i行。注意这只是一个简单的记法，并不能完全照抄。还需要通过一些语句来生成各行的数据。同理，COL[i]是对矩阵的第i列的一种简单表示方法。

所以，关键是一维FFT算法的实现。下面讨论一维FFT的算法原理。

【1D-FFT的算法实现】

设序列h(n)长度为N，将其按下标的奇偶性分成两组，即he和ho序列，它们的长度都是N/2。这样，可以将h(n)的FFT计算公式改写如下 ：

(A)

由于

所以，(A)式可以改写成下面的形式：

按照FFT的定义，上面的式子实际上是：

其中，k的取值范围是 0~N-1。

我们注意到He(k)和Ho(k)是N/2点的DFT，其周期是N/2。因此，H(k)DFT的前N/2点和后N/2点都可以用He(k)和Ho(k)来表示

快速傅立叶变换

1965年，库勒与塔基提出了计算DFT的一种新算法。对于取样点数为N的数据来说，这种算法把原来需要计算的N2次复数运算减少为Nlog2N次，因此大大节省了机器运算时间。这种算法就是通常所说的快速傅氏变换，简记为FFT。由于FFT的出现，在数字信号处理方面发生了许多重大变革，因而它具有相当的重要性。在本节中，我们将详细介绍FFT的原理、计算公式，并给出实现它的流程图。

1.问题的提出

对于一个有限序列x(n)，n=0，1，…，N-1，其DFT为

物探数字信号分析与处理技术

式(7-1-1)代表了N个方程，全部写出来则是

物探数字信号分析与处理技术

因为x(n)可以是复序列，所以在计算(7-1-2)中每个频谱分量X(m)时，需要作N次复数乘法和(N-1)次复数加法。如果算出全部N个频谱分量时，就需要作N2次复数乘法和N(N-1)次复数加法。因为两个复数相乘等于4个实数相乘，所以N2次复数相乘就相当于4N2次实数相乘。当N较大时，(7-1-2)式直接计算的工作量就很大，例如，N=1000时，要计算4百万次实数乘法;当N=5000时，就要计算1亿次实数乘法。如此大的计算工作量，即便是高速计算机，也需要花较长的机器运算时间，这就严重影响了DFT在各个领域的广泛应用。因此，人们提出了能否找到减少计算DFT时间的一种算法。

2.FFT算法的基本思想

1965年由库勒与塔基提出了减少DFT计算时间的一种新算法。我们以(7-1-2)中N=4的情况为例，来说明这种算法的基本思想。

对于N=4=22，从(7-1-2)得到

物探数字信号分析与处理技术

将(7-1-3)写成矩阵形式

物探数字信号分析与处理技术

如果在(7-1-4)中，能够将包含Wi的矩阵分解成两个矩阵，并且使这两个矩阵中每一行元素只有两个不为零，就可以减少乘法的运算次数。由于计算DFT的时间主要取决于乘法运算的多少，因此，减少乘法就可以提高计算效率。下面具体说明上述算法。

首先，将(7-1-4)中X(m)的次序重新排列如下

物探数字信号分析与处理技术

因为

所以，可以将(7-1-5)写成

物探数字信号分析与处理技术

其次，将(7-1-6)中包含Wi的矩阵分解为每一行仅有两个元素不为零的两个矩阵，于是得到

物探数字信号分析与处理技术

第三，从(7-1-7)式先令:

物探数字信号分析与处理技术

物探数字信号分析与处理技术

从(7-1-8)看到，在这一步运算中，只需要2次复数乘法和4次复数加法。

第四，将(7-1-8)代入(7-1-7)中，得到

物探数字信号分析与处理技术

从(7-1-9)看到，在这一步运算中，也只需要2次复数乘法和4次复数加法。由此可见，在计算频谱X(m)时，由于采用了矩阵分解的办法，并将零引进被分解的矩阵中，就使总的运算次数减少到只有4次复数乘法和8次复数加法。而直接去计算(7-1-3)时，总的运算却需要16次复数乘法和12次复数加法。

我们再考虑取样点数N=8的情形。从公式(7-1-2)可以得到8个方程的方程组，将它们写成矩阵形式则为

物探数字信号分析与处理技术

与N=4的情况一样，首先将X(m)的次序重排，从(7-1-10)得到，

物探数字信号分析与处理技术

根据

物探数字信号分析与处理技术

物探数字信号分析与处理技术

物探数字信号分析与处理技术

将(7-1-11)中包含Wi的矩阵分解为每一行仅有两个非零元素的三个矩阵，由(7-1-11)得

物探数字信号分析与处理技术

由(7-1-12)得

物探数字信号分析与处理技术

从(7-1-13)看到，在这一步运算中，只需要做4次复数乘法和8次复数加法。根据(7-1-13)，从(7-1-12)得到

物探数字信号分析与处理技术

从(7-1-14)看到，在第二步运算中，也只需要做4次复数乘法和8次复数加法。根据(7-1-14)，由(7-1-12)可得

物探数字信号分析与处理技术

从(7-1-15)看到，第三步运算也只需作4次复数乘法和8次复数加法。

由此可见，在计算N=8的频谱X(m)时，由于进行矩阵分解，并把零引进被分解的三个矩阵中，就使总的运算次数减少到只有12次复数乘法，24次复数加法。而直接去计算(7-1-11)时，总的运算却要作64次复数乘法和56次复数加法。综上论述我们看到:

第一，FFT算法比直接算法快速的关键在于它将包含Wi原始矩阵进行分解，分解成每一行中仅仅含有两个非零元素的乘积。当N=4时，分解成2个矩阵;当N=8时，分解成3个矩阵;当N=2n时，分解成n个矩阵。

第二，对于FFT算法总的运算次数:

当N=4时，乘法为(4/2)log24=2次，加法为4log24=8次;

当N=8时，乘法为(8/2)log28=12次，加法为8log28=24次;……;

当N=2n时，乘法为 次，加法为Nlog2N。

在此为了得出一般规律，把Wi也用作相乘。如果考虑到若干Wi项为1，并利用DFT的对称性，则实际的复数乘法还可减少得更多。为了与直接计算比较，并以最坏的情况为准，即认为FFT算法包含Nlog2N次复数运算。而直接算法的运算是N2次，当N很大时，FFT算法节省的运算次数是相当惊人的。

第三，从公式(7-1-9)与(7-1-15)还看到一个重要情况，即最终得到的结果xi(r)与所要求的谱X(m)之间还存在差异。这种现象是由于谱x(m)在次序上的重排产生的。为了解决这一矛盾，我们只需要将xi(r)中的r用二进制表示，并逆位，即得所要结果。例如，当N=4时，将(7-1-9)中的xi(r)表示为

物探数字信号分析与处理技术

将上式逆位后即得所要结果

物探数字信号分析与处理技术

当N=8时，将(7-1-15)中xi(r)用二进制表示为

物探数字信号分析与处理技术

对二进制逆位就得到所要结果

物探数字信号分析与处理技术

物探数字信号分析与处理技术

一般如果r可以按照n位(N=2n)二进制数表示为

物探数字信号分析与处理技术

则r的二进制位的逆序为

物探数字信号分析与处理技术

于是得到，

物探数字信号分析与处理技术

FFT原理的FFT基本原理

FFT是一种DFT的高效算法，称为快速傅立叶变换（fast Fourier transform）。FFT算法可分为按时间抽取算法和按频率抽取算法，先简要介绍FFT的基本原理。从DFT运算开始，说明FFT的基本原理。

DFT的运算为：

式中

由这种方法计算DFT对于X（K）的每个K值，需要进行4N次实数相乘和（4N-2）次相加，对于N个k值，共需N*N乘和N（4N-2）次实数相加。改进DFT算法，减小它的运算量，利用DFT中

的周期性和对称性，使整个DFT的计算变成一系列迭代运算，可大幅度提高运算过程和运算量，这就是FFT的基本思想。

FFT基本上可分为两类，时间抽取法和频率抽取法，而一般的时间抽取法和频率抽取法只能处理长度N=2^M的情况，另外还有组合数基四FFT来处理一般长度的FFT 设N点序列x(n),,将x(n)按奇偶分组，公式如下图

改写为：

一个N点DFT分解为两个 N/2点的DFT，继续分解，迭代下去，其运算量约为

其算法有如下规律

两个4点组成的8点DFT

四个2点组成的8点DFT

按时间抽取的8点DFT

原位计算

当数据输入到存储器中以后，每一级运算的结果仍然储存在同一组存储器中，直到最后输出，中间无需其它存储器

序数重排

对按时间抽取FFT的原位运算结构，当运算完毕时，这种结构存储单元A(1)、A(2)，…，A(8)中正好顺序存放着X(0)，X(1)，X(2)，…，X(7)，因此可直接按顺序输出，但这种原位运算的输入x(n)却不能按这种自然顺序存入存储单元中，而是按X(0)，X(4)，X(2)，X(6)，…，X(7)的顺序存入存储单元，这种顺序看起来相当杂乱，然而它也是有规律的。当用二进制表示这个顺序时，它正好是“码位倒置”的顺序。

蝶形类型随迭代次数成倍增加

每次迭代的蝶形类型比上一次蝶代增加一倍，数据点间隔也增大一倍 频率抽取2FFT算法是按频率进行抽取的算法。

设N=2^M，将x(n)按前后两部分进行分解，

按K的奇偶分为两组，即

得到两个N/2 点的DFT运算。如此分解，并迭代，总的计算量和时间抽取（DIT）基2FFT算法相同。

算法规律如下：

蝶形结构和时间抽取不一样但是蝶形个数一样，同样具有原位计算规律，其迭代次数成倍减小 时，可采取补零使其成为

，或者先分解为两个p,q的序列，其中p*q=N，然后进行计算。 前面介绍，采用FFT算法可以很快算出全部N点DFT值，即z变换X（z）在z平面单位圆上的全部等间隔取样值。实际中也许①不需要计算整个单位圆上z变换的取样，如对于窄带信号，只需要对信号所在的一段频带进行分析，这时希望频谱的采样集中在这一频带内，以获得较高的分辨率，而频带以外的部分可不考虑，②或者对其它围线上的z变换取样感兴趣，例如语音信号处理中，需要知道z变换的极点所在频率，如极点位置离单位圆较远，则其单位圆上的频谱就很平滑，这时很难从中识别出极点所在的频率，如果采样不是沿单位圆而是沿一条接近这些极点的弧线进行，则在极点所在频率上的频谱将出现明显的尖峰，由此可较准确地测定极点频率。③或者要求能有效地计算当N是素数时序列的DFT，因此提高DFT计算的灵活性非常有意义。

螺旋线采样是一种适合于这种需要的变换，且可以采用FFT来快速计算，这种变换也称作Chirp-z变换。

fft算法原理的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于fft算法原理、fft算法原理的信息别忘了在本站进行查找喔。