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