數(shù)字信號處理 黃海 課件第九章-離散傅里葉變換的計(jì)算

第九章離散傅立葉變換的計(jì)算ComputationoftheDiscreteFourierTransform9.0引言DFT算法速度-----算法有效性的最重要性能指標(biāo) （功耗、資源）DFT的有效算法：快速傅立葉變換（FastFourierTransform,FFT）算法速度------乘法和加法的次數(shù)FFT的意義： 使DFT理論在實(shí)際中得到應(yīng)用 也是信號處理技術(shù)得以普及的重要因素之一9.1離散傅立葉變換的高效計(jì)算一個N點(diǎn)序列的DFT為：

其反變換為：式中正、反變換的計(jì)算基本相同（僅符號和系數(shù)），算法可直接使用直接計(jì)算的計(jì)算量：x[n]通用性考慮----復(fù)數(shù)每計(jì)算一個X[k]值需要：N次復(fù)數(shù)乘法和N-1次復(fù)數(shù)加法全部X[k]值需要：N2次復(fù)數(shù)乘法和N(N-1)次復(fù)數(shù)加法考慮到每次復(fù)數(shù)乘法需：4次實(shí)數(shù)乘法和2次實(shí)數(shù)加法 每次復(fù)數(shù)加法需：2次實(shí)數(shù)加法直接計(jì)算量：

4N2次實(shí)數(shù)乘法和2N(2N-1)次實(shí)數(shù)加法計(jì)算量與N2成正比，當(dāng)N很大時，計(jì)算次數(shù)巨大，計(jì)算時間非常長例：當(dāng)N=1024，需四百多萬次實(shí)數(shù)乘法，實(shí)時性要求難以滿足改善DFT計(jì)算效率的一些方法：主要利用的對稱性和周期性（1）復(fù)共軛對稱性（2）對n和k的周期性（3）的有些值為0或1將某些計(jì)算項(xiàng)合并或無需乘法和加法運(yùn)算但計(jì)算量減少非常有限，不能滿足實(shí)際的要求Cooley和Tukey于1965年發(fā)表了一個快速的算法，由Cooley提出思想，Tukey完成實(shí)際的算法（程序）

------在信號處理應(yīng)用領(lǐng)域具有劃時代的意義9.3按時間抽取的FFT算法FFT算法的基本思想： 計(jì)算量與N2成正比 將計(jì)算逐次分解成較短序列的DFT計(jì)算組合最終結(jié)果 同時利用的周期性和對稱性假設(shè)序列點(diǎn)數(shù)，ν為整數(shù)，也稱基-2FFT算法由N為偶整數(shù)，將序列分解為奇數(shù)點(diǎn)和偶數(shù)點(diǎn)兩組序列DFT可以表示為：作變量代換，n=2r

（偶數(shù)）；n=2r+1（奇數(shù)）因?yàn)?，上式可寫為：式中：G[k]------原序列偶數(shù)點(diǎn)的N/2點(diǎn)DFT（周期為N/2）

H[k]------原序列奇數(shù)點(diǎn)的N/2點(diǎn)DFT（周期為N/2）例N=8時，上述的計(jì)算過程如圖：計(jì)算量：兩次N/2點(diǎn)DFT+組合運(yùn)算復(fù)數(shù)乘法：2×(N/2)2+N=N2/2+N復(fù)數(shù)加法：2×(N/2)(N/2-1)+N=N2/2與直接計(jì)算相比，當(dāng)N較大時，運(yùn)算量減少接近一半可以進(jìn)一步作上述的分解，即每一個N/2點(diǎn)DFT可以分解為兩個（按奇、偶）N/4點(diǎn)DFT并進(jìn)行組合。-------得到N/2點(diǎn)DFT即可表示為：N2N(N-1)以及：g[2l]和g[2l+1]的N/4點(diǎn)DFT+組合運(yùn)算=N/2點(diǎn)DFT-----G[k]h[2l]和h[2l+1]的N/4點(diǎn)DFT+組合運(yùn)算=N/2點(diǎn)DFT-----H[k]如圖所示：整個計(jì)算過程可表示為（考慮到，用統(tǒng)一的系數(shù)）2點(diǎn)的DFT --------本身就是組合運(yùn)算對于N=8來說，N/4=2，2點(diǎn)的DFT一般形式可用圖表示為：最終的整個計(jì)算過程可表示為：假定序列點(diǎn)數(shù)：N=2ν分解過程最終：計(jì)算2點(diǎn)的DFT-----組合運(yùn)算整個DFT計(jì)算過程：分解為一系列組合運(yùn)算分解運(yùn)算數(shù)目：ν級分解，ν

=log2N每一級的計(jì)算（組合運(yùn)算）：

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

N次復(fù)數(shù)加法整個運(yùn)算量：Nlog2N

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

Nlog2N

次復(fù)數(shù)加法利用的周期性，可以繼續(xù)減少計(jì)算次數(shù)。每一級的組合運(yùn)算：表示為N/2個碟形的運(yùn)算：考慮到：有則碟形運(yùn)算表示為：只需要1次復(fù)數(shù)乘法最終8點(diǎn)的FFT算法結(jié)構(gòu)圖為：利用的周期性，實(shí)際的FFT復(fù)數(shù)乘法次數(shù)可以減少一倍，即：(N/2)log2N

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

