用c语言实现的FFT

1、、对FFT的介绍1. FFT(FastFourierTransformation快速算法，它是根据离散傅里叶变换的奇、偶、虚、实等特性，对离散傅里叶变换的算法进行改进获得的。2. FFT算法的基本原理FFT算法是把长序列的DFT逐次分解为较短序列的DFT。按照抽取方式的不同可分为DIT-FFT(按时间抽取)和DIF-FFT(按频率抽取)算法。按蝶形运算的构成不同可分为基2,基4,基8,以及任意因子的类型。),即为快速傅里叶变换，是离散傅里叶变换的3.迭代关系V-1FK=j=0Ni1-1二le2黄氐（工QiN八0.V2-1Q此（2J）/-V二2j=Q二F/+WKFJfij+f2J十N72-1R氏

2、（2/+J=0N2-1WKY鞋2“概=04、本次程序的基本过程我们这次所研究的是数字信号处理中的FFT算法，我们这次所用的数字信号是复数类型的(1)所以首先，我们先定义了一个复数结构体，因为是进行复数的运算,我们又相继定义复数的加减乘运算的函数。(2) 紧接着，我们定义了进行FFT计算的fft()快速傅里叶变换函数initW()初始化变换核函数即旋转因子的计算，change()变址函数，output()输出傅里叶变换的结果的函数。(3) 定义主函数，并调用定义好的相关子函数，利用fft()中的蝶形运算以及change()函数来完成从时间域上选取的DIT-FFT。二、FFT中码位倒置排序1、 码

3、位倒置的实现方法：(1) 简单的利用按位与、或循环实现(2) 利用公式推导的迭代方法2、 为什么要进行码位倒置因为由于FFT的计算特性，如果按照正常顺序输入，而没有进行码位倒置的话，就会以乱序输出，就不便于我们后续对信号的相关性质进行1研究了，所以DIT-FFT算法就是在进行FFT计算之前，进行分奇偶后的码位倒置运算，即二进制数的倒位3、倒位序由奇偶分组造成，以N=8为例，说明如下:-0-八或000)0Prd二门*n0=0(偶)一x(100)4pJ口一x010)2Pnl二1_4卜X(nNgnO)d，Ii如1也L1ZIc1nl.哈1.，jr0>x(001)1a口1二0.门0三11>1

4、o1，(奇)o11三、蝶形运算X(k)?(上层示x(k曲运M是一种特殊运王x(八)=尢1(£)W：心(*)前一半(k=rx(1)=X!(i)-wyx2诟一半(k=7按照上述公式的规律进行逐级分解，直到2点DFT,如下是N=8时的(1)我们知道N点FFT运算可以分成Iog2(N)级，每一级都有N/2个碟形，FFT的基本思想是用3层循环完成全部运算(N点FFD(2)第一层循环：由于N=2m需要m级计算，第一层循环对运算的级数进行控制。(stages)(3) 第二层循环：由于第L级有2YL-1)个蝶形因子(乘数)，第二层循环根据乘数进行控制，保证对于每一个蝶形因子第三层循环要执行一次，这样

5、，第三层循环在第二层循环控制下，每一级要进行2A(L-1)次循环计算.(选择W)(4) 第三层循环：由于第L级共有N/2AL即2A(n-L)个群，并且同一级内不同群的乘数分布相同，当第二层循环确定某一乘数后，第三层循环要将本级中每个群中具有这一乘数的蝶形计算一次，即第三层循环每执行完一次要进行N/2AL个碟形计算。(执行不同group中具有相同W勺蝶形运算)(5)可以得出结论：在每一级中，第三层循环完成N/2U个碟形计算;第二层循环使第三层循环进行2YL-1)次，因此，第二层循环完成时，共进行2A(L-1)*N/2AL=N/2个碟形计算。实质是：第二、第三层循环完成了第L级的计算。五、用c语言

6、实现的FFT算法如下：<spanstyle="font-size:18px;">#include<stdio.h>#include<math.h>#include<stdlib.h>#defineN1000/*定义复数类型*/typedefstructdoublereal;doubleimg;complex;complexxN,*W;/*输入序列，变换核*/intsize_x=0;/*doublePI;/*voidfft();/*voidinitW();/*voidchange();/*输入序列的大小，在本程序中仅限圆周率*/快速傅里叶变换*/初始化变换核*/变址*/2的次幕*/voidadd(complexcomplexcomplex*);/*复数加法*/voidmul(complex,complex,complex*);/*复数乘法*/voidsub(complex,complexcomplex*);/*复数减法*/voidoutput();/*输出快速傅里叶变