3.3基2 DIT-FFT 算法
基2FFT要求DFT变换区间长度N=2M，M为自然数。DIT-FFT算法序列x(n)的N点DFT为
将上面的和式按n的奇偶性分解为
令x1(l)=x(2l),x2(l)=x(2l+1)，因为              ，所以上式可写成

按n的奇偶性将x(n)分解为两个N/2长的序列x1(l)和x2(l)，则N点DFT可分解为两个N/2点DFT来计算。用X1(k)和X2(k)分别表示x1(l)和x2(l)的N/2点DFT，即

并利用               X1(k)、X2(k)的隐含周期性可得到
    这样，就将N点DFT的计算分解为计算两个N/2点离散傅里叶变换X1(k)和X2(k)
    N=210=1024时，DIT-FFT的运算效率为
DFT的乘法次数
DIT-FFT的乘法次数

而当N =211=2048时有
3.4DIT-FFT的运算规律及编程思想
1.原位计算：观察每个蝶形的两个输入和两个输出，蝶形的输出可存入原输入数据所占存储单元利用同一组存储单元存储输入，输出数据的方法，称为原位（址）计算。（节约内存，节省寻址的时间）
2.旋转因子的变化规律：N点DIT-FFT运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子，称其为旋转因子，p称为旋转因子的指数。由于各级的旋转因子和循环方式都有所不同。为了编写计算程序，应先找出旋转因子   与运算级数的关系。用L表示从左到右的运算级数（L=1,2,…,M）。
图4.5 蝶形运算分级
由8点DIT-FFT运算流图可以发现，第L级共有2L-1个不同的旋转因子。
N=23=8时的各级旋转因子表示如下:
对N=2M的一般情况，第L级的旋转因子为
这样，就可按上面两个式子确定第L级运算的旋转因子。实际编程序时，
L为最外层循环变量。
3.蝶形运算规律：设序列x(n)经时域抽选（倒序）后，存入数组A中。如果蝶形运算的两个输入数据相距B个点，应用原位计算，则蝶形运算可表示成如下形式:
 
下标L表示第L级运算，AL(J)则表示第L级运算后数组元素A(J)的值（即第L级蝶形的输出数据）。而AL-1(J)表示第L级运算前A(J)的值（即第L级蝶形的输入数据）。
用实数运算完成上述蝶形运算，可按下面的算法进行：
设

式中，下标R表示取实部，I表示取虚部。
4.序列的倒序：DIT-FFT算法的输出X(k)为自然顺序，但为了适应原位计
算，其输入序列不是按x(n)的自然顺序排序，这种经过M-1次偶奇抽选后的排序称为序列x(n)的倒序（倒位）。 因此，在运算之前应先对序列x(n)进行倒序。由于N = 2M，因此顺序数可用M位二进制数（nM-1nM-2…n1n0）表示。M次偶奇时域抽选过程如图所示。第一次按最低位n0的0和1将x(n)分解为偶奇两组，第二次又按次低位n1的0，1值分别对偶奇组分解；依次类推，第M次按nM-1位分解，最后得到二进制倒序数。 
      
                      图5.1 形成例序的树状图(N = 23)
顺          序  倒          序
十进制数I  二进制数  二进制数  十进制数 J
按顺序输出

不按顺序排列

5.编程思想及程序框图，先从输入端（第1级）开始，逐级进行，共进行M级运算。在进行第L级运算时，依次求出B=2L-1个不同的旋转因子，每求出一个旋转因子，就计算完它对应的所有2M-L个蝶形。这样，可用三重循环程序实现DIT-FFT运算，程序框图如图程序运行后，数组A中存放的是x(n)的N点DFT，即X(k)=A(k)。