有哪些信誉好的足球投注网站- 1、本文档共26页，可阅读全部内容。
- 2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
查看更多
14.1快速傅里叶变换(FFT)
《并行算法》 * / Ch14 《并行算法》 * / Ch14 * Parallel Algorithms Chapter 14 Fast Fourier Transform Spring, 2017 * 讲授内容 14.1 快速傅里叶变换(FFT) - 离散傅里叶变换(DFT) - DFT的顺序代码 - 串行FFT递归算法 - 串行FFT非递归算法 14.2 DFT直接并行算法 - SIMD-MT上的并行DFT算法 14.3 并行FFT算法 - SIMD-MC2上的FFT算法 - SIMD-BF上的FFT算法 * 14.1 快速傅里叶变换(FFT) 1.离散傅里叶变换(DFT) - DFT定义 给定向量A=(a0,a1,…,an-1)T,DFT将A变换为B=(b0,b1,…,bn-1)T * 14.1 快速傅里叶变换(FFT) 2. DFT的顺序代码: 直接计算DFT需要O(n2)时间(代码2) 代码1 for j=0 to n-1 do b[j]=0 for k=0 to n-1 do b[j]=b[j]+ωk*ja[k] end for end for 代码2 w=ω0 for j=0 to n-1 do b[j]=0, s=ω0 for k=0 to n-1 do b[j]=b[j]+s*a[k] s=s*w end for w=w*ω end for * 14.1 快速傅里叶变换(FFT) * 14.1 快速傅里叶变换(FFT) * 14.1 快速傅里叶变换(FFT) * 14.1 快速傅里叶变换(FFT) (2)FFT的蝶式递归计算图(由蝶式递归计算原理推出) * 14.1 快速傅里叶变换(FFT) 特别地，n=8的FFT蝶式计算图(展开的) * 14.1 快速傅里叶变换(FFT) (3)SISD上的FFT分治递归算法 输入: A=(a0,a1,…,an-1); 输出: B=(b0,b1,…,bn-1) Procedure RFFT(a,b) begin if n=1 then b0=a0 else (1)RFFT(a0,a2,…,an-2, u0,u1,…,un/2-1) (2)RFFT(a1,a3,…,an-1, v0,v1,…,vn/2-1) (3)z=1 (4)for j=0 to n-1 do (4.1)bj=uj mod n/2+zvj mod n/2 (4.2)z=zω endfor 注: (1)算法时间复杂度t(n)=2t(n/2)+O(n) endif 解得 t(n)=O(nlogn) end (2)算法原理？ * 14.1 快速傅里叶变换(FFT) 4.串行FFT非递归算法 (1)蝶式计算示例 * 14.1 快速傅里叶变换(FFT) (2)蝶式计算流图 * 行0 行1 行2 行3 行4 行5 行6 行7 如: b6=[(a0+a4)-(a2+a6)]-[(a1+a5)-(a3+a7)]ω2 注: ①下行线结点处的权因子的确定问题； ②bi的下标确定:取行号的位序反。如，行3: 3=(011)2 == (110)2=6, == 行3的输出为b6 14.1 快速傅里叶变换(FFT) * 14.1 快速傅里叶变换(FFT) (3)蝶式计算的串行非递归FFT算法(算法14.1) begin //输入(a0,a1,…,an-1), 输出(b0,b1,…,bn-1) (1)for k=0 to n-1 ck?ak endfor //O(n) (2)for h=logn-1 down to 0 do //
文档评论（0）