基于位倒序寻址方222

基于位倒序寻址方式的FFT现制作者魏俊基于位倒序寻址方式的FFT现•摘要:数字信号处理在许多领域中有重要的意义，数字信号处理目的是对数字信号进行处理和转换。它采用运算的方法来处理数字信号。由于傅里叶变换和z变换在计算机上实现很不方便，所以引入了离散傅里叶变换，它在数字信号处理中有着重要的地位，面对大量的数据运算，为了提高运算速度，人们对离散傅里叶变换进行了改进，离散傅里叶运算效率大大提高，这种快速傅里叶算法的出现，在数字信号处理中发挥了巨大的作用。本文介绍了有关离散傅里叶变换和快速傅里叶变换性质、算法原理和应用举例。并用c语言编程实现快速傅里叶转换。•关键词：离散傅里叶转换、快速傅里叶转换、c语言编程第一章绪论•1.1数字信号处理的基本概念•1.2数字信号处理的特点•1.3数字信号处理的应用1.1数字信号处理的基本概念•信号是信息的物理表现形式，信息是信号的具体内容。根据信息的载体不同，信号可以是电的、磁的、光的、声的、热的和机械的等不同种类的信号。•信号通常是一个或几个自变量的函数。如果只有一个自变量，则称为一维信号；如果是两个或以上自变量，则称为多维信号。•信号的自变量可以是时间、距离、电压、温度等不同形式。本书一般把信号看做时间的函数。1.2数字信号处理的特点•1.灵活性高•2精度高•3易于大规模集成•4性能指标高1.3数字信号处理的应用1通用DSP：数字滤波、卷积、相关、FFT2语音：语音通信、语言编码、识别、；3图像图形：机器人视觉、图像传输和压缩、等；4控制：磁盘控制器、机器人控制、激光打印机、电机控制；5军事：雷达、保密通信、声纳、导航、传感器融合等；6电讯：调制解调器、蜂窝电话、、视频会议等；7汽车：自动驾驶控制、故障分析、导航、汽车音响等；8消费：数字音响、数字电视、MP3播放器、数码相机等第二章离散傅里叶变换（DFT）•2.1.傅里叶变换的几种可能形式及离散傅里叶变换定义•2.2DFT的性质2.1傅里叶变换的几种可能的形式及离散傅里叶变换的定义(j)()edjtFftt1连续时间·连续频率-----傅里叶变换1()(j)ed2jtftF•2连续时间·离散频率--傅里叶级数tjnnnTFtf0e)(0/2/21()edTjtnTTFfttT•3离散时间·连续频域-----序列的傅里叶变换DTFT[()](e)()e1IDTFT[(e)]()(e)ed2jjnnjjjnxnXxnXxnX•4离散时间·离散频率----离散傅里叶变换/2/2000()()1()():0~1:2,0~1:ssjTjnTnjTjnTsXexnTexnTXeednNkkFkNdd从•由于101,,1,0,)(1)(NknkNNnWkXNnxNFfss00Tfss1200021FTNTs2200所以1,,1,0,)()(10NkWnxkXNnnkNNjNeW22.1.1DFS的性质•1线性DFS=•其中a,b为任意常数•所得到的频域序列也是周期序列，周期为N.)(~)(~1nxDFSkX)(~)(~2nxDFSkX)(~)(~21nxbnxa)(~)(~21kXbkXa2序列的时域移位)(~)(~kXWmnxDFSmkN3序列的频域移位)(~)(~lnlkXnxWDFSN•4周期卷积•如果，则)(~)(~)(~kXkXkY)(~)(~)(~)(~)(~~11021021mnxmxmnxmxkYIDFSyNmNm•5对偶性)(~)](~[)(~)](~[kxNnXDFSkXnxDFS2.2DFT的性质•2．2.1线性性质•如果和是两个有限长序列，长度分别，若21,NN)()()(21nbxnaxny式中ａ，ｂ为任意常数)()()()(21kbXkaXnyDFTkY10Nk2.2.2圆周移位性质)()())((kXWnRmnxmkNNN)())(()(kRlkXnxWNNnlN2.2.3对偶性)()]([kXnxDFT)())(()())(()]([kRkNNxkRkNxnXDFTNNNN•2.3.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)均是有限长序列•傅里叶变换理论•信号持续时间有限长，其频谱是无限宽。•信号的频谱有限长，在时域中，该信号的持续时间无限长。•上述两种情况，在时域或频域中进行采样，得到的序列都是无限长序列，不满足DFT的变换条件。•采用的处理方法：在频域中用滤波器滤除高于折叠频率的高频分量，在时域中则是截取有限点进行DFT。第三章快速傅里叶变换•3.1改进计算的方法•3.2按时间抽取的FFT算法•3.2.1算法原理•3.2.2按时间抽取的FFT算法的运算量与运算特点•3.3按频率抽取的FFT算法•3.3.1算法原理与运算特点•3.3.2按时间抽取与按频率抽取的同异•离散傅里叶的计算工作量101,,1,0,)(1)(NknkNNnWkXNnx1,,1,0,)()(10NkWnxkXNnnkN•通常X(k),都是复数，所以计算一个X(k)的值需要N次复数乘法运算，和N-1次复数加法运算，那么所有的X(k)就要NxN复数乘法运算，N(N-1)复数加法运算，当N很大时，计算量就相当惊人，如果当N=1024时，则要完成1048576次运算这样难易做到实时处理。nkNW•改进途径，利用的周期性和对称性nkNW;,)()()(*NknNkNnNnkNnkNnkN3.2按时间抽取的FFT算法•3.2.1算法原理•一．算法原理基于(2FFT)•N/2点的DFT，先将x(n)按n的奇偶分成两组DFT，不足时补零•这样就有：N为偶数时：N为奇数时：1,,1,0),()12(1,,1,0),()2(2221NNrrxrxrrxrx10)()]([)(NnnkNWnxnxDFTkX1022102110)12(10210102222))(())(()12()2()()()(NNNNrrkNkNrrkNrkrNrrkNNnNnnkNnkNWrxWWrxWrxWrxWnxWnxkX•由于•所以可表示为222)/(222NNNWeeWjjN)()()()()(211021012222kXWkXWrxWWrxkXkNrrkkNrrkNNNN•X(k)的后一半的确定rkkrNNNWW222)()()()()2(1101)(101122222kXWrxWrxkNXNNNNNrrkkrrkNkNNkN22)(1,,1,0),()(221NkNkkXWkX)2()2()2(212NkXWNkXNkXNkN蝶形运算•蝶形运算(1111-1)()()(21kXWkXkXkN)()()2(21kXWkXkNXkN)(1kX)(2kXkNW前半部为X(0)~X(3),后半部分为X(4)~X(7)整个过程如下图所示:•有图可知一个N点分解为两个N/2点DFT后，如果直接计算N/2点DFT，则每一个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次复数加法。因此通过进一步分解后，这样分解后运算量减少了一半。3.2.2FFT的运算量和运算特点•1.位倒序•造成位倒序的原因是输入按标号的奇偶的不断分组而造成的。如果用二进制数表示为第一次分组，为偶数上半部分，为奇数在下半部分，这样观察的二进制数的最低位则序列值对应于偶数抽样，则序列值对应于奇数抽样。下一次则根据次低位的0、1来分偶奇。这种不断分成偶数子序列和基数子序列的过程如下图的二进制树状图来描述。这就是的算法输入序列的序数成为位倒序的原因。•2·位倒序的实现•如果输入序列的序号n用二进制数表示(如)，则位倒序二进制数用N表示为•当n=N时，不必调换•当nN时，才交换它们存储单元的内容•当nN时，说明已经换过了•最终得到一致的012nnn210nnn•3.蝶形运算两节点的距离:其中,m表示第m列,且m=1,…,L•例如N=8=,第一级(列)距离为=1,第二级(列)距离为=2•第三级(列)距离为=4。12m32112122132•4.存储单元•存输入序列x(n),n=0,1,,N-1,计N个单元;•存放系数,r=0,1,,N/2-1,需N/2个存储单元；共计(N+N/2)个存储单元。rNW3.3按频率抽取的FFT算法•一.算法原理10)()(NnnkNWnxkX10)(1012/102222)2()()()(NNNNnknNnnkNNNnnkNnnkNWNnxWnxWnxWnxnkNnkNWWNnxnxNN1022)2()(,12jNeWNkkNNW)1(2nkNnkWNnxnxkXN102)2()1()()(1,,1,0Nk•k为偶数时：•k为奇数时)2(rXnrnnrNnNNNWNnxnxWNnxnx22210210)2()()2()(nrnnNrnNnNNNWWNnxnxWNnxnxrX22210)12(10)2()()2()()12(•蝶形运算)(nx)2(Nnx)2()(NnxnxnNWNnxnx)2()(1,,1,02NnrNW•3.3.2按时间抽取与按频率抽取的同异•相同点•（1）进行原位运算•（2）运算量相同•不同点•（1）蝶形运算不同•(2)DIT输入为倒位序,输出为自然顺序；DIF正好与此相反。但DIT也有输入为自然顺序,输出为倒位序的情况。•(3)两种蝶形运算的关系互为转置•综上可得，如果将DIT的基本碟形运算加以转置，就得到DIF的基本碟形；反过来，将的DIF基本碟形加以转置就得到DIT的基本碟形，因而法与法的基本碟形是互为转置的。按照转置定理，两个信号流图的输入输出特性必然相同。转置就是将流图的所有之路方向都反向，并且交换输入输出，但节点变量值不交换，因而对每一种按时序抽取的FFT流图都存在一个按频率抽取的FFT流图。第四章FFT的编程•4.1FFT的软件实现•4.2用c语言实现FFT用C语言实现FFT的流程图，如下示：•４.2用c语言实现•毕业论文设计上有，这里就省了。结论••由此我们可以得出结论:快速傅里叶转换只是离散傅里叶转换的一种方法，它的出现从根本上改变了傅里叶变换的地位。它可以将一个信号变换到频域，有些信号在时域上很难看出什么特征来，但变换到频域后，就很容易看看出特征。通过对快速傅里叶的深刻理解和对c语言的掌握，这次用c语言来实现基于位倒序方式的FFT是完全可行的。该方法具有运算速度快，精确度高，实现简单，可用于各种关于离散傅里叶的计算中。它可以把复杂的计算问题简单化，具有良好的学术价值和良好的应用前景。致谢•本次设计是在廖老师的悉心指导下完成的。在整个过程中，导师给予了大量指导，并提供了很多与课题相关的重要信息，培养了我们对科学研究的严