中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr DFT的顺序代码 代码1 代码2 for j=o to n-1 do W=w bj]=0 for j=o to n-1 do for k=o to n-1 do []=0 S=00 b[jb[j]+wkJa[k for k=o to n-1 do end for b[J=b[J]+s*a[k] end for S=SW 注:代码1需要计算uJ end for 代码2的复杂度为O(n2) W=WW end for 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 7 2021/2/19 DFT的顺序代码 ▪ 代码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 注：代码1需要计算ωk*j 代码2的复杂度为O(n2) ▪ 代码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
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 111快速傅里叶变换(FFT 1111离散傅里叶变换(DFT) 1112DFT的顺序代码 111.3串行FFT递归算法 111.4串行FFT井递归算法
11.1 快速傅里叶变换(FFT) 11.1.1 离散傅里叶变换(DFT) 11.1.2 DFT的顺序代码 11.1.3 串行FFT递归算法 11.1.4 串行FFT非递归算法
中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 串行FT递归算法 ■蝶式递归计算原理 令O=已2x1m2)为n/2次单位元根,则有O=O 将b向量的偶数项(b,b2,bn2)和奇数项(b,b3bn)分别记为 (b,2)和(b,b…,b 注意推导中反复使用O"=1,om2 3 4 8 (1,0) 7 国家高性能计算中心(合肥 O=(0,-1)2021/2/19
国家高性能计算中心（合肥） 9 2021/2/19 串行FFT递归算法 ▪ 蝶式递归计算原理 令 为n/2次单位元根，则有 . 将b向量的偶数项 和奇数项 分别记为 和 注意推导中反复使用 ~ 2 i /(n / 2) e ＝ ~ 2 ＝ T n (b ,b ,...,b ) 1 3 −1 T (b ,b ,...,bn ) 0 1 1 2 − T (b ,b ,...,bn ) 0 1 1 2 − 1, 1, 1, , n n/ 2 l n s n p p = = − = = + ω8 =(1,0) ω6 =(0,-i) ω2 =( 0,i) ω4 =(-1,0) ω7 ω3 ω5 ω1 图11.1 T n (b ,b ,...,b ) 0 2 −2
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 串行FT递归算法 偶数时:b=b=∑ o d k=0 +oa+0 a+...+0 a., a. +a + a (ao+a2)+(a1+a1)+o(a2+a+2)+ (-1 (a1+an1) (ao+a2)+o(a1+a4+1)+o(a2+a2+2)+ (a, +a ∑o( 1=0,1, 因此,向量(bnx…,b2)是(a0+a241+41x,41+an)的DFT 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 10 2021/2/19 串行FFT递归算法 ( ) ( ) ( ) ( ) b b b a a a a a a DFT a a l a a a a a a a a a a a a a a a a a a a a a a a a b b a T n T n n k k k k l n l l l n l l l n l l l l l l n k k l k l l n n n n n n n n n n n n n n n n n n n n n 因此，向量 是 的 偶数时： ( , ,..., ) ( , ,..., ) ( ) 0,1, , 1 ~ ( ) ~ ( ) ~ ( ) ~ ( ) ( ) ( ) ( ) ( ) 0 2 2 0 1 1 1 1 2 1 0 1 1 1 2 2 2 0 1 1 1 1 2 1 2 2 4 1 1 2 0 1 2 1 2 4 1 2 1 2 1 2 4 1 2 0 1 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 − + − − − = + − − − + + − − − + + − − + + − − − = + + + = + = − + + = + + + + + + + + = + + + + + + + + + + = + + + + + = =
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 串行FT递归算法 奇数时:b"=b2=∑ 2+1)k =a0+Oa1+ 2(2/+1) (-121+1) a.,+ (2/+1 (+12/+1) a +o a.,+…+O (n-1)(2l+1) a0+o 0a,+002a+or(e202-ag-1 a -o ad +1 (ao-a4)+OO(a1-a2)+o-( +oo(a1-a1)+2o2( ∑bo'(a4-ak) 7=0,1,…,2-1 k=0 因此,向量(b,b3,…,bh)是(a0-a1)O(a1-a41)…,O(a41-an)的DFT 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 11 2021/2/19 串行FFT递归算法 ( ) ( ) ( ) ( ) ( ) ( ) ( ) b b b a a a a a a DFT a a l a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a b b a T n T n n k k k k l k n l l l n l l l n l l l l l n n l l l l l l n k k l k l l n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n 因此，向量 是 的 奇数时： ( , ,..., ) (( ), ( ),..., ( )) ( ) 0,1, , 1 ~ ( ) ~ ( ) ~ ( ) ~ ( ) ( ) ( ) ( ) ( ) 1 1 1 1 3 1 0 1 1 2 1 0 1 1 1 1 2 2 2 2 0 1 1 1 1 2 1 1 2 2 4 2 1 1 2 0 1 2 1 1 1 2 1 2 1 1 2 4 2 1 2 0 1 1 (2 1) 1 (2 1) 1 (2 1) 1 1 (2 1) 2 2(2 1) 1 2 1 0 1 0 (2 1) 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 − − − − + − = + − − − − + + − − − − + + − − − + − − − − − + + + + + − + + − + − = + + − − − = − = − = − + − + − + + − = − + − + − + + − − − − = + + + + − + + + = + + + + + = =