0 引言

    FFT（Fast Fourier Transform）是有限長序列DFT（Discrete Fourier Transform）的一種快速算法,，是數(shù)字信號處理中的重要工具。工程實踐中,，根據(jù)數(shù)據(jù)表現(xiàn)形式及中間過程截位規(guī)則不同,，可將FFT處理器分為3種：定點FFT、塊浮點FFT及浮點FFT,。相同的FFT算法,，在3種運(yùn)算機(jī)制下，計算過程中引入舍入誤差不同,，輸出精度存在明顯差異,。經(jīng)研究，F(xiàn)FT算法舍入誤差與算法分解級數(shù)成正比關(guān)系^[1-2],。但舍入誤差的引入與運(yùn)算過程中的截位規(guī)則,、中間結(jié)果范圍緊密相連,，因此有必要探究不同范圍的輸入信號、算法相關(guān)參數(shù)與FFT輸出精度的關(guān)系,，這對實際工程應(yīng)用改善輸出精度,、提高噪信比具有重要意義。

1 基4頻域抽取FFT算法

    FFT的核心是利用DFT中旋轉(zhuǎn)因子的周期性與對稱性,，將長序列DFT逐級分解為短序列的DFT,，從而減少運(yùn)算量，提高運(yùn)算速率^[3-5],。常用FFT包括時域抽取FFT與頻域抽取FFT,，現(xiàn)介紹工程中廣泛應(yīng)用的一種頻域抽取FFT算法，基4頻域抽取算法,。

    長度為N的x(n)序列DFT變換為：

    x(n)按順序均勻分為4個序列：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)對比可以看出,，長度為N的長序列進(jìn)行一次基4 DIF分解,，N²次復(fù)數(shù)乘累加的運(yùn)算量，降低至N²/4+2N,，且包含±j,，±1，W⁰等因子的單元可進(jìn)一步簡化運(yùn)算,。長度為N的序列,，可進(jìn)行l(wèi)og₄ N次分解，因此FFT算法大大降低離散傅里葉變換運(yùn)算量,。

2 定點,、塊浮點、浮點FFT運(yùn)算過程

    影響FFT輸出精度的因素主要包含：系數(shù)量化誤差,，運(yùn)算過程中舍入誤差,。本文主要探究運(yùn)算過程中舍入誤差對FFT輸出精度的影響,。不同運(yùn)算機(jī)制，數(shù)據(jù)表現(xiàn)形式及輸出截位規(guī)則有較大差異,，引入舍入誤差不同,，導(dǎo)致最小精度不同。因此有必要對采用定點,、塊浮點,、浮點運(yùn)算機(jī)制時，基4算法運(yùn)算單元中數(shù)據(jù)表現(xiàn)形式,、輸出截位規(guī)則,、輸出最小精度進(jìn)行分析。

2.1 定點FFT

    定點FFT是輸入,、旋轉(zhuǎn)因子,、輸出均為定點形式的一種FFT運(yùn)算機(jī)制。每級蝶形運(yùn)算,，根據(jù)輸入位寬對運(yùn)算結(jié)果采取高位截取,。如圖1所示，輸入數(shù)據(jù)位寬為a,，旋轉(zhuǎn)因子位寬為b,。蝶形輸入與因子±j，±1進(jìn)行乘加運(yùn)算,，幅值全范圍位寬擴(kuò)展至a+2位,，與b位有符號旋轉(zhuǎn)因子相乘位寬擴(kuò)展至a+b+1位，每級蝶形輸入位寬要求相同,，因此以四舍五入法截取高a位蝶形運(yùn)算結(jié)果進(jìn)行下級蝶形運(yùn)算,。

    除去與旋轉(zhuǎn)因子相乘造成的位擴(kuò)寬，基4定點FFT每級蝶形運(yùn)算以全范圍位寬溢出2位為前提進(jìn)行舍入,。每進(jìn)行一級蝶形運(yùn)算，中間結(jié)果最小精度擴(kuò)大4倍,。因此,，輸入序列長度為N時，輸出FFT最小精度為定點FFT輸出最小精度只與分解級數(shù)有關(guān),。

