fft算法的应用

1. 什么是FFT

计算离散傅里叶变换的一种快速算法,简称FFT(Fast Fourier Transform)。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少,特别是被变换的抽样点数N越多,FFT算法计算量的节省就越显着。
FFT 的出现，使信号分析从时域分析向频域分析成为可能，极大地推动了信号分析在各领域的实际应用。
http://ke..com/view/1006229.htm

2. 实序列的FFT算法

在以上讨论FFT算法中，均假定序列x(l)为复的，但实际问题中的序列大多为实的。当然，我们可以把实序列处理成虚部为零的复序列。因此，就要引进许多零参加运算。这样一来，在机器运算时间和存储单元方面都将造成很大的浪费。在本段中，我们介绍对实序列x(l)应用FFT算法的一个有效方法。

1.同时计算两个实序列的FFT算法

设有N=4的两个实序列x₁(l)与x₂(l)。为了求得它们的谱X₁(m)与X₂(m)，我们用此二实序列构造成如下复序列

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

利用上一段的方法，可以求得复序列x(l)的谱X(m)。根据(7-3-1)得到

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

上式中的m用N-m代替，则得

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

将上式两端取共轭，根据对称性有

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

根据DFT的复共轭性质，对于实序列x₁(l)与x₂(l)，有

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

于是从(7-3-4)得到

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

联立求解(7-3-2)和(7-3-6)便得到

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

例如设有两个N=4点的实序列，

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

我们用它们构造一个N=4点的复序列

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

利用FFT算法求X(m)，m=0，1，2，3(图7-3-1)，

图7-3-1 N=4点的FFT算法流程图

于是得到

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

因此从式(7-3-7)得到

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

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

2.实序列的FFT算法

设有N点的实序列x(l)，l=0，1，2，…，N-1。按照点的奇偶编号，将它们分成N/2个点的两个子序列

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

设x₁(l)的谱与x₂(l)的谱分别为X₁(m)与X₂(m)

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

其中

于是可以将实序列x(l)的谱X(m)，用两个子序列x₁(l)，x₂(l)的谱X₁(m)，X₂(m)来表示

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

其中

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

注意，x₁(l)，x₂(l)与X₁(m)，X₂(m)均以N/2为周期，

利用x₁(l)、x₂(l)构成如下复序列

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

利用FFT算法可以求得复序列 的谱 。根据(7-3-7)就求得两个实子序列的谱X₁(m)与X₂(m)

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

有了X₁(m)，X₂(m)，根据(7-3-10)就可求得X(m)。以上就是用FFT算法求实序列x(l)的谱X(m)的方法。必须指出，用公式(7-3-10)求X(m)时，第一，两个实子序列的谱X₁(m)，X₂(m)及复序列x珓(l)的谱珘X(m)均是以N/2为周期的周期序列;第二，由于x

(l)是实序列，根据DFT的复共轭性质有X(m)=X^*(N-m)，m=0，1，…，N/2，故只需求得前(N/2)+1个点的X(m)，就得到全部N个点的X(m)了

例如，有N=8点的实序列，

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

首先，按点的奇偶编号分成两个实子序列，

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

其次用它们构造如下复序列，

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

用FFT算法求此复序列的谱 (图7-3-2)

图7-3-2 N=4点的FFT算法流程图

于是得到:

根据周期性，有

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

根据(7-3-12)式，

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

根据周期性，有

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

故最终由(7-3-10)得到

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

3. 如何应用matlab进行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之后某点n用复数a+bi表示，那么这个复数的模就是
An=根号a*a+b*b，相位就是Pn=atan2(b,a)。根据以上的结果，
就可以计算出n点（n≠1，且n<=N/2）对应的信号的表达式为：
An/(N/2)*cos(2*pi*Fn*t+Pn)，即2*An/N*cos(2*pi*Fn*t+Pn)。
对于n=1点的信号，是直流分量，幅度即为A1/N。
由于FFT结果的对称性，通常我们只使用前半部分的结果，
即小于采样频率一半的结果。

好了，说了半天，看着公式也晕，下面圈圈以一个实际的
信号来做说明。

假设我们有一个信号，它含有2V的直流分量，频率为50Hz、
相位为-30度、幅度为3V的交流信号，以及一个频率为75Hz、
相位为90度、幅度为1.5V的交流信号。用数学表达式就是如下：

S=2+3*cos(2*pi*50*t-pi*30/180)+1.5*cos(2*pi*75*t+pi*90/180)

式中cos参数为弧度，所以-30度和90度要分别换算成弧度。
我们以256Hz的采样率对这个信号进行采样，总共采样256点。
按照我们上面的分析，Fn=(n-1)*Fs/N，我们可以知道，每两个
点之间的间距就是1Hz，第n个点的频率就是n-1。我们的信号
有3个频率：0Hz、50Hz、75Hz，应该分别在第1个点、第51个点、
第76个点上出现峰值，其它各点应该接近0。实际情况如何呢？
我们来看看FFT的结果的模值如图所示。

图1 FFT结果
从图中我们可以看到，在第1点、第51点、和第76点附近有
比较大的值。我们分别将这三个点附近的数据拿上来细看：
1点： 512+0i
2点： -2.6195E-14 - 1.4162E-13i
3点： -2.8586E-14 - 1.1898E-13i

