8点基于DIT的FFT的实现.docx

1、8点基于DIT的FFT的实现 摘 要 FFT，即为快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。FFT算法可分为按时间抽取算法和按频率抽取算法 本文详细介绍了快速傅里叶算法的原理及推详细推导过程，并给出了8点fft的蝶形图及matlab程序代码，并通过调用该函数就算16点的fft。关键词：matlab；fft；函数1 FFT原理与实现1.1引言 信号的傅里叶变换或频谱分析是信号处理中的一个强有力工具。它把信号、线性系统、相关、卷积等概念有机结合在一起。对于数字系统来说，我们应该把谱分析也离散化，这就是离散傅里叶变换（D

2、FT）。1965年库利与图基提出了一种快速计算DFT的方法，很快就得到了广泛的应用。常见的FFT算法有2大类，一类是按时间抽取的FFT算法（简称DIT-FFT),另一类是按频率抽取的FFT算法（简称DIF-FFT)。1.2 DFT计算公式对于N点序列，它的离散傅里叶变换（DFT）为离散傅里叶变换的逆变换（IDFT）为：1.3 旋转因子WN的特性（1）WN的对称性 （2） （2）WN的周期性 （3） 利用DFT中的周期性和对称性，使整个DFT的计算变成一系列迭代运算，可大幅度提高运算过程和运算量，这就是FFT的基本思想。（3）WN的可约性 （4)假设采样序列点数为N=2L，L为整数，如果不满足这

3、个条件可以人为地添加若干个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)的形式，此时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变

4、换过程可以用两个N/2点的DFT变换过程来表示，其具体公式如式(9)所示DFT快速算法的迭代公式：（9）上式中X(k)为偶数项分支的离散傅立叶变换，X(k)为奇数项分支的离散傅立叶变换。 式(10)的计算过程可以用图1-1的蝶形算法流图直观地表示出来。 图1-1 时间抽取蝶形运算 在图1中，输入为两个N/2点的DFT输出为一个N点的DFT结果，输入输出点数一致。运用这种表示方法，8点的DFT可以用图1-2来表示： 根据公式(10)，一个N点的DFT可以由两个N/2点的DFT运算构成，再结合图1-1的蝶形信号流图可以得到图2的8点DFT的第一次分解。该分解可以用以下几个步骤来描述： 1.将N点的

5、输入序列按奇偶分为2组分别为N/2点的序列 2.分别对1中的每组序列进行DFT变换得到两组点数为N/2的DFT变换值X1和X2 3.按照蝶形信号流图将2的结果组合为一个N点的DFT变换结果根据式(10)我们可以对图2中的4点DFT进一步分解，得到图1-3的结果，分解步骤和前面一致。最后对2点DFT进一步分解得到最终的8点FFT信号计算流图：从图2到图4的过程中关于旋转系数的变化规律需要说明一下。看起来似乎向前推一级，在奇数分组部分的旋转系数因子增量似乎就要变大，其实不是这样。事实上奇数分组部分的旋转因子指数每次增量固定为1，只是因为每向前推进一次，该分组序列的数据个数变少了，为了统一使用以原数

6、据N为基的旋转因子就进行了变换导致的。每一次分组奇数部分的系数WN,这里的N均为本次分组前的序列点数。以上边的8点DFT为例，第一次分组N=8,第二次分组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

7、(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);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

8、)+x2(5);%计算蝶形图输出y(2)=x2(2)+x2(6)*(wn.1);y(3)=x2(3)+x2(7)*(wn.2);y(4)=x2(4)+x2(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

9、)=y1+y2.*(wn.0:7); %计算前八个点y(9:16)=y1-y2.*(wn.0:7);%计算后八个点3上机过程3.1编写8点FFT函数运行matlab，新建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.0

10、000 - 4.0000i -4.0000 - 9.6569i3.2调用系统函数在命令窗口输入 fft(1:8)后按回车，通过调用系统函数fft计算8点fft，计算结果与上面一致，结果如下： 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）

11、 fft16(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.0

12、800i -0.0800 - 0.1197i -0.0800 - 0.1931i Column 16 -0.0800 - 0.4022i3.4调用系统函数 输入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.080

13、0 + 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.4022i4 心得体会 经过三天的努力，总算把数字信号处理课程设计做完了。 通过该课程设计，全面系统的理解了数字信号处理的一般原理和基本实现方法。把死板的课本知识变得生动有趣，激发了学习的积极性。把学过的数字信号处理基础

14、原理的知识强化，能够把课堂上学的知识通过自己编写的程序表示出来，加深了对理论知识的理解。 在这次课程设计中，我先是认真阅读课本上的相关知识，理解透后又翻阅关于matlab的书籍，学习matlab中一些函数及运算符的用法。总体来说,这次课设我学到了很多。在设计过程中,加深了对可内知识的理解就,真正懂得了学以致用，熟悉了matlab的使用，了解了matlab在数字信号处理中的重大应用。做课程设计我体会到了设计的艰辛的同时,更让我体会到成功的喜悦和快乐. 这次数字信号处理课程设计,虽然短暂但是让我得到多方面的提高：首先，提高了我们的对matlab语言的运用能力。matlab语言是以矩阵为基础的语言，

15、像很多高级语言中需要用循环结构来描述的算法可以用矩阵或数组的运算来表示，简洁明了同时提高了执行效率。另外，我们还更加充分的认识到，数字信号处理这门课程在科学发展中的至关重要性。其次，查阅参考书的独立思考的能力以及培养非常重要，我们在设计程序时，遇到很多不理解的东西，有的我们通过查阅参考书弄明白，有的通过网络查到，但由于时间和资料有限我们更多的还是独立思考。最后，相互讨论共同研究也是很重要的，经常出现一些问题，比如matlab中矩阵乘法与数组乘法的区别，但是和其他的同学讨论后，理解了这两种乘法的区别，并很快运用到所设计的程序中去。参考文献1邹其洪.MATLAB教程. 电子工业出版社，20052吴友宇.数字信号处理. 东南大学出版社，20083吴锡龙.信号与系统.高等教育出版社，20044 陈怀琛.MATLAB应用与提高. 西安电子科技大学出版社，20005 丁春利.DSP技术. 清华大学出版社，2002