离散傅里叶变换及其快速算法-下概要.ppt
《离散傅里叶变换及其快速算法-下概要.ppt》由会员分享,可在线阅读,更多相关《离散傅里叶变换及其快速算法-下概要.ppt(91页珍藏版)》请在咨信网上搜索。
1、第二章第二章 离散傅里叶变换及其快速算法离散傅里叶变换及其快速算法1.2.3 快速傅里叶变换快速傅里叶变换(FFT)快速傅里叶变换(FFT)是计算DFT的一种快速有效方法。从前面的讨论中看到,有限长序列在数字技术中占有很重要的地位。有限长序列的一个重要特点是其频域也可以离散化,即离散傅里叶变换(DFT)。2.虽然频谱分析和DFT运算很重要,但在很长一段时间里,由于DFT运算复杂,并没有得到真正的运用,而频谱分析仍大多采用模拟信号滤波的方法解决,直到1965年首次提出DFT运算的一种快速算法以后,情况才发生了根本变化,人们开始认识到DFT运算的一些内在规律,从而很快地发展和完善了一套高速有效的运
2、算方法快速付里变换(FFT)算法。FFT的出现,使DFT的运算大大简化,运算时间缩短一二个数量级,使DFT的运算在实际中得到广泛应用。3.1、DFT运算的特点:运算的特点:首先分析有限长序列x(n)进行一次DFT运算所需的运算量。一般,x(n)和wnkN都是复数,因此,每计算一个X(k)值,要进行N次复数相乘,和N-1次复数相加,X(k)一共有N个点,故完成全部DFT运算,需要N2次复数相乘和N(N-1)次复数相加,在这些运算中,乘法比加法复杂,需要的运算时间多,尤其是复数相乘,每个复数相乘包括4个实数相乘和2个实数相加,例又每个复数相加包括2个实数相加,所以,每计算一个X(k)要进行4N次实
3、数相乘和2N+2(N-1)=2(2N-1)次实数相加,因此,整个DFT运算需要4N2实数相乘和2N(2N-1)次实数相加。4.从上面的分析看到,在DFT计算中,不论是乘法和加法,运算量均与N2成正比。因此,N较大时,运算量十分可观。例,计算N=10点的DFT,需要100次复数相乘,而N=1024点时,需要1048576(一百多万)次复数乘法,如果要求实时处理,则要求有很高的计算速度才能完成上述计算量。反变换IDFT与DFT的运算结构相同,只是多乘一个常数1/N,所以二者的计算量相同。5.FFT算法的基本思想:考察DFT与IDFT的运算发现,利用以下两个特性可减少运算量:1)系数是一个周期函数,
4、它的周期性和对称性可用来改进运算,提高计算效率。例又如因此利用这些周期性和对称性,使DFT运算中有些项可合并;2)利用的周期性和对称性,把长度为N点的大点数的DFT运算依次分解为若干个小点数的DFT。因为DFT的计算量正比于N2,N小,计算量也就小。FFT算法正是基于这样的基本思想发展起来的。它有多种形式,但基本上可分为两类:时间抽取法和频率抽取法。6.2、按时间抽取的、按时间抽取的FFT(N点点DFT运算的分解)运算的分解)先从一个特殊情况开始,假定N是2的整数次方,N=2M,M:正整数首先将序列x(n)分解为两组,一组为偶数项,一组为奇数项,r=0,1,N/2-1 7.:将DFT运算也相应
5、分为两组8.因为故其中9.注意到,H(k),G(k)有N/2个点,即k=0,1,N/2-1,还必须应用系数wkN的周期性和对称性表示X(k)的N/2N-1点:由得:可见,一个N点的DFT被分解为两个N/2点的DFT,这两个N/2点的DFT再合成为一个N点DFT.10.依此类推,G(k)和H(k)可以继续分下去,这种按时间抽取算法是在输入序列分成越来越小的子序列上执行DFT运算,最后再合成为点的DFT。11.蝶形信号流图将G(k)和H(k)合成X(k)运算可归结为:Wa+bWa-bW-W-1a+bWa-bWWabab蝶形运算的简化(a)(b)12.图(a)为实现这一运算的一般方法,它需要两次乘法
6、、两次加减法。考虑到-bW和bW两个乘法仅相差一负号,可将图(a)简化成图2.7(b),此时仅需一次乘法、两次加减法。图(b)的运算结构像一蝴蝶通常称作蝶形运算结构简称蝶形结,采用这种表示法,就可以将以上所讨论的分解过程用流图表示。13.N=23=8的例子。N/2N/2点点点点DFTDFTG(0)G(0)G(1)G(1)G(2)G(2)G(3)G(3)X X(0)(0)X X(1)(1)X X(2)(2)X X(3)(3)x x(0)(0)x x(2)(2)x x(4)(4)x x(6)(6)N/2N/2点点点点DFTDFTH(0)H(0)H(1)H(1)H(2)H(2)H(3)H(3)X X
7、(4)(4)X X(5)(5)X X(6)(6)X X(7)(7)x x(1)(1)x x(3)(3)x x(5)(5)x x(7)(7)WWN N1 1WWN N2 2WWN N3 3-1-1-1-1-1-1-1-1两个两个4点点DFT组成组成8点点DFT14.按照这个办法,继续把N/2用除,由于N=2M,仍然是偶数,可以被整除,因此可以对两个N/2点的DFT再分别作进一步的分解。即对G(k)和H(k)的计算,又可以分别通过计算两个长度为N/4=2点的DFT,进一步节省计算量,见图。这样,一个点的DFT就可以分解为四个点的DFT。15.N/4N/4点点点点N/4N/4点点点点N/4N/4点点
8、点点N/4N/4点点点点 由由由由四四四四个个个个2 2点点点点DFTDFT组组组组成成成成8 8点点点点DFTDFT16.最后剩下的是2点DFT,它可以用一个蝶形结表示:这样,一个8点的完整的按时间抽取运算的流图由于这种方法每一步分解都是按输入时间序列是属于偶数还是奇数来抽取的,所以称为“按时间抽取法”或“时间抽取法”。17.按时间抽取的按时间抽取的8点点FFT18.时间抽取法时间抽取法FFT的运算特点:的运算特点:(1)蝶形运算)蝶形运算(2)原位计算)原位计算(3)序数重排)序数重排(4)蝶形类型随迭代次数成倍增加)蝶形类型随迭代次数成倍增加19.(1)蝶形运算)蝶形运算对于N=2M,总
9、是可以通过M次分解最后成为2点的DFT运算。这样构成从x(n)到X(k)的M级运算过程。从上面的流图可看到,每一级运算都由N/2个蝶形运算构成。因此每一级运算都需要N/2次复乘和N次复加,这样,经过时间抽取后M级运算总共需要的运算:复乘复加而直接运算时则与N2成正比。例N=2048,N2=4194304,(N/2)log2N=11264,N2/(N/2)log2N=392.4。FFT显然要比直接法快得多。20.(2)原位计算)原位计算当数据输入到存储器中以后,每一级运算的结果仍然储存在同一组存储器中,直到最后输出,中间无需其它存储器,这叫原位计算。每一级运算均可在原位进行,这种原位运算结构可节
10、省存储单元,降低设备成本,还可节省寻址的时间。(考填空题)21.(3)序数重排)序数重排对按时间抽取FFT的原位运算结构,当运算完毕时,正好顺序存放着X(0),X(1),X(2),X(7),因此可直接按顺序输出,但这种原位运算的输入x(n)却不能按这种自然顺序存入存储单元中,而是按x(0),x(4),x(2),x(6),x(7)的顺序存入存储单元,这种顺序看起来相当杂乱,然而它也是有规律的。当用二进制表示这个顺序时,它正好是“码位倒置”的顺序。例如,原来的自然顺序应是x(1)的地方,现在放着x(4),用二进制码表示这一规律时,则是在x(001)处放着x(100),x(011)处放着x(110)
11、。22.表码位倒置顺序自然顺序二进码表示码位倒置码位倒置顺序0000000010011004201001023011110641000011510110156110010371111117在实际运算中,一般直接将输入数据x(n)按码位倒置的顺序排好输入很不方便,总是先按自然顺序输入存储单元,然后再通过变址运算将自然顺序的存储转换成码位倒置顺序的存储,然后进行FFT的原位计算。目前有许多通用DSP芯片支持这种码位倒置的寻址功能。23.v第一次分偶、奇,根据最低位n0的0、1状态来分,若n0=0,则为偶序列;n0=1则为奇序列,得到两组序列:v000010100110001011101111v第二
12、次对这两个偶、奇序列再分一次偶、奇序列,这就要根据n1的、状态。若n1=0,则为偶序列;n1=1则为奇序列,得到四组序列:v000100010110001101011111v同理,再根据n2的、状态来分偶、奇序列,直到不能再分偶、奇时为止。对于N=8,n2已是最高位,最后一次分得结果为v00010001011000110101111124.(4)蝶形类型随迭代次数成倍增加)蝶形类型随迭代次数成倍增加观察8点FFT的三次迭代运算:第一级迭代,有一种类型的蝶形运算系数W08,两个数据点间隔为1第二级迭代,有二种类型的蝶形运算系数W08、W28,参加运算的两个数据点间隔为2。第三级迭代,有四类蝶形运
13、算系数W08、W18、W28、W38,参加运算的两个数据点间隔为4。结论:每迭代一次,蝶形类型增加一倍,数据点间隔也增大一倍。每一级的取数间隔和蝶形类型种类均为2i-1,i=1,2,M。25.3、按频率抽取的、按频率抽取的FFT(按输出(按输出X(k)在频域)在频域的顺序上属于偶数还是奇数分解为两组)的顺序上属于偶数还是奇数分解为两组)对于N=2M情况下的另外一种普遍使用的FFT结构是频率抽取法。对于频率抽取法,输入序列不是按偶数奇数,而是按前后对半分开,这样便将N点DFT写成前后两部分:26.又把X(k)进一步分解为偶数组和奇数组:=X(2r+1)=27.令a(n)=x(n)+x(n+N/2
14、)b(n)=x(n)-x(n+N/2wnN这两个序列都是N/2点的序列,将其代入上两式,得这正是两个N/2点的DFT运算,即将一个N点的DFT分解为两个N/2点的DFT,上式的运算关系可用下图表示.x1(n)+x2(n)WNnx1(n)x2(n)x1(n)-x2(n)WNn-128.以N=8的频率抽取为例x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)-1-1-1-1N/2点DFTa(0)a(1)a(2)a(3)N/2点DFTb(0)b(1)b(2)b(3)WN1WN2WN3X(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)按频率抽取将8点DFT分解成两个4点DF
15、T29.按频率抽取将8点DFT分解成四个2点DFT30.与时间抽取法一样,由于N=2M,N/2仍是一个偶数,这样,一个N=2M点的DFT通过M次分解后,最后只剩下全部是2点的DFT,2点DFT实际上只有加减运算。但为了比较,也为了统一运算的结构,仍用一个系数为W0N的蝶形运算来表示。频率抽取法的流图是时域抽取法流图的左右翻转。下图是N=8的频率抽取法FFT流图。N=8的按频率抽取FFT运算流图31.频率抽取法频率抽取法FFT的运算特点:的运算特点:(1)蝶形运算对于任何一个2的整数幂N=2M,总是可以通过M次分解最后完全成为2点的DFT运算。这样的M次分解,就构成从x(n)到X(k)的M级运算
16、过程。将频率抽取法的流图反转,并将输入变输出,输出变输入,得到的便是时间抽取法流图(反映了时域,频域的对称法)。频率抽取法也共有M级运算(N=2M),其运算量与时间抽取法相同。32.(2)原位计算类似于时间抽取法,当数据输入到存储器中以后,每一级运算的结果仍然储存在同一组存储器中,直到最后输出,中间无需其它存储器,所以频域抽取法也可进行原位算。33.(3)序数重排它的输入正好是自然顺序。但它的输出却是码位倒置的顺序。因此运算完毕后,要通过变址运算将码位倒置的顺序转换为自然顺序,然后输出,变址方法同时间抽取法。34.(4)蝶形类型随迭代次数成倍减少(与时间抽取法相反)第一级迭代中有N/2种蝶形运
17、算系数,参加蝶形运算的两个数据相隔N/2,随后每次迭代,蝶形类形比前一级减少一倍,间距也减少一倍,最后一级迭代,蝶形类形只有一种W0N,数据间隔为1。由这几点规律可以看出,频率抽取法与时间抽到法是两种等价的FFT运算。35.5.N为组合数的为组合数的FFT(任意基数的(任意基数的FFT算法)算法)以上讨论的都是以2为基数的FFT算法,即N=2M,这种情况实际上使用得最多。优点:程序简单,效率高,使用方便。实际应用时,有限长序列的长度N很大程度上由人为因素确定,因此多数场合可取N=2M,从而直接使用以2为基数的FFT算法。如N不能人为确定,N的数值也不是以2为基数的整数次方,处理方法有两种:补零
18、:将x(n)补零,使N=2M.例如N=30,补上x(30)=x(31)=0两点,使N=32=25,这样可直接采用以2为基数M=5的FFT程序。有限长度序列补零后并不影响其频谱X(ejw),只是频谱的采样点数增加了,上例中由30点增加到32点,所以在许多场合这种处理是可接受的。36.如要求准确的N点DFT值,可采用任意数为基数的FFT算法,其计算效率低于以2为基数FFT算法。如N为复合数,可分解为两个整数p与q的乘积,像前面以2为基数时一样,FFT的基本思想是将DFT的运算尽量分小,因此,在N=pq情况下,也希望将N点的DFT分解为p个q点DFT或q个p点DFT,以减少计算量。步骤:分别为0,1
19、,,Q-1;分别为0,1,,P-1。37.N点DFT可以重新写成为38.考虑到再令令39.以P=3,Q=4,N=12为例(1)先将x(n)通过x(n1Q+n0)改写成x(n1,n0)。因为 Q=4,n1=0,1,2,n0=0,1,2,3,故输入是按自然顺序的,即x(0,0)=x(0)x(0,1)=x(1)x(0,2)=x(2)x(0,3)=x(3)x(1,0)=x(4)x(1,1)=x(5)x(1,2)=x(6)x(1,3)=x(7)x(2,0)=x(8)x(2,1)=x(9)x(2,2)=x(10)x(2,3)=x(11)40.(2)求个点的DFT(3)X1(k0,n0)乘以得到X1(k0,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散 傅里叶变换 及其 快速 算法 概要
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。