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

劉 鳳，龔曉峰，張軍歌

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

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

劉 鳳，龔曉峰，張軍歌

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

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

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

0 引言

FFT（Fast Fourier Transform）是有限長(zhǎng)序列 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ì)稱性，將長(zhǎng)序列DFT逐級(jí)分解為短序列的DFT，從而減少運(yùn)算量，提高運(yùn)算速率[3-5]。常用 FFT包括時(shí)域抽取FFT與頻域抽取 FFT，現(xiàn)介紹工程中廣泛應(yīng)用的一種頻域抽取FFT算法，基4頻域抽取算法。

長(zhǎng)度為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頻域抽取一次分解為：

式中：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，基本蝶形運(yùn)算單位為：。

從式(1)與式(2)對(duì)比可以看出，長(zhǎng)度為 N的長(zhǎng)序列進(jìn)行一次基 4 DIF分解，N2次復(fù)數(shù)乘累加的運(yùn)算量，降低至 N2/4+2N，且包含±j，±1，W0等因子的單元可進(jìn)一步簡(jiǎn)化運(yùn)算。長(zhǎng)度為N的序列，可進(jìn)行l(wèi)og4N次分解，因此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)算。

圖1 定點(diǎn)FFT一級(jí)蝶形運(yùn)算單元

除去與旋轉(zhuǎn)因子相乘造成的位擴(kuò)寬，基4定點(diǎn)FFT每級(jí)蝶形運(yùn)算以全范圍位寬溢出2位為前提進(jìn)行舍入。每進(jìn)行一級(jí)蝶形運(yùn)算，中間結(jié)果最小精度擴(kuò)大4倍。因此，輸入序列長(zhǎng)度為 N時(shí)，輸出 FFT最小精度為 22log4N。定點(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)行截位處理。

圖2 塊浮點(diǎ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)格式。

表1 基礎(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 定點(diǎn)FFT噪信比與信號(hào)幅值范圍

圖4 塊浮點(diǎn)噪信比與信號(hào)幅值范圍

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

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

圖5 定點(diǎn)FFT噪信比與序列長(zhǎng)度

圖6 塊浮點(diǎn)FFT噪信比與塊浮點(diǎn)

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輸入位寬的增加，降低輸出最小精度，輸出噪信比降低。

圖7 定點(diǎn)FFT噪信比與FFT輸入位寬

圖8 塊浮點(diǎn)FFT噪信比與FFT輸入位寬

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)頻譜失真。

圖9 帶寬10 kHz時(shí)白噪聲頻譜

當(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é)論的正確性。

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

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輸入位寬、序列長(zhǎng)度的變化趨勢(shì)，并基于仿真結(jié)論，解決了實(shí)際工程中會(huì)遇到的小信號(hào)頻譜失真問題，驗(yàn)證了仿真結(jié)果的正確性，對(duì)工程師在實(shí)際工作中有很強(qiáng)的借鑒性和參考價(jià)值。

[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

劉鳳，龔曉峰，張軍歌.不同運(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.

2016-07-20）

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

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

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