快速傅立叶变换(fft).ppt

第6章快速傅立叶变换(FFT)虽然频谱分析和DFT运算很重要,但在很长一段时间里,由于DFT运算复杂,并没有得到真正的运用,而频谱分析仍大多采用模拟信号滤波的方法解决,直到1965年首次提出DFT运算的一种快速算法以后,情况才发生了根本变化,人们开始认识到DFT运算的一些内在规律,从而很快地发展和完善了一套高速有效的运算方法——快速付里变换(FFT)算法。FFT的出现,使DFT的运算大大简化,运算时间缩短一~二个数量级,使DFT的运算在实际中得到广泛应用。 . 1,,1,0,)()(10??????NkWnxkXNnnkN????????101,,1,0,)(1)(NknkNNnWkXNnx?通常x(n)和都是复数,所以计算一个X(k)的值需要N次复数乘法运算,,计算全部N点的X(k)就要N2次复数乘法运算,N(N-1),乘法运算要比相加运算复杂,为讨论简单起见,,运算量将是惊人的,如N=1024,则要完成1048576 次(一百多万次),?N一个X(k)的值的工作量,如X(1)1210)1()2()1()0()1(???????NNNNNWNxWxWxWxX? 1. 的对称性和周期性nkNW;,)()()(*NknNkNnNnkNnkNnkNWWWWW??????.),1(1),1()2/(2/)(2)()(2kNNkNjNNNnkNnNNkNnkNknNNkNnNWWeWWeWWWWWN??????????????????????得:对称性:周期性:利用上述特性,可以将有些项合并22)()()(NNNkXkXkX??把N点数据分成两半:其运算量为:2)2(N2)2(N2N再分两半:44)()(NNkXkX?44)()(NNkXkX?+=22N2)4(N2)4(N2)4(N2)4(N+++=24N这样一直分下去,剩下两点的变换。。因为DFT的计算量正比于N2,N小,计算量也就小。 FFT算法正是基于这样的基本思想发展起来的。1965年,库利(cooley)和图基(Tukey),仅需(N/2)=1024=210时,需要(1024/2)log2 210 =512*10=5120次。5120/1048576=% ,-40,具有50ns的单周期执行时间,每秒20000次浮点运算,完成乘法、加法及运算控制、数据存取共需约1s左右,而采用FFT算法,。 FFT有多种形式,但基本上可分为两类:时间抽取法和频率抽取法。按“基数”分:基-2FFT算法;基-4FFT算法;混合基FFT算法;分裂基FFT算法其它方法:线性调频Z变换(CZT法) 1. 设输入序列长度为N=2L(L为正整数,将该序列按时间顺序的奇偶分解为越来越短的子序列,称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。 2. 其中基数2----N=2L,,可以人为地加上若干零值(加零补长)使其达到 N= 按时间抽取(DIT)的FFT算法—库利-图基算法算法原理(1).N/,这样有: n为偶数时: n为奇数时:1,,1,0),()12(1,,1,0),()2(2221???????NNrrxrxrrxrx???????10)()]([)(NnnkNWnxnxDFTkX因此,)(nx由于:所以,上式可表示为:??????????????????????????1022102110)12(**********))(())(()12()2()()()(NNNNrrkNkNrrkNrkrNrrkNNnNnnkNnkNWrxWWrxWrxWrxWnxWnxkX(n为偶数) (n为奇数)222)/(222NNNWeeWjjN????????)()()()()(2**********kXWkXWrxWWrxkXkNrrkkNrrkNNNN??????????