快速傅里叶算法c语言
‘壹’ 利用c语言设计傅里叶程序, 求出给定信号的主频和该频率的相位。
请问有解决么，我也有这方面的需要，万分感谢
‘贰’ 快速傅里叶变换——理论
离散信号傅里叶变换的公式如下所示：
离散傅里叶变换的原理是将原本非周期的信号复制扩展为周期信号，在实际的数字电路处理中，处理的信号是有限长的，取长度为N，即N为信号 的周期，对于有限长周期信号，其离散傅里叶变换有如下性质：
其中 为周期信号的傅里叶级数，而 表示当且仅当 时有 ，因此可以将傅里叶变换转为离散表达，如下所示：
考虑 以N为周期，因此仅需要计算k从0到N-1即可，取 此公式写成矩阵乘法模式如下所示：
W为一个 的方阵，该计算的复杂度为
对于系数矩阵中的元素 ，其公式如下所示：
考虑 ，推导公式如下所示：
再考虑 和 的情况：
再考虑 和 的情况：
最后考虑 且 或 的情况：
根据上述推导，可以得出系数W具有以下四条性质，这三条性质会在后续推导中用到：
基n快速傅里叶变换用于一个长度N为 的序列，例如基2快速傅里叶作用在 的序列上，基4快速傅里叶作用在 的序列上。现在考虑基2FFT的推导（硬件实现一般使用基4或基8FFT实现），首先写出有限长离散序列的傅里叶变换，记一个信号 的FFT变换为 ：
快速傅里叶变换的核心思想为 分而治之 ，即 分治法 ，该思想的核心是将一个长度为N的问题，分级为两个长度为 的问题，应用在这里即是需要将一个序列长度为N的FFT变换问题分解为两个序列长度为 的FFT变换。首先进行如下变换：
矩阵的形式如下所示：
根据W的性质 ，代入后有：
矩阵形式的表达如下所示，现在的矩阵为两个个高度为N，长度为N/2的矩阵。
代入 ，根据W的性质 有：
矩阵表达如下所示：
代入 ，根据W的性质 有：
矩阵表达如下所示：
根据上述推导，一个长度为N点的离散傅里叶变换被变为一个长度为 的离散傅里叶变换，取 公式如下所示：
根据频域抽取基2FFT的算法，除了按前后分类外，还可以直接按奇偶进行分类，公式如下所示：
对应的矩阵表示为：
取序列 ， 代入上述表达式，取 再代入W的变换性质可得：
其对应的矩阵为：
即将对F[k]的上半部分结果分解为两个FFT结果的和，即：
现在考虑F[k]的下半部分，公式如下所示：
取 ，代入有：
代入W的性质 和 ，有：
将变量i更换为k，其矩阵形式为：
最终可以将结果汇总为：
蝶形运算的公式如下，蝶形运算输入为 和 ，输出为 和 ，系数为 ：
其转换为矩阵表达为：
蝶形公式对应着2点FFT的计算，2点FFT的计算如下所示：
转换为矩阵表达为：
对应到蝶形运算有：
首先列出基2频域抽取FFT的分治公式：
以一个8点FFT为例，输入序列为：
进行第一次分治，分为两个4点FFT，序列为：
示意图如下所示，偶数标号的结果由第一个FFT生成，奇数标号的结果由第二个FFT生成：
随后进行第二次分治，将每个4点FFT分解为两个2点FFT，每个序列为：
示意图如下所示：
最终通过2点FFT计算出结果，但如上图所示，计算出的结果位置与标号并不对应，例如计算输出的标号为2的数据（Y10[1]）应当位于输出序列（X）的标号4（X[4]）。其变换规律为计算输出的标号为n的数据（第n+1个数据）对应到输出序列标号为m的数据，n为m的二进制反序。以计算输出标号为6（第七个数据）的数据Y13[0]为例，6的二进制为110，反序为011，对应十进制数为3，即有 。
首先列出时域抽取FFT的分治公式：
‘叁’ 求基2、基4、基8FFT（快速傅里叶变换）的c语言程序，要能运行得出来的
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct{
double r;
double i;
}my_complex
;
//检查a是否为2的整数次方数
#define NOT2POW(a) (((a)-1)&(a)||(a)<=0)
//pi
#define MYPI 3.14159265358979323846
my_complex* fft(const my_complex* x, unsigned int len){
unsigned int ex=0,t=len;
unsigned int i,j,k;
my_complex *y;
double tr,ti,rr,ri,yr,yi;
if(NOT2POW(len)) return NULL; //如果失败，返回空指针
for(;!(t&1);t>>=1) ex++; //len应该等于2的ex次方
y=(my_complex*)malloc(len*sizeof(my_complex));
if(!y) return NULL;
//变址计算，库里-图基算法
for(i=0;i<len;i++){
k=i;
j=0;
t=ex;
while((t--)>0){
j<<=1;
j|=k&1;
k>>=1;
}
if(j>=i){
y[i]=x[j];
y[j]=x[i];
}
}
//用变址后的y向量进行计算
for(i=0;i<ex;i++){
t=1<<i;
for(j=0;j<len;j+=t<<1){
for(k=0;k<t;k++){
ti=-MYPI*k/t;
rr=cos(ti);
ri=sin(ti);
tr=y[j+k+t].r;
ti=y[j+k+t].i;
yr=rr*tr-ri*ti;
yi=rr*ti+ri*tr;
tr=y[j+k].r;
ti=y[j+k].i;
y[j+k].r=tr+yr;
y[j+k].i=ti+yi;
y[j+k+t].r=tr-yr;
y[j+k+t].i=ti-yi;
}
}
}
return y;
}
//以下为测试
int main()
{
int i,DATA_LEN;
my_complex *x,*y;
printf("基二FFT测试\n输入生成序列长度:");
scanf("%d",&DATA_LEN);
x=(my_complex*)malloc(DATA_LEN*sizeof(my_complex));
for(i=0;i<DATA_LEN;i++){
x[i].r=i;
x[i].i=i-1;
}
printf("处理前...\n实部\t\t虚部\n");
for(i=0;i<DATA_LEN;i++)
printf("%lf\t%lf\n",x[i].r,x[i].i);
y=fft(x,DATA_LEN);
if(!y){
printf("序列长度不为2的整数次方!\n");
return 0;
}
printf("处理后...\n实部\t\t虚部\n");
for(i=0;i<DATA_LEN;i++)
printf("%lf\t%lf\n",y[i].r,y[i].i);
free(y);
free(x);
return 0;
}
‘肆’ 快速傅里叶变换的简要介绍
有限长序列可以通过离散傅里叶变换(DFT）将其频域也离散化成有限长序列。但其计算量太大，很难实时地处理问题，因此引出了快速傅里叶变换(FFT). 1965年，Cooley和Tukey提出了计算离散傅里叶变换（DFT）的快速算法，将DFT的运算量减少了几个数量级。从此，对快速傅里叶变换（FFT）算法的研究便不断深入，数字信号处理这门新兴学科也随FFT的出现和发展而迅速发展。根据对序列分解与选取方法的不同而产生了FFT的多种算法，基本算法是基2DIT和基2DIF。FFT在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用。
快速傅氏变换（FFT），是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。
设x(n）为N项的复数序列，由DFT变换，任一X（m）的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出N项复数序列的X（m），即N点DFT变换大约就需要N^2次运算。当N=1024点甚至更多的时候，需要N2=1048576次运算，在FFT中，利用WN的周期性和对称性，把一个N项序列（设N=2k,k为正整数），分为两个N/2项的子序列，每个N/2点DFT变换需要（N/2）^2次运算，再用N次运算把两个N/2点的DFT变换组合成一个N点的DFT变换。这样变换以后，总的运算次数就变成N+2*(N/2）^2=N+N^2/2。继续上面的例子，N=1024时，总的运算次数就变成了525312次，节省了大约50%的运算量。而如果我们将这种“一分为二”的思想不断进行下去，直到分成两两一组的DFT运算单元，那么N点的DFT变换就只需要Nlog2N次的运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算量的节约就越大，这就是FFT的优越性。
‘伍’ 吐血求傅里叶逆变换（IFFT）C语言程序！
你把FFT的参数改一下不就是IFFT了吗，网上的大部分都能用，我用的很熟了
‘陆’ 一个关于128点的快速傅立叶的C语言程序
这是我写的1024点的快速傅里叶变换程序，下面有验证，你把数组
double
A[2049]={0};
double
B[1100]={0};
double
powerA[1025]={0};
改成
A[256]={0};
B[130]={0};
power[129]={0};就行了，
void
FFT(double
data[],
int
nn,
int
isign)
的程序可以针对任何点数，只要是2的n次方
具体程序如下：
#include
<iostream.h>
#include
"math.h"
#include<stdio.h>
#include<string.h>
#include
<stdlib.h>
#include
<fstream.h>
#include
<afx.h>
void
FFT(double
data[],
int
nn,
int
isign)
{
//复数的快速傅里叶变换
int
n,j,i,m,mmax,istep;
double
tempr,tempi,theta,wpr,wpi,wr,wi,wtemp;
n
=
2
*
nn;
j
=
1;
for
(i
=
1;
i<=n
;
i=i+2)
//这个循环进行的是码位倒置。
{
if(
j
>
i)
{
tempr
=
data[j];
tempi
=
data[j
+
1];
data[j]
=
data[i];
data[j
+
1]
=
data[i
+
1];
data[i]
=
tempr;
data[i
+
1]
=
tempi;
}
m
=
n
/
2;
while
(m
>=
2
&&
j
>
m)
{
j
=
j
-
m;
m
=
m
/
2;
}
j
=
j
+
m;
}
mmax
=
2;
while(
n
>
mmax
)
{
istep
=
2
*
mmax;
//这里表示一次的数字的变化。也体现了级数，若第一级时，也就是书是的第0级，其为两个虚数，所以对应数组应该增加4，这样就可以进入下一组运算
theta
=
-6.28318530717959
/
(isign
*
mmax);
wpr
=
-2.0
*
sin(0.5
*
theta)*sin(0.5
*
theta);
wpi
=
sin(theta);
wr
=
1.0;
wi
=
0.0;
for(
m
=
1;
m<=mmax;
m=m+2)
{
for
(i
=
m;
i<=n;
i=i+istep)
{
j
=
i
+
mmax;
tempr=double(wr)*data[j]-double(wi)*data[j+1];//这两句表示蝶形因子的下一个数乘以W因子所得的实部和虚部。
tempi=double(wr)*data[j+1]+double(wi)*data[j];
data[j]
=
data[i]
-
tempr;
//蝶形单元计算后下面单元的实部，下面为虚部，注意其变换之后的数组序号与书上蝶形单元是一致的
data[j
+
1]
=
data[i
+
1]
-
tempi;
data[i]
=
data[i]
+
tempr;
data[i
+
1]
=
data[i
+
1]
+
tempi;
}
wtemp
=
wr;
wr
=
wr
*
wpr
-
wi
*
wpi
+
wr;
wi
=
wi
*
wpr
+
wtemp
*
wpi
+
wi;
}
mmax
=
istep;
}
}
void
main()
{
//本程序已经和MATLAB运算结果对比，准确无误，需要注意的的是，计算中数组都是从1开始取得，丢弃了A[0]等数据
double
A[2049]={0};
double
B[1100]={0};
double
powerA[1025]={0};
char
line[50];
char
dataA[20],
dataB[20];
int
ij;
char
ch1[3]="\t";
char
ch2[3]="\n";
int
strl1,strl2;
CString
str1,str2;
ij=1;
//********************************读入文件data1024.txt中的数据,
其中的数据格式见该文件
FILE
*fp
=
fopen("data1024.txt","r");
if(!fp)
{
cout<<"Open
file
is
failing!"<<endl;
return;
}
while(!feof(fp))
//feof(fp)有两个返回值:如果遇到文件结束，函数feof（fp）的值为1，否则为0。
{
memset(line,0,50);
//清空为0
memset(dataA,0,20);
memset(dataB,0,20);
fgets(line,50,fp);
//函数的功能是从fp所指文件中读入n-1个字符放入line为起始地址的空间内
sscanf(line,
"%s%s",
dataA,
dataB);
//我同时读入了两列值，但你要求1024个，那么我就只用了第一列的1024个值
//dataA读入第一列，dataB读入第二列
B[ij]=atof(dataA);
//将字符型的dataA值转化为float型
ij++;
}
for
(int
mm=1;mm<1025;mm++)//A[2*mm-1]是实部，A[2*mm]是虚部，当只要输入实数时，那么保证虚部A[mm*2]为零即可
{
A[2*mm-1]=B[mm];
A[2*mm]=0;
}
//*******************************************正式计算FFT
FFT(A,1024,1);
//********************************************写入数据到workout.txt文件中
for
(int
k=1;k<2049;k=k+2)
{
powerA[(k+1)/2]=sqrt(pow(A[k],2.0)+pow(A[k+1],2.0));//求功率谱
FILE
*pFile=fopen("workout.txt","a+");
//?a+只能在文件最后补充，光标在结尾。没有则创建
memset(ch1,0,15);
str1.Format("%.4f",powerA[(k+1)/2]);
if
(A[k+1]>=0)
str2.Format("%d\t%6.4f%s%6.4f
%s",(k+1)/2,A[k],"+",A[k+1],"i");//保存fft计算的频谱，是复数频谱
else
str2.Format("%d\t%6.4f%6.4f
%s",(k+1)/2,A[k],A[k+1],"i");
strl1=strlen(str1);
strl2=strlen(str2);
//
用
法:fwrite(buffer,size,count,fp);
//
buffer：是一个指针，对fwrite来说，是要输出数据的地址。
//
size：要写入的字节数；
//
count:要进行写入size字节的数据项的个数；
//
fp:目标文件指针。
fwrite(str2,1,strl2,pFile);
fwrite(ch1,1,3,pFile);
fwrite(ch1,1,3,pFile);
fwrite(str1,1,strl1,pFile);
fwrite(ch2,1,3,pFile);
fclose(pFile);
}
cout<<"计算完毕，到fft_test\workout.txt查看结果"<<endl;
}
‘柒’ 怎么用C语言实现FFT算法 呀
float ar[1024],ai[1024];/* 原始数据实部，虚部 */
float a[2050];
void fft(int nn) /* nn数据长度 */
{
int n1,n2,i,j,k,l,m,s,l1;
float t1,t2,x,y;
float w1,w2,u1,u2,z;
float fsin[10]={0.000000,1.000000,0.707107,0.3826834,0.1950903,0.09801713,0.04906767,0.02454123,0.01227154,0.00613588,};
float fcos[10]={-1.000000,0.000000,0.7071068,0.9238796,0.9807853,0.99518472,0.99879545,0.9996988,0.9999247,0.9999812,};
switch(nn)
{
case 1024: s=10; break;
case 512: s=9; break;
case 256: s=8; break;
}
n1=nn/2; n2=nn-1;
j=1;
for(i=1;i<=nn;i++)
{
a[2*i]=ar[i-1];
a[2*i+1]=ai[i-1];
}
for(l=1;l<n2;l++)
{
if(l<j)
{
t1=a[2*j];
t2=a[2*j+1];
a[2*j]=a[2*l];
a[2*j+1]=a[2*l+1];
a[2*l]=t1;
a[2*l+1]=t2;
}
k=n1;
while (k<j)
{
j=j-k;
k=k/2;
}
j=j+k;
}
for(i=1;i<=s;i++)
{
u1=1;
u2=0;
m=(1<<i);
k=m>>1;
w1=fcos[i-1];
w2=-fsin[i-1];
for(j=1;j<=k;j++)
{
for(l=j;l<nn;l=l+m)
{
l1=l+k;
t1=a[2*l1]*u1-a[2*l1+1]*u2;
t2=a[2*l1]*u2+a[2*l1+1]*u1;
a[2*l1]=a[2*l]-t1;
a[2*l1+1]=a[2*l+1]-t2;
a[2*l]=a[2*l]+t1;
a[2*l+1]=a[2*l+1]+t2;
}
z=u1*w1-u2*w2;
u2=u1*w2+u2*w1;
u1=z;
}
}
for(i=1;i<=nn/2;i++)
{
ar[i]=4*a[2*i+2]/nn; /* 实部 */
ai[i]=-4*a[2*i+3]/nn; /* 虚部 */
a[i]=4*sqrt(ar[i]*ar[i]+ai[i]*ai[i]); /* 幅值 */
}
}
(http://..com/question/284943905.html?an=0&si=2)
‘捌’ 如何用C语言或汇编语言实现FFT(快速傅里叶）变换，并写出C语言或汇编代码，万分感谢。
float ar[1024],ai[1024];/* 原始数据实部，虚部 */
float a[2050];
void fft(int nn) /* nn数据长度 */
{
int n1,n2,i,j,k,l,m,s,l1;
float t1,t2,x,y;
float w1,w2,u1,u2,z;
float fsin[10]={0.000000,1.000000,0.707107,0.3826834,0.1950903,0.09801713,0.04906767,0.02454123,0.01227154,0.00613588,};
float fcos[10]={-1.000000,0.000000,0.7071068,0.9238796,0.9807853,0.99518472,0.99879545,0.9996988,0.9999247,0.9999812,};
switch(nn)
{
case 1024: s=10; break;
case 512: s=9; break;
case 256: s=8; break;
}
n1=nn/2; n2=nn-1;
j=1;
for(i=1;i<=nn;i++)
{
a[2*i]=ar[i-1];
a[2*i+1]=ai[i-1];
}
for(l=1;l<n2;l++)
{
if(l<j)
{
t1=a[2*j];
t2=a[2*j+1];
a[2*j]=a[2*l];
a[2*j+1]=a[2*l+1];
a[2*l]=t1;
a[2*l+1]=t2;
}
k=n1;
while (k<j)
{
j=j-k;
k=k/2;
}
j=j+k;
}
for(i=1;i<=s;i++)
{
u1=1;
u2=0;
m=(1<<i);
k=m>>1;
w1=fcos[i-1];
w2=-fsin[i-1];
for(j=1;j<=k;j++)
{
for(l=j;l<nn;l=l+m)
{
l1=l+k;
t1=a[2*l1]*u1-a[2*l1+1]*u2;
t2=a[2*l1]*u2+a[2*l1+1]*u1;
a[2*l1]=a[2*l]-t1;
a[2*l1+1]=a[2*l+1]-t2;
a[2*l]=a[2*l]+t1;
a[2*l+1]=a[2*l+1]+t2;
}
z=u1*w1-u2*w2;
u2=u1*w2+u2*w1;
u1=z;
}
}
for(i=1;i<=nn/2;i++)
{
ar[i]=4*a[2*i+2]/nn; /* 实部 */
ai[i]=-4*a[2*i+3]/nn; /* 虚部 */
a[i]=4*sqrt(ar[i]*ar[i]+ai[i]*ai[i]); /* 幅值 */
}
}
‘玖’ 求快速傅里叶算法的C语言实现代码
这是源于 Numerical Recipes 的关键性的函数，我曾使用过（书本可能有印刷错误，这里给的没有错误）。我不可能给你在这里讲解语句功能，你可以查原书。
isign 1 或 0 是正变换和反变换。调用前，要自己去掉 mean，尾部要自己 padding ( 最简单添0），时间域 和 频率 域 要自己 滤波。 nn 必须是2的整数次方，例如1024，4096。
#define SWAP(a,b) tempr=(a);(a)=(b);(b)=tempr
void jfour1(float ya[], unsigned long nn, int isign)
{
unsigned long n,mmax,m,j,istep,i;
double wtemp,wr,wpr,wpi,wi,theta;
float tempr,tempi;
n=nn << 1;
j=1;
for (i=1;i<n;i+=2) {
if (j > i) {
SWAP(ya[j],ya[i]);
SWAP(ya[j+1],ya[i+1]);
}
m=n >> 1;
while (m >= 2 && j > m) {
j -= m;
m >>= 1;
};
j += m;
};
mmax=2;
while (n > mmax) {
istep=mmax << 1;
theta=isign*(6.28318530717959/mmax);
wtemp=sin(0.5*theta);
wpr = -2.0*wtemp*wtemp;
wpi=sin(theta);
wr=1.0;
wi=0.0;
for (m=1;m<mmax;m+=2) {
for (i=m;i<=n;i+=istep) {
j=i+mmax;
tempr = wr * ya[j]- wi * ya[j+1];
tempi = wr * ya[j+1] + wi * ya[j];
ya[j] = ya[i] - tempr;
ya[j+1] = ya[i+1] - tempi;
ya[i] += tempr;
ya[i+1] += tempi;
};
wr = (wtemp=wr) * wpr - wi * wpi + wr;
wi = wi * wpr + wtemp * wpi + wi;
};
mmax=istep;
};
}
#undef SWAP
void jrealft(float ya[], unsigned long n, int isign)
{
void jfour1(float ya[], unsigned long nn, int isign);
unsigned long i,i1,i2,i3,i4,np3,n05;
float c1=0.5,c2,h1r,h1i,h2r,h2i;
double wr,wi,wpr,wpi,wtemp,theta;
n05 = n >> 1;
theta=3.141592653589793/(double) (n05);
if (isign == 1) {
c2 = -0.5;
jfour1(ya,n05,1);
} else {
c2=0.5;
theta = -theta;
};
wtemp=sin(0.5*theta);
wpr = -2.0*wtemp*wtemp;
wpi=sin(theta);
wr=1.0+wpr;
wi=wpi;
np3=n+3;
for (i=2;i<=(n>>2);i++) {
i4=1+(i3=np3-(i2=1+(i1=i+i-1)));
h1r = c1 * (ya[i1] + ya[i3]);
h1i = c1 * (ya[i2] - ya[i4]);
h2r = -c2* (ya[i2] + ya[i4]);
h2i = c2 * (ya[i1] - ya[i3]);
ya[i1] = h1r + wr * h2r - wi * h2i;
ya[i2] = h1i + wr * h2i + wi * h2r;
ya[i3] = h1r - wr * h2r + wi * h2i;
ya[i4] = -h1i + wr * h2i + wi * h2r;
wr= (wtemp=wr) * wpr - wi * wpi + wr;
wi=wi * wpr + wtemp * wpi + wi;
};
if (isign == 1) {
ya[1] = (h1r=ya[1]) + ya[2];
ya[2] = h1r-ya[2];
} else {
ya[1] = c1 * ((h1r=ya[1]) + ya[2]);
ya[2]=c1 * (h1r - ya[2]);
jfour1(ya,n05,-1);
}
}
‘拾’ 傅里叶变换用C语言程序怎么实现
#include <math.h>
#include <stdio.h>
#define N 8
void kkfft(double pr[], double pi[], int n, int k, double fr[], double fi[], int l, int il);
void main()
{
double xr[N],xi[N],Yr[N],Yi[N],l=0,il=0;
int i,j,n=N,k=3;
for(i=0;i<N;i++)
{
xr[i]=i;
xi[i]=0;
}
printf("------FFT------\n");
l=0;
kkfft(xr,xi,n,k,Yr,Yi,l,il);
for(i=0;i<N;i++)
{
printf("%-11lf + j* %-11lf\n",Yr[i],Yi[i]);
}
printf("-----DFFT-------\n");
l=1;
kkfft(Yr,Yi,n,k,xr,xi,l,il);
for(i=0;i<N;i++)
{
printf("%-11lf + j* %-11lf\n",xr[i],xi[i]);
}
getch();
}
void kkfft(double pr[], double pi[], int n, int k, double fr[], double fi[], int l, int il)
{
int it,m,is,i,j,nv,l0;
double p,q,s,vr,vi,poddr,poddi;
for (it=0; it<=n-1; it++)
{
m = it;
is = 0;
for(i=0; i<=k-1; i++)
{
j = m/2;
is = 2*is+(m-2*j);
m = j;
}
fr[it] = pr[is];
fi[it] = pi[is];
}
pr[0] = 1.0;
pi[0] = 0.0;
p = 6.283185306/(1.0*n);
pr[1] = cos(p);
pi[1] = -sin(p);
if (l!=0)
pi[1]=-pi[1];
for (i=2; i<=n-1; i++)
{
p = pr[i-1]*pr[1];
q = pi[i-1]*pi[1];
s = (pr[i-1]+pi[i-1])*(pr[1]+pi[1]);
pr[i] = p-q;
pi[i] = s-p-q;
}
for (it=0; it<=n-2; it=it+2)
{
vr = fr[it];
vi = fi[it];
fr[it] = vr+fr[it+1];
fi[it] = vi+fi[it+1];
fr[it+1] = vr-fr[it+1];
fi[it+1] = vi-fi[it+1];
}
m = n/2;
nv = 2;
for (l0=k-2; l0>=0; l0--)
{
m = m/2;
nv = 2*nv;
for(it=0; it<=(m-1)*nv; it=it+nv)
for (j=0; j<=(nv/2)-1; j++)
{
p = pr[m*j]*fr[it+j+nv/2];
q = pi[m*j]*fi[it+j+nv/2];
s = pr[m*j]+pi[m*j];
s = s*(fr[it+j+nv/2]+fi[it+j+nv/2]);
poddr = p-q;
poddi = s-p-q;
fr[it+j+nv/2] = fr[it+j]-poddr;
fi[it+j+nv/2] = fi[it+j]-poddi;
fr[it+j] = fr[it+j]+poddr;
fi[it+j] = fi[it+j]+poddi;
}
}
/*逆傅立叶变换*/
if(l!=0)
{
for(i=0; i<=n-1; i++)
{
fr[i] = fr[i]/(1.0*n);
fi[i] = fi[i]/(1.0*n);
}
}
/*是否计算模和相角*/
if(il!=0)
{
for(i=0; i<=n-1; i++)
{
pr[i] = sqrt(fr[i]*fr[i]+fi[i]*fi[i]);
if(fabs(fr[i])<0.000001*fabs(fi[i]))
{
if ((fi[i]*fr[i])>0)
pi[i] = 90.0;
else
pi[i] = -90.0;
}
else
pi[i] = atan(fi[i]/fr[i])*360.0/6.283185306;
}
}
return;
}