摘 要：在級(jí)數(shù)的基礎(chǔ)上，設(shè)計(jì)一種基于FPGA的多項(xiàng)式運(yùn)算器。利用該運(yùn)算器可以在數(shù)字系統(tǒng)設(shè)計(jì)中更好地處理和應(yīng)用各種函數(shù)。首先實(shí)現(xiàn)基于FPGA的多項(xiàng)式運(yùn)算器，利用這個(gè)基本單元，進(jìn)而實(shí)現(xiàn)了比較復(fù)雜的函數(shù)。經(jīng)過驗(yàn)證，該運(yùn)算器結(jié)構(gòu)簡(jiǎn)單，運(yùn)算實(shí)時(shí)性和準(zhǔn)確性都能很好地滿足需要，最后對(duì)數(shù)據(jù)進(jìn)行了誤差分析。



關(guān)鍵詞：多項(xiàng)式； 運(yùn)算器； FPGA； 電路設(shè)計(jì)

中圖分類號(hào)：TN919-34

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1004-373X(2012)01-0184-03

Design of polynomial arithmetic unit based on FPGA



HU Sheng-ling

(South-central University for Nationalities， Wuhan 430074， China)



Abstract： On the basis of the series， a kind of polynomial arithmetic unit based on FPGA is introduced， which can handle and use all sorts of functions better in digital system design. The polynomial arithmetic unit based on FPGA is realized， and the complex function is implemented through the basic unit. The experiment verifies that the unit has simple structure， real-time and accurate operation. The error analysis of the data is performed.



Keywords： polynomial; arithmetic unit; FPGA; circuit design



收稿日期：2011-09-08

0 引 言

傳統(tǒng)的DSP都基于CPU結(jié)構(gòu)，是一種基于特定指令系統(tǒng)的處理器，但隨著運(yùn)算時(shí)鐘越來越接近電子器件可以接受的極限，這種DSP的處理能力也在接近它的極限；另一方面隨著EDA技術(shù)的發(fā)展，尤其像FPGA和CPLD器件的成熟和應(yīng)用，可以通過直接設(shè)計(jì)電路來實(shí)現(xiàn)并行的運(yùn)算，這樣運(yùn)算的效率從本質(zhì)上得到了提高，而且目前能實(shí)時(shí)地實(shí)現(xiàn)非常復(fù)雜的運(yùn)算，所以基于FPGA的運(yùn)算器被提上議事日程，并受到越來越多的重視[1]。一種便于用電路實(shí)現(xiàn)而且通用性強(qiáng)的算法，可以幫助工程師簡(jiǎn)單高效地完成一個(gè)能在FPGA上工作的運(yùn)算器的設(shè)計(jì)。

1 數(shù)字電路實(shí)現(xiàn)運(yùn)算的優(yōu)缺點(diǎn)

初步的FPGA設(shè)計(jì)是用硬件描述語言完成器件邏輯功能的描述，一個(gè)好的設(shè)計(jì)必須考慮數(shù)字電路的特點(diǎn)。CPU是一個(gè)典型的數(shù)字電路，因?yàn)槠渲荒茏黾臃ㄟ\(yùn)算，所以需要通過程序?qū)⒏鞣N運(yùn)算都轉(zhuǎn)換為加法來完成。傳統(tǒng)的“數(shù)值分析”正是在這種程序設(shè)計(jì)的基礎(chǔ)上形成的，不但復(fù)雜而且效率不高，不能實(shí)現(xiàn)真正的實(shí)時(shí)運(yùn)算，而FPGA本身除了能做加法運(yùn)算外，做無符號(hào)數(shù)的減法和乘法也很方便。目前兩大FPGA生產(chǎn)商推出的集成開發(fā)軟件中，都有集成的加、減法和乘法的IP核，運(yùn)算效率非常高，對(duì)于無符號(hào)數(shù)的運(yùn)算一般只要1個(gè)時(shí)鐘，甚至是不需要時(shí)鐘的組合邏輯電路，文獻(xiàn)［2-3]中也有這些運(yùn)算器的詳細(xì)介紹。但是直接做除法則不同，雖然也有除法IP核，但是需要許多個(gè)時(shí)鐘，而且占用邏輯資源很多，無論設(shè)計(jì)還是應(yīng)用都不方便。電路運(yùn)算的另一個(gè)缺點(diǎn)是表示有符號(hào)數(shù)和小數(shù)，以及做有符號(hào)小數(shù)間的運(yùn)算也很麻煩。所以在設(shè)計(jì)DSP時(shí)總是希望能夠找到一種方法盡量的趨易避難。

