按時間抽取基-2快速傅里葉變換的誤差分析_第1頁
按時間抽取基-2快速傅里葉變換的誤差分析_第2頁
按時間抽取基-2快速傅里葉變換的誤差分析_第3頁
按時間抽取基-2快速傅里葉變換的誤差分析_第4頁
全文預覽已結束

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領

文檔簡介

按時間抽取基-2快速傅里葉變換的誤差分析

由于2-2傅里葉變換(dft)的運算量從二維減少到nlbn,因此該算法在實時處理器中得到了廣泛應用。如Welch討論了定點運算的防溢出問題,給出了塊浮點FFT輸出的誤差限;Thong和Liu考慮了塊浮點FFT輸出誤差的直流分量;Meyer分析了蝶算中不同量化位置對FFT性能的影響;Ma和Reddy考慮了截斷誤差相關性;Chowdary和Steenaart通過增加運算字長的方法減小了FFT誤差。但均沒有給出明確的誤差分析模型,且有的推導依據(jù)不充分,實際應用性不強。FFT算法的誤差分析對于FFT硬件處理器的設計非常重要,利用它可大致估計出所需的運算字長和變換點數(shù),并可得到較準確的FFT輸出結果精度和信噪比。作者對DIT基-2FFT算法的誤差進行了分析,給出了明確的誤差分析模型,得到了準確的FFT輸出誤差限。為簡化分析和推導過程,只考慮蝶形運算中的有限字長引入的均方誤差,不考慮FFT輸出誤差的直流分量。1fft的算法對N點DFT運算,有X(k)=Ν-1∑n=0x(n)WnkΝ,k=0,1,…,N-1。(1)DIT基-2FFT算法按輸入數(shù)據(jù)時標的奇偶逐級進行分解,最終將N=2υ(υ為正整數(shù))點的DFT運算轉(zhuǎn)化為υ=lbN級,每級N/2個2點蝶形運算,每一蝶算結構完成如下迭代運算:{Xs(i)=Xs-1(i)+Xs-1(j)WkΝ?Xs(j)=Xs-1(i)-Xs-1(j)WkΝ?(2)式中:s為蝶形運算的級數(shù),s=1,2,…,υ;i,j為數(shù)據(jù)所在行數(shù)和列數(shù);WN=exp(-j2π/N)。根據(jù)DIT基-2FFT算法的信號流圖,可以得到FFT蝶算誤差的規(guī)律如下:①復乘誤差源從第三級蝶算開始,第s級蝶算的復乘誤差源數(shù)目為2υ-s+1(2s-2-1);②第s級蝶算的每個復乘誤差源傳播到FFT輸出結果中的2υ-s+1個頻點;③復移誤差源從第一級蝶算開始,每個FFT輸出結果的復移誤差源數(shù)目都是υ∑s=12υ-s=2υ-1。2復加運算的信息輸出算法FFT算法實現(xiàn)中常用的是定點和塊浮點兩種數(shù)據(jù)格式,塊浮點FFT以定點運算的高速度達到了浮點運算的高精度。一次基-2蝶算最大溢出為2bit,復乘運算時可能溢出1bit,復加運算時又可能溢出1bit,故需對這兩級運算進行符號擴展,以防止輸入信號動態(tài)范圍過大時定點加法運算溢出。塊浮點FFT算法的實現(xiàn)由溢出檢測單元和指數(shù)累加單元兩部分組成。溢出檢測單元對每級FFT蝶算結果進行溢出檢測,輸出結果為本級蝶算的最大溢出位數(shù),范圍為0~2bit。指數(shù)累加單元對每級FFT的溢出檢測結果進行累加,最后得到一幀F(xiàn)FT結果的塊浮點指數(shù)。根據(jù)上述討論可知,DIT基-2FFT算法的定點FFT的蝶算誤差分析模型如圖1所示,塊浮點FFT的蝶算誤差分析模型如圖2所示。3fft的均方誤差對實數(shù)乘法和實數(shù)移位運算,假設數(shù)據(jù)格式為(b+1)bit的二進制補碼,截斷、舍入和收斂舍入(舍入到最近偶數(shù))3種量化方法的均值與方差如表1所示,Q=2-b為量化步長。假設FFT輸入數(shù)據(jù)的塊浮點指數(shù)為0,誤差上限時每級FFT蝶算發(fā)生一次溢出,且溢出由復加運算引入,誤差下限時無溢出,各誤差源之間無關。根據(jù)表1以及圖1、圖2所示的誤差分析模型,可以得到第s級蝶算的均方誤差如表2所示。由表2可以看出,舍入與收斂舍入兩種量化方法的均方誤差大小相等,所以下面只計算FFT輸出的截斷均方誤差和舍入均方誤差。3.1中斷量化誤差3.1.1輸出頻點復乘均方誤差誤差上限時,由于第s級蝶算有2υ-s+1(2s-1-1)個復乘誤差源,每個復乘誤差源傳播到FFT輸出結果中的2υ-s+1個頻點,第s級蝶算的復乘均方誤差為7Q222(s-1)/3,所以FFT所有輸出頻點復乘均方誤差的總和為δmut=υ∑s=32υ-s+1(2s-2-1)2υ-s+17Q2322(s-1)=7Q26(Ν3-2Ν2lbΝ)。(3)平均每個輸出頻點的復乘均方誤差為δmu=δmutΝ=7Q26(Ν2-2ΝlbΝ)。(4)誤差上限時,由于每個FFT輸出頻點的復移誤差源數(shù)目都是υ∑s=12υ-s=2υ-1,第s級蝶算的復移均方誤差為Q222s/4,所以每個FFT輸出頻點的復移均方誤差為δsu=υ∑s=12υ-sQ2422s=Q22(Ν2-Ν)。(5)誤差下限時,第s級蝶算的復乘均方誤差為7Q2/3,故此時FFT所有輸出頻點復乘均方誤差的總和為δmlt=υ∑s=32υ-s+1(2s-2-1)2υ-s+17Q23=7Q218(Ν2-6Ν+8)。(6)平均每個輸出頻點的復乘均方誤差為δml=δmltΝ=7Q218(Ν-6+8Ν)。(7)由于誤差下限時沒有溢出,所以此時的復移均方誤差為0,即δsl=0。(8)3.1.2復移均方誤差誤差上限時,定點FFT的復乘均方誤差與塊浮點FFT誤差下限時相同,見式(6)(7),復移均方誤差為δsu=υ∑s=12υ-sQ24=Q24(Ν-1)。(9)誤差下限時,定點FFT的復乘、復移均方誤差與塊浮點FFT時誤差下限時相同,見式(6)(7)(8)。3.2單元源的量化誤差根據(jù)表2,同上述分析方法,可以求得舍入量化時塊浮點、定點兩種FFT輸出的誤差上限和下限。3.2.1復移均方誤差的上限和下限誤差上限時,FFT所有輸出頻點復乘均方誤差的總和為δmut=υ∑s=32υ-s+1(2s-2-1)2υ-s+1Q2322(s-1)=Q26(Ν3-2Ν2lbΝ)。(10)平均每個輸出頻點的復乘均方誤差為δmu=δmutΝ=Q26(Ν2-2ΝlbΝ)。(11)復移均方誤差與截斷量化方法塊浮點FFT的誤差上限時相同,見式(5)。誤差下限時,FFT所有輸出頻點復乘均方誤差的總和為δmlt=υ∑s=32υ-s+1(2s-2-1)2υ-s+1Q23=Q218(Ν2-6Ν+8)。(12)平均每個輸出頻點的復乘均方誤差為δml=δmltΝ=Q218(Ν-6+8Ν)。(13)誤差下限時沒有溢出,此時的復移均方誤差為0,即δsl=0。(14)3.2.2復移均方誤差與斷續(xù)量化方法的關系誤差上限時,定點FFT的復乘均方誤差與塊浮點FFT誤差下限時相同,見式(12)(13)。復移均方誤差與截斷量化方法定點FFT的誤差上限時相同,見式(9)。誤差下限時,定點FFT的復乘、復移均方誤差與塊浮點FFT時誤差下限時相同,見式(12)(13)(14)。4fft輸出噪信比比較為了簡化分析,假定FFT輸入數(shù)據(jù)x(n)對不同的n值無關,且x(n)的實部、虛部均勻分布在[-1,1)上且無關,則有E{|x(n)|2}=2/3,E{|X(k)|2}=2N/3。根據(jù)本文3中得到的平均每個FFT輸出頻點的均方誤差,可以得到誤差上、下限時平均每個FFT輸出頻點相應的噪信比(RNS)如表3所示。由表3可以得到,誤差下限時,對相同的量化方法,塊浮點、定點兩種FFT算法的RNS相等;舍入(收斂舍入)量化時的RNS比截斷量化時低了大約8dB。誤差上限時,對相同的量化方法和固定的FFT點數(shù)N,塊浮點FFT的RNS上限比定點FFT低了大約

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論