kN2kXkX1kWNX2kX1kWNX2kk0112222
（11）通过上面的推导可以看出，一个N点的DFT可以分解为两个N2点的DFT，每个N2点的DFT又可以分解为两个N4点的DFT。以此类推，当N为2的整数次幂时（N2M），由于每分解一次降低一阶幂次，所以通过M次分解，最后全部成为一系列2点的DFT运算，以上就是按时间抽取的FFT算法。22DFFT以MN图形为例，将式（1）推广，可得2DFFT式：
Fuvfxyej2uxMvyN
x0y0
M1N1
u01M1（12）v01N1
将式（12）写成如下的分离形式：
Fuvej2uxMfxyej2vyN
x0y0
M1
N1
u01M1v01N1
（13）
由上述分离形式可知一个2DDFT可由连续2次运用1DDFT来实现。如式（13）可分成下列两式：
Fxvfxyej2vyN
y0
N1
v012N1
u01M1v01N1
（14）
FuvFxvej2uxM
x0
M1
（15）
对每个x值，式（14）方括号中是一个1DDFT。所以Fxv可由沿fxy的每一列求变换得到。在此基础上，再对Fxv的每一行求变换就可得到Fuv。由上述可知，对于2DFFT同样可以采取分别进行2次1DFFT来得到。
f3数字图像FFT流程图根据图像阵列的特性，对其按下列步骤进行FFT变换：（1）将图像数据阵列变换为按列存储，即从下到上，从左到右；（2）对每一列图像数据进行1DFFT；（3）将按列处理后的数据结果存储，并对它们按原图像阵列的形式，即按行重新存储；（4）对重新排列的数据逐行进行1DFFT；（5）将每行处理后的数据存储起来，即得到2D数字图像FFT结果。对一幅m
图像进行FFT其流程图如下所示：
图22DFFT流程图其中的1DFFT需要倒位序和递推计算，它们的流程图如下：
f图31DFFT流程图1DFFT中整个L级递推过程由三个嵌套循环构成。外层的一个循环控制LL
log2N级的顺序循环；内层的两个循环控制同一级各蝶形结的运算，其中最内
r一层循环控制同一种（指WN的同一个r）蝶形结的运算，而中间一层循环则是r对不同种（即WN中的r不同）蝶形结做运算。
42D离散傅里叶反变换
1fxyFuvexpj2uxvyM（16）N
u0v0
N1N1
实验过程：二维离散傅里叶变换
f实验程序：aimread2jpegsubplot221imshowatitlr