【第4章】快速傅里叶变换(FFT)

第四章快速傅里叶变换(FFT)主要内容引言直接计算DFT的特点时间抽取基2FFT算法频率抽取基2FFT算法4.1引言DFT是信号分析与处理中的一种重要变换.直接计算DFT的计算量与变换区间长度N2成正比，当N较大时，计算量太大.在快速傅里叶变换(FFT)出现以前，直接用DFT算法进行谱分析和信号的实时处理是不切实际的.1965年发现了DFT的一种快速算法以后，情况发生了根本的变化.次复加，计算量很大。乘和次复运算，需要完成整个计算量相同的和均为复数，，其中，，)1()()(1,1,0)()(1,1,0)()(21010NNNDFTIDFTDFTWkXnxNnWkXnxNkWnxkXNNkknNNnknN4.2直接计算DFT的特点长度为N的有限长序列x(n)的DFT为：22()jmlNjmmlNmNNNNWeeW其周期性表现为：2[]mNmNmmNNNNNmmNN其对称性表现为：N点DFT的复乘次数等于N2.显然，把N点DFT分解为几个较短的DFT，可使乘法次数大大减少.另外，旋转因子具有明显的周期性和对称性.FFT算法就是不断把长序列的DFT分解成几个短序列的DFT，利用上述周期性和对称性来减少DFT的运算次数.FFT算法基本上分为两大类：(1)时域抽取法FFT(DecimationInTimeFFT,简称DIT—FFT).(2)频域抽取法FFT(DecimationInFrequencyFFT,简称DIF—FFT).1、算法原理设输入序列长为N=2M(M为正整数)，将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的FFT算法.若序列长度不满足条件N=2M，可以加零补长使其达到N=2M.4.3时域抽取基2FFT算法要点：.)(点位置改变的采样点数增加，采样，只是频谱影响其频谱有限长序列补零后并不jweX2、算法步骤换第一步：分组和变量置12,,1,0)()12(12)()2(2)(1,,1,0)()(2110NrrxrxrnnrxrxrnnnxNkWnxkXNnnkN其中令奇数令偶数按奇偶分成两组：将，定义式第二步：代入DFT12,,1,0)()()()()12()2()]([)]([)(212/0212/021)12(12/012/0221NrWWrxWrxWrxWrxrxDFTrxDFTkXkNrkNNrNrrkNkrNNrNrrkN其中DFT第三步：求子序列的kNrkNNrNrrkNNNjNjNWWrxWrxkXWeeW2/12/0212/02/12/2/2222)()()()()()(21kXWkXkXkN121,0Nk其中：12,,1,0)12()()()2()()(12/012/02/2/2212/012/02/2/11NkWrxWrxkXWrxWrxkXNrNrrkNrkNNrNrrkNrkN式中：12/022/212/0)2/(2/2212/012/112/0)2/(2/11)2/(2/2/)()()()2()()()()2(NrrkNNrkNrNNrrkNNrkNrNNkrNrkNkXWrxWrxkNXkXWrxWrxkNXWW.2/的前后两半部分点律合成，并按照上述规点被分解成两个点一个DFTNDFTNDFTN要点：)()()2()2()2(212)2(12/)2/kXWkXNkXWNkXNkX（)()()2(21kXWkXNkXkN12,1,0Nk其中：结论：只要求出(0~N/2-1)区间内的各个整数k值所对应的X1(k)和X2(k)值，即可求出(0~N-1)整个区间内全部X(k)值，这就是FFT节省计算量的关键.N=2M→N/2仍为偶数→可以进一步把每个N/2点子序列再按输入n的奇偶分解为两个N/4点的子序列→按这种方法不断划分，直到最后剩下2点DFT，两点DFT实际上只是加减运算.CABA＋BCA－BC3、蝶形运算符号求N=23=8点FFT.(1)将N=8的DFT分解成2个4点DFT给出。由给出；由频域上：为奇子序列。为偶子序列；时域上：)2/()7()4()()3()0()7(),5(),3(),1()6(),4(),2(),0(NkXXXkXXXxxxxxxxx【例题】3,2,10)(()2/()()()(2121，）kkXWkXNkXkXWkXkXkNkNN点DFT的一次时域抽取分解图(N=8)⑵将4点DFT分解成2点的DFT奇序列、偶序列、奇序列、偶序列、...).........7()3(........)....5()1(:)(...).........6()2(............)4()0(:)(21xxxxrxxxxxrx将N/2(4点)子序列按奇/偶分解成两个N/4点(2点)子序列。即将x1(r)和x2(r)分解成奇/偶两个N/4点(2点)点的子序列。）（奇序列）（）偶序列）（奇序列）（）偶序列140...........12(...........)......()2(140...........12(........).........()2(62524131NLLxLxLxLxNLLxLxLxLx10)(()4/()()()()()()4/)()()62/5262/5242/3142/31，其中）（（LLXWLXNkXLXWLXkXLXWLXNkXLXWLXkXkNkNkNkNN点DFT的第二次时域抽取分解图(N=8)⑶将2点DFT分解成2个1点DFT两点DFT可分解成两个1点DFT，而1点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示.N点DIT-FFT运算流图(N=8)每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法).2(2)log22MNNCMNM级运算总共需要的复数乘次数为：4、DIT―FFT与直接DFT运算量的比较M级运算总共需要的复数加次数为：2(2)logACNMNN直接计算DFT的复数乘为N2次，复数加为N(N-1)次数。当N1时，N2(N/2)log2N。所以DIT-FFT算法比直接计算DFT的运算次数大大减少。221048576204.8(/2)log5120NNN例如：N=210=1024时：FFT算法与直接计算DFT所需乘法次数的比较曲线1、算法原理设输入序列长度为N=2M(M为正整数)，将该序列的频域输出序列X(k)按其频域顺序的奇偶分解为越来越短的子序列，称基2按频率抽取FFT算法.若序列长度不满足条件N=2M，可以加零补长使其达到N=2M.4.4频域抽取基2FFT算法2、算法步骤第一步：分组12,,1,0)2(12,,1,0)()()(1,,0)()(10NnNnxNnnxnxkXNkWnxkXNnnkN后半部分：前半部分：按前后分为两部分：奇偶分组，定义式第二步：代入DFTnkNkNNNnNnkNnNNnnkNkNnNNnnkNNnnkNWWNnxnxWNnxWnxWNnxWnxWnxkX])2()([)2()(])2()([)()(2120120)2(120)2(12010奇数偶数其中：kkeeWkjkNNjkNN11222第三步：变量置换分：偶数时，频率的偶数部当k16,4,2,0)]2()([)(12,1,0''2112/02NkWNnxnxkXNkkkWnkNNnkNN其中：，，令12,1,0')]2()([)'2('212/0NkWNnxnxkXnkNNn其中：12,1,0')]2()([)'2(('2/12/0'2/'2/2'22'2/'2NkWNnxnxkXWeeWWnkNNnnkNnkNjnkNjnkNnkN其中：）)2()()(1Nnxnxnx设：12,1,0')')()'2(1'2/12/01NkkXWnxkXnkNNn其中：（则：122,1,0Nn.2)()()(:11一半个点，所以运算量减少只有序列得到，而做的偶数部分可以由序列可见NnxDFTnxkX分：奇数时，频率的奇数部当k17,5,3,1)]2()([)(12,1,0'1'2112/02NkWNnxnxkXNkkkWnkNNnkNN其中：，，令12,1,0')]2()([)1'2(1'2(12/0NkWNnxnxkXknNNn其中：）12,1,0')2()()1'2(('2/12/0'2/'2/2'22'2/'2NkWWNnxnxkXWeeWWnkNnNNnnkNnkNjnkNjnkNnkN其中：）nNWNnxnxnx)]2()([)(2设：12,1,0')')()1'2(2'2/12/02NkkXWnxkXnkNNn其中：（则：122,1,0Nn.2)()()(12一半个点，所以运算量减少只有列得到，而序做的奇数部分可以由序列可见：NnxDFTnxkX为止。点如此分解，直到：点代入后合成，再用其中：（（先求出：点被分解为两个点一个DFTkXkXkXDFTNkkkkNkWWNnxnxkXWNnxnxkXkXkXkXDFTNDFTNnkNNnnNnkNNn2)1'2()'2()(1'2'212/1,0')]2()([)')]2()([)':)1'2()'2()(221'2/12/02'2/12/01结论：3、蝶形运算符号求N=23=8点FFT.⑴先将N=8的DIF分解成2个4点DIF时域上：x(0)，x(1)，x(2)，x(3)为偶子序列；x(4)，x(5)，x(6)，x(7)为奇子序列。频域上：X(0)，X(2)，X(4)，X(6)由x1(n)给出.X(1)，X(3)，X(5)，X(7)由x2(n)给出.【例题】nNWNnxnxnxNnxnxnx)]2/()([)()2/()()(21其中:DIF-FFT一次分解运算流图(N=8)⑵再将N=4的DIF分解成2个2点DIF)3()2()1()0(:)()3()2()1()0(:)(2222211111xxxxnxxxxxnx、、、、）（）（）（）（140)]2()([)2()()(140)]2()([)2()()(226225114113NLWNnxnxLxNnxnxLxNLWNnxnxLxNnxnxLxnNnNDIF-FFT二次分解运算流图(N=8)⑶再将N=2的DIF分解成2个1点DIF最后剩下两点DFT，它可分解成两个1点DFT，但1点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示.DIF-FFT运算流图(N=8)4.5IDFT的高效算法比较DFT和IDFT的运算公式：10)()]([)(NnknNWnxnxDFTkX10)(1)]([)(NkknNWnxNkXIDFTnx将DFT中的系数改为，最后乘以1/N，就