3.13快速傅里叶变换 思路 将傅里叶变换分成二个步骤计算,每个步骤用一个1D变换实现; 先算行,后算列; 1D变换的逐次加倍法 已知F(u)=(1/N)∑f(x)exp[-2jux/N], 令WN=exp[2ji/N,得F(u)=(1/N)∑f(x)WN; 再令N=2M,得F(u)=(1/2M)∑f(x)W2Mx; (1/2){(1/M)∑f(2X)W2M1"(2×+ ;偶部分 (1/M)∑f(2X+1)W2Mu(2x+1)};奇部分 (1/2) (u)+F odd (u) 2M§3.1.3 快速傅里叶变换 • 一、思路 • 将傅里叶变换分成二个步骤计算，每个步骤用一个1D变换实现； 先算行，后算列； • 二、1D变换的逐次加倍法 • 已知F（u）= （1/N） f（x）exp[-2jux/N] ， • 令WN= exp[-2j/N]，得F（u）= （1/N） f（x） WN ux ； • 再令N=2M，得F（u）= （1/2M） f（x） W2M ux ； • =（1/2）{（1/M）  f（2x） W2M u（2x）+ ；偶部分 • （1/M）  f（2x+1） W2M u（2x+1） } ；奇部分 • = （1/2）{Feven（u）+ Fodd（u） W2M u }；