|
详解快速傅里叶变换 FFT 算法
下面是部分内容预览：
快速傅里叶变换 FFT 是离散傅里叶变换 DFT 的一种快速算法，只有 FFT 才能在现实中有实际应用的意义。虽然许多学过数字信号处理这门课的同学都知道 DFT 和 FFT，但实际上真正理解其算法原理的屈指可数，绝大部分同学知其然而不知其所以然，况且限于高校课程教学体制，课堂上不可能把这些原理和算法讲得明明白白的。为此，特意以本文讲解 FFT 算法的原理与实际应用，给欲往电子信息类专业进修和发展的同学一些课外参考。
N点有限长序列x(n)的DFT 为
由此可见，一次复数乘法需要 4 次实数乘法和 2 次实数加减法。一次复数加法需要 2 次实数加法。所以每一个 X（k）计算需要 4N次实数乘法以及2N+2(N-1)=2(2N-1)次实数加法。整个 DFT运算总共需要 4N*N次实数乘法和 N*2(2N-1)=2N(2N-1)次实数加法。当 N足够大，N>>1 时，直接计算DFT
的乘法次数和加法次数都是和 N的平方成正比。当N=1024 时，DFT的运算量为 1048576次，即一百多万次复乘运算，一块嵌入式 32位处理器的最高速度为 105百万指令每秒，那么它要完全计算这个DFT 的时间最快也要 1 秒，期间还是独占 CPU 所有运算资源且不能有任何其他的中断请求。这样计
算量太庞大，计算速递太慢了，谈不上实时性，根本没有实用意义。
所以，我们就要利用DFT 的系数的固有特性来简化计算，减少运算量。特性如下：
完整的pdf格式文档51黑下载地址（共17页）：
详解快速傅里叶变换FFT算法带程序.pdf
(1.72 MB, 下载次数: 743)
|
[复制链接]
