FFT,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变换。

matlab自带的fft函数是快速傅里叶变换函数。主要用于降噪处理，通过使用傅里叶变换求噪声中隐藏的信号的频率分量。

该函数使用方法：

方法一：

Y = fft(X) 用快速傅里叶变换 (FFT) 算法计算 X 的离散傅里叶变换 (DFT)。

如果 X 是向量，则 fft(X) 返回该向量的傅里叶变换。

如果 X 是矩阵，则 fft(X) 将 X 的各列视为向量，并返回每列的傅里叶变换。

如果 X 是一个多维数组，则 fft(X) 将沿大小不等于 1 的第一个数组维度的值视为向量，并返回每个向量的傅里叶变换。

方法二：

Y = fft(X,n) 返回 n 点 DFT。如果未指定任何值，则 Y 的大小与 X 相同。

如果 X 是向量且 X 的长度小于 n，则为 X 补上尾零以达到长度 n。

如果 X 是向量且 X 的长度大于 n，则对 X 进行截断以达到长度 n。

如果 X 是矩阵，则每列的处理与在向量情况下相同。

如果 X 为多维数组，则大小不等于 1 的第一个数组维度的处理与在向量情况下相同。

我们通过下例，来了解fft函数使用过程：

第一步、指定信号的参数，采样频率为 1 kHz，信号持续时间为 1.5 秒。

Fs=1000；%采样频率

T=1/Fs；%采样周期

L=1500；%信号长度

t=（0:L-1）*T；%时间向量

第二步、构造一个信号，其中包含幅值为 0.7 的 50 Hz 正弦量和幅值为 1 的 120 Hz 正弦量。

S = 0.7*sin(2*pi*50*t) + sin(2*pi*120*t);

第三步、用均值为零、方差为 4 的白噪声扰乱该信号。

X = S + 2*randn(size(t));

第四步、在时域中绘制含噪信号。通过查看信号 X(t) 很难确定频率分量。

plot(1000*t(1:50),X(1:50))

title('Signal Corrupted with Zero-Mean Random Noise')

xlabel('t (milliseconds)')，ylabel('X(t)')

第五步、计算信号的傅里叶变换。

Y = fft(X);

第六步、计算双侧频谱 P2， 计算单侧频谱 P1。

P2 = abs(Y/L);

P1 = P2(1:L/2+1);

P1(2:end-1) = 2*P1(2:end-1)

第七步、定义频域 f 并绘制单侧幅值频谱 P1

f = Fs*(0:(L/2))/L;

plot(f,P1)

title('Single-Sided Amplitude Spectrum of X(t)')

xlabel('f (Hz)')，ylabel('|P1(f)|')

运行结果。

FFT , DTFT, DFT 的联系：FFT是DFT的一种高效快速算法，DFT是有限长序列的离散傅里叶变换，DTFT是非周期序列的傅里叶变换，DFT将信号的时域采样变换为其DTFT的频域采样。

FFT , DTFT, DFT 的区别是含义不同、性质不同、用途不同。

1、含义不同：DTFT是离散时间傅里叶变换，DFT是离散傅里叶变换，FFT是DFT的一种高效快速算法，也称作快速傅里叶变换。

2、性质不同：DTFT变换后的图形中的频率是一般连续的（cos(wn)等这样的特殊函数除外，其变换后是冲击串)，而DFT是DTFT的等间隔抽样，是离散的点。

快速傅里叶变换FFT其实是一种对离散傅里叶变换的快速算法，它的出现解决了离散傅里叶变换的计算量极大、不实用的问题，使离散傅里叶变换的计算量降低了 一个或几个数量级，从而使离散傅里叶变换得到了广泛应用。

3、用途不同：DFT完全是应计算机技术的发展而来的，因为如果没有计算机，用DTFT分析看频率响应就可以，为了适应计算机计算，那么就必须要用离散的值，因为计算机不能处理连续的值，FFT是为了提高速度而来。另外，FFT的出现也解决了相当多的计算问题，使得其它计算也可以通过FFT来解决。