基于DSP实现的移动场景的相位配准(6)
按以上方法反复的分解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并四舍五入