基于FPGA的多項式運算器設計

摘 要：在級數的基礎上，設計一種基于FPGA的多項式運算器。利用該運算器可以在數字系統設計中更好地處理和應用各種函數。首先實現基于FPGA的多項式運算器，利用這個基本單元，進而實現了比較復雜的函數。經過驗證，該運算器結構簡單，運算實時性和準確性都能很好地滿足需要，最后對數據進行了誤差分析。



關鍵詞：多項式； 運算器； FPGA； 電路設計

中圖分類號：TN919-34

文獻標識碼：A

文章編號：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 引 言

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

1 數字電路實現運算的優缺點

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

2 麥克勞林級數和多項式

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

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

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

(1)

大部分常用函數的高階導數項很小或者為零，所以在精度允許的范圍內取其中的有限項就可以，即用一個多項式做近似運算[4]，多項式運算的特點在文獻［4］中有詳細介紹。用FPGA實現多項式的運算，處理很多復雜的函數將會十分方便。

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

(2)

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

3 運算器設計

3.1 四則運算電路

文獻［2-3］中描述了各種無符號整數間的運算電路。雖然也可以進行用反碼表示的符號數的運算，但不傾向于使用。因為需要做四則混合運算；反碼易于做加、減法，但不易做乘、除法。而用非反碼的帶符號位的數據，符號位做單獨計算，其余數據做無符號運算，整個計算結構是最簡單的。另外即便是無符號數做除法也很復雜，不過考慮到有種特殊的除法運算除外，那就是對于二進制數去掉最末位就相當于除以2。所以運算時可以盡量避免除以非2倍數的數，以此來簡化計算。

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

122×(… b3 b2 b2 a1 a2)

(3)

運算中還是可以視為對整數的計算。這樣用無符號的定點數進行計算，配合獨立的符號位表示正負，就可以用簡單的無符號運算器進行復雜的運算。

3.2 多項式的變換

式(4)為一個3次多項式，以它為例來介紹設計方法:

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

(4)

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

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

12N2X2+12n3A3×12N2X3

(5)

式中：X，Y是x，y去掉小數點后的整數(注：這里和式(3)一樣只是去掉小數點，不是去掉小數位)。A0，A1，A2，A3作為系統的常數也是一樣；n0，n1，n2，n3分別是a0，a1，a2，a3二進制形式的小數位數。可以進一步變換式(5)為：

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

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

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

3.3 設計實例

以設計余弦函數為例，用6次多項式可以很好地擬合(0，π/2)上的余弦函數[4]。先用麥克勞林級數計算得到6次擬合多項式：

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

考慮到三角函數只有小數部分有效，所以數據只用1個整數位、另8個小數位和一個符號位表示。另外需要說明的是常數保留的小數位是可以調節的，選擇保留合適的常數小數位可以盡量在保證精確度的情況下簡化運算。

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

1211×57×1252×X6

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



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



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

圖1 ISE編譯出的RTL圖

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

從圖2中可以看到，輸出有大約3~4個時鐘的延時，對比CPU執行1條指令就需要3~4個時鐘，運算效率已經很高，而且這里使用的邏輯資源很少。

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

4 實驗結果分析

多項式擬合函數會有誤差詳見[4]。這里只分析運算器相對多項式的誤差。因為數據位寬有限，會出現截斷誤差。設計實例采用8位小數位，最大表示誤差是±2-9。由于常數也有數據截斷，實際運算誤差會更大。減小誤差的惟一辦法是增加數據的位數。在本例中將數據上傳電腦并測算，最大誤差在x=π/2處，絕對值是0.006 3，相對值是0.63%。對于一些特殊的輸入如x=0或x=0.5等，運算沒有誤差。

5 結 語

通信系統的仿真與硬件實現涉及到很多復雜的函數，直接實現會造成資源浪費，而且實現難度比較大。

采用FPGA實現多項式運算，實現起來比較簡單，為之后實現復雜函數提供了基礎，大大提高了運算速度和實

現效率，在通信系統的硬件實現上有很廣闊的應用前景。

參 考 文 獻

［1］楊海鋼，孫嘉斌，王慰.FPGA器件設計技術發展綜述［J］.電子與信息學報，2010，32(3):714-727.



［2］夏宇聞. Verilog數字系統設計［M］.北京:北京航空航天大學出版社，2008.



［3］李輝.基于FPGA的數字系統設計［M］.西安:西安電子科技大學出版社，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.