按以上方法反复的分解N点DFT成N/4点DFT直到 N=4，使得N点傅立叶变换的运算复杂度由原来的 降到 。下图演示了N=16点FFT的分解运算过程。
 
从图中可以看出，输出数据的顺序也被打乱了。这种乱序其实有规律，我们把顺序的序号用二进制数列在下表中的左边，把乱序的序号用二进制数列在下表中的右边。从表中我们可以看出，乱序序号的二进制码可由顺序序号的二进制码以 2比特为单位反转得到。
正常序列    正常序列二进制    反转序列二进制    反转序列
0    00 00    00 00    0
1    00 01    01 00    4
2    00 10    10 00    8
3    00 11    11 00    12
4    01 00    00 01    1
5    01 01    01 01    5
6    01 10    10 01    9
7    01 11    11 01    13
8    10 00    00 10    2
9    10 01    01 10    6
10    10 10    10 10    10
11    10 11    11 10    14
12    11 00    00 11    3
13    11 01    01 11    7
14    11 10    10 11    11
15    11 11    11 11    15

4.3  混合基2和基4 FFT
如果N= , 傅立叶变换可被分解成 个基4 FFT和最后一级的一个基2 FFT。下图演示了N=32点FFT的分解运算过程。
 
值得注意的是，在第一级中，每个蝶形运算的旋转因子都不一样；在第二级，四组蝶形运算使用相同的旋转因子。下一级每一组中的不同蝶运算仍使用不同的旋转因子，但是不同的蝶形组使用的是相同的一组旋转因子。重复以上规则，可得到下面的表，这个表表达了旋转因子组和FFT级之间的关系：
级数    每组中蝶的个数    蝶形组的个数    蝶的总数
1    N/4    1    N/4
2    N/16    4    N/4
…    …    …    …
 
1    N/4    N/4
FFT的实现代码利用以上关系来减少旋转因子的访问，即每一级中相同的旋转因子只读取一次，然后给所有使用这个相同旋转因子的蝶形运算用。
4.4  逆变换
逆向DFT也可以类似地按前面介绍的方法来实现。IFFT和FFT实现上的主要区别是：
（1）输出结果除N
（2）旋转因子 变成了
另外，IFFT也可以用FFT函数来计算：
     实现方法是，先把输入数据取复共轭，执行 FFT，再对结果取复共轭并除 N。但，如果输入和输出数据的复共轭计算不方便的话，就需要用专门的代码来实现 IFFT。
5  TMS320C6678上的算法实现
5.1  C6000+函数库里的FFT函数
下表总结了C6000+系列DSP库dsplib里的FFT函数：
函数    说明
Void DSP_fft16x16(
short *w, int nx, short *x, short *y)    16 bits 复输入输出数据，复数按先实部/后虚部交织存放 ；
除最后一级外，每级的结果右移 1并四舍五入 基于DSP实现的移动场景的相位配准(6):http://www.youerw.com/wuli/lunwen_1614.html