详解快速傅里叶变换FFT算法

详解快速傅里叶变换FFT算法

快速傅里叶变换FFT是离散傅里叶变换DFT的一种快速算法,只有FFT才能在现实中有实际应用的意义。虽然许多学过数字信号处理这门课的同学都知道DFT和FFT,但实际上真正理解其算法原理的屈指可数,绝大部分同学知其然而不知其所以然,况且限于高校课程教学体制,课堂上不可能把这些原理和算法讲得明明白白的。为此,特意以本文讲解FFT算法的原理与实际应用,给欲往电子信息类专业进修和发展的同学一些课外参考。

N点有限长序列x(n)的DFT为

X(k) x(n)W 其中W

nkN

n 0N 1

nkN

e

j

2 nkN

其逆变换IDFT为

1N 1 nk

x(n) X(k)WN

Nn 0

正逆变换的运算量都是相同的。x(n)和X(k)都是复数序列,计算一个X(k)值,需要N次复数乘法和N-1次复数加法。X(k)有N个点,所以总共需要N*N次复数乘法和N(N-1)次复数加法。复数运算实际上是通过实数运算来完成的。上式可以写成:

nknk

X(k) Re x(n) jIm x(n) Re WN jIm WN

n 0

N 1

nknknknk Re x(n) Re W Imx(n)ImW jRex(n)ImW Imx(n)ReW NNNN

n 0

N 1

由此可见,一次复数乘法需要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的系数的固有特性来简化计算,减少运算量。特性如下:

nk nk

1. 共轭对称性:(WN )* WN

nk(n N)kn(k N)2. 周期性: WN WN WNnknmknk/m

WN WN3. 可约性: WN/m

得出:

(k N/2)kn(N k)(N n)k nk

WNWN WN WN WNN/2 1 WN

利用上述这些系数性质就可以合并DFT某些项的计算从而减少计算量。下面仅给出按时间抽选

Word文档免费下载Word文档免费下载:详解快速傅里叶变换FFT算法 (共17页,当前第1页)

你可能喜欢

  • 离散傅里叶变换DFT
  • 算法的C语言实现
  • 快速傅里叶变换原理
  • 数字信号处理算法
  • 数字信号处理课件
  • 北京自考
  • 自考科目
  • 自考思想道德修养与法律基础

详解快速傅里叶变换FFT算法相关文档

最新文档

返回顶部