2.2 塊浮點FFT

    塊浮點FFT與定點FFT區(qū)別在于對中間截位過程的優(yōu)化,，其結(jié)果包含頻譜數(shù)據(jù)及指數(shù)。定點FFT默認(rèn)每級蝶形輸出結(jié)果均出現(xiàn)符號位溢出,，事實上不同量級的輸入,，中間結(jié)果符號位溢出情況是不同的，塊浮點FFT通過監(jiān)測每級蝶形運(yùn)算輸出范圍決定截位，從而減少被截取位寬,，降低了舍入誤差,。如圖2所示，以正負(fù)最大的數(shù)值為標(biāo)準(zhǔn),，對每級蝶形輸出結(jié)果進(jìn)行截位處理,。

    塊浮點FFT通過指數(shù)表征總體移位結(jié)果，輸出指數(shù)為exp,，則最小精度為2^exp,，指數(shù)由算法輸入位寬、輸入信號,、運(yùn)算級數(shù)共同決定,。因此塊浮點最小精度與算法輸入位寬、信號幅值范圍,、運(yùn)算級數(shù)相關(guān),。

2.3 浮點FFT

    IEEE754標(biāo)準(zhǔn)是1985年IEEE（Institute of Electrical and electronics Engineers，電子電氣工程師協(xié)會）提出的浮點運(yùn)算規(guī)范,，為浮點運(yùn)算部件工業(yè)標(biāo)準(zhǔn)^[6],。IEEE754浮點格式如下：

    如式(3)所示，IEEE754浮點格式包含一位符號位,，h位無符號偏置指數(shù),，k位尾數(shù)。數(shù)據(jù)進(jìn)行二進(jìn)制科學(xué)計數(shù)法表示后,，指數(shù)部分加上偏置值作為偏置指數(shù),，小數(shù)部分依次截取k位有效數(shù)字作為尾數(shù)。如表1所示,，IEEE754共提供3種位寬的基礎(chǔ)二進(jìn)制浮點格式,。

    相同位寬下，浮點格式所表示的數(shù)據(jù)范圍比定點格式大得多,。尾數(shù)最低位權(quán)值為所能表示的最小精度,，因此數(shù)據(jù)越大，浮點表示精度越低,。

    浮點FFT輸入,、輸出,、旋轉(zhuǎn)因子均為浮點表示形式,，涉及的運(yùn)算均遵循浮點運(yùn)算準(zhǔn)則。計算結(jié)果有效位寬溢出導(dǎo)致的舍入誤差是浮點FFT主要誤差來源,。

3 噪信比分析

    為進(jìn)一步對不同運(yùn)算機(jī)制下FFT計算精度問題進(jìn)行探索,，我們使用輸出噪信比表征FFT算法相對誤差，研究運(yùn)算級數(shù),、算法輸入位寬與輸入信號范圍與FFT精度的關(guān)系,。

3.1 浮點FFT噪信比

    浮點FFT誤差分析相對困難,，文獻(xiàn)[1]中提出了基2浮點FFT靜態(tài)模型，輸入為白噪聲時,，結(jié)果如公式(4)所示,，噪聲與信號均方差比值正比于FFT運(yùn)算級數(shù)v。文獻(xiàn)[2]則分析了DIF與DIT以及不同基數(shù)下FFT運(yùn)算下的舍入誤差,。結(jié)果表明,，浮點FFT輸出噪信比正比于運(yùn)算級數(shù)。

3.2 定點FFT與塊浮點FFT仿真模型

    現(xiàn)于MATLAB平臺建立定點與塊浮點FFT模型,。該模型采用基4頻譜抽取算法,，輸入信號范圍、輸入位寬與旋轉(zhuǎn)因子位寬可調(diào),。計算噪信比N/S=|x_m-x_mat|/|x_mat|,，x_m為模型輸出，x_mat為MATLAB平臺64位浮點計算值,。通過仿真,，得出輸入為隨機(jī)序列時，輸出噪信比與信號全范圍位寬Ls,、FFT輸入位寬Li,、運(yùn)算級數(shù)v的關(guān)系。

