【1】回顾DIT
https://blog.csdn.net/qq_42604176/article/details/105559756
【2】算法原理
设序列点数：N=2^M,M为正整数。将输入序列按照前一半、后一半分开。（并非按照奇偶分）
由于
，所以化简为：
按照k奇数偶数进行分类讨论：
注意，此时X(2r)：前半输入与后半输入之和的N/2点DFT
X(2r+1)：前半输入与后半输入之差的与WN^n之积的N/2点DFT；
将括号内的式子写作整体：
基本的蝶形运算单元：
以N=8为例，展示出1级，2级，3级分解层次：
1、第一次分解
2、第二次分解：
3、第三次分解：
由于N=2^M,N/2仍然为偶数，将N/2点DFT输出再次分解，一直进行到第M次，第M次做两点DFT。
【3】运算特点
1、通过(N/2)*M个蝶形运算完成。（N/2:行数的一半，M：列数，运算的级数）
都有这样的迭代运算：
2、DIT与DIF方法异同点：
【1】：DIF：输入自然序列，输出倒位序列。
DIT：输入倒位序列，输出自然序列。
（本质上都是重新排序）
【2】：基本蝶形运算单元不同：
DIF:复数乘积只出现在减法运算之后
DIT:先做复数乘法运算，再做加减法
【3】：运算量相同
【4】：都需要进行变址运算，且转换的方法是一样的
【5】：DIT、DIF的基本蝶形互为转置
转置：流图中所有支路方向都反向，并且交换输入输出。节点变量值不做变换。
—————————————————————————————————————————————————————————————
参考资料：
《数字信号处理第三版.刘顺兰版》