DSP 第四章：快速傅里叶变换

DSP 第四章 快速傅里叶变换FFT

题型

①. 计算直接$DFT$和$FFT$的复乘、复加的次数（时间）；

②. 画$8$点$DIT-FFT、DIF-FFT、DIT-IFFT$。

4.1 引言

FFT: Fast Fourier Transform

FFT是为了减少DFT运算量的一种快速有效的算法。

4.1.1 直接计算FFT的计算量

复运算量：

$$x(n)W_N^{nk}$$

	复数乘法	复数加法
一个$X(k)$	$N$	$N–1$
$N$个$X(k)$	$N^2$	$N (N-1)$

4.2 基 2FFT算法

4.2.1 时域抽取基-2FFT（DIT-FFT）

对于$N=2^M$点的$DFT$，共需要$M$级蝶形运算。

4.2.2 DIT-FFT与直接DFT运算量比较

复数乘法次数：$C_M=\frac N2\log_2N$

复数加法次数：$C_A=N\log_2N$

4.2.5 频域抽取基-2FFT（DIF-FFT）

频域序列$X(k)$按$k$的奇偶进行抽取对应时域上将序列$x(n)$按$n$的顺序分成前后两半。

DIT-FFT与DIF-FFT的异同

①. 运算量相同：都可原位运算；

②. 基本蝶形不同：

• DIT-FFT：先复乘后加减
• DIF-FFT：先加减后复乘

4.2.6 IDFT的高效算法