《8点基于DIT的FFT的实现》由会员分享，可在线阅读，更多相关《8点基于DIT的FFT的实现（15页珍藏版）》请在金锄头文库上搜索。
1、目 录摘要1 FFT原理与实现11.1引言11.2 DFT计算公式11.3旋转因子WN的特性11.4调用8点计算16点52 程序代码62.1 计算8点FFT代码62.2计算算16点FFT代码73上机过程83.1编写8点FFT函数83.2调用系统函数83.3 编写16点FFT函数93.4调用系统函数94 心得体会10参考文献11Word 资料摘 要 FFT，即为快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。FFT算法可分为按时间抽取算法和按频率抽取算法 本文详细介绍了快速傅里叶算法的原理及推详细推导过程，并给出了8点ff
2、t的蝶形图及matlab程序代码，并通过调用该函数就算16点的fft。关键词：matlab；fft；函数Word 资料1 FFT原理与实现1.1引言 信号的傅里叶变换或频谱分析是信号处理中的一个强有力工具。它把信号、线性系统、相关、卷积等概念有机结合在一起。对于数字系统来说，我们应该把谱分析也离散化，这就是离散傅里叶变换（DFT）。1965年库利与图基提出了一种快速计算DFT的方法，很快就得到了广泛的应用。常见的FFT算法有2大类，一类是按时间抽取的FFT算法（简称DIT-FFT),另一类是按频率抽取的FFT算法（简称DIF-FFT)。1.2 DFT计算公式对于N点序列，它的离散傅里叶变换（D
3、FT）为离散傅里叶变换的逆变换（IDFT）为：1.3 旋转因子WN的特性（1） WN的对称性 （2） （2）WN的周期性 （3） 利用DFT中的周期性和对称性，使整个DFT的计算变成一系列迭代运算，可大幅度提高运算过程和运算量，这就是FFT的基本思想。（3）WN的可约性 （4)假设采样序列点数为N=2L，L为整数，如果不满足这个条件可以人为地添加若干个0以使采样序列点数满足这一要求。首先我们将序列x(n)按照奇偶分为两组如下：X(2r)=x1(r) ,X(2r+1)=x2(r),r=0,1.N/2-1 (5)于是根据DFT计算公式(1)有： （6）至此，我们将一个N点的DFT转化为了式(6)的
4、形式，此时k的取值为0到N-1,现在分为两段来讨论，当k为0N/2-1的时候，因为x1(r)，x2(r)为N/2点的序列，因此，此时式(6)可以写为： k=0.N-1 (7)而当 k取值为N/2N-1时，k用k+N/2取代，k取值为0N/2-1。对式(6)化简可得： （8） 综合以上推导我们可以得到如下结论：一个N点的DFT变换过程可以用两个N/2点的DFT变换过程来表示，其具体公式如式(9)所示DFT快速算法的迭代公式：（9）X1(k)X2(k)上式中X(k)为偶数项分支的离散傅立叶变换，X(k)为奇数项分支的离散傅立叶变换。 式(10)的计算过程可以用图1-1的蝶形算法流图直观地表示出来。
5、 X1(k)+X2(k)X1(k)-X2(k) 图1-1 时间抽取蝶形运算图1-2 4点蝶形运算流图 在图1中，输入为两个N/2点的DFT输出为一个N点的DFT结果，输入输出点数一致。运用这种表示方法，8点的DFT可以用图1-2来表示： 根据公式(10)，一个N点的DFT可以由两个N/2点的DFT运算构成，再结合图1-1的蝶形信号流图可以得到图2的8点DFT的第一次分解。该分解可以用以下几个步骤来描述： 1.将N点的输入序列按奇偶分为2组分别为N/2点的序列 2.分别对1中的每组序列进行DFT变换得到两组点数为N/2的DFT变换值X1和X2 3.按照蝶形信号流图将2的结果组合为一个N点的DFT
6、变换结果根据式(10)我们可以对图2中的4点DFT进一步分解，得到图1-3的结果，分解步骤和前面一致。最后对2点DFT进一步分解得到最终的8点FFT信号计算流图：图1-3 8点蝶形运算流图从图2到图4的过程中关于旋转系数的变化规律需要说明一下。看起来似乎向前推一级，在奇数分组部分的旋转系数因子增量似乎就要变大，其实不是这样。事实上奇数分组部分的旋转因子指数每次增量固定为1，只是因为每向前推进一次，该分组序列的数据个数变少了，为了统一使用以原数据N为基的旋转因子就进行了变换导致的。每一次分组奇数部分的系数WN,这里的N均为本次分组前的序列点数。以上边的8点DFT为例，第一次分组N=8,第二次分组
7、N为4，为了统一根据式(4)进行了变换将N变为了8，但指数相应的需要乘以2。1.4调用8点计算16点先将16点fft拆成两个8点fft，分别调用自身8点fft函数fft8计算，然后再按以下公式计算出16点的fft（10）图1-4 16点蝶形运算图2 程序代码2.1 计算8点FFT代码function y=fft8(x)%根据蝶形图计算8点FFTwn=exp(-j*2*pi/8);%旋转因子x1(1)=x(1)+x(5);%计算蝶形图第一级x1(2)=x(1)-x(5);x1(3)=x(3)+x(7);x1(4)=x(3)-x(7);x1(5)=x(2)+x(6);x1(6)=x(2)-x(6)
8、;x1(7)=x(4)+x(8);x1(8)=x(4)-x(8);x2(1)=x1(1)+x1(3);%计算蝶形图第二级x2(2)=x1(2)+x1(4)*(wn.2);x2(3)=x1(1)-x1(3);x2(4)=x1(2)-x1(4)*(wn.2);x2(5)=x1(5)+x1(7);x2(6)=x1(6)+x1(8)*(wn.2);x2(7)=x1(5)-x1(7);x2(8)=x1(6)-x1(8)*(wn.2);y(1)=x2(1)+x2(5);%计算蝶形图输出y(2)=x2(2)+x2(6)*(wn.1);y(3)=x2(3)+x2(7)*(wn.2);y(4)=x2(4)+x2
9、(8)*(wn.3);y(5)=x2(1)-x2(5);y(6)=x2(2)-x2(6)*(wn.1);y(7)=x2(3)-x2(7)*(wn.2);y(8)=x2(4)-x2(8)*(wn.3);2.2计算16点FFT代码function y=fft16(x)%16点FFTwn=exp(-j*2*pi/16);y1=fft8(x(1:2:16);%计算偶数组的8点ffty2=fft8(x(2:2:16);%就算奇数组的8点ffty(1:8)=y1+y2.*(wn.0:7); %计算前八个点y(9:16)=y1-y2.*(wn.0:7);%计算后八个点3上机过程3.1编写8点FFT函数运行m
10、atlab，新建m文件，进入编辑器输入程序后保存为fft8，注意文件名与函数名相同。在matlab命令窗口中输入fft8（1:8)，按回车，运行结果如下fft8(1:8)ans = Columns 1 through 5 36.0000 -4.0000 + 9.6569i -4.0000 + 4.0000i -4.0000 + 1.6569i -4.0000 Columns 6 through 8 -4.0000 - 1.6569i -4.0000 - 4.0000i -4.0000 - 9.6569i3.2调用系统函数在命令窗口输入 fft(1:8)后按回车，通过调用系统函数fft计算8点f
11、ft，计算结果与上面一致，结果如下： fft(1:8)ans = Columns 1 through 5 36.0000 -4.0000 + 9.6569i -4.0000 + 4.0000i -4.0000 + 1.6569i -4.0000 Columns 6 through 8 -4.0000 - 1.6569i -4.0000 - 4.0000i -4.0000 - 9.6569i3.3 编写16点FFT函数输入fft16（3:18） fft16(3:18)ans = 1.0e+002 * Columns 1 through 5 1.6800 -0.0800 + 0.4022i -0.
12、0800 + 0.1931i -0.0800 + 0.1197i -0.0800 + 0.0800i Columns 6 through 10 -0.0800 + 0.0535i -0.0800 + 0.0331i -0.0800 + 0.0159i -0.0800 -0.0800 - 0.0159i Columns 11 through 15 -0.0800 - 0.0331i -0.0800 - 0.0535i -0.0800 - 0.0800i -0.0800 - 0.1197i -0.0800 - 0.1931i Column 16 -0.0800 - 0.4022i3.4调用系统函数
13、 输入fft（3:18）后按回车，通过调用系统函数fft计算16点fft，计算结果与上面一致，结果如下： fft(3:18)ans = 1.0e+002 * Columns 1 through 5 1.6800 -0.0800 + 0.4022i -0.0800 + 0.1931i -0.0800 + 0.1197i -0.0800 + 0.0800i Columns 6 through 10 -0.0800 + 0.0535i -0.0800 + 0.0331i -0.0800 + 0.0159i -0.0800 -0.0800 - 0.0159i Columns 11 through 15 -0.0800 - 0.0331i -0.0800 - 0.0535i -0.0800 - 0.0800i -0.0800 - 0.1197i -0.0800
