擴(kuò)展收斂域任意對數(shù)CORDIC算法與FPGA實現(xiàn)

陳旭文，劉桂雄，唐文明

（1.揭陽職業(yè)技術(shù)學(xué)院，廣東 揭陽 522051；2.華南理工大學(xué)，廣東 廣州 510640）

擴(kuò)展收斂域任意對數(shù)CORDIC算法與FPGA實現(xiàn)

陳旭文1，劉桂雄2，唐文明2

（1.揭陽職業(yè)技術(shù)學(xué)院，廣東 揭陽 522051；2.華南理工大學(xué)，廣東 廣州 510640）

針對經(jīng)典自然對數(shù)坐標(biāo)旋轉(zhuǎn)數(shù)字計算機(jī)（coordinate rotation digital computer，CORDIC）算法在應(yīng)用上存在問題，研究擴(kuò)展收斂域任意對數(shù)CORDIC算法與FPGA實現(xiàn)。通過區(qū)間壓縮方法，對收斂域外的數(shù)據(jù)進(jìn)行轉(zhuǎn)換，實現(xiàn)收斂域擴(kuò)展至全收斂域，并應(yīng)用換底公式擴(kuò)展到任意底數(shù)的對數(shù)運(yùn)算。仿真試驗表明，采用15級流水線結(jié)構(gòu)，以10為底的對數(shù)CORDIC運(yùn)算最大時延小于17個時鐘周期，最大計算誤差為0.00027。該算法應(yīng)用于40mm玻璃鋼的超聲檢測中，其TCG回波圖能有效抑制雜散波,提高信號的分辨力，運(yùn)算速度比傳統(tǒng)方法快，對超聲相控儀器的開發(fā)具有應(yīng)用價值。

擴(kuò)展收斂域；對數(shù)；區(qū)間壓縮；FPGA

0 引 言

坐標(biāo)旋轉(zhuǎn)數(shù)字計算機(jī)（coordinate rotation digital computer，CORDIC）算法，是1959年Volder[1]提出的通用迭代算法，它用一系列固定角度的不斷偏擺迭代以逼近所需旋轉(zhuǎn)角度，控制向量在線性坐標(biāo)系、圓坐標(biāo)系和雙曲坐標(biāo)系下的旋轉(zhuǎn)和定向操作，由簡單加法、移位操作實現(xiàn)各類初等函數(shù)求值運(yùn)算。對數(shù)函數(shù)的計算是在雙曲坐標(biāo)系向量模式下完成。硬件實現(xiàn)對數(shù)函數(shù)求值有很多方法，如傳統(tǒng)方法包括查表法、泰勒展開式法、多項式逼近法、拋物線合成法等。Mitchell[2]用若干條連接相鄰整數(shù)點的直線擬合，提出一種底數(shù)為2的對數(shù)近似算法，算法判斷簡單，容易用FPGA實現(xiàn)，但只能保證整數(shù)部分的準(zhǔn)確度。很多文獻(xiàn)表明：查表法隨結(jié)果準(zhǔn)確度提高或輸入值范圍增大，需大量的存儲單元；泰勒展開式法需要復(fù)雜的求導(dǎo)運(yùn)算以及大量的乘法器與除法器，速度慢效率低；多項式逼近法復(fù)雜且準(zhǔn)確度不高。近年來，在研究CORDIC算法的FPGA實現(xiàn)方面，國內(nèi)外學(xué)者做了很多有益的研究[3-5]。Maharatna[6]提出一種無需擴(kuò)展因子的SF-CORDIC算法，省去z通路和擴(kuò)展因子的計算，但僅適用于旋轉(zhuǎn)角度已知且位寬較小情況。牟勝梅等[7]提出一種統(tǒng)一的指數(shù)/對數(shù)迭代求值方法，雖面積開銷減小，但收斂域太小。黃曉可等[8]提出一種改進(jìn)的SF-CORDIC算法實現(xiàn)指數(shù)和對數(shù)運(yùn)算，省去擴(kuò)展因子的計算，但需要三階以上的麥克勞林展開式近似，以提高準(zhǔn)確度，系統(tǒng)運(yùn)算相對復(fù)雜。以上改進(jìn)算法雖取得巨大突破，但存在收斂域小或計算復(fù)雜等不足。本文提出一種運(yùn)算簡單、收斂域更廣的雙曲系統(tǒng)對數(shù)CORDIC算法的FPGA實現(xiàn)方法，并可廣泛應(yīng)用于FFT變換、超聲檢測 （time complement gain，TCG）、信道編碼系統(tǒng)等領(lǐng)域，具有較高的實用價值。

1 改進(jìn)型對數(shù)函數(shù)CORDIC算法機(jī)理

1.1 經(jīng)典自然對數(shù)函數(shù)CORDIC算法

雙曲坐標(biāo)系下的CORDIC算法有旋轉(zhuǎn)模式和向量模式兩種。圖1為雙曲函數(shù)坐標(biāo)旋轉(zhuǎn)模型圖，雙曲線x2-y2=c2上點V1（x1，y1）沿著上半軸曲線移動到點Vn（xn，yn），可表示為

