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

第8章

DSP算法實(shí)現(xiàn)

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

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

N(N-1)次復(fù)數(shù)加法DFT直接算法的運(yùn)算量:返回復(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)因子的這些特性，使得我們計(jì)算DFT更加高效。返回按時(shí)間抽取FFT算法按時(shí)間抽取FFT算法考慮序列x[n]的長度N是2的整數(shù)次冪，即：N=2:

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

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

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

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

m和n之間關(guān)系如下:n:順序排列m:新順序nb0b1b2mb2b1b0000000001100010010011110100001101101110011111111若x[n]的長度不是2的冪次,可以通過補(bǔ)零將序列長度延長為2的冪。返回FFT算法編程FFT算法編程觀察流程圖:FFT算法編程編寫FFT程序，必須解決下面問題:位倒序旋轉(zhuǎn)因子蝶形運(yùn)算返回FFT算法編程位倒序位倒序J=正序00000000序號(hào)001002003004000255000001000100000000000000J=000計(jì)算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的點(diǎn)數(shù).N=256FFT算法編程J：位倒序的序號(hào)I：倒序次數(shù)k：進(jìn)位發(fā)生的位置.c：進(jìn)位有無標(biāo)識(shí)M：最大序號(hào)對應(yīng)的二進(jìn)制位數(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點(diǎn)數(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算法編程我們可以事先計(jì)算出來旋轉(zhuǎn)因子，把它們存在存儲(chǔ)器中。從以上討論可以看出，計(jì)算N-點(diǎn)DFT，需要N/2個(gè)旋轉(zhuǎn)因子。m=0:N/2-1;W=exp(-i*2*pi*m/N);FFT算法編程FFT算法編程對第r-級(jí)運(yùn)算，旋轉(zhuǎn)因子如下式:例如，如果N=8,則R=3；即：計(jì)算8點(diǎn)DFT，要R=3級(jí)蝶形運(yùn)算。

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

forJ=0:B-1;

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

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

q