3.2.1 噪信比與輸入信號幅值范圍關(guān)系

    從圖3與圖4可以看出,，定點FFT噪信比隨輸入信號范圍增大而下降,。但對于塊浮點FFT，輸入信號范圍接近輸入位寬時,，噪信比停止下降,，甚至?xí)杂猩仙＿\(yùn)算級數(shù)固定,，定點FFT輸出最小精度不變,。頻譜分量大于最小精度時，增大信號輸入范圍,，能夠增大頻譜分量,，有效減小頻譜失真率，降低輸出噪信比,。而塊浮點FFT最小精度是隨信號頻譜分量范圍變化的,，信號輸入范圍較小時，塊浮點FFT最小精度不變,，呈現(xiàn)與定點FFT相同的規(guī)律,，但隨著信號范圍增大，最小精度也隨著變化，因此噪信比不呈現(xiàn)下降的趨勢,。

3.2.2 噪信比與輸入序列長度關(guān)系

    從圖5與圖6可以看出,，無論是定點FFT與塊浮點FFT，噪信比都與運(yùn)算級數(shù)近似正比,。這是隨著運(yùn)算級數(shù)增加,，舍入誤差線性累積的結(jié)果。

3.2.3 噪信比與FFT輸入位寬關(guān)系

    從圖7與圖8可以看出,，定點FFT輸出噪信比與定點FFT輸入位寬無關(guān),，而塊浮點FFT噪信比隨著輸入位寬增大而減小。這是因為定點FFT,，輸入位寬并不影響最小精度,。而對于塊浮點運(yùn)算機(jī)制，F(xiàn)FT輸入位寬的增加,，降低輸出最小精度,，輸出噪信比降低。

4 小信號FFT精度問題

    實際工程中,，使用FPGA進(jìn)行頻譜計算,，當(dāng)輸入為白噪聲信號時，出現(xiàn)頻譜失真的情況,，經(jīng)分析頻譜失真與塊浮點FFT計算精度有關(guān),。

    工程中，對射頻接收機(jī)輸出信號進(jìn)行采樣,，經(jīng)過DDC,，不同濾波帶寬濾波抽取后，使用塊浮點FFT ip核進(jìn)行FFT計算,，F(xiàn)FT輸出結(jié)果進(jìn)行位擴(kuò)展后,，依照式(5)進(jìn)行幅值計算。

    幅值計算包含對數(shù)運(yùn)算,，因此在位擴(kuò)展之后,，將FFT ip核輸出實部虛部分量都為0的點幅值固定為常值1，是幅值計算過程基于最小值的數(shù)值優(yōu)化,。

    當(dāng)輸入為白噪聲情況下,，降低信號帶寬，出現(xiàn)了圖9所示的信號頻譜失真,。

    當(dāng)濾波帶寬較小時,，頻譜能量小，輸出頻譜分量小于FFT ip核輸出最小精度,，因此出現(xiàn)較多零點,。

    根據(jù)圖4所示規(guī)律，塊浮點FFT運(yùn)算,，當(dāng)信號范圍較小時,，噪信比隨著輸入范圍增大而減小。因此可通過擴(kuò)大輸入信號范圍來減小噪信比,，統(tǒng)一將信號時域分量擴(kuò)大一定比例值,，以使頻譜分量大于ip核輸出最小精度，減小頻譜失真,，后續(xù)計算環(huán)節(jié)將比例值抵消后得到新的頻譜如圖10所示,，頻譜失真現(xiàn)象得到改善，驗證了仿真結(jié)論的正確性,。

5 結(jié)論

    本文通過分析定點,、塊浮點、浮點機(jī)制下,，基4算法基本單元運(yùn)算數(shù)據(jù)表現(xiàn)形式及截位規(guī)則,，得出不同運(yùn)算機(jī)制下，F(xiàn)FT舍入誤差及輸出最小精度,。利用仿真模型,，得出定點、塊浮點FFT噪信比隨輸入信號范圍,、FFT輸入位寬,、序列長度的變化趨勢，并基于仿真結(jié)論,，解決了實際工程中會遇到的小信號頻譜失真問題,，驗證了仿真結(jié)果的正確性，對工程師在實際工作中有很強(qiáng)的借鑒性和參考價值,。

參考文獻(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.