摘 要：在現(xiàn)代數(shù)字信號(hào)處理電路設(shè)計(jì)中，除法器有著廣泛的應(yīng)用。這里闡述一種復(fù)數(shù)除法器的設(shè)計(jì)思想和實(shí)現(xiàn)方法，引入CORDIC算法到復(fù)數(shù)的除法運(yùn)算中，利用CORDIC旋轉(zhuǎn)操作來(lái)代替乘、加法操作，然后采用雙比特移位操作得到最終運(yùn)算結(jié)果。經(jīng)CORDIC旋轉(zhuǎn)后數(shù)據(jù)最多只放大2位位寬，因此可以減少硬件實(shí)現(xiàn)中的器件迭代次數(shù)。經(jīng)過(guò)FPGA驗(yàn)證結(jié)果表明，整個(gè)設(shè)計(jì)運(yùn)算速度快、節(jié)省器件，并且計(jì)算精度高。

關(guān)鍵詞：CORDIC算法；除法器；FPGA；數(shù)字信號(hào)處理

中圖分類號(hào)：TN710文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：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 引 言

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

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

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

(2) 減少迭代級(jí)數(shù)。雙比特除法算法減少了實(shí)現(xiàn)的迭代級(jí)數(shù)，提高了效率，節(jié)省了器件。

2 復(fù)數(shù)除法器算法描述

設(shè)計(jì)的復(fù)數(shù)除法器用到了CORDIC算法和雙比特算法。在接下來(lái)的部分先分別介紹它們基本原理，然后說(shuō)明如何運(yùn)用二者到復(fù)數(shù)除法當(dāng)中去。

2.1 CORDIC算法的一般原理

CORDIC (Coordinate Rotation Digital Computer) ［6］，又名：坐標(biāo)旋轉(zhuǎn)數(shù)字計(jì)算，是J.Voider等人于1959年在設(shè)計(jì)美國(guó)航空導(dǎo)航控制系統(tǒng)的過(guò)程中提出來(lái)的算法。CORDIC算法適用于解決一些三角學(xué)的問(wèn)題，如平面坐標(biāo)的旋轉(zhuǎn)和直角坐標(biāo)到極坐標(biāo)的轉(zhuǎn)換等。該算法的基本思想是通過(guò)一系列固定的、與運(yùn)算基數(shù)有關(guān)的角度的不斷偏擺以逼近所需的旋轉(zhuǎn)角度^［7］。

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

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)

經(jīng)式（1）的n級(jí)旋轉(zhuǎn)迭代，這里會(huì)有一個(gè)幅度的畸變因子k=∏∞n=01+2－2i1.646 768。用該疊代方程組進(jìn)行運(yùn)算，結(jié)果會(huì)放大k倍，得到的新向量的數(shù)據(jù)位寬最多會(huì)放大2位。

運(yùn)用上面提到的CORDIC原理，可方便求任一向量的模。只需將向量逐步旋轉(zhuǎn)，直至新向量無(wú)限接近于x軸，那么新向量的虛部就接近于零，而實(shí)部就是所要求的模放大了k倍的值。如果直接用實(shí)部、虛部平方，再開(kāi)方運(yùn)算，硬件實(shí)現(xiàn)起來(lái)相當(dāng)復(fù)雜。而用CORDIC旋轉(zhuǎn)來(lái)求得，硬件實(shí)現(xiàn)起來(lái)簡(jiǎn)單得多，因而耗器件很少。

2.2 雙比特移位算法

雙比特算法是在不恢復(fù)余數(shù)法的基礎(chǔ)上實(shí)現(xiàn)的。在介紹雙比特算法之前，有必要先簡(jiǎn)單介紹一下不恢復(fù)余數(shù)法的原理。不恢復(fù)余數(shù)法又稱加減交替法，其基本原理是，先做被除數(shù)x與除數(shù)y的減法得到余數(shù)rm。若余數(shù)為正，夠減，商“1” ，余數(shù)左移1位，接下來(lái)繼續(xù)減除數(shù)再判商；若余數(shù)為負(fù)，不夠減，商“0”，余數(shù)左移1位，接下來(lái)的操作變?yōu)榧映龜?shù)再根據(jù)結(jié)果判商，如此重復(fù)操作。該操作次數(shù)等于除數(shù)的位數(shù)。

