中国科学技术大学：《并行计算 Parallel Computing》课程教学资源（习题）第十一章 快速傅里叶变换

第十一章快速傅里叶变换 习题例题: 试计算下属序列的DFT (a)(13,17,19,23) (b)(2,1,3,7,5,4,06) 2.试计算下述序列的逆DFT: (a)(16,-0.76+8.661,-6+61,-925+2.661,0,-9.25-2661,-6-61,-0.76-8661) (b)(4-1,2+i,2+i,-14-i,2+i,2+i,-,) 3.参照算法1.1,设计一个单处理机上时间为( nlogn)的离散傅氏逆变换算法;并以n=8为 例。画出其逆变换蝶氏计算流图 4. Cormen曾给了另一种形式的FFT递归算法: (a)试分析此算法的执行过程 (b)它和算法11.2有何区别 (c)按此算法画出n=8的FFT蝶氏计算流图。 算法11.7SIsD上 Cormen计算FFT算法 输入 输出:bo,b1,bn Begin ifn= l then return a (1)w=e2 (2)z=1 (3)a=(ao,a2,…,a2) (4)a=(a,a3,,.an1) (5)b0= RECURSⅤEFFT(a (6)bl= RECURSIvEFFT(all) (7) for k=0 to n/2-1 de (i) bk =be +zb (ii b +n/2=bi-zb! endfor (8)return b endif 5.根据算法11.2,逐步计算n-8的FFT,并画出其蝶氏计算流图 6.令n=8=2,在蝶式网络上,按照exp(r)=j(0≤i≤n-1,0≤r≤k)的计算方法,试 计算分布在蝶形网络中的8点FFT的系数矩阵元素w

第十一章 快速傅里叶变换 习题例题： 1. 试计算下属序列的 DFT： (a) (13,17,19,23) (b) (2,1,3,7,5,4,0,6) 2. 试计算下述序列的逆 DFT： (a) ( 16, -0.76 + 8.66i , -6+6i, -9.25+2.66i, 0, -9.25-2.66i, -6-6i, -0.76-8.66i ) (b) ( 4-i, 2+i, 2+i, -i 4-i, 2+i, 2+i, -i, ) 3. 参照算法 11.1,设计一个单处理机上时间为((nlogn)的离散傅氏逆变换算法;并以 n = 8 为 例。画出其逆变换蝶氏计算流图。 4. Cormen 曾给了另一种形式的 FFT 递归算法： (a) 试分析此算法的执行过程； (b) 它和算法 11.2 有何区别？ (c) 按此算法画出 n = 8 的 FFT 蝶氏计算流图。 算法 11.7 SISD 上 Cormen 计算 FFT 算法 输入：a0 , a1 , ... , an-1 输出：b0 , b1 ... , bn-1 Begin if n = 1 then return a else (1) w = e2πi/n (2) z=1 (3) a [0] = (a0 , a2 , ... , an-2) (4) a [1] = (a1 , a3 , ... , an-1) (5) b [0] = RECURSIVEFFT(a[0]) (6) b [1] = RECURSIVEFFT(a[1]) (7) for k=0 to n/2 -1 do (i) bk = b[0] k + zb[1] k (ii) bk + n/2 = b[0] k - zb[1] k (iii) z = z·w endfor (8) return b endif end 5. 根据算法 11.2，逐步计算 n – 8 的 FFT，并画出其蝶氏计算流图。 6. 令 n = 8 = 2k ，在蝶式网络上，按照 exp(r,i) = j (0≤i≤n-1,0≤r≤k)的计算方法，试 计算分布在蝶形网络中的 8 点 FFT 的系数矩阵元素 w j