基于ＣＯＲＤＩＣ算法的復數除法器ＦＰＧＡ實現

摘 要：在現代數字信號處理電路設計中，除法器有著廣泛的應用。這里闡述一種復數除法器的設計思想和實現方法，引入CORDIC算法到復數的除法運算中，利用CORDIC旋轉操作來代替乘、加法操作，然后采用雙比特移位操作得到最終運算結果。經CORDIC旋轉后數據最多只放大2位位寬，因此可以減少硬件實現中的器件迭代次數。經過FPGA驗證結果表明，整個設計運算速度快、節省器件，并且計算精度高。

關鍵詞：CORDIC算法；除法器；FPGA；數字信號處理

中圖分類號：TN710文獻標識碼：B

文章編號：1004-373X(2008)24-027-04

Complex Divider FPGA Implementation Based on CORDIC Algorithm

WANG Jingcun，WANG Yingbo

(College of Information Science and Engineering，Wuhan University of Science and Technology，Wuhan，430081，China)

Abstract：In the modern digital signal processing circuit design，the divider has a wide application.A complex division of the design thinking and methods are described，CORDIC algorithm is applied in the complex division operation，the use of CORDIC rotating operation to replace multiplication and addition operation，finally result is gotby two-bit-shift operation.After CORDIC rotating，data enlarged two interfaces at most，thereby reducing the hardware devices in the number of iterations.FPGA verification results show that the whole design computing speed，saving devices，and high precision.

Keywords：CORDIC algorithm;divider;FPGA;digital signal processing

1 引 言

現代數字信號處理中，通常信號以復數形式出現并進行各種處理，這樣就無法避免復數信號進行除法運算。國內外關于除法器的研究已經進行了很長時間，并且一直都在研究發展當中^［1］。目前已經有多種算法，比如：恢復余數法、不恢復余數法^［2］、雙比特算法^［3］、SRT算法^［4］、牛頓疊代算法^［5］等。在一般的單片機中，主要采用恢復余數法和不恢復余數法兩種算法，它們的優點是算法簡單且容易通過硬件實現，但處理速度比較慢。牛頓算法需要用到查找表，那么肯定通過大量ROM來實現，會消耗大量的器件，但其整體結構簡單，容易實現。SRT算法硬件規模較小，運算精度很高，但該算法比較復雜，硬件實現比較困難。雙比特算法是基于不恢復余數法的基礎上出現的，每個周期可以左移2位，運算速率提高1倍。以上這些都是針對實數除法器提出的算法思想，復數除法器正是在這些實數除法器算法基礎上來實現的。為此提出了一種基于CORDIC算法并結合雙比特算法在FPGA上實現復數除法器的方法。

該方法大量節省了器件，并能得到較高的性能。它具有如下2個重要特征：

(1) 減少運算量。乘法器、加法器是很耗器件的，這里運用CORDIC算法來避免乘法操作、減少加法操作；

(2) 減少迭代級數。雙比特除法算法減少了實現的迭代級數，提高了效率，節省了器件。

2 復數除法器算法描述

設計的復數除法器用到了CORDIC算法和雙比特算法。在接下來的部分先分別介紹它們基本原理，然后說明如何運用二者到復數除法當中去。

2.1 CORDIC算法的一般原理

CORDIC (Coordinate Rotation Digital Computer) ［6］，又名：坐標旋轉數字計算，是J.Voider等人于1959年在設計美國航空導航控制系統的過程中提出來的算法。CORDIC算法適用于解決一些三角學的問題，如平面坐標的旋轉和直角坐標到極坐標的轉換等。該算法的基本思想是通過一系列固定的、與運算基數有關的角度的不斷偏擺以逼近所需的旋轉角度^［7］。

例如：計算OQ=OP·ejθ。即將向量OP逆時針旋轉θ度角得到向量OQ，假設分n次旋轉，第i次旋轉角度為δiθi，并且滿足關系tan θi=2－i，約定δi代表向量的旋轉方向，第i次旋轉時與目標角度的差為Zi，可令Z0=θ，Zi+1=Zi-δiθi，于是Zn→0。當Zi≥0，δi=1；當Zi<0，δi=-1時，每次旋轉有如下遞推關系：