采用雙比特算法后，從每次左移1位變成移2位了，移位相減操作次數(shù)減少了一半。每次移2位后變?yōu)樾伦兞縩ewrm，這樣每次操作就要產(chǎn)生2位商，這2位商的取值是通過(guò)對(duì)3個(gè)減法器的結(jié)果進(jìn)行判斷來(lái)得到的^［8］。這3個(gè)減法器結(jié)果分別為：

rm1=newrm-y

rm2=newrm-2y

rm3=newrm-3y(2)

對(duì)應(yīng)的商值如下所示:

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)

由于雙比特算法每次移動(dòng)2位，所以它的執(zhí)行周期比不恢復(fù)余數(shù)法降低了近一半。它非常適合高性能的運(yùn)算。同時(shí)因?yàn)槟軠p少器件，所以在面積上也有其優(yōu)越性。

2.3 引入CORDIC算法后的復(fù)數(shù)除法思想

復(fù)數(shù)p=x1+y1j除以復(fù)數(shù)q=x2+y2j，計(jì)算公式如下：

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）可知，硬件實(shí)現(xiàn)該除法運(yùn)算需要做6次乘法，3次加法，最后還有做2次除法，耗大量器件是可想而知的。這樣的運(yùn)算可以運(yùn)用CORDIC算法來(lái)使其簡(jiǎn)單化。

引入CORDIC算法，將向量q=x2+jy2做旋轉(zhuǎn)使之無(wú)限接近x軸，變?yōu)樾碌南蛄縬2=x22+jy22（此時(shí)：y220）。p=x1+jy1跟著旋轉(zhuǎn)相同角度變?yōu)樾碌南蛄縫2=x11+y11j。那么新的計(jì)算公式如下：

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

由式（5）可知，經(jīng)過(guò)CORDIC旋轉(zhuǎn)之后，向量q2和p2同時(shí)放大了1.646 768倍，這并不影響除法結(jié)果。然后只需做x11/x22，y11/x22兩次實(shí)數(shù)除法，這里引入雙比特算法來(lái)實(shí)現(xiàn)。硬件上可以復(fù)用1個(gè)實(shí)數(shù)除法器來(lái)完成2次除法運(yùn)算，就得到了最終結(jié)果。

注意，CORDIC旋轉(zhuǎn)只適應(yīng)一、四象限的向量。如果這里的除法向量不在一象限或四象限，可以給該向量加負(fù)號(hào)使之調(diào)整到一、四象限。同時(shí)被除數(shù)向量做同樣調(diào)整，使它們保持一致

性。這樣的調(diào)整方法可覆蓋各個(gè)象限，適用任何情況數(shù)據(jù)的運(yùn)算。

3 復(fù)數(shù)除法器的結(jié)構(gòu)設(shè)計(jì)

3.1 整體體系結(jié)構(gòu)

基于CORDIC算法的復(fù)數(shù)除法器的總體結(jié)構(gòu)框圖如圖1所示。

圖1 復(fù)數(shù)除法器的總體結(jié)構(gòu)框圖

該系統(tǒng)主要由CORDIC旋轉(zhuǎn)模塊和實(shí)數(shù)除法器模塊組成。被除數(shù)向量x1+jy1和除數(shù)向量x2+jy2經(jīng)CORDIC旋轉(zhuǎn)模塊旋轉(zhuǎn)相同角度得到新的向量X11+jY11和X22+jY22，此時(shí)，Y220；X11與X22，Y11與X22再經(jīng)過(guò)實(shí)數(shù)除法器模塊得到最終的除法結(jié)果Quo1，Quo2。其思想可在式（5）中表現(xiàn)出來(lái)。

3.2 CORDIC旋轉(zhuǎn)模塊

