《DSP课程设计基于MATLAB的FFT算法实现》由会员分享，可在线阅读，更多相关《DSP课程设计基于MATLAB的FFT算法实现（30页珍藏版）》请在金锄头文库上搜索。
1、目 录1 引言12 基于MATLAB的FFT算法实现22.1系统总体流程图22.2 FFT运算规律及编程思想32.2.1语音信号的采集32.2.2 DIT-FFT算法的基本原理32.2.3 DIT-FFT算法的运算规律及编程思想53 Matlab程序实现104 系统人机对话界面134.1 GUI简介134.2 界面设计134.3 运行调试145 心得体会16参考文献17附录18附录21 / 1 引言MATLAB是矩阵实验室Matrix Laboratory的简称,是美国MathWorks公司出品的商数学软件,用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境,主要包括
2、MATLAB和Simulink两大部分。MATLAB 的应用围非常广,包括信号和图像处理、通讯、控制系统设计、测试和测量、财务建模和分析以及计算生物学等众多应用领域。附加的工具箱单独提供的专用 MATLAB 函数集扩展了 MATLAB 环境,以解决这些应用领域特定类型的问题。它以矩阵运算为基础,把计算、可视化、程序设计融合在一个简单易用的交互式工作环境中,是一款数据分析和处理功能都非常强大的工程适用软件。它可以将声音文件变换为离散的数据文件,然后利用其强大的矩阵运算能力处理数据,如数据滤波、傅立叶变换、时域和频域分析、声音回放以及各种图的呈现等,它的信号处理与分析工具箱位语音信号分析提供了十分
3、丰富的功能函数,利用这些功能函数可以快捷而又方便的完成语音信号的处理和分析以及信号的可视化。数字信号处理是MATLAB重要应用的领域之一。对于有限长序列x,若要求其N点的傅里叶变换DFT需要经过次复数乘法运算和N*次复数加法运算。随着N的增加,运算量将急剧增加,而在实际问题中,N往往是较大的,如当N=1024时,完成复数乘法和复数加法的次数分别为百万以上,无论是用通用计算机还是用DSP芯片,都需要消耗大量的时间和机器存,不能满足实时的要求。因此,DFT的这种运算只能进行理论上的计算,不适合对实时处理要求高的场合。因此,研究作为DSP的快速算法的FFT是相当必要的,快速傅里叶变换FFT是为提高D
4、FT运算速度而采用的一种算法,快速算法的种类很多,而且目前仍在改进和提高,它是根据离散傅里叶变换的奇、偶、虚、实等特性,对离散傅立叶变换的算法进行改进获得的。基于本学期所学的DIT-FFT的运算规律和编程思想以及Matlab的学习和使用,本课设要求在Matlab环境下编写基2 DIT-FFT算法实现对离散信号的快速傅里叶变换,再与Matlab软件自带的FFT函数实现对离散信号的傅里叶变换进行比较,如果得到的频谱相同,那么我们编写的程序就是正确的。其中离散信号是通过PC自带的录音机录制一段wav语音信号,用Matlab采样得到离散序列x1。如果有能力可以选做系统人机对话界面。用GUI界面完成人机
5、交互方便使用的。本课程设计主要是对数字信号的分析。2 基于MATLAB的FFT算法实现2.1系统总体流程图本设计要求录制一段个人自己的语音信号,并对录制的信号进行采样；画出采样后语音信号的时域波形和频谱图；在Matlab环境下编写基2 DIT-FFT算法；利用自己编写的算法对已采集的语音信号进行频谱分析,并画出语音信号的时域与频谱图,并与Matlab数字信号处理工具箱中的fft函数进行对比研究,验证自编算法的正确性。所以得到系统总体流程图如图1所示。语音信号采集完成信号时域图完成信号频率响应编写fft程序,画出信号频谱图实现输入信号的倒序实现一级中不同种蝶形算运实现一级中相同种蝶形运算与Mat
6、lab自带的FFT比较图1 系统总体流程图2.2 FFT运算规律及编程思想2.2.1语音信号的采集利用PC机自带的录音机,录制一段语音信号,保存格式为wave的文件,并将其保存在电脑中。在MATLAB中,fn=input; x,fs,nb=wavread; 用于读取语音,采样值放在向量x中,fs表示采样频率,nb表示采样位数。n1 n2表示读取从n1点到n2点的值若只有一个n的点则表示读取前n点的采样值。sound; 用于对声音的回放。向量x则就代表了一个信号也即一个复杂的函数表达式也就是说可以像处理一个信号表达式一样处理这个声音信号。采集到语音信号之后,需要对语音信号进行分析,如语音信号的时
7、域分析、频谱分析、谱图分析。2.2.2 DIT-FFT算法的基本原理快速傅里叶变换FFT是为提高DFT运算速度而采用的一种算法。对一个有限长度序列x的N点的DFT为：所以,要求N点的DFT,需要N2次的复数乘法运算,N*次复数乘法运算算。随着N的增加,运算量将急剧增加,而在实际问题中,N往往是较大的,如当N=1024时,完成复数乘法和复数加法的次数分别为百万以上,无论是用通用计算机还是用DSP芯片,都需要消耗大量的时间,不能满足实时的要求,不适合于对实时处理要求高的场合。为了能实时处理DFT,要想减少DFT的运算量可以有两个途径：第一是降N,N的值减小了,运算量就减少了；第二是利用旋转因子的周
8、期性,对称性和可约性。利用这两个途径实现DFT的快速傅里叶变换FFT,FFT算法基本上可分为按时间抽取的FFT算法DIT-FFT和按频率抽取的FFT算法DIF-FFT。旋转因子的性质：1周期性2共轭对称性3可约性本次课设要求用用基2的按时间抽取的FFT算法DIT-FFT实现FFT功能,设序列x的长度为N,且N满足N=2M,M为正整数。若N不能满足上述关系,可以将序列x补零实现。按时间抽取基2-FFT算法的基本思路是将N点序列按时间下标的奇偶分为两个N/2点序列,计算这两个N/2点序列的N/2点DFT,计算量可减小约一半；每一个N/2点序列按照同样的划分原则,可以划分为两个N/4点序列,最后,将
9、原序列划分为多个2点序列,将计算量大大降低。按时间下标的奇偶将N点x分别抽取组成两个N/2点序列,分别记为x1和x2,将x的DFT转化为x1和x2的DFT的计算。利用旋转因子的可约性,即：用蝶形运算可表示为如图2所示：图2 DIT-FFT蝶形运算流图符号以此类推,还可以把x1和x2按n值得奇偶分为两个序列,这样就达到了降N得目的,从而减少了运算量。FFT对DFT的数学运算量改进：直接采用DFT进行计算,运算量为N2次复数乘法和N*次复数乘法。当采用M次FFT时,由N=2M求得M=logN,运算流图有M级蝶形,每一级都由N/2个蝶形运算构成,这样每一级蝶形运算都需要N/2次复数乘法和N次复数加法
10、。M级运算共需要复数乘法次数为C=N/2*M,复数加法次数为C=N*M。当N值较大时,FFT减少运算量的特点表现的越明显。2.2.3 DIT-FFT算法的运算规律及编程思想为了编写DIT-FFT算法的运算程序,首先要分析其运算规律,总结编程思想并绘出程序框图。1. 原位计算对点的FFT共进行M级运算,每级由N/2个蝶形运算组成。在同一级中,每个蝶的输入数据只对本蝶有用,且输出节点与输入节点在同一水平线上,这就意味着每算完一个蝶后,所得数据可立即存入原输入数据所占用的数组元素,这种原位计算的方法可节省大量存。2. 蝶形运算实现FFT运算的核心是蝶形运算,找出蝶形运算的规律是编程的基础。蝶形运算是
11、分级进行的；每级的蝶形运算可以按旋转因子的指数大小排序进行；如果指数大小一样则可从上往下依次蝶算。对点的FFT共有M级运算,用L表示从左到右的运算级数。第L级共有个不同指数的旋转因子,用R表示这些不同指数旋转因子从上到下的顺序。第R个旋转因子的指数,旋转因子指数为P的第一个蝶的第一节点标号k从R开始,由于本级中旋转因子指数相同的蝶共有个,且这些蝶的相邻间距为,故旋转因子指数为P的最后一个蝶的第一节点标号k为：,本级中各蝶的第二个节点与第一个节点都相距B点。应用原位计算,蝶形运算可表示成如下形式： = + * = -* 总结上述运算规律,可采用如下运算方法进行DIT-FFT运算。首先读入数据,根
12、据数据长度确定运算级数M,运算总点数,不足补0处理。然后对读入数据进行数据倒序操作。数据倒序后从第1级开始逐级进行,共进行M级运算。在进行第L级运算时,先算出该级不同旋转因子的个数,再从R=0开始按序计算,直到R=B-1结束。每个R对应的旋转因子指数,旋转因子指数相同的蝶从上往下依次逐个运算,各个蝶的第一节点标号k都是从R开始,以为步长,到结束。考虑到蝶形运算有两个输出,且都要用到本级的两个输入数据,故第一个输出计算完毕后,输出数据不能立即存入输入地址,要等到第二个输出计算调用输入数据完毕后才能覆盖。这样数据倒序后的运算可用三重循环程序实现。整个蝶形运算流程图如图3所示。图3 整个蝶形运算流程
13、图送入x,MN=2M倒序L=1:MB=2J=0:B-1P=J*2 K=J:2L:N-1T=A+A*WNPA=A-A*WNPA=T输出开始 结束束束3.序列倒序为了保证运算输出的X按顺序排列,要求序列x倒序输入,即在运算前要先对输入的序列进行位序颠倒。如果总点数为的x的顺序数是用M位二进制数表示,则倒序数只需将顺序数的二进制位倒置即可,按照这一规律用硬件电路和汇编语言很容易产生倒序数。但用MATLAB等高级语言实现倒序时,直接倒置二进制数位的方法不可取,还须找出产生倒序的十进制规律。将十进制顺序数用I表示,与之对应的二进制数用IB表示。十进制倒序数用J表示,与之对应的二进制数用表示。是IB的位倒
14、置结果,十进制顺序数I增加1,相当于IB最低位加1且逢2向高位进1,即相当于最高位加1且逢2向低位进1。的变化规律反映到J的变化分二种情况：如果的最高位是0,则直接由加1得到下一个倒序值；如果的最高位是1,则要先将最高位变0,再在次高位加1。但次高位加1时,同样要判断0、1值,如果是0 ,则直接加1,否则要先将次高位变0,再判断下一位。依此类推,直到完成最高位加1,逢2向右进位的运算。利用这一算法可按顺序数I的递增顺序,依次求得与之对应的倒序数J。为了节省存,数据倒序可原址进行,当I = J时不需要交换,当I J时需要交换数据。另外,为了避免再次调换前面已经调换过的一对数据,只对IJ的情况进行数据交换即可实现数据倒序操作。图3中数据倒序的程序流程图如图4所示。例如,N=8时,序列倒序结果如表1所示。