xi+1=xi－δi×yi×2－i

yi+1=yi+δi×xi×2－i

zi+1=zi－δi×arctan 2－i(1)

經式（1）的n級旋轉迭代，這里會有一個幅度的畸變因子k=∏∞n=01+2－2i1.646 768。用該疊代方程組進行運算，結果會放大k倍，得到的新向量的數據位寬最多會放大2位。

運用上面提到的CORDIC原理，可方便求任一向量的模。只需將向量逐步旋轉，直至新向量無限接近于x軸，那么新向量的虛部就接近于零，而實部就是所要求的模放大了k倍的值。如果直接用實部、虛部平方，再開方運算，硬件實現起來相當復雜。而用CORDIC旋轉來求得，硬件實現起來簡單得多，因而耗器件很少。

2.2 雙比特移位算法

雙比特算法是在不恢復余數法的基礎上實現的。在介紹雙比特算法之前，有必要先簡單介紹一下不恢復余數法的原理。不恢復余數法又稱加減交替法，其基本原理是，先做被除數x與除數y的減法得到余數rm。若余數為正，夠減，商“1” ，余數左移1位，接下來繼續減除數再判商；若余數為負，不夠減，商“0”，余數左移1位，接下來的操作變為加除數再根據結果判商，如此重復操作。該操作次數等于除數的位數。

采用雙比特算法后，從每次左移1位變成移2位了，移位相減操作次數減少了一半。每次移2位后變為新變量newrm，這樣每次操作就要產生2位商，這2位商的取值是通過對3個減法器的結果進行判斷來得到的^［8］。這3個減法器結果分別為：

rm1=newrm-y

rm2=newrm-2y

rm3=newrm-3y(2)

對應的商值如下所示:

quo［2i+1∶2i］=11，rm3≥0;

quo［2i+1∶2i］=10，rm3<0，rm2≥0;

quo［2i+1∶2i］=01，rm2<0，rm1≥0;

quo［2i+1∶2i］=00，rm1<0;(3)

由于雙比特算法每次移動2位，所以它的執行周期比不恢復余數法降低了近一半。它非常適合高性能的運算。同時因為能減少器件，所以在面積上也有其優越性。

2.3 引入CORDIC算法后的復數除法思想

復數p=x1+y1j除以復數q=x2+y2j，計算公式如下：

x1+jy1x2+jy2=

(x1x2+y1y2)+j(x2y1－x1y2)x22+y22(4)

由式（4）可知，硬件實現該除法運算需要做6次乘法，3次加法，最后還有做2次除法，耗大量器件是可想而知的。這樣的運算可以運用CORDIC算法來使其簡單化。

引入CORDIC算法，將向量q=x2+jy2做旋轉使之無限接近x軸，變為新的向量q2=x22+jy22（此時：y220）。p=x1+jy1跟著旋轉相同角度變為新的向量p2=x11+y11j。那么新的計算公式如下：

x1+jy1x2+jy2x11+jy11x22+jy22=x11x22+jy11x22(5)

由式（5）可知，經過CORDIC旋轉之后，向量q2和p2同時放大了1.646 768倍，這并不影響除法結果。然后只需做x11/x22，y11/x22兩次實數除法，這里引入雙比特算法來實現。硬件上可以復用1個實數除法器來完成2次除法運算，就得到了最終結果。

注意，CORDIC旋轉只適應一、四象限的向量。如果這里的除法向量不在一象限或四象限，可以給該向量加負號使之調整到一、四象限。同時被除數向量做同樣調整，使它們保持一致

性。這樣的調整方法可覆蓋各個象限，適用任何情況數據的運算。

3 復數除法器的結構設計

3.1 整體體系結構

基于CORDIC算法的復數除法器的總體結構框圖如圖1所示。

圖1 復數除法器的總體結構框圖

