《基于位倒序寻址方.ppt》由会员分享，可在线阅读，更多相关《基于位倒序寻址方.ppt（51页珍藏版）》请在三一办公上搜索。
1、基于位倒序寻址方式的FFT现,制作者魏俊,基于位倒序寻址方式的FFT现,摘要:数字信号处理在许多领域中有重要的意义，数字信号处理目的是对数字信号进行处理和转换。它采用运算的方法来处理数字信号。由于傅里叶变换和z 变换在计算机上实现很不方便，所以引入了离散傅里叶变换，它在数字信号处理中有着重要的地位，面对大量的数据运算，为了提高运算速度，人们对离散傅里叶变换进行了改进，离散傅里叶运算效率大大提高，这种快速傅里叶算法的出现，在数字信号处理中发挥了巨大的作用。本文介绍了有关离散傅里叶变换和快速傅里叶变换性质、算法原理和应用举例。并用c语言编程实现快速傅里叶转换。关键词：离散傅里叶转换、快速傅里叶转换
2、、c语言编程,第一章 绪论,1.1数字信号处理的基本概念 1.2数字信号处理的特点 1.3数字信号处理的应用,1.1数字信号处理的基本概念,信号是信息的物理表现形式，信息是信号的具体内容。根据信息的载体不同，信号可以是电的、磁的、光的、声的、热的和机械的等不同种类的信号。信号通常是一个或几个自变量的函数。如果只有一个自变量，则称为一维信号；如果是两个或以上自变量，则称为多维信号。信号的自变量可以是时间、距离、电压、温度等不同形式。本书一般把信号看做时间的函数。,1.2数字信号处理的特点,1.灵活性高2精度高3易于大规模集成4性能指标高,1.3数字信号处理的应用,1通用DSP：数字滤波、卷积、相
3、关、FFT2语音：语音通信、语言编码、识别、；3图像图形：机器人视觉、图像传输和压缩、等；4控制：磁盘控制器、机器人控制、激光打印机、电机控制；5军事：雷达、保密通信、声纳、导航、传感器融合等；6电讯：调制解调器、蜂窝电话、视频会议等；7汽车：自动驾驶控制、故障分析、导航、汽车音响等；8消费：数字音响、数字电视、MP3播放器、数码相机等,第二章 离散傅里叶变换（DFT）,2.1.傅里叶变换的几种可能形式及离散傅里叶变换定义2.2DFT的性质,2.1傅里叶变换的几种可能的形式及离散傅里叶变换的定义,1连续时间连续频率-傅里叶变换,2连续时间离散频率-傅里叶级数,3离散时间连续频域-序列的傅里叶变
4、换,4离散时间离散频率-离散傅里叶变换,由于,所以,的性质,1线性DFS=其中 a,b为任意常数所得到的频域序列也是周期序列，周期为N.,2序列的时域移位,3序列的频域移位,4周期卷积如果，则,5对偶性,2.2DFT的性质,22.1线性性质如果和是两个有限长序列，长度分别，若,式中，为任意常数,圆周移位性质,对偶性,用DFT对信号进行谱分析,2.3离散傅里叶的应用,用DFT对连续信号进行谱分析,先对xa(t)进行时域采样，得到时域离散信号x(n)=xa(nT),对x(n)进行DFT，得到的X(k)是x(n)的傅里叶变换X(ejw)在区间0,2上的N点等间隔采样,x(n)和X(k)均是有限长序列
5、,傅里叶变换理论 信号持续时间有限长，其频谱是无限宽。信号的频谱有限长，在时域中，该信号的持续时间无限长。上述两种情况，在时域或频域中进行采样，得到的序列都是无限长序列，不满足DFT的变换条件。采用的处理方法：在频域中用滤波器滤除高于折叠频率的高频分量，在时域中则是截取有限点进行DFT。,第三章 快速傅里叶变换,3.1改进计算的方法3.2按时间抽取的FFT算法算法原理 按时间抽取的FFT算法的运算量与运算特点3.3按频率抽取的FFT算法 算法原理与运算特点按时间抽取与按频率抽取的同异,离散傅里叶的计算工作量,通常X(k),都是复数，所以计算一个X(k)的值需要N次复数乘法运算，和N-1次复数加
6、法运算，那么所有的X(k)就要NxN复数乘法运算，N(N-1)复数加法运算，当N很大时，计算量就相当惊人，如果当N=1024时，则要完成1048576次运算这样难易做到实时处理。,改进途径，利用 的周期性和对称性,3.2按时间抽取的FFT算法,算法原理一 算法原理基于(2FFT)N/2点的DFT，先将x(n)按n的奇偶分成两组DFT，不足时补零这样 就有：,N为偶数时：N为奇数时：,由于所以可表示为,X(k)的后一半的确定,蝶形运算,蝶形运算,前半部为X(0)X(3),后半部分为X(4)X(7)整个过程如下图所示:,有图可知一个N点分解为两个N/2点DFT后，如果直接计算N/2点DFT，则每一
7、个N/2点DFT只需要/4次复数乘法N/2(N/2-1)次复数加法。两个N/2点DFT共需/2次复数乘法和N(N/2-1)次复数加法。此外，把两个N/2点DFT合成N点DFT时，有N/2个碟形运算，需要N/2次复数乘法及N次复数加法。因此通过进一步分解后，这样分解后运算量减少了一半。,的运算量和运算特点,1.位倒序,造成位倒序的原因是输入按标号的奇偶的不断分组而造成的。如果用二进制数表示为第一次分组，为偶数上半部分，为奇数在下半部分，这样观察的二进制数的最低位则序列值对应于偶数抽样，则序列值对应于奇数抽样。下一次则根据次低位的0、1来分偶奇。这种不断分成偶数子序列和基数子序列的过程如下图的二进
8、制树状图来描述。这就是的算法输入序列的序数成为位倒序的原因。,2位倒序的实现如果输入序列的序号n用二进制数表示(如)，则位倒序二进制数用N表示为当n=N时，不必调换当nN时，说明已经换过了最终得到一致的,3.蝶形运算两节点的距离:其中,m表示第m列,且m=1,L例如N=8=,第一级(列)距离为=1,第二级(列)距离为=2第三级(列)距离为=4。,4.存储单元存输入序列x(n),n=0,1,N-1,计N个单元;存放系数,r=0,1,N/2-1,需N/2个存储单元；共计(N+N/2)个存储单元。,3.3按频率抽取的FFT算法,一.算法原理,k为偶数时：k为奇数时,蝶形运算,按时间抽取与按频率抽取的
9、同异相同点（1）进行原位运算（2）运算量相同不同点（1）蝶形运算不同,(2)DIT输入为倒位序,输出为自然顺序；DIF正好与此相反。但DIT也有输入为自然顺序,输出为倒位序的情况。(3)两种蝶形运算的关系互为转置,综上可得，如果将DIT的基本碟形运算加以转置，就得到DIF的基本碟形；反过来，将的DIF基本碟形加以转置就得到DIT的基本碟形，因而法与法的基本碟形是互为转置的。按照转置定理，两个信号流图的输入输出特性必然相同。转置就是将流图的所有之路方向都反向，并且交换输入输出，但节点变量值不交换，因而对每一种按时序抽取的FFT流图都存在一个按频率抽取的FFT流图。,第四章 FFT的编程,4.1
10、FFT的软件实现4.2用c语言实现 FFT,用C语言实现FFT的流程图，如下示：,.2用c语言实现毕业论文设计上有，这里就省了。,结论,由此我们可以得出结论:快速傅里叶转换只是离散傅里叶转换的一种方法，它的出现从根本上改变了傅里叶变换的地位。它可以将一个信号变换到频域，有些信号在时域上很难看出什么特征来，但变换到频域后，就很容易看看出特征。通过对快速傅里叶的深刻理解和对c语言的掌握，这次用c语言来实现基于位倒序方式的FFT是完全可行的。该方法具有运算速度快，精确度高，实现简单，可用于各种关于离散傅里叶的计算中。它可以把复杂的计算问题简单化，具有良好的学术价值和良好的应用前景。,致谢,本次设计是
11、在廖老师的悉心指导下完成的。在整个过程中，导师给予了大量指导，并提供了很多与课题相关的重要信息，培养了我们对科学研究的严谨态度和创新精神，对我影响深远。不仅我掌握了基本的科学研究方法，还使我明白了许多待人接物与人处事的道理，这非常有利于我今后的学习和工作。本论文从最初选题到最终完成，每一步都是在导师的指导下完成的，倾注了导师大量的精力。在此，谨向导师表示衷心的感谢和至高的敬意！,参考文献,刘明、徐洪波，数字信号处理-原理与算法实现，清华大学出版社赵健、李勇，数字信号处理，清华大学出版社张立材，吴冬梅，数字信号处理，北京邮电大学出版社阎毅，黄联芬，数字信号处理，北京大学出版社彭启琮，李玉柏，数字信号处理技术，电子科技大学出版社王维俊，江渝，DSP的c语言开发应用，北京航天大学出版社张洪涛，万红，数字信号处理，华中科技大学出版社刘益成，孙祥娥，数字信号处理，电子工业出版社奥本海姆，巴克，刘树棠，黄建国译，离散时间信号处理，西安交通大学出版社,