該模塊實(shí)現(xiàn)被除和除法向量的旋轉(zhuǎn)，得到2個(gè)新的旋轉(zhuǎn)向量。這里根據(jù)式（1）的邏輯思想進(jìn)行改進(jìn)，每級(jí)的旋轉(zhuǎn)方向由上一級(jí)的輸出除法向量的y值符號(hào)進(jìn)行判斷來(lái)旋轉(zhuǎn)。按新邏輯思想可在FPGA上設(shè)計(jì)實(shí)現(xiàn)一級(jí)旋轉(zhuǎn)單元。本模塊設(shè)計(jì)可以根據(jù)性能要求來(lái)確定旋轉(zhuǎn)單元迭代的級(jí)數(shù)。本設(shè)計(jì)用到了12級(jí)旋轉(zhuǎn)單元迭代，結(jié)構(gòu)框圖如圖2所示。

圖2 CORDIC模塊框圖

圖2采用的是流水線設(shè)計(jì)，該設(shè)計(jì)可以達(dá)到較高的速率。第一組數(shù)據(jù)經(jīng)過(guò)第1級(jí)模塊延時(shí)1級(jí)；接著經(jīng)過(guò)第2級(jí)模塊又延時(shí)1級(jí)，同時(shí)第二組數(shù)據(jù)經(jīng)過(guò)第1級(jí)模塊延時(shí)1級(jí)；依此類推，第一組數(shù)據(jù)經(jīng)12級(jí)延時(shí)從最后一級(jí)出來(lái)，而第二組數(shù)據(jù)經(jīng)13級(jí)延時(shí)從最后一級(jí)出來(lái)，后面數(shù)據(jù)照這樣延時(shí)輸出?？梢?jiàn)，整體數(shù)據(jù)延遲是一級(jí)延遲。

在對(duì)設(shè)計(jì)的時(shí)間要求不嚴(yán)格的前提下，可采用復(fù)用一級(jí)旋轉(zhuǎn)單元，這樣可以節(jié)省器件。如要實(shí)現(xiàn)12級(jí)迭代，那么復(fù)用的旋轉(zhuǎn)單元的輸出數(shù)據(jù)需返回給單元的輸入，再次進(jìn)行旋轉(zhuǎn)操作。這樣返回操作11次，在第12次取單元的輸出作為結(jié)果輸出。可見(jiàn)，整體數(shù)據(jù)延遲是12級(jí)。

復(fù)用設(shè)計(jì)與流水設(shè)計(jì)相比，所用器件大為減少，但數(shù)據(jù)延遲卻增加了很多。

3.3 實(shí)數(shù)除法器div模塊

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

圖3 實(shí)數(shù)除法器模塊框圖

圖3中模塊1用來(lái)記錄除數(shù)y左移到最接近被除數(shù)x時(shí)所需要的次數(shù)；模塊2用來(lái)得到商的整數(shù)部分；模塊3用來(lái)得到商的小數(shù)部分。由于模塊2和模塊3思想是一樣的，在這里只對(duì)模塊2進(jìn)行說(shuō)明。

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

圖4 模塊1中一級(jí)迭代模塊內(nèi)部結(jié)構(gòu)框圖

同理，為了節(jié)省器件，可采用第3.2節(jié)中提到的復(fù)用單元模塊的結(jié)構(gòu)設(shè)計(jì)。

4 設(shè)計(jì)性能分析

4.1 器件分析

根據(jù)前面提到的復(fù)數(shù)除法器算法思想和結(jié)構(gòu)設(shè)計(jì)來(lái)實(shí)現(xiàn)22位的復(fù)數(shù)除法器。為了證明本設(shè)計(jì)的優(yōu)越性，另外采用原始的直接計(jì)算方案來(lái)設(shè)計(jì)并與之對(duì)比。對(duì)比方案不采用CORDIC算法的設(shè)計(jì)，直接做多次乘法和加法操作，然后進(jìn)行實(shí)數(shù)除法操作。2種設(shè)計(jì)分別經(jīng)Verilog語(yǔ)言在ISE上進(jìn)行邏輯描述，通過(guò)Synplify綜合工具綜合得到2種不同的復(fù)數(shù)除法器整體系統(tǒng)。然后，分別經(jīng)ISE工具映射成網(wǎng)表文件后，查看映射報(bào)告可知道兩種設(shè)計(jì)的器件使用情況，如表1所示：

