FFT快速傅里叶变换解析课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《FFT快速傅里叶变换解析课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- FFT 快速 傅里叶变换 解析 课件
- 资源描述:
-
1、快速傅里叶变换FFTyL2013-9我们关心的问题u快速解决多项式乘法问题u衍生问题高精度乘法问题的描述u记一个多项式次数界为n的多项式A(x)u则u其中a为每一项的系数u注意最高次系数为n-110)(njjjxaxA问题的描述u两个多项式相乘u我们记一般形式为uC的次数界为A与B次数界的和u普通的时间复杂度为O(n2)()()(xBxAxCPART1中心思想2 N次单位复数根3 FFT4 演示转换思路u普通的相乘方法u提出概念:点值,插值ijjijibac02 N次单位复数根3 FFT4 演示点值u一个次数界为n的多项式A(x)的点值表达就是一个由n个点值对所组成的集合:u其中每一个x都不相
2、同,且uE.G.u多项式 的一个合法点值表达是),(,),(),(111100nnyxyxyx)(kkxAy 23)(2xxxA)12,5(),2,0(2 N次单位复数根3 FFT4 演示插值u插值运算是点值运算的逆运算u假设我们得到了一个有n个点值对点值对的点点值表达值表达u那我们可以确定唯一的一个次数界为n的多项式2 N次单位复数根3 FFT4 演示多项式乘法u我们来探究一下如何用点值与插值来完成多项式乘法u我们确定一组x,求得A与B的点值表达u那我们可以得知C的点值表达u通过插值运算,我们可以知道多项式C的系数),(,),(),(:111100nnyxyxyxA),(,),(),(:11
3、1100nnyxyxyxB),(,),(),(:111111000nnnyyxyyxyyxC2 N次单位复数根3 FFT4 演示注意的地方u设A与B的次数界均为nu则C的次数界为2nu则我们要找出2n个x来求点值表达u否则不可以进行插值运算2 N次单位复数根3 FFT4 演示算法流程u对于次数界均为n的多项式A与Bu1点值运算u构造长度为2n的点值表达u2逐点相乘u计算出C的点值表达u3插值运算u通过C的点值表达求出多项式C的每项系数2 N次单位复数根3 FFT4 演示时间复杂度u可以证明,若选取n个xu计算点值与插值的时间复杂度均为O(N2)u本质上没有解决时间的问题u但我们可以巧妙的选择这
4、些数来优化时间复杂度。2 N次单位复数根3 FFT4 演示PART2N次单位复数根及其性质1 点值与插值3 FFT4 演示N次单位复数根un次单位复数根是满足 的复数w。un次单位复数根根恰好有n个,对于k=0,1,.,n-1,这些根是 。为了解释这个表达式,我们利用复数的指数形式的定义:u下一页图说明n个单位复数根均匀地分布在以复平面的原点为圆心的单位半径的圆周上。1nwnike/2)sin()cos(uiueiu1 点值与插值3 FFT4 演示N次单位复数根28w18w08w78w68w58w48wii38w,N1210nnnnnwwww次单位复数根为我们记1 点值与插值3 FFT4 演示
5、性质u我们需要N次单位复数根u我们首先来探究这些根的性质1 点值与插值3 FFT4 演示性质1主n次单位根u我们称 为主n次单位根u同时注意到,n次单位复数根都是经过旋转而得到的u每次旋转都是一定角度un次单位复数根可视为公比为主n次单位根的等比数列1nnww nininwww11 点值与插值3 FFT4 演示性质2群的性质u因为u所以u推论10nnnwwnkjnkjnknjnwwwwmod)(nknknwwknknww22)(1 点值与插值3 FFT4 演示11nnnww性质3消去引理&折半引理.u消去引理:u推论:u折半引理:如果n0为偶数,那么n次单次单位复数根位复数根的平方的集合就是n
6、/2次单位复次单位复数根数根的集合。u证明:可以知道 的平方相同。kndkdnww122/wwnn)2/(nknknww与222222/)()(knknnnknnknnknwwwwwwknknww2/2)(1 点值与插值3 FFT4 演示性质4求和引理u求和引理:对于任意整数n1和不能被n整除的非负整数k,有u等比数列求和u所以u注意k不能是n的倍数,否则分母为0100)(njjknw011)1(11)(11)()(10knkknknnknnknnjjknwwwwww1 点值与插值3 FFT4 演示PART3FFT及其关键算法1 点值与插值2 N次单位复数根4 演示DFT离散傅里叶变换u我们希
7、望计算次数界为n的多项式u在n次单位复数根处的值(共n个)u接下来定义结果yuy即为a的离散傅里叶变换(DFT)u我们也可记为10)(njjjxaxA10)(njkjnjknkwawAy)(aDFTyn1 点值与插值2 N次单位复数根4 演示FFT快速傅里叶变换u大前提:n为2的整数幂(方便计算)u利用复数单位根复数根的特殊性质u我们可以在 时间内计算出uFFT利用了分治策略)lg(nnO)(aDFTn1 点值与插值2 N次单位复数根4 演示PART3.1点值运算1 点值与插值2 N次单位复数根4 演示分治策略u如何求出单个数x的函数值A(x)?u我们定义两个新多项式u观察两个多项式的特点u1
8、分别拥有奇数下标的系数与偶数下标的分别拥有奇数下标的系数与偶数下标的系数系数u2次数界变为次数界变为n/2(缩小了一半)(缩小了一半)12/12531112/224200)()(nnnnxaxaxaaxAxaxaxaaxA1 点值与插值2 N次单位复数根4 演示分治策略u对于一个数x,求A(x)u则根据上两个多项式)()()(2120 xxAxAxAy1 点值与插值2 N次单位复数根4 演示分治策略u至此我们成功的转换了问题u原问题:求一个多项式A(x)在 的函数值。u现问题:求两个多项式 在 的函数值。110,nnnnwww)(A)(10 xxA与212120)(,)(,)(nnnnwww1
9、 点值与插值2 N次单位复数根4 演示分治策略u现问题:求两个多项式 在 的函数值。u根据折半引理,并不是n个不同的值,而是由n/2个n/2次单位复数根组成,而每个根恰好出现2次u于是,我们递归地对n/2的多项式A0(x)与A1(x)在n/2个n/2次单位复数根进行求值)(A)(10 xxA与212120)(,)(,)(nnnnwww212120)(,)(,)(nnnnwww1 点值与插值2 N次单位复数根4 演示程序实现1 点值与插值2 N次单位复数根4 演示我们关心的程序实现问题u1/2:规定程序递归出口u3/4/12:定义主n次单位根,更新w值u5/6/7/8:定义两个多项式并递归求解u
10、13:返回DFTu9/10/11:递归结束后的处理工作1 点值与插值2 N次单位复数根4 演示递归结束后的处理工作u10:u11:)()()(212010knknknknkknkkwAwAwwAywyy)()()()()()2/(21)2/(2021)2/(201)2/(010)2/(nknnknnknnknknnknknknknkkknknkwAwAwwAwAwwAywyywyy1 点值与插值2 N次单位复数根4 演示FFT时间复杂度u对于运行时间有以下的递归式u所以采用FFT,我们可以在O(nlgn)时间内实现点值运算(求出次数界为n的多项式在n次单位复数根处的值)。)lg()()2/(2
展开阅读全文