傅里叶变换简言之,就是把一个输入信号分解成一堆正弦波的叠加,可

https://m.toutiao.com/is/iJswRFKE/ 

傅里叶变换;简言之,就是把一个输入信号分解成一堆正弦波的叠加,可以从一个复杂的频谱中把最重要的成分表达出来，得到和原始频率非常接近的波形。其时域/频域两种变换分析是最基本的方法之一,在数字处理领域有广泛的应用，也是许多数字信号处理方法的基础。
傅里叶变换是一个很有实用价值的运算，比如在电网系统中因存在大量开关以及电容等，运行中会产生危害极大谐波，它是电力运行故障的罪魁祸首。
工程师在做嵌入式单片机的电力保护器时，单片机采集一定数量的点，然后通过FFT变换，来分析出谐波内部所含的谐波及幅值，然后有针对性的通过外加设备进行滤波净化，使电网更加安全的运行。
傅里叶变换还体现在对音频的处理，等等。
本人尝试通过相对简便C语言的FFT变换表达出来，希望能便于理解。
FFT:是快速傅里叶变换是DFT:是离散傅里叶变换的高效算法。可分为按时间抽取算法和按频率抽取算法。本人采取的是频率抽取算法。
//FFT
//复数结构体
typedef struct
{
float re;
float im;
}complex;
 
//定义旋转因子
Complex W(int N,int n)
{
complex out;
out.re=(float)cos(2*PI*((float)n/(float)N));
out.im=-(float)sin(2*PI*((float)n/(float)N));
return out;
}
//复数加法，out=a+b
complex add(complex a,complex b)
{
complex out;
out.re=a.re+b.re;
out.im=a.im+b.im;
return out;
}
//复数减法，out=a-b
complex sub(complex a,complex b)
{
complex out;
out.re=a.re-b.re;
out.im=a.im-b.im;
return out;
}
//复数乘法，out=a*b
complex mul(complex a,complex b)
{
complex out;
out.re=a.re*b.re-a.im*b.im;
out.im=a.re*b.im+a.im*b.re;
return out;
}
//复数赋值
complex comcpy(complex a)
{
complex out;
out.re=a.re;
out.im=a.im;
return out;
}
//变换运算
bool DOFFT(complex *x,complex *F,int N)
{
int K=(int)(log(N+1)/log(2));
int i,j,m;
for(m=1;m<=K;m++)
{
for(i=0;i<(1<<K);i+=1<<m)
{
for(j=0;j<(1<<(m-1));j++)
    {
    F[i+j]=add(x[i+j],mul(x[i+j+(1<<(m-1))],W(1<<m,j)));
F[i+j+(1<<(m-1))]=sub(x[i+j],mul(x[i+j+(1<<(m-1))],W(1<<m,j)));
    }
   }
for(i=0;i<N;i++)
x[i]=comcpy(F[i]);
  }
   return true;
}
//变换后数组反序
int reverse(int n,int j)
{
int  i,k,power;
power=(int)(log(n+1)/log(2));
k=0;
for(i=0;i<power;i++)
if(j&(1<<i)) k+=1<<(power-i-1);
return k;
}
//对变换后的数组做运算
void FFT(void)
{
WORD i;
complex *x,*f;
 
x = X;
f = F;
for(i=0;i<64;i++) //设定采集频率的64
{
x[i].re=ADSumple[i];
x[i].im=0;
}
 
for(i=0;i<64;i++)
{
f[i]=comcpy(x[reverse(64,i)]);
}
for(i=0;i<64;i++)
{
x[i]=comcpy(f[i]);
}
DOFFT(x,f,64);
}
//变换后，可以把频谱分离出来，可以清晰看出构成此谐波中不同频率正弦波的分布。