2 麥克勞林級(jí)數(shù)和多項(xiàng)式

運(yùn)算器的作用是對(duì)數(shù)據(jù)進(jìn)行各種運(yùn)算，這個(gè)過程可以用一個(gè)函數(shù)來表示：y=f(x)。任何一個(gè)在零附近連續(xù)的函數(shù)都可以展開為麥克勞林級(jí)數(shù)[4]：

f(x)= f(0)+f′(0)x+f(2)(0)2!x2+…+

f(n)(0)n!xn+…

(1)

大部分常用函數(shù)的高階導(dǎo)數(shù)項(xiàng)很小或者為零，所以在精度允許的范圍內(nèi)取其中的有限項(xiàng)就可以，即用一個(gè)多項(xiàng)式做近似運(yùn)算[4]，多項(xiàng)式運(yùn)算的特點(diǎn)在文獻(xiàn)［4］中有詳細(xì)介紹。用FPGA實(shí)現(xiàn)多項(xiàng)式的運(yùn)算，處理很多復(fù)雜的函數(shù)將會(huì)十分方便。

y=a0 +a1×x+a2×x2+…+an×xn

(2)

本文討論的是一種可以用FPGA或CPLD實(shí)現(xiàn)多項(xiàng)式(2)運(yùn)算的運(yùn)算器。對(duì)于簡(jiǎn)單的多項(xiàng)式可以是一個(gè)組合邏輯電路，不需要時(shí)鐘，所以運(yùn)算效率很高。這樣許多運(yùn)算都可以簡(jiǎn)單而且高效的完成。

3 運(yùn)算器設(shè)計(jì)

3.1 四則運(yùn)算電路

文獻(xiàn)［2-3］中描述了各種無符號(hào)整數(shù)間的運(yùn)算電路。雖然也可以進(jìn)行用反碼表示的符號(hào)數(shù)的運(yùn)算，但不傾向于使用。因?yàn)樾枰鏊膭t混合運(yùn)算；反碼易于做加、減法，但不易做乘、除法。而用非反碼的帶符號(hào)位的數(shù)據(jù)，符號(hào)位做單獨(dú)計(jì)算，其余數(shù)據(jù)做無符號(hào)運(yùn)算，整個(gè)計(jì)算結(jié)構(gòu)是最簡(jiǎn)單的。另外即便是無符號(hào)數(shù)做除法也很復(fù)雜，不過考慮到有種特殊的除法運(yùn)算除外，那就是對(duì)于二進(jìn)制數(shù)去掉最末位就相當(dāng)于除以2。所以運(yùn)算時(shí)可以盡量避免除以非2倍數(shù)的數(shù)，以此來簡(jiǎn)化計(jì)算。

表示小數(shù)在計(jì)算中是必須的。文獻(xiàn)［3］中介紹了二進(jìn)制定點(diǎn)小數(shù)，比如需要保留數(shù)的2位二進(jìn)制小數(shù)位，可以將二進(jìn)制小數(shù)“… b3 b2b1.a1a2”表示為：

122×(… b3 b2 b2 a1 a2)

(3)

運(yùn)算中還是可以視為對(duì)整數(shù)的計(jì)算。這樣用無符號(hào)的定點(diǎn)數(shù)進(jìn)行計(jì)算，配合獨(dú)立的符號(hào)位表示正負(fù)，就可以用簡(jiǎn)單的無符號(hào)運(yùn)算器進(jìn)行復(fù)雜的運(yùn)算。

