资源描述：
《数字信号处理 3》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数字信号处理DigitalSignalProcessing(DSP)信息学院电子系第3章快速傅里叶变换3.1引言3.2直接计算DFT的问题及改进的途径3.3按时间抽取（DIT）的基2-FFT算法3.4按频率抽取（DIF）的基2-FFT算法3.5N为复合数的FFT算法3.6线性调频Z变换（Chirp-Z变换）算法3.7利用FFT分析时域连续信号频谱3.8FFT的其他应用3.1引言DFT实现了时域序列的频域离散化,因此在数字信号处理中用途很广但是DFT的计算量太大，不适于实时处理，所以没有得到真正的运用快速傅里叶变换(FFT)就是为了缩短DFT运算时间而产生的,运算时间一
2、般可缩短一二个数量级FFT并不是一种新的变换,而是DFT的一种快速算法3.2直接计算DFT的问题及改进的途径3.2.1直接计算DFT的运算量问题k=0,1,…,N-1设x(n)为N点有限长序列，其DFT为通常x(n)和WNnk都是复数，因此一个X(k)需要N次复数乘法和N-1次复数加法完成整个DFT运算则需要N2次复数乘法及N(N-1)次复数加法由于DFT的运算次数与N2成正比,N较大时,运算量非常可观例对一幅N×N点的二维图像进行DFT变换，当N=1024时,直接计算DFT所需复乘次数为1012次，用每秒可做10万次复数乘法的计算机计算需要近3000小时3.2.2改
3、善途径把长序列的DFT分解成短序列的DFT运算利用系数WＮnk的特性对称性周期性可约性其它3.3按时间抽取（DIT）的基-2FFT算法设序列x(n)长度为N，且满足N=2M，M为正整数。按n的奇偶把x(n)分解为两个N/2点的子序列：FFT分为两大类:按时间抽取法(DecimationinTime)和按频率抽取法(DecimationinFrequency),本节先介绍第一种算法3.3.1算法原理一个N点DFT的分解将DFT[x(n)]分解为DFT[x1(r)]与DFT[x2(r)]的线性组合代入重写DFT(X1(k)与X2(k)分别是x1(r)及x2(r)的N/2点
4、DFT)上式为X(k)的前一半值,而后一半值可表示为化简得到上式将N点DFT分解为两个N/2点的DFT运算，运算过程如下图示时间抽取法蝶形运算流图分解后运算工作量节省了近一半将X(k)表达式为前后两部分,重写如下N点DFT的一次时域抽取分解过程见下图（N=8）两个N/2点DFT的分解N点DFT分解X1(k)的分解由于N=2M仍是偶数，可以把每个N/2点子序列再进行分解N/2点DFT分解X1(k)分解图示X2(k)的分解图示N点DFT的第二次时域抽取分解图（N=8）N点DFT的第二次时域抽取分解图（N=8）上式不需要乘法,类似可求出X4(k)，X5(k)，X6(k)四个
5、N/4点DFT的计算X3(k)的分解完整的N=8DIT-FFT运算流图由于输入序列在时域上进行奇偶分解，故称为“按时间抽取法”N=2M点的FFT共进行M级运算，每级由N/2个蝶形运算组成3.3.2DIT-FFT算法与直接计算DFT运算量的比较直接计算DFT与FFT算法的计算量之比为N越大，FFT的优点越为明显例3-2P1093000h---2m3.3.3按时间抽取的FFT算法的特点1.原位运算（同址运算）定义：利用同一存贮单元存贮蝶形运算输入、输出数据的方法DIT-FFT的运算规律同一级中，每个蝶形的两个输入数据只对计算本蝶形有用，可采用原位运算，则全部运算过程只需要
6、N个存储单元2.倒位序规律（N=2M）输入序列的排序为N的二进制倒位序，输出序列则为自然顺序N＝8时的输入输出值3.蝶形运算两节点的“距离”对N=2M点FFT，当输入为倒位序，输出为正常顺序时，其第m级运算，每个蝶形的两节点“距离”为2m-1x(0)X(0)x(4)X(1)－10NWx(2)X(2)x(6)X(3)－10NW0NW2NW－1－1x(1)X(4)x(5)X(5)－10NWx(3)X(6)x(7)X(7)－10NW0NW2NW－1－10NW1NW2NW3NW－1－1－1－1x(0),x(1)x(0),x(2)x(0),x(4)3.3.4按时间抽取的FFT算
7、法的其他形式流图对于任何流图，只要保持各节点所连的支路及传输系数不变，则不论节点位置怎么排列所得流图总是等效的将左图x(4)与x(1),x(6)与x(3)对调时间抽取、输入自然顺序、输出倒位序的FFT流图特点数据存放的方式不同取用系数的顺序不同3.4按频率抽取（DIF）的基-2FFT算法3.4.1算法原理将长度为N=2M的序列x(n)前后对半分开,其N点DFT可表示为k=0,1,…,N-1统一求和区间按k的奇偶可将X(k)分为两部分:偶数奇数式中k=0,1,…,N-1k取偶数时x(n)前后两部分和的N/2点DFTk取奇数时x(n)前后两部分差再乘以W
