【原文:
http://blog.csdn.net/xiahouzuoxin/article/details/9790455】
傅里叶变换或者FFT的理论参考:
[1]
http://www.dspguide.com/ch12/2.htm
The Scientist and Engineer's Guide to Digital Signal Processing, By Steven
W. Smith, Ph.D.
[2]
http://blog.csdn.net/v_JULY_v/article/details/6196862,可当作[1]的中文参考
[3] 任意一本数字信号处理教材,上面都有详细的推导DCT求解转换为FFT求解的过程
[4] TI文档:基于TMS320C64x+DSP的FFT实现。 使用baidu/google可以搜索到。
另外,FFT的开源代码可参考:
[1]
FFTW: http://www.fftw.org/ 最快,最好的开源FFT。
[2]
FFTReal: http://ldesoras.free.fr/prod.html#src_fftreal 轻量级FFT算法实现
[3]
KISS FFT: http://sourceforge.net/projects/kissfft/ 简单易用的FFT的C语言实现
1. 有关FFT理论的一点小小解释
关于FFT这里只想提到两点:
(1)DFT变换对的表达式(
必须记住)
—— 称旋转因子
(2)FFT用途——目标只有一个,加速DFT的计算效率。
DFT计算X(k)需要N^2次复数乘法和N(N-1)次复数加法;FFT将N^2的计算量降为
。
“
FFT其实是很难的东西,即使常年在这个领域下打拼的科学家也未必能很好的写出FFT的算法。”——摘自参考上面提供的参考文献[1]
因此,我们不必太过纠结于细节,当明白FFT理论后,将已有的算法挪过来用就OK了,不必为闭着教材写不出FFT而郁闷不堪。
FFT的BASIC程序伪代码如下:
IFFT的BASIC程序伪代码如下(IFFT通过调用FFT计算):
FFT算法的流程图如下图,总结为3过程3循环:
(1)3过程:单点时域分解(倒位序过程) + 单点时域计算单点频谱 + 频域合成
(2)3循环:外循环——分解次数,中循环——sub-DFT运算,内循环——2点蝶形算法
分解过程或者说倒位序的获得参考下图理解:
2. FFT的DSP实现
下面为本人使用C语言实现的FFT及IFFT算法实例,能计算任意以2为对数底的采样点数的FFT,算法参考上面给的流程图。
[cpp] view
plaincopyprint?
-
-
-
-
-
-
-
-
#ifndef ZX_FFT_H_
-
#define ZX_FFT_H_
-
-
typedef float FFT_TYPE;
-
-
#ifndef PI
-
#define PI (3.14159265f)
-
#endif
-
-
typedef struct complex_st {
-
FFT_TYPE real;
-
FFT_TYPE img;
-
} complex;
-
-
int fft(complex *x, int N);
-
int ifft(complex *x, int N);
-
void zx_fft(void);
-
-
#endif /* ZX_FFT_H_ */
[cpp] view
plaincopyprint?
-
-
-
-
-
-
-
-
-
-
-
#include "zx_fft.h"
-
#include
-
#include
-
-
-
-
-
-
-
-
-
-
-
-
-
static void BitReverse(complex *x, complex *r, int n, int l)
-
{
-
int i = 0;
-
int j = 0;
-
short stk = 0;
-
static complex *temp = 0;
-
-
temp = (complex *)malloc(sizeof(complex) * n);
-
if (!temp) {
-
return;
-
}
-
-
for(i=0; i
-
stk = 0;
-
j = 0;
-
do {
-
stk |= (i>>(j++)) & 0x01;
-
if(j
-
{
-
stk <<= 1;
-
}
-
}while(j
-
-
if(stk < n) {
-
temp[stk] = x[i];
-
}
-
}
-
-
for (i=0; i
-
r[i] = temp[i];
-
}
-
free(temp);
-
}
-
-
-
-
-
-
-
-
-
-
-
int fft(complex *x, int N)
-
{
-
int i,j,l,ip;
-
static int M = 0;
-
static