dit算法matlab仿真 结合二叉树

根据DIT算法的思想，可以将一个长度为2^n的序列不断地进行奇偶拆分，从而得到n个两点的序列。再对这n个两点序列计算DFT，根据上述公式对两点序列的DFT进行组合，即可得到n/2个四点序列的DFT，重复上述操作，最后即可得到原序列的DFT。由此也可看出这一过程是先将一个序列由上而下进行奇偶拆分，再自底向上两两组合，我们发现，用二叉树的遍历和回溯可以很好的描述这一过程。