第4章_快速傅里叶变换

k
（5）指数因子的共轭对称性
共轭对称性：
W
kn * N
( N k ) n WNkn＝WN WNk ( N n )
*
将x(n) x (n)称为共轭偶对称。 将x(n) x (n)称为共轭奇对称。
*
证明：
WN e
j
2 N
( N k ) n WN WNNnWN kn WN kn
W
k ( N n ) N
W W
kN N
kn N
W
kn N
（6）指数因子的正交性
W
k 0
N 1
kn N
N , n rN , r为整数 其他n 0 ,
证明：
WN e
j
2 N
（7）序列的分解
结论：将一个长序列分解为两个短序列来进行 DFT的计算，可以使DFT乘法的次数减少一半。 证明： 2 2
j
N
（1）指数因子的特殊值
WN WN WN
WN
N 4
0
N
kN
1
3N 4
WN
N 2
1
j
WN
2 j N
j
证明： WN e
WN
kN N 2
e e
2 j kN N j 2 N N 2
e j 2k 1 e
j
WN
1
（2）指数因子的周期性
, k 0,1,2,, N 1
综合公式：
1 xn IDFTX k X k e N k 0
N 1
j
2 kn N
, n 0,1,2,, N 1
通常，有限长序列x(n)可以是实数，也可以 是复数，而其DFT即X(k)一般是复数。 2 j 为了表示简便，令复数 WN e N ，称为 DFT的指数因子（或加权因子、或旋转因子）。 2 j N W e N 当DFT的变换区间长度N给定时， 是 一个复数常数，且由DFT的变换区间长度N唯一 确定。而且有下式成立：
2 j N
证明： WN e
WN
kn
e
j
2 kn N
e
j
2 mkn mN
WmN
mkn
（4）指数因子的半对称性
指数因子 WN e 对称，即 N
j 2 N
以半个周期N/2为
k
WN
k
2
WN
2 N
证明：
WN e
j
WN
N k 2
W N WN
k
N 2
WN
Signal Processing 19 (1990) 259-299 INVITED PAPER FAST FOURIER TRANSFORMS: A TUTORIAL REVIEW AND A STATE OF THE ART P. DUHAMEL M. VETTERLI Abstract. The publication of the Cooley-Tukey fast Fourier transform (FFT) algorithm in 1965 has opened a new area in digital signal processing by reducing the order of complexity of some crucial computational tasks like Fourier transform and convolution from N2 to N*log2(N), where N is the problem size. The development of the major algorithms (Cooley-Tukey and split-radix FFT, prime factor algorithm and Winograd fast Fourier transform) is reviewed. Then, an attempt is made to indicate the state of the art on the subject, showing the standing of research, open problems and implementations.
4.1 DFT的计算工作量
在计算机应用中，可以采用算术乘法 和加法的次数作为算法的计算工作量的度 量，因为算术乘法和加法的次数直接与计 算机的计算速度有关。 有限长序列x(n)的N点DFT为： 分析公式：
X k DFTxn xne
N 1 n 0 j 2 kn N
指数因子 WN e
j 2 N
以N为周期，即
k N n
WN
kn
WN
k n N
WN
j 2 N
WN
k lN nmN
证明：
WN e
（3）指数因子的可约性
W2 N W N
k k 2
WmN
WN
m kn m
mk
WN
k
WN
kn
WmN
mkn
虽然频谱分析和DFT运算很重要，但在很长一段 时间里，由于DFT运算复杂，并没有得到真正的运用， 而频谱分析仍大多采用模拟信号滤波的方法解决。 直到1965年，当Cooley和Tukey首次提出DFT运算 的一种快速算法以后，情况才发生了根本变化。人们开 始认识到DFT运算的一些内在规律，从而很快地发展和 完善了一套高速有效的运算方法，被称为快速傅里叶变 换（FFT）算法。FFT的出现，使DFT的运算大大简化， 运算时间缩短一至二个数量级，使DFT的运算在实际中 得到广泛应用。下面这篇文献具有划时代的意义。 经典文献：J. W. Cooley, and J. W. Tukey, An Algorithm for the Machine Calculation of Complex Fourier Series, Mathematics of Computation, Vol. 19, No. 90, 1965, P.297~301.
4.2 FFT的基本思想
FFT的基本思想：利用DFT系数的特性， 合并DFT运算中的某些项，把长序列DFT变成 短序列DFT，从而减少其运算工作量。 改善DFT计算效率的方法主要取决于指数 因子。下面对指数因子的特性进行分析。充分 利用指数因子的特性，可以大大减少DFT的运 算工作量。 2
WN e
FFT的分类方法之一： ①将长序列按照时间分解为短序列，称为 按时间抽取法（Decimation In Time，DIT）。 此算法的推导过程所遵循的两个基本规则是： 对时间进行偶奇分解，对频率进行前后分解。 ②将长序列按照频率分解为短序列，称为 按频率抽取法（Decimation In Frequency， DIF）。此算法的推导过程所遵循的两个基本 规则是：对时间进行前后分解，对频率进行偶 奇分解。
WN e
2 j N
WN e
kn
2 j kn N
WN e
m
j
2 m N
由此可见，DFT虽然解决了采用计算机进行 信号分析的算法的理论问题，但是并没有解决实 际的应用问题，因为随着采样点数N的增大， DFT乘法的次数是按照指数的规律增加的，几乎 不可能实现计算机的实时计算。 为了提高计算机的计算速度，有必要研究 DFT的高效计算方法。DFT的乘法计算次数能否 减少，关键在于DFT的计算是否存在规律，以及 如何利用这些规律来减少DFT的乘法计算次数。
第4章 快速傅里叶变换 （离散傅里叶变换的快速算法）
4.1 DFT的计算工作量 4.2 FFT的基本思想 4.3 FFT的基本形式 4.4 FFT的逆变换算法 4.5 FFT的应用举例
本章内容参考： 郑君里等《信号与系统（第3版）》下册 第九章 离散傅里叶变换以及其他离散正交变换
快速傅里叶变换（Fast Fourier Transform， FFT）是计算离散傅里叶变换（DFT）的一种快速有 效的方法。 从前面的讨论中可以看到，有限长序列在数字 技术中占有很重要的地位。对有限长序列进行计算和 分析的最重要的工具是离散傅里叶变换（DFT）。 离散傅里叶变换（DFT）之所以在各个学科领 域获得了广泛的应用，原因主要有两个： 第一，离散傅里叶变换（DFT）在时域和频域 都是离散的，适合于用计算机来计算。 第二，离散傅里叶变换（DFT）存在高效的快 速计算方法，即FFT。 因此，离散傅里叶变换（DFT）在数字信号处 理中具有核心的作用。
FFT的分类方法之二： ①当有限长序列x(n)的点数（DFT变换 区间长度）N=2r时，称为以2为基底的FFT 算法，简称基2算法。基2算法使用最普遍。 ②当有限长序列x(n)的点数（DFT变换 区间长度）N=4r时，称为以4为基底的FFT 算法，简称基4算法。 ③还有以其它值为基底的FFT算法。
kn n 0
11
k 0,1 1
总结： FFT的基本思想就是，将一个长序列依 次分解为两个短序列来进行DFT的计算，并 且充分利用指数因子的周期性和对称性，进 而计算出这些短序列的相应的DFT，然后进 行适当的组合，最终实现消除重复计算、减 少乘法次数、提高计算速WN e
2 j N
WN e
kn N
kn
2 j kn N
WN e
m
j
2 m N
DFT 的因子 W
e
j 2N kn
是一个周期复数序列。
此时，由x(n)和X(k)组成的N点离散傅里叶 变换对（ DFT ）可以简写为：
分析公式：
X k DFTxn xn WN , k 0,1,2,, N 1
DFT的反变换IDFT与DFT的运算结构相同， 只是多乘一个常数1/N，所以二者的计算量相同。