【转】数字信号处理 教案 ---- 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……