定理 FFT高效实现 任意给定阶为n的向量a和b,其中n是2的密,有 由于FFT在信号处理等方面有相当大的需 a8b= DFT(DFTn(a)-DFT2n(b) 求,故其高效实现有非常重要的意义。 过精心设计可以让复杂度系数变得更小 其中我们把a和b前面用0补足到2n长。 著名的蝴蝶操作:左边两个输 分治的递归调用图【n=8】 入,y1乘以onk 一 循环实现 FFT-BASE(A) 1n∈ length(a]∥ n is a power of2. 递归实现中的10-13 2fors∈1 to Ig n do 行的优化:相同乘法 do Ioy 5tork∈oton-1 by m do orj∈otom2-1co7 定理 • 任意给定阶为n的向量a和b，其中n是2的密，有 • 其中我们把a和b前面用0补足到2n长。 FFT高效实现 • 由于FFT在信号处理等方面有相当大的需 求，故其高效实现有非常重要的意义。通 过精心设计可以让复杂度系数变得更小。 著名的蝴蝶操作：左边两个输 入 ，yk [1]乘以ωn k 分治的递归调用图【n=8】 循环实现 • 递归实现中的10－13 行的优化：相同乘法 只做一次 FFT-BASE(A) • 1 n Å length[a] // n is a power of 2. • 2 for s Å 1 to lg n do • 3 m Å 2s • 4 ωm Å e2π i/m • 5 for k Å 0 to n - 1 by m do • 6 ω Å 1 • 7 for j Å 0 to m/2 - 1 do • 8 t Å ω A[k + j + m/2] • 9 u Å A[ k + j] • 10 A[k + j] Å u + t • 11 A[k + j + m /2] Å u - t • 12 ω Å ωωm