向量模式下，設(shè)旋轉(zhuǎn)方向為di，校模因子為K，令θ=tanh-1（2-i），則zi+1=zi-ditanh-1（2-i），式（1）可轉(zhuǎn)化為

為滿足迭代序列收斂，迭代序列i的取值從第4項開始，每個3k+1（k∈Z+）項必須重復(fù)一次，即i=1，2，3，4，4，5，…，13，13，14，…，通過yi控制微旋轉(zhuǎn)方向，使得yi→0。經(jīng)過n次旋轉(zhuǎn)后，有：

圖1 雙曲函數(shù)坐標(biāo)旋轉(zhuǎn)模型

從而獲得自然對數(shù)CORDIC算法的表達(dá)式。

1.2 自然對數(shù)函數(shù)CORDIC算法的收斂域擴(kuò)展

根據(jù)式（3）可知雙曲線坐標(biāo)CORDIC算法的收斂范圍為

故經(jīng)典對數(shù)函數(shù)CORDIC算法的收斂域[9]為

由于zin的范圍較小，實際應(yīng)用意義不大，必須對收斂域進(jìn)行擴(kuò)張?zhí)幚怼?/p>

當(dāng)zin超出收斂域時，可令D=θ·2Q，則：

其物理意義是：若整數(shù)Q能確定，則Qln2可轉(zhuǎn)換為定點數(shù)，可把ln（θ·2Q）的計算等效轉(zhuǎn)化為lnθ的計算，即把收斂域外的輸入值運(yùn)算轉(zhuǎn)化為收斂域內(nèi)的迭代，通過區(qū)間壓縮方法實現(xiàn)對數(shù)函數(shù)CORDIC算法的收斂域擴(kuò)展。

圖2 自然對數(shù)CORDIC算法在擴(kuò)展收斂域的Matlab系統(tǒng)仿真圖

圖2給出了自然對數(shù)CORDIC算法在擴(kuò)展收斂域的Matlab系統(tǒng)仿真圖?？梢钥闯?，通過對收斂域的擴(kuò)展，自然對數(shù)CORDIC算法在收斂域以外的區(qū)間里，都與理論值基本重合，實現(xiàn)任意輸入角度的運(yùn)算，這對提升對數(shù)CORDIC的應(yīng)用具有實際意義。

1.3 任意對數(shù)函數(shù)CORDIC算法的推廣實現(xiàn)

圖3 底數(shù)為10的對數(shù)函數(shù)CORDIC算法Matlab系統(tǒng)仿真圖

2 對數(shù)函數(shù)CORDIC算法的FPGA實現(xiàn)

2.1 FPGA實現(xiàn)結(jié)構(gòu)

為保證高準(zhǔn)確度和快速運(yùn)算的要求，必須把小數(shù)轉(zhuǎn)化成整數(shù)，即通過擴(kuò)大2N倍（N的大小決定運(yùn)算的準(zhǔn)確度）對小數(shù)進(jìn)行定點化，以保證快速運(yùn)算。FPGA的實現(xiàn)只需兩個乘法器，即可實現(xiàn)整數(shù)Q和小數(shù)θ定點化值求解。

考慮準(zhǔn)確度和速度的矛盾問題，在FPGA實現(xiàn)上采用查找表和流水線法相結(jié)合的解決方案，即對部分固定角度通過查找表進(jìn)行存儲，只占用極少存儲空間，有利于提高運(yùn)算速度，同時保證一定運(yùn)算準(zhǔn)確度。

2.2 性能分析

為驗證對數(shù)CORDIC算法的系統(tǒng)資源、運(yùn)算準(zhǔn)確度和時間延遲等性能，本文以10為底的對數(shù)為例，采用15級流水線算法結(jié)構(gòu)，即擴(kuò)大216進(jìn)行定點化運(yùn)算?；贛odelsim進(jìn)行FPGA仿真，圖4給出了FPGA仿真的時延波形，設(shè)置時間周期T=10 ns（T為時鐘周期，主時鐘頻率為100 MHz），算法時間延遲t1=17T，考慮初始時延等情況，算法總時延t＜25T（250ns）。表1列出了收斂域zin∈[1，100]部分輸入值的對數(shù)運(yùn)算結(jié)果，最大運(yùn)算誤差為0.00027，達(dá)到10-3數(shù)量級，可以滿足實際應(yīng)用要求。

2.3 應(yīng)用測試

