傅立叶改换的重要性不必我说，想必咱们也很清楚，有了傅立叶改换，咱们就能够从信号的频域特征去剖析信号。尤其在无线通信体系中，傅里叶改换的重要性就愈加显着了，无论是设计者仍是测验工程师，在作业中都会和傅立叶改换打交道。在以下的文章中，我给出一种傅里叶改换的C言语完结办法（参阅了C常用算法集），能够用于在嵌入式体系中完结傅立叶改换。
惯例的傅立叶改换算法并不适用于嵌入式控制体系，原因是运算量太大（涉及到复数运算），比方离散的傅立叶改换等同于用序列Y(n×1列矢量)乘以n×n 矩阵Fn，需求n×n次乘法。若n=1024,则是104，8576次乘法运算。哇，这么多呀！什么概念呢？假如你选用的CPU单周期指令为25ns, 单周期也能够完结一次乘法运算，那么要核算1024点的傅立叶改换则需求26.2144ms,这还不包括加法或其它运算，关于大多数实时体系，这个处理时刻真实太长。所以寻觅一个快速的傅立叶改换算法是人们所希望的。
原本我想把FFT的整个数学推导进程列完出来，但当自己硬着头皮看完后，发现对我没有任何用途，我又不是专门研究数学算法的，哪有那么多时刻跟着书本的公式去渐渐推导。我想，这些推导问题仍是让数学家想去吧。我需求的不过是了解它，然后学会运用它就行。有爱好的读者能够参阅相关的材料，这方面的材料真实太多了。
尽管FFT大幅度地降低了惯例傅立叶改换的运算量，但关于一般的单片机而言，处理FFT运算仍是无能为力。首要原因是FFT核算进程中的蝶形运算是复数运算，要分隔实部和虚部别离核算，想想这是多么繁琐的作业。可能会有些初学者以为，有这么杂乱吗？我在PC上运用C++相同能够对复数直接进行加、减、乘、除运算。你说得不错，能够这么做，但那是C++封装了对复数处理的类，直接调用就行。在PC上运算这种类型的算法一般不考虑时刻和空间，多一两秒的运转时刻不会有什么灾难性的成果。
所以咱们要衡量一个处理器有没有满意的才干来运转FFT算法，依据以上的简略介绍能够得出以下两点：
处理器要在一个指令周期能完结乘和累加的作业，由于复数运算要屡次查表相乘才干完结。
直接寻址，能够完结增/减1个变址量，便利各种查表办法。FFT要对原始序列进行反序摆放，处理器要有反序直接寻址的才干。
所以，在数字信号的剖析处理运用中，DSP比其它的处理器有肯定的优势，由于DSP彻底具有以上条件。这便是单片机（51系列，AVR，PIC等等）或ARM处理器很少用来进行数字信号剖析的原因。
要点来了，下面的这段程序便是用C言语完结傅里叶改换
//**********************************************************
// 函数名: 快速傅立叶改换（来历《C常用算法集》）
// 本函数测验OK,能够在TC2.0,VC++6.0,Keil C51测验通过。
// 假如你的MCS51体系有满意的RAM时,能够验证一下用单片机处理FFT有多么的慢。
//
// 进口参数：
// l: l = 0, 傅立叶改换; l = 1, 逆傅立叶改换
// il: il = 0,不核算傅立叶改换或逆改换模和幅角；il = 1,核算模和幅角
// n: 输入的点数，为偶数，一般为32，64，128，…,1024等
// k: 满意n=2^k(k>0),实质上k是n个采样数据能够分解为偶次幂和奇次幂的次数
// pr[]: l=0时，寄存N点采样数据的实部
// l=1时, 寄存傅立叶改换的N个实部
// pi[]: l=0时，寄存N点采样数据的虚部
// l=1时, 寄存傅立叶改换的N个虚部
//
// 出口参数：
// fr[]: l=0, 回来傅立叶改换的实部
// l=1, 回来逆傅立叶改换的实部
// fi[]: l=0, 回来傅立叶改换的虚部
// l=1, 回来逆傅立叶改换的虚部
// pr[]: il = 1,i = 0 时，回来傅立叶改换的模
// il = 1,i = 1 时，回来逆傅立叶改换的模
// pi[]: il = 1,i = 0 时，回来傅立叶改换的辐角
// il = 1,i = 1 时，回来逆傅立叶改换的辐角
// data: 2005.8.15,Mend Xin Dong
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;
}
