数字信号处理第4章 快速傅里叶变换(FFT)

第4章快速傅里叶变换通信与信息工程学院第4章快速傅里叶变换4.1引言4.2直接计算DFT的问题及改进的途径4.3按时间抽取（DIT）的基2-FFT算法4.4按频率抽取（DIF）的基2-FFT算法4.5IDFT的高效算法4.6FFT的其他应用—快速卷积学习目标理解按时间抽取的基-2FFT算法的原理、运算流图、所需计算量和算法特点；理解按频率抽取的基-2FFT算法的原理、运算流图、所需计算量和算法特点；理解IFFT算法；§4.1引言快速傅里叶变换（FFT）并不是一种新的变换，而是离散傅里叶变换（DFT）的一种快速算法。在信号的频谱分析、系统的分析、设计和实现中都会用到DFT的计算。DFT的计算量太大，很难对问题进行实时处理，难以实用。1965年首次发现了DFT运算的一种快速算法以后，人们开始认识到DFT运算的一些内在规律，从而很快地发展和完善了一套高速有效的运算方法，这就是快速傅里叶变换（FFT）的算法。FFT出现后使DFT的运算大大简化，运算时间一般可缩短一二个数量级之多，使DFT的运算在实际中真正得到了广泛的应用。§4.2直接计算DFT的问题及改进的途径一、直接计算DFT的运算量问题设x(n)为N点有限长序列，其DFT为10)()(NnnkNWnxkXk=0,1,…,N-1反变换（IDFT）为10)(1)(NknkNWkXNnXn=0,1,…,N-1运算量一个X(k)复数乘法复数加法NN-1N2N(N-1)N个X(k)10NnknNWnx])}Re[)](Im[]Im[)]((Re[][Im)](Im[]Re[)]({Re[]}Im[])]}{Re[(Im[)]({Re[)()(101010nkNnkNnkNNnnkNNnnkNnkNNnnkNWnxWnxjWnxWnxWjWnxjnxWnxkX一次复数乘法需用四次实数乘法和二次实数加法；一次复数加法需二次实数加法。一个X(k)实数乘法实数加法4N2N+2(N-1)=2(2N-1)4N22N(2N-1)N个X(k)二、改进的途径x(n)长序列————短序列WNkn10NnknNWnx§4.3按时间抽取（DIT）的基-2FFT算法一、算法原理1.一次分解N→N/2设序列x(n)长度为N，且满足N=2M，M为正整数。按n的奇偶把x(n)分解为两个N/2点的子序列：12,,1,0)()12()()2(21NrrxrxrxrxrkNNrkNrkNNrkrNNrrkNNrNnnnkNNnNnnnkNnkNWrxWWrxWrxWrxWnxWnxWnxnxDFTkX))(()()()12()2()()()()]([)(2120221201)12(1202120101010为奇数为偶数1202/22/1120)()()(NrrkNkNrkNNrWrxWWrxkXk=0,1,…..,N/2-1222222NNjNjNWeeWX1(k)与X2(k)分别是x1(r)及x2(r)的N/2点DFT：rkNNrrkNNrrkNNrrkNNrWrxWrxkXWrxWrxkX2/1202/212022/1202/11201)12()()()2()()(一个N点DFT已分解成两个N/2点的DFT)()(21kXWkXkN利用周期性求X(k)的后半部分kNkNNNNkN22221121222,又为周期的是以X2(k)X1(k)kNW－1X1(k)＋kNWX2(k)X1(k)－kNWX2(k)kX2NkX12,...,1,022121NkkXWkXNkXkXWkXkXkNkNN点（N=8）DFTx(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X1(0)X1(1)X1(2)X1(3)X2(1)X2(2)X2(3)X2(0)-1-1-1-1WN0WN1WN2WN3N/2点DFTN/2点DFTx(0)=x1(0)x(2)=x1(1)x(4)=x1(2)x(6)=x1(3)x(1)=x2(0)x(3)=x2(1)x(5)=x2(2)x(7)=x2(3)14101224131Nllxlxlxlx,,,)()()()(14101224231404421404314012211402211NkkXWkXWlxWWlxWlxWlxkXkNNllkNkNNllkNNlklNNllkN,,,)()()()()()()(////)(//2.二次分解N/2→N/4)()(/kXWkXkNXkN4231414,,1,0NkX2(k)也可进行同样的分解：)()(4)()()(62/5262/52kXWkXkNXkXWkXkXkNkN14,,1,0Nk1404/21404/661404/21404/55)12()()()2()()(NllkNNllkNNllkNNllkNWlxWlxkXWlxWlxkXx(0)=x1(0)x(2)=x1(1)x(4)=x1(2)x(6)=x1(3)x(1)=x2(0)x(3)=x2(1)x(5)=x2(2)x(7)=x2(3)N/2点DFTN/2点DFTX1(0)X(0)X1(1)X(1)X1(2)X(2)X1(3)X(3)X2(1)X(5)X2(2)X(6)X2(3)X(7)X2(0)X(4)-1-1-1-1WN0WN1WN2WN3N/2点DFT分解为两个N/4点DFTDFT4点NX3(0)X3(1)x3(0)＝x1(0)＝x(0)x3(1)＝x1(2)＝x(4)X1(0)X1(1)DFT4点NX4(0)X4(1)x4(0)＝x1(1)＝x(2)x4(1)＝x1(3)＝x(6)X1(2)X1(3)－1－102/NW12/NW一个N=8点DFT分解为四个N/4点DFTDFT4点NX3(0)X3(1)x3(0)＝x1(0)＝x(0)x3(1)＝x1(2)＝x(4)X1(0)X1(1)DFT4点NX4(0)X4(1)x4(0)＝x1(1)＝x(2)x4(1)＝x1(3)＝x(6)X1(2)X1(3)－1－10NW2NWX(0)X(1)X(2)X(3)DFT4点NX5(0)X5(1)x5(0)＝x2(0)＝x(1)x5(1)＝x2(2)＝x(5)X2(0)X2(1)DFT4点NX6(0)X6(1)x6(0)＝x2(1)＝x(3)x6(1)＝x2(3)＝x(7)X2(2)X2(3)－1－1X(4)X(5)X(6)X(7)0NW1NW2NW3NW－1－1－1－10NW2NWN=8，四个N/4点DFT即四个2点DFT，其输出分别为：X3(k)，X4(k)，X5(k)，X6(k)，k=0,1)4()0()4()0()1()0()1()4()0()4()0()1()0()0(012311210233002301200233xWxxWxxWWxXxWxxWxxWWxXNN0122121NjjWeeW140433NllkNWlxkX/)()(N=8按时间抽取的FFT运算流图x(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－1X3(0)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)N=8时共有三级蝶形运算，每一级有N/2=4个蝶形X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)x3(0)x3(1)x4(0)x4(1)x5(0)x5(1)x6(0)x6(1)二、按时间抽取的FFT算法与直接计算DFT运算量的比较N=2M时，共有M级蝶形，每级都由N/2个蝶形运算组成；每个蝶形需要一次复乘、二次复加；每级运算都需N/2次复乘和N次复加；M级运算总共需要：复乘数22log22logFFNNmMNaNMNN====复加数以乘法为例，直接DFT复数乘法次数是N2，FFT复数乘法次数是(N/2)log2N；直接计算DFT与FFT算法的复数乘法计算量之比为：bNNbNNNMNN1212222当N=2048时，这一比值为372.4，即直接计算DFT的运算量是FFT运算量的372.4倍；当点数N越大时，FFT的优点更为明显。对一个连续时间信号xa(t)采样1秒得到一个4096个采样点的序列，若计算采样信号的4096点DFT。假定仅对200≤f≤300Hz频率范围所对应的DFT采样点感兴趣。（1）若直接用DFT，要计算这些值需要多少次复乘？MN=101×4096=413696（2）若用基2的DIT-FFT计算，则需要多少次复乘？N/2log2N=4096/2log24096=24576思考题N点x(n)序列，构造新序列y(n)=x(n/2),n为偶数时，y(n)=0，n为奇数时，n=0,1,2,…2N-1，求：Y(K)与X(K)的关系，K=0,1,2,….2N-1例题：KRKXKYNKKXKYWKYNKYKXKYWKYKYNNkNkN22212211,...1,0解：由DIT-FFT可得y(2n)=y1(n)=x(n),Y1(K)=X(K)y(2n+1)=y2(n)=0,Y2(K)=0n=0,1,….,N-1已知x(n)长度为N（N为偶数）。定义两个长度为N/2的序列如下:其中，G(k)=DFT[g(n)],H(k)=DFT[h(n)],分别为N/2长。试利用G(k)和H(k)表示出X(k)=DFT[x(n)]，k=0,1,……N-1。补充题1222112221nxnxnhnxnxng三、按时间抽取的FFT算法的特点1.原位运算（同址运算）x(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－1第一级蝶形运算第二级蝶形运算第三级蝶形运算rNmmmrNmmmWjXkXjXWjXkXkX)()()()()()(1111m表示第m级迭代，k,j为数据所在行数；某一级的两个节点k和j的节点变量进行蝶形运算后，得到结果为下一级k,j两节点的节点变量，即每个蝶形的输入、输出数据节点同在一条水平线上；与其他节点变量无关，即蝶形的两个输出值仍放回蝶形的两个输入所在的存储器中；每级的N/2个蝶形运算全部完成后，再开始下一级的蝶形运算；这样经过M级运算后，原存放输入数据的N个存储单元中依次存放输出的N个值；这种利用同一存储单元存放蝶形计算输入、输出数据的方法称为原位运算。可以节省存储单元,降低设备成本。2.倒位序规律基2的DIT-FFT的输出X(k)按正常顺序排列在存储单元中，即按X(0)，X(1)，…，X(7)的顺序排列；输入x(n)却不是按自然顺序存储的，而是按x(0)，x(4)，…，x(7)的顺序存入存储单元，看起来好像是“混乱无序”的；实际上是有规律的，我们称之为倒位序。n用二进制数表示为(n2n1n0)2（当N=8=23时，二进制为三位）第一次