表1 復(fù)數(shù)除法器器件使用情況表

設(shè)計(jì)方案Flip Flop數(shù)目LUT數(shù)目Slice數(shù)目器件使用率

采用CORDIC2 3263 9312 7688%

不采用CORDIC3 5176 6314 76514%

比較2種方案，可見(jiàn)不采用CORDIC方案所耗器件比采用CORDIC方案多很多。原因除了多次乘法、加法操作所耗器件比CORDIC操作多外，最主要的是采用CORDIC方案旋轉(zhuǎn)后數(shù)據(jù)只放大了2位位寬，而不采用CORDIC方案經(jīng)乘法操作后的數(shù)據(jù)位寬增加了1倍，那么造成實(shí)數(shù)除法計(jì)算商模塊迭代次數(shù)增加了1倍，所耗器件那么多是理所當(dāng)然的。得出結(jié)論：設(shè)計(jì)采用CORDIC方案具有其優(yōu)越性。

設(shè)計(jì)在旋轉(zhuǎn)模塊、實(shí)數(shù)除法模塊中的求商模塊中都采用了迭代的實(shí)現(xiàn)方法。如果在時(shí)間速度要求不高的前提下，可以重復(fù)使用一級(jí)迭代，實(shí)現(xiàn)器件上的復(fù)用。例如，旋轉(zhuǎn)模塊中可以使用一級(jí)迭代結(jié)構(gòu)來(lái)完成6級(jí)的迭代操作，當(dāng)然該復(fù)用結(jié)構(gòu)要做一些小的調(diào)整，但改動(dòng)不大。與6級(jí)流水迭代所用器件想比，節(jié)省了很多器件。采用復(fù)用迭代方案后，系統(tǒng)時(shí)鐘頻率仍可以達(dá)到69.87 MHz。

4.2 精度分析

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

5 結(jié) 語(yǔ)

基于CORDIC算法提出了復(fù)數(shù)除法器的FPGA實(shí)現(xiàn)方案。設(shè)計(jì)利用CORDIC旋轉(zhuǎn)操作替換了乘法、加法操作，從而大量節(jié)省了器件。在實(shí)數(shù)除法上，運(yùn)算速度是不恢復(fù)余數(shù)法的近2倍，同時(shí)在雙比特算法的基礎(chǔ)上改進(jìn)，能完成有符號(hào)的除法，這大大提高了其廣泛的適用性。該設(shè)計(jì)已經(jīng)通過(guò)了FPGA驗(yàn)證。而且仿真測(cè)試結(jié)果與在Matlab上的計(jì)算結(jié)果相比較能達(dá)到65.073 6 dB的信噪比，說(shuō)明其有較高的精度。實(shí)驗(yàn)表明，該設(shè)計(jì)在面積、性能上都具有較高優(yōu)越性。

參考文獻(xiàn)

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

［2］張歡歡，宋國(guó)新．不恢復(fù)余數(shù)陣列除法器的形式化描述和驗(yàn)證方法［J］．計(jì)算機(jī)科學(xué)，2007，34(6):283-285.

［3］李俠，孫惠，章倩苓.基于雙比特算法的新型除法器［J］．半導(dǎo)體學(xué)報(bào)，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算法的直接數(shù)字頻率合成器的設(shè)計(jì)［J］．電光與控制，2006，13(5):77-79．

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

［9］夏宇聞．復(fù)雜數(shù)字電路與系統(tǒng)的VerilogHDL設(shè)計(jì)技術(shù)［M］．北京:北京航空航天大學(xué)出版社，1998．

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

作者簡(jiǎn)介 王景存 男，1965年出生，碩士生導(dǎo)師。研究方向?yàn)閿?shù)字信號(hào)處理。

王映波 男，1982年出生，碩士研究生。研究方向?yàn)閿?shù)字信號(hào)處理。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文