软件fft算法

❶ IDFT的运算怎么用FFT实现，在软件中怎样进行设置

IDFT就是Inverse Discrete Fourier Transform 离散傅里叶逆变换。

FFT就是Fast Fourier Transform 快速傅里叶变换。

两者的应用都是将时域中难以处理的信号转换成易于复处理的频域信号，分析完成后进行傅里叶反变换即得到原始的粗瞎郑时域岩颂信号。

两者的异同是：我们知道在数学上用级数来无限逼进某个函数，以便简化计算过程而又不致使误差过大，这样工程上才能应用，否则一些数学模型是无法实现快速求解的。

IDFT：对于有限长的序列我们可以使用离散傅立叶变换，神指IDFT是对制序列傅立叶变换的等距采样。

FFT：并不是与IDFT不相同的另一种变换（即原理是一样的），而是为了减少IDFT运算次数的一种快速算法。它是对IDFT变换式进行一次次的分解，使其成为若干小点数IDFT的组合，从而减小运算量。常用的FFT是以2为基数，它的运算效率高，程序比较简单，使用也十分地方便。

❷ 怎样用C语言实现FFT算法啊

1、二维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算法的实现。

2、例程：

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#defineN1000
/*定义复数类型*/
typedefstruct{
doublereal;
doubleimg;
}complex;
complexx[N],*W;/*输入序列,变换核*/
intsize_x=0;/*输入序列的大小，在本程序中仅限2的次幂*/
doublePI;/*圆周率*/
voidfft();/*快速傅里叶变换*/
voidinitW();/*初始化变换核*/
voidchange();/*变址*/
voidadd(complex,complex,complex*);/*复数加法*/
voidmul(complex,complex,complex*);/*复数乘法*/
voidsub(complex,complex,complex*);/*复数减法*/
voidoutput();
intmain(){
inti;/*输出结果*/
system("cls");
PI=atan(1)*4;
printf("Pleaseinputthesizeofx:
");
scanf("%d",&size_x);
printf("Pleaseinputthedatainx[N]:
");
for(i=0;i<size_x;i++)
scanf("%lf%lf",&x[i].real,&x[i].img);
initW();
fft();
output();
return0;
}
/*快速傅里叶变换*/
voidfft(){
inti=0,j=0,k=0,l=0;
complexup,down,proct;
change();
for(i=0;i<log(size_x)/log(2);i++){/*一级蝶形运算*/
l=1<<i;
for(j=0;j<size_x;j+=2*l){/*一组蝶形运算*/
for(k=0;k<l;k++){/*一个蝶形运算*/
mul(x[j+k+l],W[size_x*k/2/l],&proct);
add(x[j+k],proct,&up);
sub(x[j+k],proct,&down);
x[j+k]=up;
x[j+k+l]=down;
}
}
}
}
/*初始化变换核*/
voidinitW(){
inti;
W=(complex*)malloc(sizeof(complex)*size_x);
for(i=0;i<size_x;i++){
W[i].real=cos(2*PI/size_x*i);
W[i].img=-1*sin(2*PI/size_x*i);
}
}
/*变址计算，将x(n)码位倒置*/
voidchange(){
complextemp;
unsignedshorti=0,j=0,k=0;
doublet;
for(i=0;i<size_x;i++){
k=i;j=0;
t=(log(size_x)/log(2));
while((t--)>0){
j=j<<1;
j|=(k&1);
k=k>>1;
}
if(j>i){
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
}
}
/*输出傅里叶变换的结果*/
voidoutput(){
inti;
printf("Theresultareasfollows
");
for(i=0;i<size_x;i++){
printf("%.4f",x[i].real);
if(x[i].img>=0.0001)printf("+%.4fj
",x[i].img);
elseif(fabs(x[i].img)<0.0001)printf("
");
elseprintf("%.4fj
",x[i].img);
}
}
voidadd(complexa,complexb,complex*c){
c->real=a.real+b.real;
c->img=a.img+b.img;
}
voidmul(complexa,complexb,complex*c){
c->real=a.real*b.real-a.img*b.img;
c->img=a.real*b.img+a.img*b.real;
}
voidsub(complexa,complexb,complex*c){
c->real=a.real-b.real;
c->img=a.img-b.img;
}

❸ 如何应用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('相位-频率曲线图');

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

❹ 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运算。具体的实现办法如下：
先对各行逐一进行一维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)来表示

❻ Python科学计算——复杂信号FFT

FFT (Fast Fourier Transform, 快速傅里叶变换) 是离散傅里叶变换的快速算法，也是数字信号处理技术中经常会提到的一个概念。用快速傅里叶变换能将时域的数字信号转换为频域信号，转换为频域信号后我们可以很方便地分析出信号的频率成分。

当我们把双频信号FFT示例中的 fft_size 的值改为 2**12 时，这时，基频为 16Hz，不能被 1kHz整除，所以 1kHz 处发生了频谱泄露，而它能被 4kHz 整除，所以 4kHz 可以很好地被采样。

由于波形的前后不是连续的，出现波形跳变，而跳变处有着非常广泛的频谱，因此FFT的结果中出现了频谱泄漏。

为了减小FFT所截取的数据段前后的跳变，可以对数据先乘以一个窗函数，使得其前后数据能平滑过渡。常用的hanning窗函数的定义如下：

50Hz 正弦波与hann窗函数乘积之后的重复波形如下：

我们对频谱泄漏示例中的1kHz 和 4kHz 信号进行了 hann 窗函数处理，可以看出能量更加集中在 1kHz 和 4kHz，在一定程度上抑制了频谱泄漏。

以 1kHz 三角波为例，我们知道三角波信号中含有丰富的频率信息，它的傅里叶级数展开为：

当数字信号的频率随时间变化时，我们称之为扫频信号。以频率随时间线性变化的扫频信号为例，其数学形式如下：

其频率随时间线性变化，当我们在 [0,1] 的时间窗口对其进行采样时，其频率范围为 0~5kHz。当时间是连续时，扫频信号的频率也是连续的。但是在实际的处理中，是离散的点采样，因此时间是不连续的，这就使扫频信号的快速傅里叶变换问题退化为多点频信号快速傅里叶变换问题。其快速傅里叶变换得到的频谱图如下所示：

以 50Hz 正弦信号相位调制到 1kHz 的信号为例，其信号形式如下：

它的时域波形，频率响应和相位响应如下图所示：

以扫频信号为例，当我们要探究FFT中的能量守恒时，我们要回归到信号最初的形式：

❼ 实序列的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)得到

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

❽ 16点DFT的FFT算法

FFT（快速傅里叶变换）是DFT的一种特殊情况，就是当运算点的个数是2的整数次幂的时候进行的运算（不够用0补齐）。

FFT计算原理及流程图：

原理：FFT的计算要求点数必须为2的整数次幂，如果点数不够用0补齐。例如计算{2，3，5，8，4}的16点FFT，需要补11个0后进行计算。FFT计算运用蝶形运算，在蝶形运算中变化规律由W(N, p)推导，其中N为FFT计算点数，J为下角标的值。

L = 1时，W(N, p) = W(N, J) = W(2^L, J)，其中J = 0;

L = 2时，W(N, p) = W(N, J) = W(2^L, J)，其中J = 0, 1;

L = 3时，W(N, p) = W(N, J) = W(2^L, J)，其中J = 0, 1, 2, 3;

所以，W(N, p) = W(2^L, J)，其中J = 0, 1, ..., 2^(L-1)-1

又因为2^L = 2^M*2^(L-M) = N*2^(L-M)，这里N为2的整数次幂，即N=2^M，

W(N, p) = W(2^L, J) = W(N*2^(L-M), J) = W(N, J*2^(M-L))

所以，p = J*2^(M-L)，此处J = 0, 1, ..., 2^(L-1)-1，当J遍历结束但计算点数不够N时，J=J+2^L，后继续遍历，直到计算点数为N时不再循环。

流程图：

/*======================================================================
*方法名：fft
*方法功能：计算数组的FFT，运用蝶形运算
*
*变量名称：
*yVector-原始数据
*length-原始数据长度
*N-FFT计算点数
*fftYreal-FFT后的实部
*fftYImg-FFT后的虚部
*
*返回值：是否成功的标志，若成功返回true，否则返回false
*=====================================================================*/

+(BOOL)fft:(floatfloat*)yVectorandOriginalLength:(NSInteger)lengthandFFTCount:(NSInteger)NandFFTReal:(floatfloat*)fftYRealandFFTYImg:(floatfloat*)fftYImg
{
//确保计算时时2的整数幂点数计算
NSIntegerN1=[selfnextNumOfPow2:N];

//定义FFT运算是否成功的标志
BOOLisFFTOK=false;

//判断计算点数是否为2的整数次幂
if(N!=N1)
{
//不是2的整数次幂，直接计算DFT
isFFTOK=[selfdft:yVectorandOriginalLength:lengthandFFTCount:NandFFTReal:fftYRealandFFTYImg:fftYImg];

//返回成功标志
returnisFFTOK;
}


//如果计算点数位2的整数次幂，用FFT计算，如下
//定义变量
floatyVectorN[N1];//N点运算的原始数据
NSIntegerpowOfN=log2(N1);//N=2^powOfN，用于标记最大运算级数(公式中表示为：M)
NSIntegerlevel=1;//运算级数（第几次运算），最大为powOfN，初值为第一级运算(公式中表示为：L)
NSIntegerlineNum;//行号，倒序排列后的蝶形运算行号(公式中表示为：k)
floatinverseOrderY[N1];//yVector倒序x
NSIntegerdistanceLine=1;//行间距，第level级运算每个蝶形的两个节点距离为distanceLine=2^(L-1)(公式中表示为：B)
NSIntegerp;//旋转因子的阶数，旋转因子表示为W(N,p)，p=J*2^(M-L)
NSIntegerJ;//旋转因子的阶数，旋转因子表示为W(2^L,J)，J=0,1,2,...,2^(L-1)-1=distanceLine-1
floatrealTemp,imgTemp,twiddleReal,twiddleImg,twiddleTheta,twiddleTemp=PI_x_2/N1;
NSIntegerN_4=N1/4;

//判断点数是否够FFT运算点数
if(length<=N1)
{
//如果N至少为length，先把yVector全部赋值
for(NSIntegeri=0;i<length;i++)
{
yVectorN[i]=yVector[i];
}

if(length<N1)
{
//如果N>length后面补零
for(NSIntegeri=length;i<N1;i++)
{
yVectorN[i]=0.0;
}
}
}
else
{
//如果N<length截取相应长度的数据进行运算
for(NSIntegeri=0;i<N1;i++)
{
yVectorN[i]=yVector[i];
}
}

//调用倒序方法
[selfinverseOrder:yVectorNandN:N1andInverseOrderVector:inverseOrderY];

//初始值
for(NSIntegeri=0;i<N1;i++)
{
fftYReal[i]=inverseOrderY[i];
fftYImg[i]=0.0;
}

//三层循环
//第三层（最里）：完成相同旋转因子的蝶形运算
//第二层（中间）：完成旋转因子的变化，步进为2^level
//第一层（最外）：完成M次迭代过程，即计算出x(k)=A0(k),A1(k),...,Am(k)=X(k)

//第一层循环
while(level<=powOfN)
{
distanceLine=powf(2,level-1);//初始条件distanceLine=2^(level-1)
J=0;
NSIntegerpow2_Level=distanceLine*2;//2^level
NSIntegerpow2_NSubL=N1/pow2_Level;//2^(M-L)

//第二层循环
while(J<distanceLine)
{
p=J*pow2_NSubL;
lineNum=J;
NSIntegerstepCount=0;//J运算的步进计数

//求旋转因子
if(p==0)
{
twiddleReal=1.0;
twiddleImg=0.0;
}
elseif(p==N_4)
{
twiddleReal=0.0;
twiddleImg=-1.0;
}
else
{
//计算尤拉公式中的θ
twiddleTheta=twiddleTemp*p;

//计算复数的实部与虚部
twiddleReal=cos(twiddleTheta);
twiddleImg=-11*sin(twiddleTheta);
}

//第三层循环
while(lineNum<N1)
{
//计算下角标
NSIntegerfootNum=lineNum+distanceLine;

/*---------------------------------------
*用复数运算计算每级中各行的蝶形运算结果
*X(k)=X(k)+X(k+B)*W(N,p)
*X(k+B)=X(k)-X(k+B)*W(N,p)
*---------------------------------------*/
realTemp=fftYReal[footNum]*twiddleReal-fftYImg[footNum]*twiddleImg;
imgTemp=fftYReal[footNum]*twiddleImg+fftYImg[footNum]*twiddleReal;

//将计算后的实部和虚部分别存放在返回数组中
fftYReal[footNum]=fftYReal[lineNum]-realTemp;
fftYImg[footNum]=fftYImg[lineNum]-imgTemp;
fftYReal[lineNum]=fftYReal[lineNum]+realTemp;
fftYImg[lineNum]=fftYImg[lineNum]+imgTemp;

stepCount+=pow2_Level;

//行号改变
lineNum=J+stepCount;
}

//旋转因子的阶数变换，达到旋转因子改变的效果
J++;
}

//运算级数加一
level++;
}

isFFTOK=true;
returnisFFTOK;
}

❾ 基-2fft算法的软件实现 matlab代码

% 基于Matlab的时间抽取基2FFT算法
function y=myditfft(x)
%本程序对输入序列实现DIT-FFT基2算法，点数取大于等于长度的2的幂次
%------------------------------------
% Leo's fft program(改编网上的一个程序)
%------------------------------------
m=log2(2^nextpow2(length(x))); %求的x长度对应的2的最低幂次m
N=2^m;
if length(x)<N
x=[x,zeros(1,N-length(x))]; %若长度不是2的幂，补0到2的整数幂
end
x;
%--------------------------------------------------------------------------
%对输入序列进行倒序
%如果输入序列的自然顺序号I用二进制数（例如n2n1n0）表示
%则其倒位序J对应的二进制数就是（n0n1n2），这样，在原来自然顺序时应该放x(I)的
%单元，现在倒位序后应放x(J)。
%--------------------------------------------------------------------------
%以下程序相当于以下程序:
%nxd=bin2dec(fliplr(dec2bin([1:N]-1,m)))+1; %求1：2^m数列的倒序
%y=x(nxd); %将倒序排列作为初始值
%--------------------------------------------------------------------------
NV2=N/2;
NM1=N-1;
I=0;
J=0;
while I<NM1
if I<J
T=x(J+1);
x(J+1)=x(I+1);
x(I+1)=T;
end
K=NV2;

while K<=J
J=J-K;
K=K/2;
end
J=J+K;
I=I+1;
end
x;
%--------------------------------------------------------------------------
%以下程序解释:
%第一级从x(0)开始,跨接一阶蝶形,再取每条对称
%第二级从x(0)开始,跨接两阶蝶形,再取每条对称
%第m级从x(0)开始,跨接2^(m-1)阶蝶形,再取每条对称....
%--------------------------------------------------------------------------
for mm=1:m %将DFT做m次基2分解，从左到右，对每次分解作DFT运算
Nmr=2^mm;
u=1; %旋转因子u初始化
WN=exp(-j*2*pi/Nmr); %本次分解的基本DFT因子WN＝exp(-i*2*pi/Nmr)
for n=1:Nmr/2 %本次跨越间隔内的各次碟形运算
for k=n:Nmr:N %本次碟形运算的跨越间隔为Nmr=2^mm
kp=k+Nmr/2; %确定碟形运算的对应单元下标(对称性)
t=x(kp)*u; %碟形运算的乘积项
x(kp)=x(k)-t; %碟形运算的加法项
x(k)=x(k)+t;
end
u=u*WN; %修改旋转因子，多乘一个基本DFT因子WN
end
end
y=x; %输出

❿ FFT算法分几种

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