3.2 多項(xiàng)式的變換

式(4)為一個(gè)3次多項(xiàng)式，以它為例來介紹設(shè)計(jì)方法:

y=a0 +a1×x+a2×x2+a3×x3

(4)

首先將式(4)中所有的數(shù)都用一個(gè)符號(hào)位加無符號(hào)二進(jìn)制形式表示。分別用N1，N2表示y和x中包含的小數(shù)位數(shù)，可以將式(4)寫成：

12N1Y=12n0A0+12n1A1×12N2X+12n2A2×

12N2X2+12n3A3×12N2X3

(5)

式中：X，Y是x，y去掉小數(shù)點(diǎn)后的整數(shù)(注：這里和式(3)一樣只是去掉小數(shù)點(diǎn)，不是去掉小數(shù)位)。A0，A1，A2，A3作為系統(tǒng)的常數(shù)也是一樣；n0，n1，n2，n3分別是a0，a1，a2，a3二進(jìn)制形式的小數(shù)位數(shù)?？梢赃M(jìn)一步變換式(5)為：

Y=12n0－N1A0+12n1－N1A1×12N2X+12n2－N1A2×

12N2×2X2+12n3－N1A3×12N2×3X3

不難發(fā)現(xiàn)式(6)是很容易實(shí)現(xiàn)的。先進(jìn)行各項(xiàng)符號(hào)位的計(jì)算，然后就只剩下無符號(hào)整形數(shù)據(jù)計(jì)算；而且除法全是除以2的倍數(shù)。最后各項(xiàng)之間根據(jù)符號(hào)位做加、減運(yùn)算就得到輸出Y，是帶符號(hào)有N1位小數(shù)的定點(diǎn)數(shù)。

3.3 設(shè)計(jì)實(shí)例

以設(shè)計(jì)余弦函數(shù)為例，用6次多項(xiàng)式可以很好地?cái)M合(0，π/2)上的余弦函數(shù)[4]。先用麥克勞林級(jí)數(shù)計(jì)算得到6次擬合多項(xiàng)式：

y=1-12x2+124x4-1720x6

考慮到三角函數(shù)只有小數(shù)部分有效，所以數(shù)據(jù)只用1個(gè)整數(shù)位、另8個(gè)小數(shù)位和一個(gè)符號(hào)位表示。另外需要說明的是常數(shù)保留的小數(shù)位是可以調(diào)節(jié)的，選擇保留合適的常數(shù)小數(shù)位可以盡量在保證精確度的情況下簡(jiǎn)化運(yùn)算。

128Y=1-1217X2+128×85×1235×X4-

1211×57×1252×X6

確定數(shù)據(jù)格式后式(7)可以寫成式(8)的形式，進(jìn)一步可將式(8)變化為式(9)，并在XILINX公司的ISE中完成設(shè)計(jì)。



Y=28-129X2+1235×85×X4-1255×57×X6



設(shè)計(jì)中考慮到純粹的異步組合邏輯電路容易出現(xiàn)“競(jìng)爭(zhēng)-冒險(xiǎn)”，所以加入了同步時(shí)鐘，這里利用同步時(shí)鐘分三步完成運(yùn)算，同時(shí)為了使每一步的運(yùn)算保持同步還需要加入延時(shí)模塊，這樣雖然犧牲了一些時(shí)間，但是保證了運(yùn)行的穩(wěn)定性。圖1是將多項(xiàng)式(9)用ISE編譯出的RTL電路圖，其中 “input”為式(9)中的X，“×”為乘法器，“FD”為延時(shí)模塊，“output”為式(9)中的Y。

圖1 ISE編譯出的RTL圖

將設(shè)計(jì)下載到芯片XC2VP30，并用Chipscope進(jìn)行片內(nèi)邏輯分析，外部時(shí)鐘和采樣時(shí)鐘都是100 MHz，得到電路的輸入/輸出曲線(見圖2)。圖2中虛線是輸入變量x，實(shí)線是輸出變量y?？v坐標(biāo)的數(shù)值顯示的是Y=y×28的值，即顯示時(shí)沒有考慮小數(shù)點(diǎn)。

