打印本文 打印本文  关闭窗口 关闭窗口  
C++基础(快速傅里叶变换（FFT）源代码)
作者：佚名  文章来源：不详  点击数  更新时间：2008/10/22 21:33:53  文章录入：杜斌  责任编辑：杜斌
　　为了看明白那堆积分变换，不得不把复变函数扫了一遍，可看完了，才发现原来这堆变换说白了只是一些数字游戏，Examda提示: 也没用到啥复变函数的知识。最后，用C++程序实现了下FFT，也算告一段落，代码如下：
　　#include <iostream>
　　#include <fstream>
　　#include <math.h>
　　using namespace std;
　　const double PI = 3.14159265358979323846;
　　int n; // 数据个数 = 2的logn次方
　　int logn;
　　/// 复数结构体
　　struct stCompNum
　　{
　　double re;
　　double im;
　　};
　　stCompNum* pData1 = NULL;
　　stCompNum* pData2 = NULL;
　　/// Examda提示: 正整数位逆序后输出
　　int reverseBits(int value, int bitCnt)
　　{
　　int i;
　　int ret = 0;
　　for(i=0; i<bitCnt; i++)
　　{
　　ret |= (value & 0x1) << (bitCnt - 1 - i);
　　value >>= 1;
　　}
　　return ret;
　　}
　　void main()
　　{
　　ifstream fin("data.txt");
　　int i,j,k;
　　// input logn
　　fin>>logn;
　　// calculate n
　　for(i=0, n=1; i<logn; i++) n *= 2;
　　// malloc memory space
　　pData1 = new stCompNum[n];
　　pData2 = new stCompNum[n];
　　// input raw data
　　for(i=0; i<n; i++) fin>>pData1[i].re;
　　for(i=0; i<n; i++) fin>>pData1[i].im;
　　// FFT transform
　　int cnt = 1;
　　for(k=0; k<logn; k++)
　　{
　　for(j=0; j<cnt; j++)
　　{
　　int len = n / cnt;
　　double c = - 2 * PI / len;
　　for(i=0; i<len/2; i++)
　　{
　　int idx = len * j + i;
　　pData2[idx].re = pData1[idx].re + pData1[idx + len/2].re;
　　pData2[idx].im = pData1[idx].im + pData1[idx + len/2].im;
　　}
　　for(i=len/2; i<len; i++)
　　{
　　double wcos = cos(c * (i - len/2));
　　double wsin = sin(c * (i - len/2));
　　int idx = len * j + i;
　　stCompNum tmp;
　　tmp.re = pData1[idx - len/2].re - pData1[idx].re;
　　tmp.im = pData1[idx - len/2].im - pData1[idx].im;
　　pData2[idx].re = tmp.re * wcos - tmp.im * wsin;
　　pData2[idx].im = tmp.re * wsin + tmp.im * wcos;
　　}
　　}
　　cnt <<= 1;
　　stCompNum* pTmp = NULL;
　　pTmp = pData1;
　　pData1 = pData2;
　　pData2 = pTmp;
　　}
　　// resort
　　for(i=0; i<n; i++)
　　{
　　int rev = reverseBits(i, logn);
　　stCompNum tmp;
　　if(rev > i)
　　{
　　tmp = pData1[i];
　　pData1[i] = pData1[rev];
　　pData1[rev] = tmp;
　　}
　　}
　　// output result data
　　for(i=0; i<n; i++) cout<<pData1[i].re<<"\t";
　　cout<<endl;
　　for(i=0; i<n; i++) cout<<pData1[i].im<<"\t";
　　cout<<endl;
　　// free memory space
　　delete []pData1;
　　delete []pData2;
　　fin.close();
　　system("pause");
　　}
　　输入文件data.txt的内容如下：
　　4
　　2.2 4.5 6.7 8.5 10.2 12.3 14.5 16.2 19.3 21.2 25.2 29.4 36.4 39.2 45.2 50.1
　　0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 来源：考试大
打印本文 打印本文  关闭窗口 关闭窗口