FFT原理（DFT的高效算法）

FFT原理

DFT的高效算法

FFT是一种DFT的高效算法，称为快速傅立叶变换（fast Fourier transform）。傅里叶变换是时域一频域变换分析中最基本的方法之一。在数字处理领域应用的离散傅里叶变换(DFT：Discrete Fourier Transform)是许多数字信号处理方法的基础。

原理简介

由于计算机技术的快速发展，在70年代中期，美国和日本的一些电子设备企业开始设计和生产数字式傅里叶分析仪，但是由于离散傅里叶变换的计算量较大，直到DFT的快速算法(FFT)发现之后，有限离散傅里叶变换(DFT)才真正获得了广泛的应用   。

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=2M的情况，另外还有组合数基四FFT来处理一般长度的FFT。

所谓抽选，就是把长序列分为短序列的过程，可在时域也可在频域进行。最常用的时域抽选方法是按奇偶将长序列不断地变为短序列，结果使输入序列为倒序，输出序列为顺序排列，这就是Coolly—Tukey算法。

时间抽取

设N点序列x(n),  ,将x(n)按奇偶分组，公式如图2所示：

改写为：

一个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=2M，将x(n)按前后两部分进行分解，

按K的奇偶分为两组，即

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

算法规律如下：

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

组合数基四FFT

N≠2M时，可采取补零使其成为N=2，或者先分解为两个p、q的序列，其中p*q=N，然后进行计算。

Chirp-z变换

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

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

应用

FFT计算IDFT

DFT变换则说明对于时间有限的信号（有限长序列），也可以对其进行频域采样，而不丢失任何信息。所以只要时间序列足够长，采样足够密，频域采样也就可较好地反映信号的频谱趋势，所以FFT可以用以进行连续信号的频谱分析。

当然，这里作了几次近似处理：

1、用离散采样信号的傅立叶变换来代替连续信号的频谱，只有在严格满足采样定理的前提下，频谱才不会有畸变，否则只是近似；

2、用有限长序列来代替无限长离散采样信号。

FFT计算线性卷积

线性卷积是求离散系统响应的主要方法之一,许多重要应用都建立在这一理论基础上,如卷积滤波等。

以前曾讨论了用圆周卷积计算线性卷积的方法归纳如下:

将长为N2的序列x(n)延长到L,补L-N2个零

将长为N1的序列h(n)延长到L,补L-N1个零

如果L≥N1+N2-1,则圆周卷积与线性卷积相等，此时，可有FFT计算线性卷积，方法如下:

a.计算X(k)=FFT

b.求H(k)=FFT

c.求Y(k)=H(k)Y(k) k=0～L-1

d.求y(n)=IFFT n=0～L-1

可见，只要进行二次FFT,一次IFFT就可完成线性卷积计算。计算表明,L>32时,上述计算线性卷积的方法比直接计算线卷积有明显的优越性,因此,也称上述圆周卷积方法为快速卷积法

FFT计算相关函数

互相关和自相关函数的计算可利用FFT实现。由于离散付里叶变换隐含着周期性，所以用FFT计算离散相关函数也是对周期序列而言的。直接做N点FFT相当于对两个N点序列x(n)、y(n)作周期延拓，作相关后再取主值（类似圆周卷积）。而实际一般要求的是两个有限长序列的线性相关，为避免混淆，需采用与圆周卷积求线性卷积相类似的方法，先将序列延长补0后再用上述方法。

实数序列FFT

信号是实数序列，任何实数都可看成虚部为零的复数，例如，求某实信号y(n)的复谱,可认为是将实信号加上数值为零的虚部变成复信号(x(n)+j0)，再用FFT求其离散付里叶变换。这种作法很不经济，因为把实序列变成复序列，存储器要增加一倍，且计算机运行时，即使虚部为零，也要进行涉及虚部的运算，浪费了运算量。合理的解决方法是利用复数据FFT对实数据进行有效计算，下面介绍方法。

一个N点FFT同时计算两个N点实序列的DFT

设x1(n)，x2(n)是彼此独立的两个N点实序列,且X1(k)=DFT，X2(k)=DFT

可通过一次FFT运算同时获得X1(k)，X2(k)。算法如下：

首先将x1(n)，x2(n)分别当作一复序列的实部及虚部,令

x(n)=x1(n)+jx2(n)

通过FFT运算可获得x(n)的DFT值 X(k)=DFT+jDFT=X1(k)+jX2(k)

利用离散付里叶变换的共轭对称性

X1(K)=1/2*]

X2(K)=1/2*]

有了x(n)的FFT运算结果X(k),由上式即可得到X1(k),X2(k)的值。

参考资料

1.自相关函数·术语在线