文獻(xiàn)標(biāo)識(shí)碼: A
DOI:10.16157/j.issn.0258-7998.2016.12.005
中文引用格式: 劉鳳,,龔曉峰,張軍歌. 不同運(yùn)算機(jī)制下FFT計(jì)算精度分析[J].電子技術(shù)應(yīng)用,,2016,,42(12):23-26.
英文引用格式: Liu Feng,Gong Xiaofeng,,Zhang Junge. Accuracy analysis of FFT with different operation mechanism[J].Application of Electronic Technique,,2016,42(12):23-26.
0 引言
FFT(Fast Fourier Transform)是有限長序列DFT(Discrete Fourier Transform)的一種快速算法,是數(shù)字信號(hào)處理中的重要工具,。工程實(shí)踐中,,根據(jù)數(shù)據(jù)表現(xiàn)形式及中間過程截位規(guī)則不同,,可將FFT處理器分為3種:定點(diǎn)FFT、塊浮點(diǎn)FFT及浮點(diǎn)FFT,。相同的FFT算法,,在3種運(yùn)算機(jī)制下,計(jì)算過程中引入舍入誤差不同,,輸出精度存在明顯差異,。經(jīng)研究,F(xiàn)FT算法舍入誤差與算法分解級(jí)數(shù)成正比關(guān)系[1-2],。但舍入誤差的引入與運(yùn)算過程中的截位規(guī)則,、中間結(jié)果范圍緊密相連,因此有必要探究不同范圍的輸入信號(hào),、算法相關(guān)參數(shù)與FFT輸出精度的關(guān)系,,這對(duì)實(shí)際工程應(yīng)用改善輸出精度、提高噪信比具有重要意義,。
1 基4頻域抽取FFT算法
FFT的核心是利用DFT中旋轉(zhuǎn)因子的周期性與對(duì)稱性,,將長序列DFT逐級(jí)分解為短序列的DFT,從而減少運(yùn)算量,,提高運(yùn)算速率[3-5],。常用FFT包括時(shí)域抽取FFT與頻域抽取FFT,現(xiàn)介紹工程中廣泛應(yīng)用的一種頻域抽取FFT算法,,基4頻域抽取算法,。
長度為N的x(n)序列DFT變換為:
x(n)按順序均勻分為4個(gè)序列:x(i),x(i+N/4),,x(i+N/2),,x(i+3N/4)。X(k)則按照除以4所得余數(shù)分為4組:X(4r),,X(4r+1),,X(4r+2),X(4r+3),,i,,r=0,1,,…,,N/4。則基4頻域抽取一次分解為:
從式(1)與式(2)對(duì)比可以看出,,長度為N的長序列進(jìn)行一次基4 DIF分解,,N2次復(fù)數(shù)乘累加的運(yùn)算量,降低至N2/4+2N,,且包含±j,,±1,,W0等因子的單元可進(jìn)一步簡(jiǎn)化運(yùn)算。長度為N的序列,,可進(jìn)行l(wèi)og4 N次分解,,因此FFT算法大大降低離散傅里葉變換運(yùn)算量。
2 定點(diǎn),、塊浮點(diǎn),、浮點(diǎn)FFT運(yùn)算過程
影響FFT輸出精度的因素主要包含:系數(shù)量化誤差,運(yùn)算過程中舍入誤差,。本文主要探究運(yùn)算過程中舍入誤差對(duì)FFT輸出精度的影響,。不同運(yùn)算機(jī)制,數(shù)據(jù)表現(xiàn)形式及輸出截位規(guī)則有較大差異,,引入舍入誤差不同,,導(dǎo)致最小精度不同。因此有必要對(duì)采用定點(diǎn),、塊浮點(diǎn),、浮點(diǎn)運(yùn)算機(jī)制時(shí),基4算法運(yùn)算單元中數(shù)據(jù)表現(xiàn)形式,、輸出截位規(guī)則,、輸出最小精度進(jìn)行分析。
2.1 定點(diǎn)FFT
定點(diǎn)FFT是輸入,、旋轉(zhuǎn)因子、輸出均為定點(diǎn)形式的一種FFT運(yùn)算機(jī)制,。每級(jí)蝶形運(yùn)算,,根據(jù)輸入位寬對(duì)運(yùn)算結(jié)果采取高位截取。如圖1所示,,輸入數(shù)據(jù)位寬為a,,旋轉(zhuǎn)因子位寬為b。蝶形輸入與因子±j,,±1進(jìn)行乘加運(yùn)算,,幅值全范圍位寬擴(kuò)展至a+2位,與b位有符號(hào)旋轉(zhuǎn)因子相乘位寬擴(kuò)展至a+b+1位,,每級(jí)蝶形輸入位寬要求相同,,因此以四舍五入法截取高a位蝶形運(yùn)算結(jié)果進(jìn)行下級(jí)蝶形運(yùn)算。
除去與旋轉(zhuǎn)因子相乘造成的位擴(kuò)寬,,基4定點(diǎn)FFT每級(jí)蝶形運(yùn)算以全范圍位寬溢出2位為前提進(jìn)行舍入,。每進(jìn)行一級(jí)蝶形運(yùn)算,中間結(jié)果最小精度擴(kuò)大4倍,。因此,,輸入序列長度為N時(shí),,輸出FFT最小精度為定點(diǎn)FFT輸出最小精度只與分解級(jí)數(shù)有關(guān)。
2.2 塊浮點(diǎn)FFT
塊浮點(diǎn)FFT與定點(diǎn)FFT區(qū)別在于對(duì)中間截位過程的優(yōu)化,,其結(jié)果包含頻譜數(shù)據(jù)及指數(shù),。定點(diǎn)FFT默認(rèn)每級(jí)蝶形輸出結(jié)果均出現(xiàn)符號(hào)位溢出,事實(shí)上不同量級(jí)的輸入,,中間結(jié)果符號(hào)位溢出情況是不同的,,塊浮點(diǎn)FFT通過監(jiān)測(cè)每級(jí)蝶形運(yùn)算輸出范圍決定截位,從而減少被截取位寬,,降低了舍入誤差,。如圖2所示,以正負(fù)最大的數(shù)值為標(biāo)準(zhǔn),,對(duì)每級(jí)蝶形輸出結(jié)果進(jìn)行截位處理,。
塊浮點(diǎn)FFT通過指數(shù)表征總體移位結(jié)果,輸出指數(shù)為exp,,則最小精度為2exp,,指數(shù)由算法輸入位寬、輸入信號(hào),、運(yùn)算級(jí)數(shù)共同決定,。因此塊浮點(diǎn)最小精度與算法輸入位寬、信號(hào)幅值范圍,、運(yùn)算級(jí)數(shù)相關(guān),。
2.3 浮點(diǎn)FFT
IEEE754標(biāo)準(zhǔn)是1985年IEEE(Institute of Electrical and electronics Engineers,電子電氣工程師協(xié)會(huì))提出的浮點(diǎn)運(yùn)算規(guī)范,,為浮點(diǎn)運(yùn)算部件工業(yè)標(biāo)準(zhǔn)[6],。IEEE754浮點(diǎn)格式如下:
如式(3)所示,IEEE754浮點(diǎn)格式包含一位符號(hào)位,,h位無符號(hào)偏置指數(shù),,k位尾數(shù)。數(shù)據(jù)進(jìn)行二進(jìn)制科學(xué)計(jì)數(shù)法表示后,,指數(shù)部分加上偏置值作為偏置指數(shù),,小數(shù)部分依次截取k位有效數(shù)字作為尾數(shù)。如表1所示,,IEEE754共提供3種位寬的基礎(chǔ)二進(jìn)制浮點(diǎn)格式,。
相同位寬下,浮點(diǎn)格式所表示的數(shù)據(jù)范圍比定點(diǎn)格式大得多,。尾數(shù)最低位權(quán)值為所能表示的最小精度,,因此數(shù)據(jù)越大,浮點(diǎn)表示精度越低。
浮點(diǎn)FFT輸入,、輸出,、旋轉(zhuǎn)因子均為浮點(diǎn)表示形式,涉及的運(yùn)算均遵循浮點(diǎn)運(yùn)算準(zhǔn)則,。計(jì)算結(jié)果有效位寬溢出導(dǎo)致的舍入誤差是浮點(diǎn)FFT主要誤差來源,。
3 噪信比分析
為進(jìn)一步對(duì)不同運(yùn)算機(jī)制下FFT計(jì)算精度問題進(jìn)行探索,我們使用輸出噪信比表征FFT算法相對(duì)誤差,,研究運(yùn)算級(jí)數(shù),、算法輸入位寬與輸入信號(hào)范圍與FFT精度的關(guān)系。
3.1 浮點(diǎn)FFT噪信比
浮點(diǎn)FFT誤差分析相對(duì)困難,,文獻(xiàn)[1]中提出了基2浮點(diǎn)FFT靜態(tài)模型,,輸入為白噪聲時(shí),結(jié)果如公式(4)所示,,噪聲與信號(hào)均方差比值正比于FFT運(yùn)算級(jí)數(shù)v,。文獻(xiàn)[2]則分析了DIF與DIT以及不同基數(shù)下FFT運(yùn)算下的舍入誤差。結(jié)果表明,,浮點(diǎn)FFT輸出噪信比正比于運(yùn)算級(jí)數(shù),。
3.2 定點(diǎn)FFT與塊浮點(diǎn)FFT仿真模型
現(xiàn)于MATLAB平臺(tái)建立定點(diǎn)與塊浮點(diǎn)FFT模型。該模型采用基4頻譜抽取算法,,輸入信號(hào)范圍,、輸入位寬與旋轉(zhuǎn)因子位寬可調(diào)。計(jì)算噪信比N/S=|xm-xmat|/|xmat|,,xm為模型輸出,,xmat為MATLAB平臺(tái)64位浮點(diǎn)計(jì)算值。通過仿真,,得出輸入為隨機(jī)序列時(shí),,輸出噪信比與信號(hào)全范圍位寬Ls、FFT輸入位寬Li,、運(yùn)算級(jí)數(shù)v的關(guān)系。
3.2.1 噪信比與輸入信號(hào)幅值范圍關(guān)系
從圖3與圖4可以看出,,定點(diǎn)FFT噪信比隨輸入信號(hào)范圍增大而下降,。但對(duì)于塊浮點(diǎn)FFT,輸入信號(hào)范圍接近輸入位寬時(shí),,噪信比停止下降,,甚至?xí)杂猩仙_\(yùn)算級(jí)數(shù)固定,,定點(diǎn)FFT輸出最小精度不變,。頻譜分量大于最小精度時(shí),增大信號(hào)輸入范圍,能夠增大頻譜分量,,有效減小頻譜失真率,,降低輸出噪信比。而塊浮點(diǎn)FFT最小精度是隨信號(hào)頻譜分量范圍變化的,,信號(hào)輸入范圍較小時(shí),,塊浮點(diǎn)FFT最小精度不變,呈現(xiàn)與定點(diǎn)FFT相同的規(guī)律,,但隨著信號(hào)范圍增大,,最小精度也隨著變化,因此噪信比不呈現(xiàn)下降的趨勢(shì),。
3.2.2 噪信比與輸入序列長度關(guān)系
從圖5與圖6可以看出,,無論是定點(diǎn)FFT與塊浮點(diǎn)FFT,噪信比都與運(yùn)算級(jí)數(shù)近似正比,。這是隨著運(yùn)算級(jí)數(shù)增加,,舍入誤差線性累積的結(jié)果。
3.2.3 噪信比與FFT輸入位寬關(guān)系
從圖7與圖8可以看出,,定點(diǎn)FFT輸出噪信比與定點(diǎn)FFT輸入位寬無關(guān),,而塊浮點(diǎn)FFT噪信比隨著輸入位寬增大而減小。這是因?yàn)槎c(diǎn)FFT,,輸入位寬并不影響最小精度,。而對(duì)于塊浮點(diǎn)運(yùn)算機(jī)制,F(xiàn)FT輸入位寬的增加,,降低輸出最小精度,,輸出噪信比降低。
4 小信號(hào)FFT精度問題
實(shí)際工程中,,使用FPGA進(jìn)行頻譜計(jì)算,,當(dāng)輸入為白噪聲信號(hào)時(shí),出現(xiàn)頻譜失真的情況,,經(jīng)分析頻譜失真與塊浮點(diǎn)FFT計(jì)算精度有關(guān),。
工程中,對(duì)射頻接收機(jī)輸出信號(hào)進(jìn)行采樣,,經(jīng)過DDC,,不同濾波帶寬濾波抽取后,使用塊浮點(diǎn)FFT ip核進(jìn)行FFT計(jì)算,,F(xiàn)FT輸出結(jié)果進(jìn)行位擴(kuò)展后,,依照式(5)進(jìn)行幅值計(jì)算。
幅值計(jì)算包含對(duì)數(shù)運(yùn)算,,因此在位擴(kuò)展之后,,將FFT ip核輸出實(shí)部虛部分量都為0的點(diǎn)幅值固定為常值1,是幅值計(jì)算過程基于最小值的數(shù)值優(yōu)化。
當(dāng)輸入為白噪聲情況下,,降低信號(hào)帶寬,,出現(xiàn)了圖9所示的信號(hào)頻譜失真。
當(dāng)濾波帶寬較小時(shí),,頻譜能量小,,輸出頻譜分量小于FFT ip核輸出最小精度,因此出現(xiàn)較多零點(diǎn),。
根據(jù)圖4所示規(guī)律,,塊浮點(diǎn)FFT運(yùn)算,當(dāng)信號(hào)范圍較小時(shí),,噪信比隨著輸入范圍增大而減小,。因此可通過擴(kuò)大輸入信號(hào)范圍來減小噪信比,統(tǒng)一將信號(hào)時(shí)域分量擴(kuò)大一定比例值,,以使頻譜分量大于ip核輸出最小精度,,減小頻譜失真,后續(xù)計(jì)算環(huán)節(jié)將比例值抵消后得到新的頻譜如圖10所示,,頻譜失真現(xiàn)象得到改善,,驗(yàn)證了仿真結(jié)論的正確性。
5 結(jié)論
本文通過分析定點(diǎn),、塊浮點(diǎn),、浮點(diǎn)機(jī)制下,基4算法基本單元運(yùn)算數(shù)據(jù)表現(xiàn)形式及截位規(guī)則,,得出不同運(yùn)算機(jī)制下,,F(xiàn)FT舍入誤差及輸出最小精度。利用仿真模型,,得出定點(diǎn),、塊浮點(diǎn)FFT噪信比隨輸入信號(hào)范圍、FFT輸入位寬,、序列長度的變化趨勢(shì),,并基于仿真結(jié)論,解決了實(shí)際工程中會(huì)遇到的小信號(hào)頻譜失真問題,,驗(yàn)證了仿真結(jié)果的正確性,,對(duì)工程師在實(shí)際工作中有很強(qiáng)的借鑒性和參考價(jià)值。
參考文獻(xiàn)
[1] WEINSTEIN C.Roundoff noise in floating point fast Fourier transform computation[J].IEEE Transactions on Audio and Electroacoustics,,1969,17(3):209-215.
[2] THONG T,,LIU B.Accumulation of roundoff errors in floating point FFT[J].IEEE Transactions on Circuits and Systems,,1977,24(3):132-143.
[3] COOLEY J W,TUKEY J W.An algorithm for the machine calculation of complex Fourier series[J].Mathematics of computation,,1965,,19(90):297-301.
[4] COCHRAN W T,COOLEY J W,,F(xiàn)AVIN D L,,et al.What is the fast Fourier transform?[J].Proceedings of the IEEE,1967,,55(10):1664-1674.
[5] BRIGHAM E O,,BRIGHAM E O.The fast Fourier transform[M].Englewood Cliffs,NJ:Prentice-Hall,,1974.
[6] Floating-Point Working Group.IEEE standard for binary floating-point arithmetic[C].SIGPLAN.1987,,22:9-25.