該系統主要由CORDIC旋轉模塊和實數除法器模塊組成。被除數向量x1+jy1和除數向量x2+jy2經CORDIC旋轉模塊旋轉相同角度得到新的向量X11+jY11和X22+jY22，此時，Y220；X11與X22，Y11與X22再經過實數除法器模塊得到最終的除法結果Quo1，Quo2。其思想可在式（5）中表現出來。

3.2 CORDIC旋轉模塊

該模塊實現被除和除法向量的旋轉，得到2個新的旋轉向量。這里根據式（1）的邏輯思想進行改進，每級的旋轉方向由上一級的輸出除法向量的y值符號進行判斷來旋轉。按新邏輯思想可在FPGA上設計實現一級旋轉單元。本模塊設計可以根據性能要求來確定旋轉單元迭代的級數。本設計用到了12級旋轉單元迭代，結構框圖如圖2所示。

圖2 CORDIC模塊框圖

圖2采用的是流水線設計，該設計可以達到較高的速率。第一組數據經過第1級模塊延時1級；接著經過第2級模塊又延時1級，同時第二組數據經過第1級模塊延時1級；依此類推，第一組數據經12級延時從最后一級出來，而第二組數據經13級延時從最后一級出來，后面數據照這樣延時輸出。可見，整體數據延遲是一級延遲。

在對設計的時間要求不嚴格的前提下，可采用復用一級旋轉單元，這樣可以節省器件。如要實現12級迭代，那么復用的旋轉單元的輸出數據需返回給單元的輸入，再次進行旋轉操作。這樣返回操作11次，在第12次取單元的輸出作為結果輸出。可見，整體數據延遲是12級。

復用設計與流水設計相比，所用器件大為減少，但數據延遲卻增加了很多。

3.3 實數除法器div模塊

為了使本設計的除法器適應各種情況，應用性強。這里分2種情況進行考慮。第一，被除數大于除數，那么它們的商就會有整數部分和小數部分；第二，被除數小于除數，那么它們的商只要小數部分。另外，被除數等于除數可歸于第一種考慮。這2種考慮分兩種情況進行實現：第一種情況，計算商的整數部分，說明此時被除數大于除數，則需要將除數左移到最接近被除數，得到一個新除數，記下所移的次數n，接下來進行n次被除數與新除數左移位相減或加的操作，可得到商的整數部分。第二種情況，計算商的小數部分，利用前面操作里的余數與原除數進行小數位次移位相減或加來得到商的小數部分。其結構框圖如圖3所示。

圖3 實數除法器模塊框圖

圖3中模塊1用來記錄除數y左移到最接近被除數x時所需要的次數；模塊2用來得到商的整數部分；模塊3用來得到商的小數部分。由于模塊2和模塊3思想是一樣的，在這里只對模塊2進行說明。

模塊2用來實現求商的整數部分。輸入是被除數x、經左移調整后的新除數Y和記錄的左移次數n；輸出為余數X、原除數y和所得商的整數部分qu。該模塊為了有較高的計算精度，也采用了12級流水迭代結構。每一級的功能，就是完成式（2）的減法，然后根據式（3）來進行判商，其內部結構框圖如圖4所示。

圖4 模塊1中一級迭代模塊內部結構框圖

同理，為了節省器件，可采用第3.2節中提到的復用單元模塊的結構設計。

4 設計性能分析

4.1 器件分析

根據前面提到的復數除法器算法思想和結構設計來實現22位的復數除法器。為了證明本設計的優越性，另外采用原始的直接計算方案來設計并與之對比。對比方案不采用CORDIC算法的設計，直接做多次乘法和加法操作，然后進行實數除法操作。2種設計分別經Verilog語言在ISE上進行邏輯描述，通過Synplify綜合工具綜合得到2種不同的復數除法器整體系統。然后，分別經ISE工具映射成網表文件后，查看映射報告可知道兩種設計的器件使用情況，如表1所示：

表1 復數除法器器件使用情況表

設計方案Flip Flop數目LUT數目Slice數目器件使用率

