數(shù)字信號處理第8章

第8章

DSP算法實現(xiàn)

8.3離散傅里葉變換(DFT)的計算本節(jié)中，我們討論傅里葉變換的快速算法---FFT算法。我們僅考慮按時間抽取FFT算法。DFT直接算法的運算量復(fù)旋轉(zhuǎn)因子WNkn的性質(zhì)按時間抽取FFT算法的原理8.3離散傅里葉變換(DFT)的計算蝶形運算位倒序FFT算法編程DFT直接算法的運算量N2

次復(fù)數(shù)乘法

N(N-1)次復(fù)數(shù)加法DFT直接算法的運算量:返回復(fù)旋轉(zhuǎn)因子WNk的性質(zhì)我們研究FFT算法，首先要關(guān)注復(fù)旋轉(zhuǎn)因子WNk的性質(zhì):復(fù)旋轉(zhuǎn)因子WNk的性質(zhì)首先，它是k的周期函數(shù)，周期為N:其次，復(fù)旋轉(zhuǎn)因子WNk的性質(zhì)第三，它是關(guān)于k的對稱函數(shù):利用復(fù)旋轉(zhuǎn)因子的這些特性，使得我們計算DFT更加高效。返回按時間抽取FFT算法按時間抽取FFT算法考慮序列x[n]的長度N是2的整數(shù)次冪，即：N=2:

x[0],x[1],x[2],x[3],x[4],…,x[N-1]則x[n]的DFT：令按時間抽取FFT算法x[0],x[1],x[2],x[3],x[4],…,x[N-1]

令：按時間抽取FFT算法流程圖表示N=2=8(N2/2)+N

復(fù)數(shù)乘法(N2/2)復(fù)數(shù)加法按時間抽取FFT算法再令：得到： 按時間抽取FFT算法流程圖表示N=2=8按時間抽取FFT算法這四個2點DFT：Xij[k],i,j=0,1，很容易計算出來按時間抽取FFT算法8-點DFT的完整流圖如下：按時間抽取FFT算法整個流圖包含3級。第一級計算四個2-點DFT；第二級計算兩個4-點DFT；第三級計算期望的8-點DFT。每一級的復(fù)數(shù)乘法和復(fù)數(shù)加法的次數(shù)均為8，即DFT變換的點數(shù)。按時間抽取FFT算法DFT直接算法和基-2FFT算法的比較：返回蝶形運算可以進一步簡化運算。.在上面過程中，我們考慮同和的相乘也為復(fù)數(shù)。利用對稱性質(zhì):蝶形運算重新再看流圖:流圖顯示DFT運算過程中的每一級都用到了相同的基本運算模塊。蝶形運算基本運算模塊稱為蝶形運算。蝶形運算基本運算模塊稱為蝶形運算。蝶形運算基本運算模塊稱為蝶形運算。蝶形運算利用改進的蝶形運算模塊，使FFT計算的復(fù)數(shù)乘法的總數(shù)減少了50%.蝶形運算N=8,μ=3蝶形運算改進的蝶形運算模塊的新流圖，N=8:蝶形運算上述改進的FFT算法的另一個吸引人的特性是存儲要求。避免，，和的乘法，進一步降低了運算復(fù)雜度。蝶形運算我們從[]和[]計算出

+1[]和+1[]，它們可以存在[]和[]先前存放的位置，這種存儲位置共享特性通常稱為同址計算，明顯節(jié)省了整個算法的存儲要求。返回位倒序位倒序在算法流圖中可以看出：DFT樣本X[k]在輸出端順序排列時，輸入時域樣本x[n]不是順序排列的。位倒序來看下面的流程圖:位倒序變量

m和n之間關(guān)系如下:n:順序排列m:新順序nb0b1b2mb2b1b0000000001100010010011110100001101101110011111111若x[n]的長度不是2的冪次,可以通過補零將序列長度延長為2的冪。返回FFT算法編程FFT算法編程觀察流程圖:FFT算法編程編寫FFT程序，必須解決下面問題:位倒序旋轉(zhuǎn)因子蝶形運算返回FFT算法編程位倒序位倒序J=正序00000000序號001002003004000255000001000100000000000000J=000計算JIfJ<N/2,thenJ=J+N/2=12800000001IfJ≥N/2，thenJ=J-N/2+N/4=64000000100010000010000000IfJ<N/2，thenJ=J+N/2=64+128=192If(J≥N/2)thenJ=J–N/2If(J≥N/4)thenJ=J-N/4If(J<N/8)thenJ=J+N/8=3211111111111111110000001111000000相同的J=255N是DFT的點數(shù).N=256FFT算法編程J：位倒序的序號I：倒序次數(shù)k：進位發(fā)生的位置.c：進位有無標(biāo)識M：最大序號對應(yīng)的二進制位數(shù)I=1:N-2J=0J≥N/2kJ=J-N/2kJ=J+N/2kc=1x1(I+1)=x(J+1)k~=M+1&c~=1k=1;c=0;k=k+1YYNNc=0N：DFT點數(shù).FFT算法編程%Name:bit_reversed_orderx=input(‘Typeinthesequence:');N=length(x);M=log2(N);x1=zeros(1,N);x1(1)=x(1);x1(N)=x(N);J=0;forI=1:N-2;

k=1;c=0;

whilek~=M+1&c~=1;

if

J>=N/(2.^k);J=J-N/(2.^k);c=0;

elseJ=J+N/(2.^k);c=1;

end

k=k+1;

end

x1(I+1)=x(J+1);end返回FFT算法編程我們可以事先計算出來旋轉(zhuǎn)因子，把它們存在存儲器中。從以上討論可以看出，計算N-點DFT，需要N/2個旋轉(zhuǎn)因子。m=0:N/2-1;W=exp(-i*2*pi*m/N);FFT算法編程FFT算法編程對第r-級運算，旋轉(zhuǎn)因子如下式:例如，如果N=8,則R=3；即：計算8點DFT，要R=3級蝶形運算。

旋轉(zhuǎn)因子的指數(shù)為：返回FFT算法編程蝶形運算對第1級:r=1FFT算法編程對第1級:r=1FFT算法編程對第1級:r=1FFT算法編程對第2級,r=2FFT算法編程對第2級,r=2FFT算法編程對第2級,r=2FFT算法編程對第2級,r=2FFT算法編程對第2級,r=2FFT算法編程對第3級:r=3forr=1:M;%risthestageindexB=2^(r-1);%Bisthedistanceoftwoinputsfor%蝶形運算

forJ=0:B-1;

p=2^(M-r)*J;%Computetheexponentof%weightingfactor

fork=J+1:2^r:N-1;

q