摘 要：浮點(diǎn)指數(shù)運(yùn)算是粒子濾波算法中的關(guān)鍵運(yùn)算之一，在信號(hào)處理等諸多領(lǐng)域有著十分重要的應(yīng)用，通過(guò)分析Tabledriven算法，給出基于Tabledriven算法實(shí)現(xiàn)浮點(diǎn)指數(shù)運(yùn)算的硬件結(jié)構(gòu)，并以Verilog HDL進(jìn)行建模仿真及綜合，同時(shí)將仿真結(jié)果與浮點(diǎn)DSP C6701運(yùn)算結(jié)果進(jìn)行比較。結(jié)果表明基于FPGA的浮點(diǎn)指數(shù)運(yùn)算在保持一定精度的條件下，可以獲得更快的運(yùn)算速度。

關(guān)鍵詞：浮點(diǎn)數(shù)；指數(shù)運(yùn)算；Tabledriven算法；FPGA

中圖分類號(hào)：TP302 文獻(xiàn)標(biāo)識(shí)碼：B 文章編號(hào)：1004373X(2008)1811903

FPGA Implementation of Float Point Exponential Function in Particle Filtering Algorithm

XIE Yuelei，CHEN Min

(School of Information and Communications，Guilin University of Electronic Technology，Guilin，541004，China)

Abstract：Float point exponential function is a key arithmetic of particle filter and is very important in signal processing and other fields.A hardware architecture of float point exponential function is constructed by analyzing the Tabledriven algorithm.The design is simulated modeling and implemented by using Verilog HDL.The results show that the FPGAbased float point exponential function with proper decision gets fast comparing to the C6701 DSP.

Keywords：float point;exponential function;Tabledriven algorithm;FPGA

序列Monte Carlo方法又稱粒子濾波，由于能處理非線性非高斯信號(hào)，且具有良好的并行性結(jié)構(gòu)，其在無(wú)線通信、跟蹤及圖像處理等領(lǐng)域應(yīng)用有著十分廣闊前景。指數(shù)運(yùn)算是粒子濾波算法中的關(guān)鍵運(yùn)算之一，權(quán)值更新運(yùn)算及似然函數(shù)的計(jì)算，都離不開(kāi)指數(shù)運(yùn)算，利用傳統(tǒng)DSP和通用處理器等固定架構(gòu)處理器實(shí)現(xiàn)指數(shù)運(yùn)算，難以滿足信號(hào)處理實(shí)時(shí)性要求，F(xiàn)PGA因其具有高集成度、高速和高可靠性的顯著特點(diǎn)，因而在實(shí)時(shí)信號(hào)處理中得到了廣泛的應(yīng)用。浮點(diǎn)數(shù)^［1］在不增加位數(shù)的前提下，與定點(diǎn)數(shù)相比，擴(kuò)展了所能表示的數(shù)的動(dòng)態(tài)范圍，然而浮點(diǎn)數(shù)運(yùn)算要比定點(diǎn)數(shù)復(fù)雜，但在對(duì)精度要求比較高的場(chǎng)合，如圖像處理、粒子濾波等信號(hào)處理算法中，浮點(diǎn)運(yùn)算是無(wú)法避免的。因此，利用FPGA實(shí)現(xiàn)浮點(diǎn)信號(hào)處理算法，是當(dāng)今研究的熱點(diǎn)之一。

指數(shù)運(yùn)算在浮點(diǎn)信號(hào)處理算法中占有相當(dāng)重要的地位，但在目前FPGA開(kāi)發(fā)中還沒(méi)有標(biāo)準(zhǔn)的庫(kù)函數(shù)可調(diào)用，需要自己編寫浮點(diǎn)指數(shù)運(yùn)算函數(shù)。目前實(shí)現(xiàn)浮點(diǎn)指數(shù)運(yùn)算主要的方法有2種：一種是基于cordic迭代算法^［2］；另一種是基于級(jí)數(shù)展開(kāi)和查找表的Tabledriven算法^［3］。其中cordic算法由于迭代運(yùn)算的特性，運(yùn)算速度比較慢，在對(duì)實(shí)時(shí)性要求越來(lái)越高的發(fā)展趨勢(shì)下，利用Tabledriven實(shí)現(xiàn)浮點(diǎn)指數(shù)運(yùn)算成為主要選擇。

