333李立广FFT课程设计报告(2)

nk③WN的可约束性

WNnkmnk?WmN, （6）

nknk/mW?W NN/m （7）

由此可得出

n(N?k)(N?n)k?nkN/2(k?N/2)kWN?WN?WN,WN??1,WN??WN

nk利用这些特性,使DFT运算中有些项可以合并;利用WN的对称性、周期性和可约束性，

可以将长序列的DFT分解为短序列的DFT。

由DFT 的定义可以看出，在x[n]为复数序列的情况下，完全直接运算N点DFT需要

(N?1)2次复数乘法和N?(N?1)次加法。因此，对于一些相当大的N值（如1024）来说，直接计算它的DFT所作的计算量是很大的。FFT的基本思想在于，将原有的N点序列分成两个较短的序列，这些序列的DFT可以很简单的组合起来得到原序列的DFT。例如，若N 为偶数，将原有的N 点序列分成两个（N/2）点序列，那么计算N 点DFT 将只需要约[(N.2)2?2]?N2/2次复数乘法。即比直接计算少做一半乘法。因子(N.2)2表示直接计算（N/2点DFT所需要的乘法次数，而乘数2代表必须完成两个DFT。上述处理方法可以反复使用，即（N/2）点的DFT计算也可以化成两个（N/4）点的DFT（假定N/2为偶数），从而又少做一半的乘法。这样一级的划分下去一直到最后就划分成两点的FFT运算的情况。比如，一个N=8点的按时间抽取法FFT运算按照这种方法来计算FFT变换，可以用图1所示的运算流图表示。

图1 N=8按时间抽选法FFT运算流图

6

三、 详细设计步骤

1、输入数据

先输入要进行FFT运算的数据点数，再输入数据。因为可能输入错误的数据或者是一些无效的数，必须得重新输入。比如，输入的数据点数就不能小于等于0，那就得重新输入一个正的整数；还有在用户自己确定进行FFT变换的点数N时，N就要等于2的整数幂，否则得重新输入。用户可以自己选择是否自动产生进行FFT变换的点数，也可以由用户来自己定。具体的输入数据程序片段如下：

disp('请输入所有要输入数据的点数(要大于0)：'); N=input(' N= '); while N<=0;

disp('对不起！您输入的点数不能小于等于0,请重新输入一个有效的数！！！'); N=input(' N= '); end;

for i=1:N; %输入数据 T(i)=input('T= '); end;

disp('是否自动产生一个执行FFT变换的点数？(y/n):'); str=input('y/n: ','s'); while (str~='y')&&(str~='n')

disp('您输入的字符无效，请重新输入一个有效的字符(y/n)！！！'); disp('是否自动产生一个执行FFT变换的点数？(y/n):'); str=input('y/n: ','s'); end; n=size(T); if str=='y' if n(2)==1; N1=2; L=1; else

for l=0:32, %算出N和L if 2^l>=n(2),

7

N1=2^l; L=l; break; end; end; end;

disp('自动产生的执行FFT变换的点数为:'); N=N1 elseif str=='n'

N1=input('请输入您所想要执行FFT变换的点数： N1= '); n=size(T); while n(2)>N1

disp('您输入的FFT变换的点数已小于输入数据的点数，请重新输入！！！'); N1=input('请输入您所想要执行FFT变换的点数(要大于等于输入数据的点数)： N1= '); end; w=1; n1=0; while n1

if n1>N1 %n1是为了判断输入的FFT变换点数是否等于2的整数幂 disp('您输入的FFT变换的点数不等于2的整数幂，请重新输入一个有效的数！！！');

N1=input('请输入您所想要执行FFT变换的点数(要等于2的整数幂)：

N1= ');

w=1; n1=0; end;

while n(2)>N1%n(2)是为了判断输入的FFT变换点数是否小于输入数据的点数 disp('您输入的FFT变换的点数已小于输入数据的点数，请重新输入！！！');

8

N1=input('请输入您所想要执行FFT变换的点数(要大于等于输入数据的点数)： N1= '); w=1; n1=0; end; end;

for l=0:32, %计算出L if 2^l>=N1, N=2^l; L=l; break; end; end; end;

2、补零成整数幂

先判断N是否为2的整数幂，如果不是则其后补零：把N扩展成为2的整数幂，扩展部分置零。先求出点数N和其最高幂数L，再判断N是否满足2的L次幂，程序片段如下：

n=size(T);

for l=0:12, if 2^l>=n, N=2^l; L=l; break; end;

end;

x=n(1)*n(2); f=N-x;

A=zeros(1,f) ; X=[T,A]; 3、实现倒位序：

9

从原理图中我们可以看到输入的X(n)不是按自然顺序存储的，而是按X(0)，X(4)，X(2)，?，X(7)的顺序存入存储单元，初看起来好像是“混乱无序”的，实际上是有规律的，我们称之为倒位序。

一般实际运算中，总是先按顺序将输入序列存入存储单元，为了得到倒位序的排列，我们通过变址运算来完成。如果输入序列的序号n用二进制（例如n2 n1 n0）表示，则其倒位序二进制序号n'就应该是（n0 n1 n2），这样，在原来自然顺序时应该放X(n)的单元，现在倒位序应放X(n')中。在编程过程中，由于为了简单，直接在X中抽取对应的倒位序的X(n')放入X1中，最后再把X1返赋给X，就可以了。程序片段如下：

X1=X;

for i=1:N, z=dec2bin(i-1,L); for k=1:L/2, t=z(k); z(k)=z(L-k+1); z(L-k+1)=t; end;

m=bin2dec(z)+1; X1(i)=X(m); end; X=X1 4、FFT运算

①、蝶形运算两结点的“距离”

输入是倒位序的，输出是自然顺序的，其第一级(第一列)每个蝶形的两节点间“距离”为1，第二级每个蝶形的两节点“距离”为2，第三级每个蝶形的两节点“距离”为4，由此类推得，对N?2L点FFT，当输入为倒位序，输出为正常顺序时，其第m级运算，每个蝶形的两节点“距离”为N?2L。

②、r值的计算

①、蝶形运算两节点中的第一个节点标号值，即k值，表示成L位（注意N?2L）二进制；

②、把此二进制数乘上N?2(L?m)，即将此L位二进制数左移L-m位(注意m是第m级的运算)，把右边空出的位置补零，此数即为所求r的二进制数。

10

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库333李立广FFT课程设计报告(2)在线全文阅读。