1.简介
这一篇说到哪里就写到哪里，因为这个问题是信号处理的基本问题，也没什么太多好讲的，而且讲这个的文章也太多了。如果留意的话，放狗搜一下，还能发现有一本比较老的书：《快速傅里叶变换及其C程序》。
先摆出DFT与IDFT的定义：
对于，先假设
也是一个复数，那么每一个
就有n个点的
(是一个复数)求和，这一个点就需要N-1次加法运算和N次复数乘法运算。对于
(有n个点)，就总共需要
次复数乘法运算与
次复数加法运算了。
计算一下，对个点做DFT处理，就有
的复数乘法与
的加法运算。这种计算量对于DSP做实时处理而言将是灾难性的，所以就需要做优化，降低计算量。
这个时候，就由的设计的合理性来起作用了，因为
是无规律的，而
的可设计性很强。
做一个简单的示例，使用4点DFT来说后面的优化：
从这个示例来看，比较复杂，有，可是再代入
，再简单手算一下，可以得出一个等价关系：
，所以简化以上计算，就变为：
从这里就能看出本来需要次复数乘法与
次复数加法的运算最终变为1次复数乘法了，这明显提高了运算速率。注意到一点，缩减运算量主要是运用
的对称性。
继续这个例子，假设有4个点，值为：(2,3,3,2)，则计算结果为：
使用matlab编写以上程序，程序如下：
clc;
clear all;
format long;
N=4;
n=0:N-1;
xn=[2 3 3 2];
Xk=fft(xn)
2.算法提速
根据上面的基础，再来看一下，运用这种对称关系，能将上面的算法速率提高到多少。
还是摆公式：
=
这里，可以将一个复杂问题进行分解，令：
从上面的式子中，可以发现一个问题，从一个范围
变为范围为
了，因此，最终计算的
只能表示一般的数，为了补足另外一半的数据，需要自己重新扩展另外一半，也就是下面的式子。
另外：
故：
所以，从这里可以看出与
组合起来做一次蝶形运算，而该运算只需要一次复数运算即可。那么按照这样的方式推导，一共有
次运算，每次运算有
次复数运算，所以共有复数运算
次复数运算。顺便计算一下复数加法，即：
次。
到这一步，再去跟前面的计算量对比，可以发现，效率提高了很多了。
3.应用
这节主要说一下在TMS320C6748上的使用。
可以使用两个API来执行fft与ifft操作，分别如：
void DSPF_sp_fftSPxSP(int N, float *ptr_x, float *ptr_w, float *ptr_y,
unsigned char *brev, int n_min, int offset, int n_max);
void DSPF_sp_ifftSPxSP (int N, float *ptr_x, float *ptr_w, float *ptr_y,
unsigned char *brev, int n_min, int offset, int n_max);
如果要知道每一个代入参数来由，可以参考链接 ,另外提一句，在文档里面说了一个产生旋转因子的话:
void tw_gen (float *w, int n)//This is for FFT, IFF will be slightly different
其实fft与ifft都可以用此函数并只需产生一次，经过验证并没有问题。而旋转因子是怎么产生的，可以参考链接
4.参考资料
关于本小节的内容，可以参考书籍：《数字信号处理理论、算法与实现 第3版 [胡广书 编著]》
网友评论