ERATIVE-FFT(a Bit-reverse位反转] IT-REVERSE-COPY(a, A) n length(a] /n is a power of 2 ·001→100 011110 100→001 k的位反转记为rev(k) Aku+ 把lgn位长度的数字按照二进制数进行位反 转,递归图的顺序排列就是一个位反转排 BIT-REVERSE-COPY(a, A) Parallel ffT to n-1 do 3A[rev(∈a 总结 多项式的表示可以有多种 多项式的乘法可以利用FFT加快计算速度 FFT是信号处理中非常普遍的运算,其速度 直接影响许多仪器的性能 ·换一种思路,开阔你的眼界 ·FFT的实现细节8 ITERATIVE-FFT(a) • 1 BIT-REVERSE-COPY (a, A) • 2 n Å length[a] //n is a power of 2. • 3 for s Å 1 to lg n do • 4 m Å 2s • 5 ωm Å e2 π I /m • 6 ω Å 1 • 7 for j Å 0 to m/2 - 1 do • 8 for k j to n - 1 by m do • 9 t Å ω A[k + m/2] • 10 u Å A[k] • 11 A[k] Å u + t • 12 A[k + m/2] Å u - t • 13 ω Å ωωm • 14 return A Bit-reverse[ reverse[位反转] • 001Æ100 • 010Æ010 • 011Æ110 • 100Æ001 • ……，k的位反转记为rev（k） • 把lgn位长度的数字按照二进制数进行位反 转，递归图的顺序排列就是一个位反转排 列 BIT-REVERSE-COPY(a, A) • 1 n Å length[a] • 2 for k Å 0 to n - 1 do • 3 A[rev(k)] Å ak Parallel FFT 总结 • 多项式的表示可以有多种 • 多项式的乘法可以利用FFT加快计算速度 • FFT是信号处理中非常普遍的运算，其速度 直接影响许多仪器的性能 • 换一种思路，开阔你的眼界 • FFT的实现细节