本文對(duì)Tabledriven算法進(jìn)行分析，給出實(shí)現(xiàn)浮點(diǎn)指數(shù)運(yùn)算的一種結(jié)構(gòu)，并對(duì)該結(jié)構(gòu)進(jìn)行時(shí)延分析，最后給出使用流水線提高浮點(diǎn)指數(shù)運(yùn)算的結(jié)構(gòu)。

1 Tabledriven算法簡(jiǎn)介

Tabledriven算法^［3］是一種級(jí)數(shù)展開(kāi)近似和查找表方法的結(jié)合，對(duì)于一個(gè)浮點(diǎn)數(shù)x，實(shí)現(xiàn)浮點(diǎn)指數(shù)運(yùn)算方法如下，首先將x進(jìn)行分解:x=(32×m+j)ln 232+r(1)其中m，j為整數(shù)；r為實(shí)數(shù)，且|r|

=2m×2j32×exp(r)(2)

對(duì)于exp(r)可用泰勒級(jí)數(shù)近似:exp(r)=1+r+12!r2+…+1n!rn(3)

可見(jiàn)，浮點(diǎn)指數(shù)運(yùn)算的關(guān)鍵是計(jì)算出m，j和r。計(jì)算這3個(gè)參數(shù)過(guò)程如下：N=round(X*C₁)(4)

j=Nmod 32(5)

m=(N－j)/32(6)

r=X－N·C₂(7)其中C₁=32/ln 2；C₂=ln 2/32為常數(shù)；round表示取整運(yùn)算；mod表示取余運(yùn)算，令s=2j32（j＝0，1，…，31），可通過(guò)查表計(jì)算，詳細(xì)分析參見(jiàn)文獻(xiàn)［3］。

2 浮點(diǎn)指數(shù)函數(shù)的硬件結(jié)構(gòu)

通過(guò)對(duì)Tabledriven算法進(jìn)行分析，可以將其分解為4模塊，即計(jì)算m，j，r模塊Get_m_j_r；計(jì)算exp(r)模塊Get_exp(r)；計(jì)算s模塊Get_s，最后的指數(shù)計(jì)算模塊Get_exp(x)；而每個(gè)模塊又可分解為基本的浮點(diǎn)加法、乘法運(yùn)算、整數(shù)加、乘運(yùn)算，取整、取余運(yùn)算等基本模塊，整體結(jié)構(gòu)如圖1所示：

圖1 浮點(diǎn)指數(shù)運(yùn)算的結(jié)構(gòu)圖(1) 計(jì)算m_j_r模塊。Get_m_j_r單元輸入為浮點(diǎn)數(shù)x；輸出為m，j為正整數(shù)；r為浮點(diǎn)數(shù)。輸入的浮點(diǎn)數(shù)x先和常數(shù)C₁進(jìn)行1次浮點(diǎn)乘運(yùn)算;然后取整得到N，再對(duì)N進(jìn)行模32取余可得j;然后進(jìn)行1次整數(shù)減運(yùn)算，再右移位5位可得m，再進(jìn)行一次浮點(diǎn)乘和浮點(diǎn)減可得r，結(jié)構(gòu)如圖2所示。

圖2Get_m_j_r單元結(jié)構(gòu)(2)計(jì)算s的模塊Cal_s。該模塊根據(jù)輸入j的值來(lái)計(jì)算2j/32，輸出s為浮點(diǎn)數(shù)，由于j的取值為小于32的整數(shù)，故這一過(guò)程可以通過(guò)查找表的方法實(shí)現(xiàn)。

