1快速傅里叶变换

1、快速傅里叶变换（ FFT）的算法思想和源代码信息科学学院 计算机应用技术 102009328 马梦琦 思想：快速傅氏变换 （Fast Fourier Transform ,FFT ，是离散傅氏变换的快速算 法，也可用于计算离散傅里叶变换的逆变换。快速傅里叶变换有广泛的应用，如 数字信号处理、计计算大整数乘法、求解偏微分方程等等它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进 获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中 应用离散傅立叶变换，可以说是进了一大步。把一个序列分为长度减半的偶序列和奇序列，原序列的 DFT 就有着两个 N/2

2、 列求得。进一 步把 N/2 序列分解成两个 N/4 序列，一直分解为单点序列。以 L=3,L=8 为例，需要三级分 解，源代码如下：#using std;const double PI = 3.14159265358979323846;n; / 数据个数 = 2logn 次方logn;/ 复数结构体struct stCompNumdouble re;double im;stCompNum* pData1 = NULL;stCompNum* pData2 = NULL;/ 正整数位逆序后输出 reverseBits( value, bitCnt i;ret = 0;for(i=0; iret

3、|= (value & 0x1 = 1;ret;voidstream fin(data.txt;i,j,k;/ input logn finlogn;/ calculate nfor(i=0, n=1; i/ malloc memory space pData1 = stCompNumn;pData2 = stCompNumn;/ input raw datafor(i=0; i pData1i.re;for(i=0; i pData1i.im;/ FFT transformcnt = 1;for(k=0; kfor(j=0; jlen = n / cnt;double c = - 2 * P

4、I / len;for(i=0; iidx = len * j + i;pData2idx.re = pData1idx.re + pData1idx + len/2.re; pData2idx.im = pData1idx.im + pData1idx + len/2.im; for(i=len/2; idouble wcos = cos(c * (i - len/2;double wsin = sin(c * (i - len/2;idx = len * j + i;stCompNum tmp;tmp.re = pData1idx - len/2.re - pData1idx.re;tmp

5、.im = pData1idx - len/2.im - pData1idx.im;pData2idx.re = tmp.re * wcos - tmp.im * wsin;pData2idx.im = tmp.re * wsin + tmp.im * wcos;cnt itmp = pData1i;pData1i = pData1rev; pData1rev = tmp;/ output result datafor(i=0; icoutfor(i=0; icout/ free memory spacedelete pData1;delete pData2; fin.close;system(pause;输入文件 data.txt 内容如下 :4 2.2 4.5 6.7 8.5 10.2 12.3