超聲檢測中，超聲回波增益用分貝dB表示，與放大倍數(shù)Au成對數(shù)關(guān)系，即dB=20lgAu，超聲儀器傳統(tǒng)TCG補(bǔ)償通?？緾PU調(diào)用C語言庫函數(shù)來實現(xiàn)其中的對數(shù)函數(shù)，運(yùn)算耗時較長。如何解決運(yùn)算準(zhǔn)確度和運(yùn)算速度的矛盾成為超聲儀器極待解決的技術(shù)難點?；贔PGA應(yīng)用擴(kuò)展對數(shù)CORDIC算法，可準(zhǔn)確、快速計算出任意增益的大小，圖5為超聲回波增加TCG效果對比圖，其中圖5（a）為40mm玻璃鋼正?；夭▓D，圖5（b）為40mm玻璃鋼加TCG回波圖，可知增加TCG功能后能有效抑制雜散波，提高信號分辨力。測試證明：本算法運(yùn)算準(zhǔn)確度能夠滿足工業(yè)超聲檢測要求，運(yùn)算速度比傳統(tǒng)方法更快，這對超聲相控儀器的開發(fā)具有較大應(yīng)用價值。

3 結(jié)束語

1）通過區(qū)間壓縮方法，對收斂域外的數(shù)據(jù)進(jìn)行轉(zhuǎn)換，并通過定點化技術(shù)，實現(xiàn)收斂域擴(kuò)展至全收斂域，解決傳統(tǒng)自然對數(shù)收斂域太窄的問題，并用換底公式擴(kuò)展到任意底數(shù)的對數(shù)運(yùn)算，極大地提高對數(shù)CORDIC算法的應(yīng)用范圍。

2）任意底數(shù)對數(shù)CORDIC運(yùn)算仿真結(jié)果表明最大時延小于25個時鐘周期，運(yùn)算準(zhǔn)確度達(dá)10-3數(shù)量級，完全滿足目前超聲相控陣儀器實際應(yīng)用要求。

圖4 FPGA仿真的時延波形

表1 收斂域zin∈[1袁100]部分輸入值的對數(shù)運(yùn)算結(jié)果

圖5 超聲回波增加TCG效果對比圖

3）對數(shù)函數(shù)CORDIC算法的FPGA實現(xiàn)徹底解決信息處理中運(yùn)算準(zhǔn)確度、時間延遲、系統(tǒng)資源等關(guān)鍵技術(shù)問題，在超聲檢測中實現(xiàn)TCG功能的重要算法有重要的實用價值。

[1]Volder J E.The CORDIC trigonometric computing technique[J].IRE Transon Electronic Computers，1959，8（3）：330-334.

[2]Mitchell J N.Computer multiplication and division using binary logarithms[J].IRE Trans Electronic Computers，1962，11（8）：512-517.

[3]劉美娟，許建華，張超.基于CORDIC算法的對數(shù)放大器的FPGA實現(xiàn)[J].儀器儀表學(xué)報，2008，29（4）：328-331.

[4]林若波，劉桂雄，唐文明.應(yīng)用補(bǔ)碼的通項式正余弦CORDIC算法FPGA實現(xiàn)[J].中國測試，2014，40（3）：102 -106.

[5]牟勝梅.面向可重構(gòu)系統(tǒng)的幾個常用算法及其實現(xiàn)技術(shù)研究[D].長沙：國防科技大學(xué)，2008.

[6]Maharatna K， Banerjee S， Grass E， et al.Modified virtually scaling-free adaptive CORDIC rotator algorithm and architecture[J].IEEE Transactions on Circuits and Systems for Video Technology，2005，11（11）：1463-1474.

[7]牟勝梅，李兆剛.一種面向FPGA的指/對數(shù)函數(shù)求值算法[J].計算機(jī)工程與應(yīng)用，2014，47（33）：59-61.

[8]黃曉可，劉洛琨，汪濤，等.基于改進(jìn)SF-CORDIC的指數(shù)和對數(shù)函數(shù)求值算法[J].計算機(jī)應(yīng)用與軟件，2014，31（2）：279-282.

Arbitrary logarithm CORDIC algorithm based on expansion convergence domain and FPGA implementation

CHEN Xuwen1，LIU Guixiong2，TANG Wenming2
（1.Jieyang Vocational and Technical College，Jieyang 522051，China；2.South China University of Technology，Guangzhou 510640，China）

Aiming at the problems of classic natural logarithm CORDIC algorithm on application，the convergence domain of extension arbitrary logarithm CORDIC algorithm and FPGA implementation is discussed.Using interval compression method to convert the extraterritorial data of convergence domain，the whole convergence domain is extended，and the arbitrary base logarithm operation is extended on the application ofthe soled formula.Simulation results show that using 15 stage pipeline structure，the maximum delay of logarithm CORDIC algorithm with base 10 is less than 17 clock cycles，and the maximum error is obtained 0.000 27.Ultrasonic testing on the 40 mm glass steel，the TCG echo can effectively suppress the spuriouswave，improve the signalresolution，and the operation speed isfasterthan traditional methods， which has important application value on development of ultrasonic phased array instrument.

extended convergence domain；logarithm；interval compression；FPGA

A

：1674-5124（2015）07-0108-04

10.11857/j.issn.1674-5124.2015.07.025

2015-02-08；

：2015-03-17

國家重大科學(xué)儀器設(shè)備開發(fā)專項（2013YQ230575）

陳旭文（1976-），男，廣東揭陽市人，講師，碩士，主要從事計算機(jī)應(yīng)用研究與教學(xué)工作。