50点：-6.2076E-13 - 2.1713E-12i
51点：332.55 - 192i
52点：-1.6707E-12 - 1.5241E-12i

75点：-2.2199E-13 -1.0076E-12i
76点：3.4315E-12 + 192i
77点：-3.0263E-14 +7.5609E-13i

很明显，1点、51点、76点的值都比较大，它附近的点值
都很小，可以认为是0，即在那些频率点上的信号幅度为0。
接着，我们来计算各点的幅度值。分别计算这三个点的模值，
结果如下：
1点： 512
51点：384
76点：192
按照公式，可以计算出直流分量为：512/N=512/256=2；
50Hz信号的幅度为：384/(N/2)=384/(256/2)=3；75Hz信号的
幅度为192/(N/2)=192/(256/2)=1.5。可见，从频谱分析出来
的幅度是正确的。
然后再来计算相位信息。直流信号没有相位可言，不用管
它。先计算50Hz信号的相位，atan2(-192, 332.55)=-0.5236,
结果是弧度，换算为角度就是180*(-0.5236)/pi=-30.0001。再
计算75Hz信号的相位，atan2(192, 3.4315E-12)=1.5708弧度，
换算成角度就是180*1.5708/pi=90.0002。可见，相位也是对的。
根据FFT结果以及上面的分析计算，我们就可以写出信号的表达
式了，它就是我们开始提供的信号。

总结：假设采样频率为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，这在一定程度上能够提高频率分辨力。
具体的频率细分法可参考相关文献。

[附录：本测试数据使用的matlab程序]
close all; %先关闭所有图片
Adc=2; %直流分量幅度
A1=3; %频率F1信号的幅度
A2=1.5; %频率F2信号的幅度
F1=50; %信号1频率(Hz)
F2=75; %信号2频率(Hz)
Fs=256; %采样频率(Hz)
P1=-30; %信号1相位(度)
P2=90; %信号相位(度)
N=256; %采样点数
t=[0:1/Fs:N/Fs]; %采样时刻

%信号
S=Adc+A1*cos(2*pi*F1*t+pi*P1/180)+A2*cos(2*pi*F2*t+pi*P2/180);
%显示原始信号
plot(S);
title('原始信号');

figure;
Y = fft(S,N); %做FFT变换
Ayy = (abs(Y)); %取模
plot(Ayy(1:N)); %显示原始的FFT模值结果
title('FFT 模值');

figure;
Ayy=Ayy/(N/2); %换算成实际的幅度
Ayy(1)=Ayy(1)/2;
F=([1:N]-1)*Fs/N; %换算成实际的频率值
plot(F(1:N/2),Ayy(1:N/2)); %显示换算后的FFT模值结果
title('幅度-频率曲线图');

figure;
Pyy=[1:N/2];
for i="1:N/2"
Pyy(i)=phase(Y(i)); %计算相位
Pyy(i)=Pyy(i)*180/pi; %换算为角度
end;
plot(F(1:N/2),Pyy(1:N/2)); %显示相位图
title('相位-频率曲线图');

看完这个你就明白谐波分析了。

4. 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变换。

5. 如何理解FFT

fft在matlab中可以按原理采样来运算，也可以用快速fft算法。
clear
fs=1000
t=0:1/fs:0.6;
f1=100;
f2=300;
x=sin(2*pi*f1*t)+sin(2*pi*f2*t);
subplot(711)
plot(x);
title('f1（100Hz）\f2(300Hz)的正弦信号，初相0')
xlabel('序列（n）')
grid on

number=512

y=fft(x,number);
n=0:length(y)-1;
f=fs*n/length(y);
subplot(713)
plot(f,abs(y));
title('f1\f2的正弦信号的FFT（512点）')
xlabel('频率Hz')
grid on

x=x+randn(1,length(x));
subplot(715)
plot(x);
title('原f1\f2的正弦信号（含随机噪声）')
xlabel('序列（n）')
grid on

y=fft(x,number);
n=0:length(y)-1;
f=fs*n/length(y);
subplot(717)
plot(f,abs(y));
title('原f1\f2的正弦信号（含随机噪声）的FFT（512点）')
xlabel('频率Hz')
grid on

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

二维FFT相当于对行和列分别进行一维FFT运算。具体的实现办法如下：
先对各行逐一进行一维FFT，然后再对变换后的新矩阵的各列逐一进行一维FFT。相应的伪代码如下所示：
for (int i=0; i<M; i++)
FFT_1D(ROW[i]，N);
for (int j=0; j<N; 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)来表示

7. FFT , DTFT, DFT 的区别和联系

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来解决。

(7)fft算法的应用扩展阅读

DTFT是以2pi为周期的。而DFT的序列X(k）是有限长的。

DTFT是以复指数序列{exp（-jwn）}的加权和来表示的，而DFT是等间隔抽样，DFT里面有个重要的参数就是N，抽样间隔就是将单位元分成N个间隔来抽样，绕圆一周，（2*pi）/N是间隔（一个圆周是2*pi，分成N个等分）

DTFT和DFT都能表征原序列的信息。因为现在计算主要使用计算机，必需要是离散的值才能参与运算，因此在工程中DFT应用比较广泛，DFT还有一个快速算法，那就是FFT。