采用CORDIC2 3263 9312 7688%

不采用CORDIC3 5176 6314 76514%

比較2種方案，可見不采用CORDIC方案所耗器件比采用CORDIC方案多很多。原因除了多次乘法、加法操作所耗器件比CORDIC操作多外，最主要的是采用CORDIC方案旋轉后數據只放大了2位位寬，而不采用CORDIC方案經乘法操作后的數據位寬增加了1倍，那么造成實數除法計算商模塊迭代次數增加了1倍，所耗器件那么多是理所當然的。得出結論：設計采用CORDIC方案具有其優越性。

設計在旋轉模塊、實數除法模塊中的求商模塊中都采用了迭代的實現方法。如果在時間速度要求不高的前提下，可以重復使用一級迭代，實現器件上的復用。例如，旋轉模塊中可以使用一級迭代結構來完成6級的迭代操作，當然該復用結構要做一些小的調整，但改動不大。與6級流水迭代所用器件想比，節省了很多器件。采用復用迭代方案后，系統時鐘頻率仍可以達到69.87 MHz。

4.2 精度分析

根據比較設計與Matlab的運算結果來分析設計的精確度。數據經Matlab計算可以得到高精度的結果。以此為基準，通過分析設計與Matlab的結果差距來判斷設計精度的優劣。給設計與Matlab 3 780個相同的隨機輸入數據，輸入數據都用22位表示，分配為1位符號、5位整數、16位小數位。比較發現結果的最大差距為0.031 1，相對于數據而言，可謂很小。用計算信噪比公式SNR=10*lg(sum/noise)來客觀證明結果非常相近。noise是二者結果數據差的平方和，表示誤差；sum是Matlab值的平方和，代表真實值；最終計算結果SNR=65.073 6。這是一個較高的信噪比，證實了該設計的精度高。

5 結 語

基于CORDIC算法提出了復數除法器的FPGA實現方案。設計利用CORDIC旋轉操作替換了乘法、加法操作，從而大量節省了器件。在實數除法上，運算速度是不恢復余數法的近2倍，同時在雙比特算法的基礎上改進，能完成有符號的除法，這大大提高了其廣泛的適用性。該設計已經通過了FPGA驗證。而且仿真測試結果與在Matlab上的計算結果相比較能達到65.073 6 dB的信噪比，說明其有較高的精度。實驗表明，該設計在面積、性能上都具有較高優越性。

參考文獻

［1］Stuart F Oberman，Michael J Flynn.Division Algorithms and Implementations［J］.IEEE Transactions on Computers，1997，46(8):883-884.

［2］張歡歡，宋國新．不恢復余數陣列除法器的形式化描述和驗證方法［J］．計算機科學，2007，34(6):283-285.

［3］李俠，孫惠，章倩苓.基于雙比特算法的新型除法器［J］．半導體學報，2004，25(6):645-649.

［4］Mark McCann M，Nicholas Pippenger N．SRT Division Algorithms as Dynamical［J］． Computer Arithmetic，2003.Proceedings.16th IEEE Symposium，2003:46-53.

［5］Israel Koren.Computer Arithmetic Algorithms.AK Peters.2002 .

［6］Volder J.The CORDIC Trigonometric Computering-technique［J］.IRE Transaction on Electronic Computers，1959:330-334．

［7］郭立浩，段哲民，白森．采用CORDIC算法的直接數字頻率合成器的設計［J］．電光與控制，2006，13(5):77-79．

［8］張俊，胡德俊，王科，等．將雙比特算法應用到有符號除法器中［J］．IT技術，2006(1):45-46．

［9］夏宇聞．復雜數字電路與系統的VerilogHDL設計技術［M］．北京:北京航空航天大學出版社，1998．

［10］王金明.Verilog HDL程序設計教程［M］.北京:人民郵電出版社，2004.

作者簡介 王景存 男，1965年出生，碩士生導師。研究方向為數字信號處理。

王映波 男，1982年出生，碩士研究生。研究方向為數字信號處理。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文