⑴ 基于FFT的算法优化 要C语言完整程序（利用旋转因子的性质），有的请留言，答谢！！！(有核心代码，望指教
实现(C描述)
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
//#include "complex.h"
// --------------------------------------------------------------------------
#define N 8 //64
#define M 3 //6 //2^m=N
#define PI 3.1415926
// --------------------------------------------------------------------------
float twiddle[N/2] = {1.0, 0.707, 0.0, -0.707};
float x_r[N] = {1, 1, 1, 1, 0, 0, 0, 0};
float x_i[N]; //N=8
/*
float twiddle[N/2] = {1, 0.9951, 0.9808, 0.9570, 0.9239, 0.8820, 0.8317, 0.7733,
0.7075, 0.6349, 0.5561, 0.4721, 0.3835, 0.2912, 0.1961, 0.0991,
0.0000,-0.0991,-0.1961,-0.2912,-0.3835,-0.4721,-0.5561,-0.6349,
-0.7075,-0.7733, 0.8317,-0.8820,-0.9239,-0.9570,-0.9808,-0.9951}; //N=64
float x_r[N]={1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,};
float x_i[N];
*/
FILE *fp;
// ----------------------------------- func -----------------------------------
/**
* 初始化输出虚部
*/
static void fft_init( void )
{
int i;
for(i=0; i<N; i++) x_i[i] = 0.0;
}
/**
* 反转算法.将时域信号重新排序.
* 这个算法有改进的空间
*/
static void bitrev( void )
{
int p=1, q, i;
int bit_rev[ N ]; //
float xx_r[ N ]; //
bit_rev[ 0 ] = 0;
while( p < N )
{
for(q=0; q<p; q++)
{
bit_rev[ q ] = bit_rev[ q ] * 2;
bit_rev[ q + p ] = bit_rev[ q ] + 1;
}
p *= 2;
}
for(i=0; i<N; i++) xx_r[ i ] = x_r[ i ];
for(i=0; i<N; i++) x_r[i] = xx_r[ bit_rev[i] ];
}
/* ------------ add by sshc625 ------------ */
static void bitrev2( void )
{
return ;
}
/* */
void display( void )
{
printf("\n\n");
int i;
for(i=0; i<N; i++)
printf("%f\t%f\n", x_r[i], x_i[i]);
}
/**
*
*/
void fft1( void )
{ fp = fopen("log1.txt", "a+");
int L, i, b, j, p, k, tx1, tx2;
float TR, TI, temp; // 临时变量
float tw1, tw2;
/* 深M. 对层进行循环. L为当前层, 总层数为M. */
for(L=1; L<=M; L++)
{
fprintf(fp,"----------Layer=%d----------\n", L);
/* b的意义非常重大,b表示当前层的颗粒具有的输入样本点数 */
b = 1;
i = L - 1;
while(i > 0)
{
b *= 2;
i--;
}
// -------------- 是否外层对颗粒循环, 内层对样本点循环逻辑性更强一些呢! --------------
/*
* outter对参与DFT的样本点进行循环
* L=1, 循环了1次(4个颗粒, 每个颗粒2个样本点)
* L=2, 循环了2次(2个颗粒, 每个颗粒4个样本点)
* L=3, 循环了4次(1个颗粒, 每个颗粒8个样本点)
*/
for(j=0; j<b; j++)
{
/* 求旋转因子tw1 */
p = 1;
i = M - L; // M是为总层数, L为当前层.
while(i > 0)
{
p = p*2;
i--;
}
p = p * j;
tx1 = p % N;
tx2 = tx1 + 3*N/4;
tx2 = tx2 % N;
// tw1是cos部分, 实部; tw2是sin部分, 虚数部分.
tw1 = ( tx1>=N/2)? -twiddle[tx1-N/2] : twiddle[ tx1 ];
tw2 = ( tx2>=N/2)? -twiddle[tx2-(N/2)] : twiddle[tx2];
/*
* inner对颗粒进行循环
* L=1, 循环了4次(4个颗粒, 每个颗粒2个输入)
* L=2, 循环了2次(2个颗粒, 每个颗粒4个输入)
* L=3, 循环了1次(1个颗粒, 每个颗粒8个输入)
*/
for(k=j; k<N; k=k+2*b)
{
TR = x_r[k]; // TR就是A, x_r[k+b]就是B.
TI = x_i[k];
temp = x_r[k+b];
/*
* 如果复习一下 (a+j*b)(c+j*d)两个复数相乘后的实部虚部分别是什么
* 就能理解为什么会如下运算了, 只有在L=1时候输入才是实数, 之后层的
* 输入都是复数, 为了让所有的层的输入都是复数, 我们只好让L=1时候的
* 输入虚部为0
* x_i[k+b]*tw2是两个虚数相乘
*/
fprintf(fp, "tw1=%f, tw2=%f\n", tw1, tw2);
x_r[k] = TR + x_r[k+b]*tw1 + x_i[k+b]*tw2;
x_i[k] = TI - x_r[k+b]*tw2 + x_i[k+b]*tw1;
x_r[k+b] = TR - x_r[k+b]*tw1 - x_i[k+b]*tw2;
x_i[k+b] = TI + temp*tw2 - x_i[k+b]*tw1;
fprintf(fp, "k=%d, x_r[k]=%f, x_i[k]=%f\n", k, x_r[k], x_i[k]);
fprintf(fp, "k=%d, x_r[k]=%f, x_i[k]=%f\n", k+b, x_r[k+b], x_i[k+b]);
} //
} //
} //
}
/**
* ------------ add by sshc625 ------------
* 该实现的流程为
* for( Layer )
* for( Granule )
* for( Sample )
*
*
*
*
*/
void fft2( void )
{ fp = fopen("log2.txt", "a+");
int cur_layer, gr_num, i, k, p;
float tmp_real, tmp_imag, temp; // 临时变量, 记录实部
float tw1, tw2;// 旋转因子,tw1为旋转因子的实部cos部分, tw2为旋转因子的虚部sin部分.
int step; // 步进
int sample_num; // 颗粒的样本总数(各层不同, 因为各层颗粒的输入不同)
/* 对层循环 */
for(cur_layer=1; cur_layer<=M; cur_layer++)
{
/* 求当前层拥有多少个颗粒(gr_num) */
gr_num = 1;
i = M - cur_layer;
while(i > 0)
{
i--;
gr_num *= 2;
}
/* 每个颗粒的输入样本数N' */
sample_num = (int)pow(2, cur_layer);
/* 步进. 步进是N'/2 */
step = sample_num/2;
/* */
k = 0;
/* 对颗粒进行循环 */
for(i=0; i<gr_num; i++)
{
/*
* 对样本点进行循环, 注意上限和步进
*/
for(p=0; p<sample_num/2; p++)
{
// 旋转因子, 需要优化...
tw1 = cos(2*PI*p/pow(2, cur_layer));
tw2 = -sin(2*PI*p/pow(2, cur_layer));
tmp_real = x_r[k+p];
tmp_imag = x_i[k+p];
temp = x_r[k+p+step];
/*(tw1+jtw2)(x_r[k]+jx_i[k])
*
* real : tw1*x_r[k] - tw2*x_i[k]
* imag : tw1*x_i[k] + tw2*x_r[k]
* 我想不抽象出一个
* typedef struct {
* double real; // 实部
* double imag; // 虚部
* } complex; 以及针对complex的操作
* 来简化复数运算是否是因为效率上的考虑!
*/
/* 蝶形算法 */
x_r[k+p] = tmp_real + ( tw1*x_r[k+p+step] - tw2*x_i[k+p+step] );
x_i[k+p] = tmp_imag + ( tw2*x_r[k+p+step] + tw1*x_i[k+p+step] );
/* X[k] = A(k)+WB(k)
* X[k+N/2] = A(k)-WB(k) 的性质可以优化这里*/
// 旋转因子, 需要优化...
tw1 = cos(2*PI*(p+step)/pow(2, cur_layer));
tw2 = -sin(2*PI*(p+step)/pow(2, cur_layer));
x_r[k+p+step] = tmp_real + ( tw1*temp - tw2*x_i[k+p+step] );
x_i[k+p+step] = tmp_imag + ( tw2*temp + tw1*x_i[k+p+step] );
printf("k=%d, x_r[k]=%f, x_i[k]=%f\n", k+p, x_r[k+p], x_i[k+p]);
printf("k=%d, x_r[k]=%f, x_i[k]=%f\n", k+p+step, x_r[k+p+step], x_i[k+p+step]);
}
/* 开跳!:) */
k += 2*step;
}
}
}
/*
* 后记:
* 究竟是颗粒在外层循环还是样本输入在外层, 好象也差不多, 复杂度完全一样.
* 但以我资质愚钝花费了不少时间才弄明白这数十行代码.
* 从中我发现一个于我非常有帮助的教训, 很久以前我写过一部分算法, 其中绝大多数都是递归.
* 将数据量减少, 减少再减少, 用归纳的方式来找出数据量加大代码的规律
* 比如FFT
* 1. 先写死LayerI的代码; 然后再把LayerI的输出作为LayerII的输入, 又写死代码; ......
* 大约3层就可以统计出规律来. 这和递归也是一样, 先写死一两层, 自然就出来了!
* 2. 有的功能可以写伪代码, 不急于求出结果, 降低复杂性, 把逻辑结果定出来后再添加.
* 比如旋转因子就可以写死, 就写1.0. 流程出来后再写旋转因子.
* 寥寥数语, 我可真是流了不少汗! Happy!
*/
void dft( void )
{
int i, n, k, tx1, tx2;
float tw1,tw2;
float xx_r[N],xx_i[N];
/*
* clear any data in Real and Imaginary result arrays prior to DFT
*/
for(k=0; k<=N-1; k++)
xx_r[k] = xx_i[k] = x_i[k] = 0.0;
// caculate the DFT
for(k=0; k<=(N-1); k++)
{
for(n=0; n<=(N-1); n++)
{
tx1 = (n*k);
tx2 = tx1+(3*N)/4;
tx1 = tx1%(N);
tx2 = tx2%(N);
if(tx1 >= (N/2))
tw1 = -twiddle[tx1-(N/2)];
else
tw1 = twiddle[tx1];
if(tx2 >= (N/2))
tw2 = -twiddle[tx2-(N/2)];
else
tw2 = twiddle[tx2];
xx_r[k] = xx_r[k]+x_r[n]*tw1;
xx_i[k] = xx_i[k]+x_r[n]*tw2;
}
xx_i[k] = -xx_i[k];
}
// display
for(i=0; i<N; i++)
printf("%f\t%f\n", xx_r[i], xx_i[i]);
}
// ---------------------------------------------------------------------------
int main( void )
{
fft_init( );
bitrev( );
// bitrev2( );
//fft1( );
fft2( );
display( );
system( "pause" );
// dft();
return 1;
}
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/sshcx/archive/2007/06/14/1651616.aspx
⑵ 急求 快速傅里叶变换的程序 会的大侠帮忙做一个~
以前用FFT都是直接用Matlab里面的，可是如果实际工程里面需要，还是得写一个C语言版本的。C++处理复数比较容易，但目前嵌入式开发还是C语言的天下，因此C语言的FFT应用起来更方便。写完贴出来，希望对大家有一些帮助。贴出来排版可能有点乱，那不是我的原因，我写的程序都是整整齐齐的，可以直接点击文章后面的目录下载源程序。
最近C程序写的比较多，C++好久不写，有点荒废了。。。
/**
* FFT - Fast Fourier transform. The length of X must be a power
* of two, for a fast radix-2 fast-Fourier transform algorithm
* is used. spadger@bmy <[email protected]> 2007.9.2
*/
＃i nclude <math.h>
＃i nclude <stdio.h>
#define M_PI 3.14159265358979323846
typedef struct { double r,i; } cplx_t;
void cplx_mul(cplx_t *x, cplx_t *y, cplx_t *r)
{
r->r=x->r*y->r-x->i*y->i;
r->i=x->r*y->i+x->i*y->r;
}
void cplx_exp(cplx_t *x, cplx_t *r)
{
double expx=exp(x->r);
r->r=expx*cos(x->i);
r->i=expx*sin(x->i);
}
void bit_reverse(cplx_t *x, int N)
{
double t;
cplx_t tmp;
unsigned int i=0,j=0,k=0;
for(i=0; i<N; i++) {
k=i;
j=0;
t=log(0.0+N)/log(2.0);
while((t--)>0) {
j<<=1;
j|=k&1;
k>>=1;
}
if(j>i) {
tmp=x[i];
x[i]=x[j];
x[j]=tmp;
}
}
}
void fft(cplx_t *x, int N)
{
cplx_t u,d,p,W,tmp;
int i=0,j=0,k=0,l=0,M=floor(log(0.0+N)/log(2.0));
if(log(0.0+N)/log(2.0)-M > 0){
printf("The length of x (N) must be a power of two!!!\n");
return;
}
bit_reverse(x,N);
for(i=0; i<M; i++) {
l=1<<i;
for(j=0; j<N; j+=2*l ) {
for(k=0; k<l; k++) {
tmp.r=0.0;
tmp.i=-2*M_PI*k/2/l;
cplx_exp(&tmp,&W);
cplx_mul(&x[j+k+l],&W,&p);
u.r=x[j+k].r+p.r;
u.i=x[j+k].i+p.i;
d.r=x[j+k].r-p.r;
d.i=x[j+k].i-p.i;
x[j+k]=u;
x[j+k+l]=d;
}
}
}
}
/**
* for test and demonstation, set '#if 0' to comment this out.
*/
#if 1
#define DATA_LEN 64
int main()
{
int i;
cplx_t x[DATA_LEN];
for(i=0;i<DATA_LEN;i++){
x[i].r=i;
x[i].i=0;
}
printf("Before...\nReal\t\tImag\n");
for(i=0;i<DATA_LEN;i++)
printf("%f\t%f\n",x[i].r,x[i].i);
fft(x,DATA_LEN);
printf("After...\nReal\t\tImag\n");
for(i=0;i<DATA_LEN;i++)
printf("%f\t%f\n",x[i].r,x[i].i);
return 0;
}
#endif
源程序下载：
http://www.blog.com.cn/user88/spadger/upload/92271850.rar
⑶ 傅里叶变换用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;
}
⑷ 求FFT的c语言程序
快速傅里叶变换 要用C++ 才行吧 你可以用MATLAB来实现更方便点啊
此FFT 是用.0编写，由FFT.CPP；STDAFX.H和STDAFX.CPP三个文件组成，编译成功。程序可以用文件输入和输出为文件。文件格式为TXT文件。测试结果如下：
输入文件：8.TXT 或手动输入
8 //N
1
2
3
4
5
6
7
8
输出结果为：或保存为TXT文件。（8OUT.TXT）
8
(36,0)
(-4,9.65685)
(-4,4)
(-4,1.65685)
(-4,0)
(-4,-1.65685)
(-4,-4)
(-4,-9.65685)
下面为FFT.CPP文件：
// FFT.cpp : 定义控制台应用程序的入口点。
#include "stdafx.h"
#include <iostream>
#include <complex>
#include <bitset>
#include <vector>
#include <conio.h>
#include <string>
#include <fstream>
using namespace std;
bool inputData(unsigned long &, vector<complex<double> >&); //手工输入数据
void FFT(unsigned long &, vector<complex<double> >&); //FFT变换
void display(unsigned long &, vector<complex<double> >&); //显示结果
bool readDataFromFile(unsigned long &, vector<complex<double> >&); //从文件中读取数据
bool saveResultToFile(unsigned long &, vector<complex<double> >&); //保存结果至文件中
const double PI = 3.1415926;
int _tmain(int argc, _TCHAR* argv[])
{
vector<complex<double> > vecList; //有限长序列
unsigned long ulN = 0; //N
char chChoose = ' '; //功能选择
//功能循环
while(chChoose != 'Q' && chChoose != 'q')
{
//显示选择项
cout << "\nPlease chose a function" << endl;
cout << "\t1.Input data manually, press 'M':" << endl;
cout << "\t2.Read data from file, press 'F':" << endl;
cout << "\t3.Quit, press 'Q'" << endl;
cout << "Please chose:";
//输入选择
chChoose = getch();
//判断
switch(chChoose)
{
case 'm': //手工输入数据
case 'M':
if(inputData(ulN, vecList))
{
FFT(ulN, vecList);
display(ulN, vecList);
saveResultToFile(ulN, vecList);
}
break;
case 'f': //从文档读取数据
case 'F':
if(readDataFromFile(ulN, vecList))
{
FFT(ulN, vecList);
display(ulN, vecList);
saveResultToFile(ulN, vecList);
}
break;
}
}
return 0;
}
bool Is2Power(unsigned long ul) //判断是否是2的整数次幂
{
if(ul < 2)
return false;
while( ul > 1 )
{
if( ul % 2 )
return false;
ul /= 2;
}
return true;
}
bool inputData(unsigned long & ulN, vector<complex<double> >& vecList)
{
//题目
cout<< "\n\n\n==============================Input Data===============================" << endl;
//输入N
cout<< "\nInput N:";
cin>>ulN;
if(!Is2Power(ulN)) //验证N的有效性
{
cout<< "N is invalid (N must like 2, 4, 8, .....), please retry." << endl;
return false;
}
//输入各元素
vecList.clear(); //清空原有序列
complex<double> c;
for(unsigned long i = 0; i < ulN; i++)
{
cout << "Input x(" << i << "):";
cin >> c;
vecList.push_back(c);
}
return true;
}
bool readDataFromFile(unsigned long & ulN, vector<complex<double> >& vecList) //从文件中读取数据
{
//题目
cout<< "\n\n\n===============Read Data From File==============" << endl;
//输入文件名
string strfilename;
cout << "Input filename:" ;
cin >> strfilename;
//打开文件
cout << "open file " << strfilename << "......." <<endl;
ifstream loadfile;
loadfile.open(strfilename.c_str());
if(!loadfile)
{
cout << "\tfailed" << endl;
return false;
}
else
{
cout << "\tsucceed" << endl;
}
vecList.clear();
//读取N
loadfile >> ulN;
if(!loadfile)
{
cout << "can't get N" << endl;
return false;
}
else
{
cout << "N = " << ulN << endl;
}
//读取元素
complex<double> c;
for(unsigned long i = 0; i < ulN; i++)
{
loadfile >> c;
if(!loadfile)
{
cout << "can't get enough infomation" << endl;
return false;
}
else
cout << "x(" << i << ") = " << c << endl;
vecList.push_back(c);
}
//关闭文件
loadfile.close();
return true;
}
bool saveResultToFile(unsigned long & ulN, vector<complex<double> >& vecList) //保存结果至文件中
{
//询问是否需要将结果保存至文件
char chChoose = ' ';
cout << "Do you want to save the result to file? (y/n):";
chChoose = _getch();
if(chChoose != 'y' && chChoose != 'Y')
{
return true;
}
//输入文件名
string strfilename;
cout << "\nInput file name:" ;
cin >> strfilename;
cout << "Save result to file " << strfilename << "......" << endl;
//打开文件
ofstream savefile(strfilename.c_str());
if(!savefile)
{
cout << "can't open file" << endl;
return false;
}
//写入N
savefile << ulN << endl;
//写入元素
for(vector<complex<double> >::iterator i = vecList.begin(); i < vecList.end(); i++)
{
savefile << *i << endl;
}
//写入完毕
cout << "save succeed." << endl;
//关闭文件
savefile.close();
return true;
}
void FFT(unsigned long & ulN, vector<complex<double> >& vecList)
{
//得到幂数
unsigned long ulPower = 0; //幂数
unsigned long ulN1 = ulN - 1;
while(ulN1 > 0)
{
ulPower++;
ulN1 /= 2;
}
//反序
bitset<sizeof(unsigned long) * 8> bsIndex; //二进制容器
unsigned long ulIndex; //反转后的序号
unsigned long ulK;
for(unsigned long p = 0; p < ulN; p++)
{
ulIndex = 0;
ulK = 1;
bsIndex = bitset<sizeof(unsigned long) * 8>(p);
for(unsigned long j = 0; j < ulPower; j++)
{
ulIndex += bsIndex.test(ulPower - j - 1) ? ulK : 0;
ulK *= 2;
}
if(ulIndex > p)
{
complex<double> c = vecList[p];
vecList[p] = vecList[ulIndex];
vecList[ulIndex] = c;
}
}
//计算旋转因子
vector<complex<double> > vecW;
for(unsigned long i = 0; i < ulN / 2; i++)
{
vecW.push_back(complex<double>(cos(2 * i * PI / ulN) , -1 * sin(2 * i * PI / ulN)));
}
for(unsigned long m = 0; m < ulN / 2; m++)
{
cout<< "\nvW[" << m << "]=" << vecW[m];
}
//计算FFT
unsigned long ulGroupLength = 1; //段的长度
unsigned long ulHalfLength = 0; //段长度的一半
unsigned long ulGroupCount = 0; //段的数量
complex<double> cw; //WH(x)
complex<double> c1; //G(x) + WH(x)
complex<double> c2; //G(x) - WH(x)
for(unsigned long b = 0; b < ulPower; b++)
{
ulHalfLength = ulGroupLength;
ulGroupLength *= 2;
for(unsigned long j = 0; j < ulN; j += ulGroupLength)
{
for(unsigned long k = 0; k < ulHalfLength; k++)
{
cw = vecW[k * ulN / ulGroupLength] * vecList[j + k + ulHalfLength];
c1 = vecList[j + k] + cw;
c2 = vecList[j + k] - cw;
vecList[j + k] = c1;
vecList[j + k + ulHalfLength] = c2;
}
}
}
}
void display(unsigned long & ulN, vector<complex<double> >& vecList)
{
cout << "\n\n===========================Display The Result=========================" << endl;
for(unsigned long d = 0; d < ulN;d++)
{
cout << "X(" << d << ")\t\t\t = " << vecList[d] << endl;
}
}
下面为STDAFX.H文件：
// stdafx.h : 标准系统包含文件的包含文件，
// 或是常用但不常更改的项目特定的包含文件
#pragma once
#include <iostream>
#include <tchar.h>
// TODO: 在此处引用程序要求的附加头文件
下面为STDAFX.CPP文件：
// stdafx.cpp : 只包括标准包含文件的源文件
// FFT.pch 将成为预编译头
// stdafx.obj 将包含预编译类型信息
#include "stdafx.h"
// TODO: 在 STDAFX.H 中
//引用任何所需的附加头文件，而不是在此文件中引用
⑸ 谁会GUI设计我需要做一个快速傅里叶变换的演示程序 急！！！
程序如下，把“lpk..."改成你需要的文件夹的名字，或者把文件夹名字改了。function varargout = lpkfft(varargin)% LPKFFT M-file for lpkfft.fig% LPKFFT, by itself, creates a new LPKFFT or raises the existing% singleton*.%% H = LPKFFT returns the handle to a new LPKFFT or the handle to% the existing singleton*.%% LPKFFT('CALLBACK',hObject,eventData,handles,...) calls the local% function named CALLBACK in LPKFFT.M with the given input arguments.%% LPKFFT('Property','Value',...) creates a new LPKFFT or raises the% existing singleton*. Starting from the left, property value pairs are% applied to the GUI before lpkfft_OpeningFcn gets called. An% unrecognized property name or invalid value makes property application% stop. All inputs are passed to lpkfft_OpeningFcn via varargin.%% *See GUI Options on GUIDE's Tools menu. Choose "GUI allows only one% instance to run (singleton)".%% See also: GUIDE, GUIDATA, GUIHANDLES % Edit the above text to modify the response to help lpkfft % Last Modified by GUIDE v2.5 20-Dec-2010 22:21:43 % Begin initialization code - DO NOT EDITgui_Singleton = 1;gui_State = struct('gui_Name', mfilename, ... 'gui_Singleton', gui_Singleton, ... 'gui_OpeningFcn', @lpkfft_OpeningFcn, ... 'gui_OutputFcn', @lpkfft_OutputFcn, ... 'gui_LayoutFcn', [] , ... 'gui_Callback', []);if nargin && ischar(varargin{1}) gui_State.gui_Callback = str2func(varargin{1});end if nargout [varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:});else gui_mainfcn(gui_State, varargin{:});end% End initialization code - DO NOT EDIT % --- Executes just before lpkfft is made visible.function lpkfft_OpeningFcn(hObject, eventdata, handles, varargin)% This function has no output args, see OutputFcn.% hObject handle to figure% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA)% varargin command line arguments to lpkfft (see VARARGIN) % Choose default command line output for lpkffthandles.output = hObject; % Update handles structureguidata(hObject, handles); % UIWAIT makes lpkfft wait for user response (see UIRESUME)% uiwait(handles.figure1); % --- Outputs from this function are returned to the command line.function varargout = lpkfft_OutputFcn(hObject, eventdata, handles) % varargout cell array for returning output args (see VARARGOUT);% hObject handle to figure% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % Get default command line output from handles structurevarargout{1} = handles.output; % --- Executes on button press in chushi.function kaishi_Callback(hObject, eventdata, handles)% hObject handle to chushi (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA)N=64;n=0:127;x=cos(14*pi*n/N)+1/2*cos(38*pi*n/N); plot(handles.chushi,n,x,'-g');set(handles.chushi,'XGrid','on','YGrid','on');title(handles.chushi,'x(n)'); % --- Executes on button press in fd.function fd_Callback(hObject, eventdata, handles)% hObject handle to fd (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) N=64;n=0:127;x=cos(14*pi*n/N)+1/2*cos(38*pi*n/N);X=fft(x);X1=abs(X);plot(handles.fd1,n,X1,'-r');set(handles.fd1,'XGrid','on','YGrid','on');title(handles.fd1,'幅度'); % --- Executes on button press in xw.function xw_Callback(hObject, eventdata, handles)% hObject handle to xw (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA)N=64;n=0:127;x=cos(14*pi*n/N)+1/2*cos(38*pi*n/N);X=fft(x);X1=angle(X);stem(handles.xw1,n,X1,'*');set(handles.xw1,'XGrid','on','YGrid','on');title(handles.xw1,'相位'); % --- Executes on button press in clr.function clr_Callback(hObject, eventdata, handles)% hObject handle to clr (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA)try delete(allchild(handles.chushi)); delete(allchild(handles.fd1)); delete(allchild(handles.xw1));end % --- Executes on button press in chushi.function kaishi_Callback(hObject, eventdata, handles)% hObject handle to chushi (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA)
⑹ 怎样用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;
}
⑺ 一个关于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;
}