基-2FFT算法的软件实现

实验二 基-2FFT算法的软件实现

一、实验目的

1、 加深对DFT算法原理和基本性质的理解； 2、 熟悉FFT算法的流程； 3、 了解FFT算法的应用。

—

二、基本原理

1、 DFT算法原理 （见教材第三章）

2、 按时间抽取（DIT）的-2FFT算法

（1）算法原理

~

序列x(n)的N(N=2-M)点DFT为

X(k)DFT[x(n)]N点将式（）按n的奇偶性分解为

x(n)Wn0N1knN，k=0,

1, …, N-1 （）

X(k)n偶数x(n)WN/21n偶数knNk2lNn奇数x(n)WN/21knN （）

k(2l1)Nx(2l)Wn奇数x(2l1)Wk2l令x1(l)x(2l), x2(l)x(2l1)，因为WNklWN/2, 所以式（）可写成

$

N/21X(k)x(l)W1l0klN/2WkNM21n奇数x(l)W2k(2l1)N/2 （）

式（）说明，按n的奇偶性将x(n)分解为两个N/2长的序列x1(l)和x2(l)，则N点DFT可分解为两个N/2点DFT来计算。用X1(k)和X2(k)分别表示

N/21X1(k)DFT[x1(l)]N/2点

x1(l)WNkl/2 k0,1,...,l0N1 （） 2

N/21X2(k)DFT[x2(l)]N/2点将式和式代入式，并利用WN

kX(k)X1(k)WNX2(k)kN2x(l)W2l0klN/2 k0,1,...,N1 （） 2kWN和X1(k)、 X2(k)的隐含周期性可得到：

Nk0,1,...1 （） Nk2X(k)X1(k)WNX2(k)2这样，将N点DFT的计算分解为计算两个N/2点离散傅立叶变换X1(k)和X2(k)，再计算式。为了将如上分解过程用运算流图表示，以便估计其运算量，观察运算规律，总结编程方法，先介绍一种表示式的蝶形图。

图蝶形运算图

）

图 8点DFT一次时域抽取分解运算流图

根据图可以求得第一次分解后的运算量。图包括两个N/2点DFT和N/2个蝶形，每个N/2点DFT需要(N/2)次复数乘法和(N/21)N/2次复数加法运算，每个蝶形只有一次复数乘法运算和两次复数加法运算。所以，总的复数乘法次数为

2

总的复数加法次数为

）

N2NNN2()2(N1)|N1 （） 2222NNNN2(1)22 （） 2222N=8点DIT-FFT的运算流图如图(a)所示。根据WkN/m所示的标准形式的运算流图

=WkmN，将图(a)转换成如图(b)

图 N=8点DIT-FFT的运算流图

]

（2）算法效率

由图可见，N=2M时，DIT-FFT运算流图由M级蝶形构成，每级有N/2个蝶形。因

此，每级需要N/2次复数乘法运算和N次复数加法运算，M级形共需复数乘法次数CM(2)和复数加法次数CA(2)分别为

CM(2)NNMlbN （） 22CA(2) =N·M=N lb N （）

式中，lb N=log2 N。直接计算N点DFT的复数乘法次数为N2,复数加法次数为(N-1)N。当N1时, N2/CM(2)>>1，所以N越大，DIT-FFT运算效率越高。DIT-FFT算法与DFT所需乘法次数与N的关系曲线如图所示。例如，N=210=1024时，DIT-FFT的运算效率为

DFT的乘法次数N210242204.8 （）

1024DITFFT的乘法次数CM(2)102%

而当N=211=2048时，

N2N22N22048372.37 （）

CM(2)NMM112

图 DIT-FFT与DFT所需乘法次数比较曲线

（3）运算规律

.

rWN的确定

第m级运算，一个DIT蝶型运算的的两接点“距离”为2m1，所以

rXm(k)Xm1(k)Xm1(k2m1)WNXm(k2>

m1)Xm1(k)Xm1(k2m1)WrN （）

Lr的求解：（1）将式（）中第一个节点的标号k表示成L（N2）位二进制数；（2）把此二进制数乘上2Lm，即将L位二进制数左移Lm位（注意m是第m级运算），把右边空出的位置补0，此数即为所求r的二进制数。

序列的倒序

DIT-FFT算法的输入序列的排序看起来似乎很乱，但仔细分析就会发现这种倒序是很有规律的。由于N2，因此顺序数可用L位二进制数(nL1nL2n1n0)表示。M次偶奇时域抽选过程如图所示。

第一次按最低位n0的0和1将x(n)分解为偶奇两组，第二次又按次低位n1的0、 1值

L分别对偶奇组分解； 依次类推，第L次按nL1位分解，最后所得二进制倒序数如图所示。

】

图 形成例序的树状图(N=23)

形成倒序J后，将原存储器中存放的输入序列重新按倒序排列。设原输入序列x(n)先按

x(1), …,

自然顺序存入数组A中。例如，对N=8, A(0)，A(1)，A(2)，…，A(7)中依次存放着x(0),x(7)。对x(n)的重新排序(倒序)规律如图所示。

图倒序规律

》

三、实验仪器

计算机

四、实验要求及内容

用所学过的编程语言，自行设计出一个按时间抽取的、输入倒位序、输出顺序的基-2 FFT算法程序。

/

五、实验报告

（1）简述实验目的及原理； （2）画出程序流程框图；

（3）主要给出实验内容的程序（要求程序模块化并加注释）。

(

~

程序流程框图

\"

实验的程序 #include<> #include<> #include<> (

#define PI class Plural. } return m; }

(

/*************对二进制数倒序加一*****************/ void add(int xu[],int i) { xu[0]++; for(int j=0;j/*************倒序**********************************/ void daoxu(Plural x[],int n) { float m=float (n); int i=0;

for(i=0;m>1;i++)how(); if((i+1)%4==0) cout<}

if(xu[j]==2){ xu[j]=0;

xu[j+1]++;.... }

通过本次实验：

1、加深了对DFT算法原理和基本性质的理解； 2、熟悉了FFT算法的流程；

3、了解FFT算法的应用。