劉 鳳，龔曉峰，張軍歌

（四川大學(xué) 電氣信息學(xué)院，四川 成都610065）

不同運算機(jī)制下FFT計算精度分析*

劉 鳳，龔曉峰，張軍歌

（四川大學(xué) 電氣信息學(xué)院，四川 成都610065）

主要研究定點、塊浮點和浮點運算機(jī)制下，頻域抽取基4算法的精度問題。首先分析了定點、塊浮點、浮點等運算機(jī)制下，基4算法基本運算單元中數(shù)據(jù)不同表現(xiàn)形式及輸出截位規(guī)則。然后利用MATLAB平臺建立了定點與塊浮點FFT仿真模型，以噪信比作為FFT輸出精度指標(biāo)，研究輸出精度與輸入信號范圍、算法參數(shù)之間的關(guān)系。仿真表明，輸入為隨機(jī)序列時，定點與塊浮點FFT輸出噪信比與輸入信號幅值范圍、輸入序列長度及算法輸入位寬有關(guān)。此結(jié)論可用以解決實際工程中小信號頻譜失真問題，在工程分析與設(shè)計中具有重要參考價值。

運算機(jī)制；基4頻域抽取算法；運算單元；仿真模型

0 引言

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

1 基4頻域抽取FFT算法

FFT的核心是利用 DFT中旋轉(zhuǎn)因子的周期性與對稱性，將長序列DFT逐級分解為短序列的DFT，從而減少運算量，提高運算速率[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頻域抽取一次分解為：

式中：a1=[1，j，-1，-j]，a1=[1，-1，1，-1]，a1=[1，-j，-1，j]，a1=[1，1，1，1]，c=[x(i)，x(i+N/4)，x(i+N/2)，x(i+3N/4)]T，基本蝶形運算單位為：。

從式(1)與式(2)對比可以看出，長度為 N的長序列進(jìn)行一次基 4 DIF分解，N2次復(fù)數(shù)乘累加的運算量，降低至 N2/4+2N，且包含±j，±1，W0等因子的單元可進(jìn)一步簡化運算。長度為N的序列，可進(jìn)行l(wèi)og4N次分解，因此FFT算法大大降低離散傅里葉變換運算量。

2 定點、塊浮點、浮點FFT運算過程

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

2.1 定點FFT

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

圖1 定點FFT一級蝶形運算單元

除去與旋轉(zhuǎn)因子相乘造成的位擴(kuò)寬，基4定點FFT每級蝶形運算以全范圍位寬溢出2位為前提進(jìn)行舍入。每進(jìn)行一級蝶形運算，中間結(jié)果最小精度擴(kuò)大4倍。因此，輸入序列長度為 N時，輸出 FFT最小精度為 22log4N。定點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)測每級蝶形運算輸出范圍決定截位，從而減少被截取位寬，降低了舍入誤差。如圖2所示，以正負(fù)最大的數(shù)值為標(biāo)準(zhǔn)，對每級蝶形輸出結(jié)果進(jìn)行截位處理。

圖2 塊浮點截位處理

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

2.3 浮點FFT

IEEE754標(biāo)準(zhǔn)是 1985年 IEEE（Institute of Electrical and electronics Engineers，電子電氣工程師協(xié)會）提出的浮點運算規(guī)范，為浮點運算部件工業(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)制浮點格式。

表1 基礎(chǔ)二進(jìn)制浮點格式位寬

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

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

3 噪信比分析

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

3.1 浮點FFT噪信比

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

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

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

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

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

圖3 定點FFT噪信比與信號幅值范圍

圖4 塊浮點噪信比與信號幅值范圍

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

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

圖5 定點FFT噪信比與序列長度

圖6 塊浮點FFT噪信比與塊浮點

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

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

圖7 定點FFT噪信比與FFT輸入位寬

圖8 塊浮點FFT噪信比與FFT輸入位寬

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

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

圖9 帶寬10 kHz時白噪聲頻譜

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

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

圖10 擴(kuò)展信號范圍后白噪聲頻譜

5 結(jié)論

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

[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.

Accuracy analysis of FFT with different operation mechanism

Liu Feng，Gong Xiaofeng，Zhang Junge
(School of Electrical Engineering and Information，Sichuan University，Chengdu 610065，China)

Accuracy in radix 4 decimation in frequency(DIF)algorithm is researched with different operation mechanisms.We analyze different data forms and roundoff rules of radix 4 operation unit with fixed-point,block floating point and floating point.A simulation model is established on MATLAB platform for operation mechanisms including fixed-point and block floating point.In this model,accuracy is measured by noise signal ratio.The result shows that,when the input is rand sequence,the noise signal ratio is effected by input length and scale and input width of algorithm.With the simulation result,we solved the spectral distortion with weak signal in practice.Consequently this scheme has better valve in practice.

operation mechanism；radix 4 decimation in frequency algorithm；operation unit；simulation model

TN402

A

10.16157/j.issn.0258-7998.2016.12.005

劉鳳，龔曉峰，張軍歌.不同運算機(jī)制下 FFT計算精度分析[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.

2016-07-20）

劉鳳（1992-），女，碩士研究生，主要研究方向：檢測技術(shù)與自動化裝置。

國家自然科學(xué)基金青年項目（31300539）；四川大學(xué)校青年基金（2015SCU11064）

龔曉峰(1965-)，通信作者，男，博士，教授，主要研究方向：無線電頻譜監(jiān)測與認(rèn)知無線電，E-mail：gongxiaofeng@ scu.edu.cn。