https://blog.csdn.net/qq_42604176/article/details/105559756

设序列点数：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。

1、通过(N/2)*M个蝶形运算完成。（N/2:行数的一半，M：列数，运算的级数） 都有这样的迭代运算： 2、DIT与DIF方法异同点： 【1】：DIF：输入自然序列，输出倒位序列。 DIT：输入倒位序列，输出自然序列。 （本质上都是重新排序） 【2】：基本蝶形运算单元不同： DIF:复数乘积只出现在减法运算之后 DIT:先做复数乘法运算，再做加减法 【3】：运算量相同 【4】：都需要进行变址运算，且转换的方法是一样的 【5】：DIT、DIF的基本蝶形互为转置

转置：流图中所有支路方向都反向，并且交换输入输出。节点变量值不做变换。

————————————————————————————————————————————————————————————— 参考资料：

《数字信号处理第三版.刘顺兰版》