FFT快速傅里叶变换解析课件.ppt
《FFT快速傅里叶变换解析课件.ppt》由会员分享,可在线阅读,更多相关《FFT快速傅里叶变换解析课件.ppt(51页珍藏版)》请在三一办公上搜索。
1、快速傅里叶变换FFT,yL,2013-9,快速傅里叶变换FFTyL2013-9,我们关心的问题,快速解决多项式乘法问题衍生问题高精度乘法,我们关心的问题快速解决多项式乘法问题,问题的描述,记一个多项式次数界为n的多项式A(x)则其中a为每一项的系数注意最高次系数为n-1,问题的描述记一个多项式次数界为n的多项式A(x),问题的描述,两个多项式相乘我们记一般形式为C的次数界为A与B次数界的和普通的时间复杂度为O(n2),问题的描述两个多项式相乘,PART1中心思想,1 点值与插值2 N次单位复数根3 FFT4 演示,PART1中心思想1 点值与插值,转换思路,普通的相乘方法提出概念:点值,插值,
2、1 点值与插值2 N次单位复数根3 FFT4 演示,转换思路普通的相乘方法1 点值与插值,点值,一个次数界为n的多项式A(x)的点值表达就是一个由n个点值对所组成的集合:其中每一个x都不相同,且E.G.多项式 的一个合法点值表达是,1 点值与插值2 N次单位复数根3 FFT4 演示,点值一个次数界为n的多项式A(x)的点值表达就是一个由n个点,插值,插值运算是点值运算的逆运算假设我们得到了一个有n个点值对的点值表达那我们可以确定唯一的一个次数界为n的多项式,1 点值与插值2 N次单位复数根3 FFT4 演示,插值插值运算是点值运算的逆运算1 点值与插值,多项式乘法,我们来探究一下如何用点值与插
3、值来完成多项式乘法我们确定一组x,求得A与B的点值表达那我们可以得知C的点值表达通过插值运算,我们可以知道多项式C的系数,1 点值与插值2 N次单位复数根3 FFT4 演示,多项式乘法我们来探究一下如何用点值与插值来完成多项式乘法1,注意的地方,设A与B的次数界均为n则C的次数界为2n则我们要找出2n个x来求点值表达否则不可以进行插值运算,1 点值与插值2 N次单位复数根3 FFT4 演示,注意的地方设A与B的次数界均为n1 点值与插值,算法流程,对于次数界均为n的多项式A与B1点值运算构造长度为2n的点值表达2逐点相乘计算出C的点值表达3插值运算通过C的点值表达求出多项式C的每项系数,1 点
4、值与插值2 N次单位复数根3 FFT4 演示,算法流程对于次数界均为n的多项式A与B1 点值与插值,时间复杂度,可以证明,若选取n个x计算点值与插值的时间复杂度均为O(N2)本质上没有解决时间的问题但我们可以巧妙的选择这些数来优化时间复杂度。,1 点值与插值2 N次单位复数根3 FFT4 演示,时间复杂度可以证明,若选取n个x1 点值与插值,PART2N次单位复数根及其性质,1 点值与插值2 N次单位复数根3 FFT4 演示,PART2N次单位复数根及其性质1 点值与插值,N次单位复数根,n次单位复数根是满足 的复数w。n次单位复数根根恰好有n个,对于k=0, 1, . , n-1,这些根是
5、。为了解释这个表达式,我们利用复数的指数形式的定义:下一页图说明n个单位复数根均匀地分布在以复平面的原点为圆心的单位半径的圆周上。,1 点值与插值2 N次单位复数根3 FFT4 演示,N次单位复数根n次单位复数根是满足 的复数,N次单位复数根,1 点值与插值2 N次单位复数根3 FFT4 演示,N次单位复数根1 点值与插值,性质,我们需要N次单位复数根我们首先来探究这些根的性质,1 点值与插值2 N次单位复数根3 FFT4 演示,性质我们需要N次单位复数根1 点值与插值,性质1主n次单位根,我们称 为主n次单位根同时注意到,n次单位复数根都是经过旋转而得到的每次旋转都是一定角度n次单位复数根可
6、视为公比为主n次单位根的等比数列,1 点值与插值2 N次单位复数根3 FFT4 演示,性质1主n次单位根我们称 为主n次单,性质2群的性质,因为所以推论,1 点值与插值2 N次单位复数根3 FFT4 演示,性质2群的性质因为1 点值与插值,性质3消去引理&折半引理.,消去引理:推论:折半引理:如果n0为偶数,那么n次单位复数根的平方的集合就是n/2次单位复数根的集合。证明:可以知道 的平方相同。,1 点值与插值2 N次单位复数根3 FFT4 演示,性质3消去引理&折半引理.消去引理:1 点值与插值,性质4求和引理,求和引理:对于任意整数n1和不能被n整除的非负整数k,有等比数列求和所以注意k不
7、能是n的倍数,否则分母为0,1 点值与插值2 N次单位复数根3 FFT4 演示,性质4求和引理求和引理:对于任意整数n1和不能被n整除,PART3FFT及其关键算法,1 点值与插值2 N次单位复数根3 FFT4 演示,PART3FFT及其关键算法1 点值与插值,DFT离散傅里叶变换,我们希望计算次数界为n的多项式在n次单位复数根处的值(共n个)接下来定义结果yy即为a的离散傅里叶变换(DFT)我们也可记为,1 点值与插值2 N次单位复数根3 FFT4 演示,DFT离散傅里叶变换我们希望计算次数界为n的多项式1 点,FFT快速傅里叶变换,大前提:n为2的整数幂(方便计算)利用复数单位根复数根的特
8、殊性质我们可以在 时间内计算出FFT利用了分治策略,1 点值与插值2 N次单位复数根3 FFT4 演示,FFT快速傅里叶变换大前提:n为2的整数幂(方便计算)1,PART3.1点值运算,1 点值与插值2 N次单位复数根3 FFT4 演示,PART3.1点值运算1 点值与插值,分治策略,如何求出单个数x的函数值A(x)?我们定义两个新多项式观察两个多项式的特点1分别拥有奇数下标的系数与偶数下标的系数2次数界变为n/2(缩小了一半),1 点值与插值2 N次单位复数根3 FFT4 演示,分治策略如何求出单个数x的函数值A(x)?1 点值与插值,分治策略,对于一个数x,求A(x)则根据上两个多项式,1
9、 点值与插值2 N次单位复数根3 FFT4 演示,分治策略对于一个数x,求A(x)1 点值与插值,分治策略,至此我们成功的转换了问题原问题:求一个多项式A(x)在 的函数值。现问题:求两个多项式 在 的函数值。,1 点值与插值2 N次单位复数根3 FFT4 演示,分治策略至此我们成功的转换了问题1 点值与插值,分治策略,现问题:求两个多项式 在 的函数值。根据折半引理, 并不是n个不同的值,而是由n/2个n/2次单位复数根组成,而每个根恰好出现2次于是,我们递归地对n/2的多项式A0(x)与A1(x)在n/2个n/2次单位复数根进行求值,1 点值与插值2 N次单位复数根3 FFT4 演示,分治
10、策略现问题:求两个多项式,程序实现,1 点值与插值2 N次单位复数根3 FFT4 演示,程序实现1 点值与插值,我们关心的程序实现问题,1/2:规定程序递归出口3/4/12:定义主n次单位根,更新w值5/6/7/8:定义两个多项式并递归求解13:返回DFT9/10/11:递归结束后的处理工作,1 点值与插值2 N次单位复数根3 FFT4 演示,我们关心的程序实现问题1/2:规定程序递归出口1 点值与插值,递归结束后的处理工作,10:11:,1 点值与插值2 N次单位复数根3 FFT4 演示,递归结束后的处理工作10:1 点值与插值,FFT时间复杂度,对于运行时间有以下的递归式所以采用FFT,我
11、们可以在O(nlgn)时间内实现点值运算(求出次数界为n的多项式在n次单位复数根处的值)。,1 点值与插值2 N次单位复数根3 FFT4 演示,FFT时间复杂度对于运行时间有以下的递归式1 点值与插值,PART3.2插值运算,1 点值与插值2 N次单位复数根3 FFT4 演示,PART3.2插值运算1 点值与插值,矩阵乘积,我们可以把点值运算表示成一个矩阵方程我们把DFT写成矩阵乘积y=Vna,1 点值与插值2 N次单位复数根3 FFT4 演示,矩阵乘积我们可以把点值运算表示成一个矩阵方程1 点值与插值,逆矩阵,到此为止我们把插值运算改写成y与 的逆矩阵 的乘积,1 点值与插值2 N次单位复数
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- FFT 快速 傅里叶变换 解析 课件
链接地址:https://www.31ppt.com/p-1284712.html