次復(fù)數(shù)加法比較N=1024直接計(jì)算：N=210，N2=220=1,048,576復(fù)數(shù)乘法FFT計(jì)算：(N/2)log2N=5,120減少200多倍的復(fù)數(shù)乘法，N越大效果越明顯9.3.1同址計(jì)算基-2FFT:點(diǎn)數(shù)N=2ν，ν級分解運(yùn)算，每級N/2個蝶形運(yùn)算每個蝶形運(yùn)算：1次復(fù)數(shù)乘法，2次復(fù)數(shù)加法整個DFT運(yùn)算(N/2)log2N

個蝶形運(yùn)算每一級:N個復(fù)數(shù)（輸入）N/2個蝶形運(yùn)算N個復(fù)數(shù)（輸出）每一個蝶形運(yùn)算可表示為：

m----節(jié)點(diǎn)的列數(shù)p,q-----節(jié)點(diǎn)的行數(shù)用方程表示為：兩個復(fù)數(shù)（輸入）乘法、加法兩個復(fù)數(shù)（輸出）表示：蝶形運(yùn)算的輸出只與相應(yīng)的輸入節(jié)點(diǎn)值有關(guān)，而與其他節(jié)點(diǎn)無關(guān)輸出值可以覆蓋輸入值（放到輸入值的存儲單元） 同址計(jì)算整個計(jì)算過程只需要N個復(fù)數(shù)寄存器為實(shí)現(xiàn)同址技術(shù)，輸入序列放置順序-----非正常排序：需要倒序過程：以N=8=23為例，將N表示成3位二進(jìn)制碼：n2n1n0序列x[n]=x[n2n1n0]，如x[3]=x[011]正常排序方式為從高位n2到低位n0倒序表示：可見，倒序只需將序列x[n]=x[n2n1n0]X0[n]=x[n0n1n2]例x[3]=x[011]x[110]=X0[6]倒序方式：從低位n0到高位n2奇偶分組對x[n]進(jìn)行分組即在時間域分組稱時間抽取全稱：基2時間抽取法9.4按頻率抽取的FFT算法將輸出序列（結(jié)果）X

[k]進(jìn)行分組，分成越來越短的序列稱：基2頻率抽取法因?yàn)槠渑夹蛄袨榭梢员硎緸榇鷵Q第二個求和變量（與第一個相同）由的周期性：并由可得：序列x[n]N點(diǎn)DFTX[k]的偶序列X[2r]：

序列x[n]前N/2點(diǎn)與后N/2點(diǎn)之和的N/2點(diǎn)DFT同樣，DFTX[k]的奇序列X[2r+1]為：

同前，重寫為：第二和式其中考慮到：奇序列可寫為：改變系數(shù)形式，序列x[n]N點(diǎn)DFTX[k]的奇序列X[2r+1]：序列x[n]前N/2點(diǎn)與后N/2點(diǎn)之差并乘以系數(shù)后的N/2點(diǎn)DFT定義兩個N/2點(diǎn)序列：

g[n]=x[n]+x[n+N/2]

h[n]=x[n]-x[n+N/2]DFT可以表示為：計(jì)算g[n]和h[n]計(jì)算h[n]分別計(jì)算相應(yīng)的N/2點(diǎn)DFT不直接計(jì)算N/2點(diǎn)的DFT，重復(fù)上述過程，用N/4點(diǎn)的DFT來代替同樣，可以繼續(xù)重復(fù)上述過程，直至最終只需求2點(diǎn)的DFT而2點(diǎn)的DFT也可以用下圖的蝶形運(yùn)算：當(dāng)N=8時的基2頻率抽取法流程圖：與基2時間抽取算法比較，（1）整個算法都由一系列蝶形運(yùn)算組成（2）蝶形運(yùn)算的級數(shù)相同，均為ν級，即N=2ν（3）每一級的蝶形運(yùn)算數(shù)相同，均為N/2個（4）蝶形運(yùn)算的具體計(jì)算不同，加減與乘系數(shù)次序相反（5）整個算法的計(jì)算量相同，均為

復(fù)數(shù)乘法次數(shù)：(N/2)log2N

復(fù)數(shù)加法次數(shù)：Nlog2N

（6）都具有同址計(jì)算特性（7）輸入不倒序，輸出倒序，即先計(jì)算后倒序（8）倒序方法相同9.5實(shí)現(xiàn)問題考慮（1）倒序

時間抽?。狠斎氲剐?，輸出不倒序

頻率抽?。狠敵龅剐?，輸入不倒序

倒序過程----可同址進(jìn)行，成對交換，不存在abc

如：x[1]x[4]，x[3]x[6]（2）碟距碟距：蝶形運(yùn)算的兩點(diǎn)之間距離------(q-p)=2m-1第一級=1；第二級=2；第三級=4（3）系數(shù)的確定如何確定r：（根據(jù)m,p）

p----蝶形兩節(jié)點(diǎn)的第一節(jié)點(diǎn)標(biāo)號值（從0開始）p

ν

位二進(jìn)制數(shù)左移ν

–m位（右邊補(bǔ)0）r值如N=8,ν

=3m=2,p=1,ν

–m=1,p=00

1010r=2

的產(chǎn)生：建立系數(shù)表；用正、余弦函數(shù)；利用遞推

如：（4）離散傅立葉反變換（IDFT）的快速算法兩種方法：第一種：進(jìn)行FFT，輸出乘以1/Nx[n]第二種：（5）一般N值的FFT算法

N為復(fù)合數(shù)：N=RQ

混合基算法R

個Q點(diǎn)DFT的和，或Q

個R點(diǎn)DFT的和算