按以上方法反复的分解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并四舍五入
上一篇:渥拉斯顿棱镜透射光强扰动分析+文献综述
下一篇:含葡萄糖的混浊液后向散射特性的Mueller矩阵实验研究

基于大概念的初中科学教材分析力学相关部分

二三维一体化CAD系统中工...

基于初中科学实验教具的创新

基于landsat8遥感影像的水稻田降温效应研究

基于大概念的初中科学教材分析

FLUENT基于CFD圆柱绕流数值模拟研究

光波单向波导的设计与实现

10万元能开儿童乐园吗,我...

医院财务风险因素分析及管理措施【2367字】

承德市事业单位档案管理...

神经外科重症监护病房患...

AT89C52单片机的超声波测距...

公寓空调设计任务书

国内外图像分割技术研究现状

中国学术生态细节考察《...

C#学校科研管理系统的设计

志愿者活动的调查问卷表