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

陳旭文，劉桂雄，唐文明

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

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

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

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

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

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

0 引 言

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

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上點(diǎn)V1（x1，y1）沿著上半軸曲線移動(dòng)到點(diǎn)Vn（xn，yn），可表示為

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

為滿足迭代序列收斂，迭代序列i的取值從第4項(xiàng)開始，每個(gè)3k+1（k∈Z+）項(xiàng)必須重復(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的范圍較小，實(shí)際應(yīng)用意義不大，必須對收斂域進(jìn)行擴(kuò)張?zhí)幚怼?/p>

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

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

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

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

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

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

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

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

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

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

2.2 性能分析

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

2.3 應(yīng)用測試

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

3 結(jié)束語

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

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

圖4 FPGA仿真的時(shí)延波形

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

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

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

[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實(shí)現(xiàn)[J].儀器儀表學(xué)報(bào)，2008，29（4）：328-331.

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

[5]牟勝梅.面向可重構(gòu)系統(tǒng)的幾個(gè)常用算法及其實(shí)現(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ì)算機(jī)工程與應(yīng)用，2014，47（33）：59-61.

[8]黃曉可，劉洛琨，汪濤，等.基于改進(jìn)SF-CORDIC的指數(shù)和對數(shù)函數(shù)求值算法[J].計(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ā)專項(xiàng)（2013YQ230575）

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