c语言编写fft程序

《c语言编写fft程序》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、DSP课程作业用C语言编写FFT程序1，快速傅里叶变换FFT简介快速傅氏变换(FFT),是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论丼没有新的发现，但是对于迕计算机系统或者说数字系统中应用离散傅立叶变换，对以说是进了一大步。我们假设x(n)为N项的复数序列，由DFT变换，任一X(m)的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于叫次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次fi数加法定义成一次“运算”(四次实数乘法和四次实数

2、加法)，那么求HiN项S数序列的X(m)，即N点DH变换大约就需要N"2次运算。当N=1024点甚至更多的时候，需要N2=1048576次运算，在FFT中，利川WN的周期性和对称性，把一个N项序列(设N=2k,k为正整数)，分为W个N/2项的子序列，每个N/2点DH变换需要(N/2)2次运算，再用N次运算把两个N/2点的DFT变换组合成一个N点的变换。这样变换以总的运算次数就变成N+2(N/2)2=N+N2/2。继续上而的例子，N=1024时，总的运算次数就变成了525312次，节宵了人约50%的运算堂。而如果我们将这种“一分为二”的思想不断进行下去，直到

3、分成两两一组的DH运算单元，那么^(的DFT变换就只需耍Nlog2N次的运算，N在1024点吋，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算景的节约就越人，这就是FFT的优越性。2,FFT算法的基本原理FFT算法的基本思想：利川DFT系数的特性，合并DET运算屮的某些项，吧长序列的DFT—〉短序列的DFT，从而减少其运兑量。PFT算法分类：时间抽选法DTT:Decimation-Tn-Time:频率抽选法DTE:Decimation-In-Frequency按时间抽选的基-2FH算法1、算法原理设序列点数N=2L，L为整数。若不满足，则补

4、零。N为2的整数幂的FFT算法称基-2FFT算法。将序列x(n)按n的奇偶分成W组:r=0’l，…，普-1(2r)=^(r)(2r+l)=x2(r则x(n)的DFT:N_iAMx⑷=+2>(W?/=()n=0zj=()=f^(2r)W，+^(2r+l)<’/q0r=04_,r=0r=0夸一1夸一1=$>(0<2+吣乞r=0r=0=^(幻+1%；12(/：)(以=(u”•.令—D其中&⑻=⑺W=5>(2r)Wr=()*r=()A•一

5、!-iX,(k)=^xSr)W^=j42r)<什=0，1，…芷-1)r=0r=02X,=XAk)x/)t+—<2,A2；再利用

6、周期性求X（k）的后半部分:•••芩（w2（幻是以I为周期的久⑷又w,:+*NN«=-cX(k)=XSk)+W^X2(k)%(人+争二X

7、(KX2(幻Xi⑻*~~X側湖•，’Ai（女>析伴令X2*Vi<3)«rC6)，3fz<0>-v(1)，,vt(1)=v(3)，似2>赚v(F>•'■(Q>■，Ai(2)1■尋足，p>，tV2(V>mWA«hAX1)V<2)Ml)M4)况5)V

8、A>2点i>FT側后的运算量:城總复—"W2点DFTj^/2(y/2-i)两个及/2点DFTAP/2-^蝶形I2及/2个蝶麻ff/2If总计的2+#/2^N2/2«2^/2运算量齡了近一半！2）、运算量当N=2L时，共有L级蝶形，毎级N/2个蝶形，坤NN复数乘注：mF=yL=ylog2A^比较DFTmF(DFT)mF(FFT)2NN_Tlog2/V10^aF=NL=Nog2N3)、算法特点原位计算蝶形运算两节点的第一个节点为k值，表示成L位二进制数，左移L-m位，把右边空出的位置补零，结果为r的二进制数。{xM=xt^)+xfaj)K♦V图4-7按时闻抽

9、逸蝶形运算结构倒位序x(n)打=(^2/^)2倒位序自然序«0«1000000000001100410011001022010111063011100001141001101551011001136110111177111蝶形运筧对=2L点FFT,输入倒位序，输出自然序，第m级运算毎个蝶形的两节点距离为2m-1(k4-2-1)=(^)-X,^{k+2-1)尋)-义鄰〜卿％咖)一4-7按时问抽选蝶形运算结构c的确定蝶形运算两节点的第一个节点为k位，表示成L位二进制数，左移L-m位，把右边空出的位置补零，结果为r的二进制数。存储单元输入序列x(n):N个存储

10、单元系数:N/2个存储单元3,快速傅立叶变换的C语言实现方法我们要