【转】数字信号处理 教案 ---- 4、快速傅立叶变换(FFT)

【转】数字信号处理 教案 ---- 4、快速傅立叶变换(FFT)

【转】 数字信号处理 教案 ---- 4、快速傅立叶变换(FFT)
第四章 快速傅立叶变换(FFT)
4．1引言
快速傅立叶变换（FFT）并不是一种新的变换，而是离散傅立叶变换（DFT）的一种快速
算法。
DFT的计算在数字信号处理中非常有用。例如在FIR滤波器设计中会遇到从h(n)求H(k)或
由H(k)计算h(n)，这就要计算DFT；信号的谱分析对通信、图像传输、雷达等都是很重要
的，也要计算DFT。因直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时
，计算量太大。
自从1965年图基（J. W. Tukey）和库利（T. W. Coody）在《计算数学》（Math.
Computation , Vol. 19,
1965）杂志上发表了著名的《机器计算傅立叶级数的一种算法》论文后，桑德(G. Sand)-
图基等快速算法相继出现，又经人们进行改进，很快形成一套高效运算方法，这就是快
速傅立叶变换简称FFT（Fast Fourier
Transform）。这种算法使DFT的运算效率提高1~2个数量级。
4．2 基2 FFT算法
一、直接计算DFT的问题及改进的途径
设x(n)为N点有限长序列，其DFT正变换为
[pic]= [pic]， k=0，1，…，N-1
其反变换(IDFT)
x(n)= [pic]，n=0，1，…，N-1
二者的差别只在于[pic]的指数符号不同，以及差一个常数乘因子1/N，因而下面我们只
讨论DFT正变换的运算量，反变换的运算量是完全相同的。
考虑x(n)为复数序列的一般情况，每计算一个X(k)，需要N次复数乘法以及（N-
1）次复数加法。因此，对所有N个k值，共需N2次复数乘法及
N（N-
1）次复数加法运算。所以直接计算DFT，乘法次数和加法次数都是和N