文档介绍：第十一章快速傅里叶变换
习题例题:
试计算下属序列的DFT:
(13,17,19,23)
(2,1,3,7,5,4,0,6)
试计算下述序列的逆DFT:
( 16, - + , -6+6i, -+, 0, --, -6-6i, -- )
( 4-i, 2+i, 2+i, -i 4-i, 2+i, 2+i, -i, )
,设计一个单处理机上时间为((nlogn)的离散傅氏逆变换算法;并以n = 8为例。画出其逆变换蝶氏计算流图。
Cormen曾给了另一种形式的FFT递归算法:
试分析此算法的执行过程;
?
按此算法画出n = 8的FFT蝶氏计算流图。
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
,逐步计算 n – 8的FFT,并画出其蝶氏计算流图。
令 n = 8 = 2k ,在蝶式网络上,按照exp(r,i) = j (0≤i≤n-1,0≤r≤k)的计算方法,试计算分布在蝶形网络中的8点FFT的系数矩阵元素wj。