(3) 計(jì)算泰勒級(jí)數(shù)模塊Cal_exp(r)。計(jì)算泰勒級(jí)數(shù)，展開(kāi)的級(jí)數(shù)越多，近似精度越高，但所需的運(yùn)算量也相應(yīng)變大，由于r是一個(gè)較小的值，故可以用較少的展開(kāi)級(jí)數(shù)就可獲得較好的精度^［4］，取2級(jí)展開(kāi)式，則需要2次浮點(diǎn)乘、2次浮點(diǎn)加法完成。取k1=0.5，k2=1，其實(shí)現(xiàn)框圖如圖3所示。

(4)Cal_exp完成最后的指數(shù)運(yùn)算，將s與p進(jìn)行一次浮點(diǎn)乘法，然后將結(jié)果的指數(shù)部分加上m，最后再進(jìn)行1次浮點(diǎn)數(shù)規(guī)格化就可得到最后結(jié)果exp(x)，共需要1次浮點(diǎn)乘法和1次加法及1次浮點(diǎn)數(shù)規(guī)格化，實(shí)現(xiàn)框圖如圖4所示：

圖3 Cal_exp(r)單元結(jié)構(gòu)圖4 Cal_exp單元結(jié)構(gòu)3 仿真及綜合分析

采用Verilog硬件描述語(yǔ)言^［5］，在Modelsim軟件環(huán)境下，先對(duì)浮點(diǎn)乘法、浮點(diǎn)加法、浮點(diǎn)定點(diǎn)轉(zhuǎn)換、模32取余等基本運(yùn)算進(jìn)行建模，然后利用數(shù)字系統(tǒng)結(jié)構(gòu)化的設(shè)計(jì)方法，參照3中給出的結(jié)構(gòu)，分別對(duì)Get_m_j_r，Cal_s，Cal_exp(r)及Cal_exp進(jìn)行建模，最后實(shí)現(xiàn)浮點(diǎn)指數(shù)函數(shù)運(yùn)算，完整實(shí)現(xiàn)一次浮點(diǎn)指數(shù)運(yùn)算的modelsim下的仿真結(jié)果如圖5所示：

圖5 浮點(diǎn)指數(shù)的仿真波形圖在合適的數(shù)值范圍內(nèi)，選取一組輸入數(shù)據(jù)，對(duì)Tabledriven算法實(shí)現(xiàn)的浮點(diǎn)指數(shù)運(yùn)算結(jié)果及DSP浮點(diǎn)指數(shù)運(yùn)算結(jié)果進(jìn)行仿真比較。其中以Pentium 4 CPU硬件平臺(tái)上，Matlab環(huán)境下雙精度浮點(diǎn)數(shù)運(yùn)算的結(jié)果作為標(biāo)準(zhǔn)結(jié)果，DSP為TI公司和TMS320C6701浮點(diǎn)DSP^［6］，浮點(diǎn)指數(shù)運(yùn)算選用TI自帶浮點(diǎn)指數(shù)運(yùn)算函數(shù)，運(yùn)算結(jié)果見(jiàn)表1。

表1 浮點(diǎn)指數(shù)運(yùn)算結(jié)果對(duì)比

輸入數(shù)據(jù)標(biāo)準(zhǔn)結(jié)果Tabledriven結(jié)果DSP結(jié)果-20.130 01.809 9e-0091.063 5e-0091.809 891e-09-15.168 02.586 0e-0072.391 6e-0072.585 956e-07-10.340 03.231 4e-0053.231 5e-0053.231 432e-05-5.780 00.003 10.003 10.003 088 715-0.640 00.527 30.527 30.5272 9240111.00.640 01.896 51.896 51.896 4815.780 0323.759 2323.759 9323.759 210.340 03.094 6e+0043.094 6e+0043.094 604e+00415.168 03.867 0e+0063.332 993e+0063.867 041e+00620.130 05.525 2e+0085.372 240e+0085.525 194e+08

