傅立叶变换/逆变换 C

用法：
// 函数名: 快速傅立叶变换（来源《C常用算法集》）
// 本函数测试OK可以在TC2.0VC++6.0Keil 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 = 1i = 0 时，返回傅立叶变换的模
// il = 1i = 1 时，返回逆傅立叶变换的模
// pi[]: il = 1i = 0 时，返回傅立叶变换的辐角
// il = 1i = 1 时，返回逆傅立叶变换的辐角
// data: 2005.8.15Mend Xin Dong

程序代码：
#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=0il=0;
     int ijn=Nk=3;
     for（i=0;i     {
         xr[i]=i;
         xi[i]=0;
     }
     printf（“------FFT------\n“）;
     l=0;
     kkfft（xrxinkYrYilil）;
     for（i=0;i     {
         printf（“%-11lf + j* %-11lf\n“Yr[i]Yi[i]）;
     }

     printf（“-----DFFT-------\n“）;
     l=1;
     kkfft（YrYinkxrxilil）;
     for（i=0;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 itmisijnvl0;
     double pqsvrvipoddrpoddi;
     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]