数字信号处理基于MATLAB的FFT算法设计课设说明书(2)

课程设计说明书

图3-2 DIT-FFT蝶形运算流图符号

以此类推，还可以把x1(n)和x2(n)按n值得奇偶分为两个序列，这样就达到了降N得目的，从而减少了运算量。FFT对DFT的数学运算量改进：

直接采用DFT进行计算，运算量为N2次复数乘法和N*(N-1)次复数乘法。 当采用M次FFT时，由N=2M求得M=logN，运算流图有M级蝶形，每一级都由N/2个蝶形运算构成，这样每一级蝶形运算都需要N/2次复数乘法和N次复数加法。M级运算共需要复数乘法次数为C=N/2*M，复数加法次数为C=N*M。

当N值较大时，FFT减少运算量的特点表现的越明显。

3.3 DIT-FFT算法的运算规律及编程思想

为了编写DIT-FFT算法的运算程序，首先要分析其运算规律，总结编程思想并绘出程序框图。

1.原位计算

对N?2点的FFT共进行M级运算，每级由N/2个蝶形运算组成。在同一级中，每个蝶的输入数据只对本蝶有用，且输出节点与输入节点在同一水平线上，这就意味着每算完一个蝶后，所得数据可立即存入原输入数据所占用的数组元素（存储单元）中，这种原位（址）计算的方法可节省大量内存。

2.蝶形运算

实现FFT运算的核心是蝶形运算，找出蝶形运算的规律是编程的基础。蝶形运算是分级进行的，每级的蝶形运算可以按旋转因子的指数大小排序进行，如果指数大小一样则可从上往下依次蝶算。对N?2点的FFT共有M级运算，用L表示从左到右的运算级数(L=1，2，…，M )。第L级共有B?2L?1个不同指数的旋转因子，用R表示这些不同指数旋转因子从上到下的顺序(R=0，1，…，B-1)。第R个旋转因子的指数P?2M?LR，旋转因子指数为P的第一个蝶的第一节点标号k从R开始，由于本级中旋转因子指数相同的蝶共有2M?L个，且这些蝶的相邻间距为2L，故旋转因子指数为P的最后一个蝶的第一节点标号k为：

(2M?L?1)?2L?R?N?2L?R，本级中各蝶的第二个节点与第一个节点都相距

MMB点。

应用原位计算，蝶形运算可表示成如下形式：

PAL(J)= AL-1(J)+ AL-1(J+B)*WN

AL (J+B)= AL-1(J)-AL-1(J+B)*WN

P总结上述运算规律，可采用如下运算方法进行DIT-FFT运算。首先读入数

5

课程设计说明书

据，根据数据长度确定运算级数M，运算总点数N?2，不足补0处理。然后对读入数据进行数据倒序操作。数据倒序后从第1级开始逐级进行，共进行M级运算。在进行第L级运算时，先算出该级不同旋转因子的个数B?2L?1（也是该级中各个蝶形运算两输入数据的间距），再从R=0开始按序计算，直到R=B-1结束。每个R对应的旋转因子指数P?2M?LR，旋转因子指数相同的蝶从上往下依次逐个运算，各个蝶的第一节点标号k都是从R开始，以2L为步长，到N?2LM?R（可简

取极值N-2）结束。考虑到蝶形运算有两个输出，且都要用到本级的两个输入数据，故第一个输出计算完毕后，输出数据不能立即存入输入地址，要等到第二个输出计算调用输入数据完毕后才能覆盖。这样数据倒序后的运算可用三重循环程序实现。整个蝶形运算流程图如图3-3所示。

开始 送入x(n),M N=2^M 倒序 L=1:M B=2^(L-1) J=0:B-1 P=J*2^(M-L) K=J:2^L:N T=A(K)+A(K+B)*WN^P A(K+B)=A(K)-A(K+B)*WN^P A(K)=T 输出 结束图3-3整个蝶形运算流程图

3.序列倒序

为了保证运算输出的X(k)按顺序排列，要求序列x(n)倒序输入，即在运算前

6

课程设计说明书

要先对输入的序列进行位序颠倒。如果总点数为N?2的x(n)的顺序数是用M位二进制数表示，则倒序数只需将顺序数的二进制位倒置即可，按照这一规律用硬件电路和汇编语言很容易产生倒序数。但用MATLAB等高级语言实现倒序时，直接倒置二进制数位的方法不可取，还须找出产生倒序的十进制规律。将十进制顺序数用I表示，与之对应的二进制数用IB表示。十进制倒序数用J表示，与之对应的二进制数用JB表示。JB是IB的位倒置结果，十进制顺序数I增加1，相当于IB最低位加1且逢2向高位进1，即相当于JB最高位加1且逢2向低位进1。JB的变化规律反映到J的变化分二种情况：如果JB的最高位是0(J?N/2)，则直接由加1(J?J?N/2)得到下一个倒序值；如果JB的最高位是1(J?N/2)，则要先将最高位变0(J?J?N/2)，再在次高位加1(J?J?N/4)。但次高位加1时，同样要判断0、1值，如果是0 (J?N/4)，则直接加1(J?J?N/4)，否则要先将次高位变0(J?J?N/4)，再判断下一位。依此类推，直到完成最高位加1，逢2向右进位的运算。利用这一算法可按顺序数I的递增顺序，依次求得与之对应的倒序数J。为了节省内存，数据倒序可原址进行，当I = J时不需要交换，当I ≠ J时需要交换数据。另外，为了避免再次调换前面已经调换过的一对数据，只对I

7

M课程设计说明书

4 MATLAB实现程序

在MATLAB环境下编写程序，即不调用系统现有函数的FFT算法、IFFT算法和调用系统现有函数的FFT算法、IFFT算法，实现对选定图片的FFT计算、IFFT计算（还原）。

实现步骤如下：

首先打开MATLAB软件，出现如图4-1所示界面。

图4-1 MATLAB主界面

其次，左击File按钮，选中New，点击M-File，出现如图4-2所示界面，写入编写好的程序，保存。

图4-2 M-File界面

最后，点击Run图标，运行，选择要分析的图片后，出现如图4-3所示界面。这就是对选定图片进行FFT计算、IFFT计算后的结果。对出现的两组图做对比，

8

课程设计说明书

进行分析。

图4-3运行程序后的结果

9

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数字信号处理基于MATLAB的FFT算法设计课设说明书(2)在线全文阅读。