由表1中結(jié)果可見(jiàn)，當(dāng)輸入數(shù)絕對(duì)值較小時(shí)，Tabledriven算法結(jié)果與DSP運(yùn)算結(jié)果相近，都逼近標(biāo)準(zhǔn)結(jié)果，但當(dāng)輸入數(shù)絕對(duì)值較大時(shí)，Tabledriven算法結(jié)果誤差要大于DSP運(yùn)算結(jié)果，誤差是由Tabledriven算法中泰勒級(jí)數(shù)展開(kāi)造成的，取的級(jí)數(shù)越多、誤差越小，但硬件結(jié)構(gòu)越復(fù)雜。

在synplify pro綜合軟件環(huán)境下，選取Altera公司的Cyclone Ⅱ FPGA芯片進(jìn)行了邏輯綜合，綜合后的結(jié)果如表2所示：

表2 綜合結(jié)果

綜合后邏輯單元延遲/ns浮點(diǎn)指數(shù)684 6291.692浮點(diǎn)加法53324.621浮點(diǎn)乘法3723.755取整24713.006模32取余969.932

由表2中可知，完成1次浮點(diǎn)指數(shù)運(yùn)算，基本Cyclone Ⅱ至少需要291.692 ns，而在TMS320C6701上完成一次浮點(diǎn)指數(shù)運(yùn)算需要6 135 ns，基本FPGA實(shí)現(xiàn)的浮點(diǎn)指數(shù)運(yùn)算速度要遠(yuǎn)遠(yuǎn)快于DSP，但精度較DSP略差。

4 結(jié) 語(yǔ)

浮點(diǎn)指數(shù)運(yùn)算是信號(hào)處理中的關(guān)鍵運(yùn)算之一，Tabledriven算法是實(shí)現(xiàn)浮點(diǎn)指數(shù)運(yùn)算的一種快速方法，文中給出利用FPGA實(shí)現(xiàn)浮點(diǎn)指數(shù)運(yùn)算的的硬件結(jié)構(gòu)，以Verilog硬件描述語(yǔ)言進(jìn)行建模，并在EDA軟件下進(jìn)行仿真與綜合，結(jié)果表明在保持結(jié)果一定精度條件下，可獲得比DSP更快的運(yùn)算速度，下一步工作可在考慮功耗的基礎(chǔ)上優(yōu)化浮點(diǎn)指數(shù)運(yùn)算。

參 考 文 獻(xiàn)

［1］IEEE Standard for RadixIndependent FloatingPoint Arithmetic［S］.The Institute of Electrical and Electronics Engineers，1987.

［2］Kantabutra V.On Hardware for Computing Exponential and Trigonometric Functions［J］.IEEE Trans.on Computers，1996，45(3):96107.

［3］Tang P T P.Tabledriven Implementation of the Exponential Function in IEEE FloatingPoint Arithmetic［J］.ACM Trans.on Mathematical Software，1989，15(2):144157.

［4］Tang P T P.Accurate and Efficient Testing of the Exponential and Logarithm Functions［J］.ACM Trans.on Mathematical Software，1990，16(6):185200.

［5］Donald E T，Philip T R.The Verilog Hardware Description Language［M］.Khwer Academic Publishers，2001.

［6］TMS320C67x/C67x+ DSP CPU and Instruction Set Reference Guide.http://www.ti.com Literature Number:SPRU733A，2006.

作者簡(jiǎn)介 謝躍雷 男，1975年出生，河北邯鄲人，講師，碩士。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文研究方向?yàn)橥ㄐ判盘?hào)處理、非線性濾波技術(shù)、VLSI信號(hào)處理等。

陳 敏 男，1984年出生，江西人，桂林電子科技大學(xué)碩士研究生。研究方向?yàn)樾盘?hào)處理、DSP、ARM應(yīng)用等。