從圖2中可以看到，輸出有大約3~4個(gè)時(shí)鐘的延時(shí)，對(duì)比CPU執(zhí)行1條指令就需要3~4個(gè)時(shí)鐘，運(yùn)算效率已經(jīng)很高，而且這里使用的邏輯資源很少。

圖2 電路的輸入/輸出曲線

4 實(shí)驗(yàn)結(jié)果分析

多項(xiàng)式擬合函數(shù)會(huì)有誤差詳見[4]。這里只分析運(yùn)算器相對(duì)多項(xiàng)式的誤差。因?yàn)閿?shù)據(jù)位寬有限，會(huì)出現(xiàn)截?cái)嗾`差。設(shè)計(jì)實(shí)例采用8位小數(shù)位，最大表示誤差是±2-9。由于常數(shù)也有數(shù)據(jù)截?cái)啵瑢?shí)際運(yùn)算誤差會(huì)更大。減小誤差的惟一辦法是增加數(shù)據(jù)的位數(shù)。在本例中將數(shù)據(jù)上傳電腦并測(cè)算，最大誤差在x=π/2處，絕對(duì)值是0.006 3，相對(duì)值是0.63%。對(duì)于一些特殊的輸入如x=0或x=0.5等，運(yùn)算沒有誤差。

5 結(jié) 語

通信系統(tǒng)的仿真與硬件實(shí)現(xiàn)涉及到很多復(fù)雜的函數(shù)，直接實(shí)現(xiàn)會(huì)造成資源浪費(fèi)，而且實(shí)現(xiàn)難度比較大。

采用FPGA實(shí)現(xiàn)多項(xiàng)式運(yùn)算，實(shí)現(xiàn)起來比較簡(jiǎn)單，為之后實(shí)現(xiàn)復(fù)雜函數(shù)提供了基礎(chǔ)，大大提高了運(yùn)算速度和實(shí)

現(xiàn)效率，在通信系統(tǒng)的硬件實(shí)現(xiàn)上有很廣闊的應(yīng)用前景。

參 考 文 獻(xiàn)

［1］楊海鋼，孫嘉斌，王慰.FPGA器件設(shè)計(jì)技術(shù)發(fā)展綜述［J］.電子與信息學(xué)報(bào)，2010，32(3):714-727.



［2］夏宇聞. Verilog數(shù)字系統(tǒng)設(shè)計(jì)［M］.北京:北京航空航天大學(xué)出版社，2008.



［3］李輝.基于FPGA的數(shù)字系統(tǒng)設(shè)計(jì)［M］.西安:西安電子科技大學(xué)出版社，2008.



［4］ATKINSON Kendall， HAN Wei-min. Elementary numerical analysis [M]. USA: John Wiley Sons， 2009.



［5］BROWN Stephen， VRANESIC Zvonko. Fundamentals of digital logic with verilog design[M].2nd Edition. USA: McGraw-Hill， 2001.



［6］BROWN S， ROSE J. FPGA and CPLD architectures: a tutorial [J]. IEEE Design and Test of Computers， 1996， 12(2): 42-57.



［7］BROWN S D， FRANCIS R， ROSE J， et al. Field- programmable gate arrays [M]. Netherland: Kluwer Academic Publishers， 1992.



［8］Xilinx. Virtex-5 user guide [EB/OL]. [2009-06-15]. http://china.xilinx.com.



［9］Xilinx. Advantages of virtex-5 FPGA 6-input LUT architecture [EB/OL]. [2007-12-23]. http://china.xilinx.com.



［10］BISWAS P， BANERJEE S， DUTT N， et al. Performance and energy benefits of instruction set extensions in an FPGA soft core [C]// Proceedings of International Confe-rence on VLSI Design. Hyderabad: [s.n.]， 2006: 651-656.