應(yīng)用補(bǔ)碼的通項(xiàng)式正余弦CORDIC算法FPGA實(shí)現(xiàn)

林若波劉桂雄唐文明

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

應(yīng)用補(bǔ)碼的通項(xiàng)式正余弦CORDIC算法FPGA實(shí)現(xiàn)

林若波1,2,劉桂雄2,唐文明2

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

針對(duì)經(jīng)典CORDIC算法在FPGA實(shí)現(xiàn)存在的問(wèn)題，研究通項(xiàng)式正余弦CORDIC算法，采用數(shù)學(xué)歸納法推導(dǎo)正余弦CORDIC算法通項(xiàng)公式，通過(guò)先算出固定旋轉(zhuǎn)角度變量，然后應(yīng)用補(bǔ)碼法求解角度變量，判斷旋轉(zhuǎn)方向，借助旋轉(zhuǎn)方向的移位、加法運(yùn)算完成正余弦函數(shù)的計(jì)算。仿真試驗(yàn)表明：輸入角度采用13位位寬，通項(xiàng)法使用的寄存器僅為流水線的1/6；計(jì)算時(shí)間與流水線相同，但初始時(shí)延僅為3個(gè)時(shí)鐘周期，遠(yuǎn)小于傳統(tǒng)迭代法、流水線法初始時(shí)延11個(gè)時(shí)鐘周期；cosθ迭代值與cosθ函數(shù)真值的差值約0.8%的計(jì)算誤差。該方法具有初始時(shí)延小、速度快、存儲(chǔ)資源少的特點(diǎn)，適用于信號(hào)實(shí)時(shí)處理。

CORDIC算法；補(bǔ)碼；旋轉(zhuǎn)方向；正余弦；FPGA技術(shù)

0 引 言

坐標(biāo)旋轉(zhuǎn)數(shù)字計(jì)算（coordinate rotation digital computer，CORDIC）算法是1959年由Volder J提出[1]，通過(guò)一系列固定的與運(yùn)算基數(shù)有關(guān)角度不斷偏擺迭代以逼近所需旋轉(zhuǎn)角度，由簡(jiǎn)單加法、移位操作即可完成三角函數(shù)、指數(shù)函數(shù)、對(duì)數(shù)函數(shù)等超越函數(shù)的計(jì)算[2]。1971年Walther J D[3]把圓周旋轉(zhuǎn)、雙曲旋轉(zhuǎn)和直線旋轉(zhuǎn)統(tǒng)一成標(biāo)準(zhǔn)CORDIC迭代方程，進(jìn)一步增加算法運(yùn)算功能。CORDIC算法具有規(guī)則化、結(jié)構(gòu)簡(jiǎn)單的特點(diǎn)，容易通過(guò)硬件方法實(shí)現(xiàn)。流水線法、

迭代法是目前CORDIC算法在FPGA實(shí)現(xiàn)的主要方法[4-5]。其中流水線法基于并行結(jié)構(gòu)，處理速度快，但存在結(jié)構(gòu)復(fù)雜、占用硬件資源多的問(wèn)題，初始時(shí)延較大；迭代法基于串行結(jié)構(gòu)，結(jié)構(gòu)簡(jiǎn)單、占用資源少，但存在迭代次數(shù)多、運(yùn)算速度慢的問(wèn)題，初始時(shí)延較大。為提高CORDIC算法在FPGA實(shí)現(xiàn)性能，國(guó)內(nèi)外開(kāi)展很多研究，如Antelo等[6]（2008）研究低功耗流水線CORDIC處理器、Vachhani等[7]（2009）研究低存儲(chǔ)高運(yùn)算量CORDIC算法結(jié)構(gòu)、Erdal Oruklu等[8]（2012）研究基于FFT處理器的CORDIC算法結(jié)構(gòu)，從不同角度對(duì)CORDIC算法進(jìn)行結(jié)構(gòu)改進(jìn)，減少存儲(chǔ)單元、降低功耗，部分存在算法復(fù)雜的問(wèn)題。為此，本文研究一種基于通項(xiàng)式的CORDIC算法，采用通項(xiàng)公式迭代求解，具有初始時(shí)延小、速度快、存儲(chǔ)資源少的特點(diǎn)，適合應(yīng)用于超聲相控陣[9-10]等信號(hào)實(shí)時(shí)處理。

1 通項(xiàng)式的正余弦CORDIC算法機(jī)理

通項(xiàng)式的正余弦CORDIC算法基于經(jīng)典CORDIC算法。對(duì)于如圖1所示的直角坐標(biāo)系旋轉(zhuǎn)向量圖，單位向量p0（x0，y0）旋轉(zhuǎn)角θ到pn（xn，yn），可表示為[1]

將角度θ分成n個(gè)遞減小角度θi=arctan（2-i）之和，即方向系數(shù)di順時(shí)針、逆時(shí)針?lè)謩e取-1、1。令ki=cosθi，引入角度中間變量zi，可由式（1），推得CORDIC公式[2]：

由于經(jīng)過(guò)n次旋轉(zhuǎn)后變量zn+1→0，令校模因子則有：

況且有n→∞，K=0.607 253。在初值x0=1/K，y0=0，z0=θ情況下，通過(guò)n次迭代后CORDIC公式輸出[7]：

故基于初值多次迭代，獲得角度θ的正余弦值，這就是一般基于CORDIC算法計(jì)算正余弦函數(shù)的原理。同時(shí)，由于每次迭代都必需依賴于上一次迭代結(jié)果旋轉(zhuǎn)方向判斷，直接導(dǎo)致存儲(chǔ)資源增加、運(yùn)算速度緩慢，若可減少或不用旋轉(zhuǎn)判斷將非常有意義。

1.1 通項(xiàng)式的CORDIC算法

該式可用數(shù)學(xué)歸納法加以證明。

（1）i=1，由式（4）有：

（2）假設(shè)i=n-1時(shí)等式成立，即：

由CORDIC算法通項(xiàng)公式可看出，計(jì)算轉(zhuǎn)化為旋轉(zhuǎn)方向di的移位、加法運(yùn)算，若先確定每次旋轉(zhuǎn)方向，則可省去每次判斷，用一個(gè)時(shí)鐘周期即可同時(shí)計(jì)算任何一項(xiàng)迭代結(jié)果，非常適合FPGA實(shí)現(xiàn)[11]。如果先確定旋轉(zhuǎn)次數(shù)n，借助zi計(jì)算，di就可確定。

1.2 應(yīng)用補(bǔ)碼的通項(xiàng)式CORDIC算法FPGA實(shí)現(xiàn)

根據(jù)zi大小判斷下次di，設(shè)固定旋轉(zhuǎn)角度φi位寬為w，zi符號(hào)位以及擴(kuò)展到w位分別表示為Czi、| Czi|w，第i次旋轉(zhuǎn)固定角度φi的原碼、補(bǔ)碼及反碼分別表示為[φi]原、[φi]補(bǔ)、[φi]反，那么有：

（1）對(duì)于zi＞0情況，Czi=0，需順時(shí)針旋轉(zhuǎn)φi，再通過(guò)zi+1=zi-[φi]原求出下次zi+1，[φi]原由|Czi|w與φi異或求得；

（2）對(duì)于zi＜0情況，Czi=1，需逆時(shí)針旋轉(zhuǎn)φi，由zi+1=zi+[φi]原=zi-[φi]補(bǔ)求出zi+1，[φi]補(bǔ)先由|Czi|w與φi異或得[φi]反再加Czi得到。

綜合以上分析，可得如下表達(dá)式：

其物理意義是：在先知道一系列φi以及初始值z(mì)0、迭代次數(shù)n情況下，可借助zi+1及Czi+1，獲得下次di+1，通過(guò)一條數(shù)據(jù)鏈可連續(xù)求出n位旋轉(zhuǎn)方向d1、d2、…、dn，再按式（5）計(jì)算坐標(biāo)值（xi+1、yi+1）。

設(shè)坐標(biāo)（xi、yi）位寬w，di符號(hào)位以及擴(kuò)展到w位分別表示為Cdi、|Cdi|w；xi、yi右移i位后分別表示為xi（＞＞i）、yi（＞＞i），它們的反碼、補(bǔ)碼分別表示為[xi（＞＞i）]反和[yi（＞＞i）]反、[xi（＞＞i）]補(bǔ)和[yi（＞＞i）]補(bǔ)，那么式（5）計(jì)算可用式（7）實(shí)現(xiàn)，這里省略ki，在n足夠大時(shí)，校模因子用K=0.607253統(tǒng)一處理。

其FPGA實(shí)現(xiàn)代碼為：

可以看出，采用一條數(shù)據(jù)鏈連續(xù)迭代n次，即可獲得運(yùn)算結(jié)果xn+1=cosθ，yn+1=sinθ。

2 仿真試驗(yàn)與結(jié)果分析

為驗(yàn)證算法效果，將本文通項(xiàng)法與迭代法、流水線法進(jìn)行對(duì)比。實(shí)驗(yàn)基于Quartus II9.0和Modelsim6.5環(huán)境，采用Altrea公司EP2S15F484C3芯片完成邏輯設(shè)計(jì)。輸入角度采用13位位寬，迭代法、流水線、通項(xiàng)法所需的邏輯單元（ALUTs）以及寄存器（registers）分別為330，369，370和168，322，52，這3種方法所需邏輯單元比較接近，但通項(xiàng)法使用寄存器要少得多，僅流水線所需的1/6左右，硬件資源明顯減少。

按照表1仿真參數(shù)表設(shè)置進(jìn)行性能仿真，輸入角度位寬w=13。添加測(cè)試文件，輸入角度θ為0°～360°，添加cosθ輸出作為觀察信號(hào)（sinθ類似），波形顯示方式。

圖2為θ=0°～360°輸入下迭代法、流水線、通項(xiàng)法3種方法cosθ計(jì)算實(shí)時(shí)輸出顯示波形圖?？梢钥闯?，通項(xiàng)法在采取僅流水線所需1/6左右寄存器情況下，通項(xiàng)法、流水線輸出波形幾乎同步，而迭代法則慢得多。

若輸出直接采用數(shù)字方式表示，選擇θ=0°作為觀察對(duì)象，圖3為迭代法、流水線、通項(xiàng)法3種方法cosθ實(shí)時(shí)輸出數(shù)字表示方式時(shí)延圖，圖中4097處表示cosθ=1、時(shí)鐘周期為T(mén)?？梢钥闯?，通項(xiàng)法的初始時(shí)延3T明顯優(yōu)于傳統(tǒng)迭代法、流水線法的初始時(shí)延11T。

為直觀起見(jiàn)，表2列出角度位寬w=13下迭代法、流水線法和通項(xiàng)法的硬件開(kāi)銷、初始時(shí)延比較表。同理，可得到表3所示角度位寬w=8下迭代法、流水線法和通項(xiàng)法的硬件開(kāi)銷、初始時(shí)延比較。

盡管通項(xiàng)法在占用資源、運(yùn)算速度以及初始時(shí)延方面具有很好的綜合特性，但運(yùn)算精度能否滿足實(shí)際要求是關(guān)乎該方法應(yīng)用價(jià)值的關(guān)鍵。

表4列出通項(xiàng)法在θ=0°～90°下cosθ迭代值與cosθ函數(shù)真值之比較。由于采用13位運(yùn)算精度，量化誤差為1/4096，表中cosθ迭代值與cosθ函數(shù)真值的差值最大為0.007 6，約0.8%的計(jì)算誤差，在一定要求下是可以接受的。

3 結(jié)束語(yǔ)

（1）研究通項(xiàng)式正余弦CORDIC算法，借助旋轉(zhuǎn)方向di的移位、加法運(yùn)算就可完成。指出先確定旋轉(zhuǎn)次數(shù)n，借助角度變量zi，即可確定旋轉(zhuǎn)方向di。

（2）已知一系列固定旋轉(zhuǎn)角角度φi以及初始角度z0、迭代次數(shù)n情況下，應(yīng)用補(bǔ)碼方法，可獲得下次旋轉(zhuǎn)方向di+1，用一條數(shù)據(jù)鏈可連續(xù)求出n位旋轉(zhuǎn)方向d1、d2、…、dn，計(jì)算坐標(biāo)值（xi+1、yi+1）。

（3）仿真試驗(yàn)表明，輸入角度采用13位位寬，通

項(xiàng)法使用的寄存器僅為流水線的1/6，初始時(shí)延僅為3T，遠(yuǎn)小于傳統(tǒng)迭代法、流水線法的初始時(shí)延11T；cosθ迭代值與cosθ函數(shù)真值的差值約0.8%的計(jì)算誤差，在一定要求下可以接受。

（4）通項(xiàng)式CORDIC算法實(shí)現(xiàn)實(shí)質(zhì)是知道迭代次數(shù)n，提前計(jì)算出固定旋轉(zhuǎn)角度變量φi，判斷旋轉(zhuǎn)方向di，能更好地解決實(shí)時(shí)性問(wèn)題，計(jì)算時(shí)間與流水線相同，初始時(shí)延比流水線還短，存儲(chǔ)單元比流水線少得多，在信號(hào)實(shí)時(shí)計(jì)算中具有重要的實(shí)際意義。

[1]Volder J E.The CORDIC Trigonometric Computing Technique[J].IRE Trans on Electronic Computers，1959，8（3）：330-334.

[2]Meher P K.50 Years of CORDIC：algorithms，architectures，and applications[J].IEEE Transactions on Circuits and Systems-I：Regular Papers，2009，56（9）：1893-1907.

[3]Walther J S.A Unified algorithm for elementary functions[C]∥Proc of AFIPS’71，1971：389-385.

[4]?？玛?yáng)，曾岳南，陳平，等.CORDIC算法在正余弦函數(shù)中的應(yīng)用及其FPGA實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（7）：140-143.

[5]段文偉，于龍洋，李署堅(jiān).一種改進(jìn)的CORDIC算法及其FPGA實(shí)現(xiàn)[J].微電子學(xué)與計(jì)算機(jī)，2012，29（2）：95-98.

[6]Antelo E，Villalba J，Zapata E L.A low-latency pipelined 2D and 3D CORDIC processors[J].IEEE Trans Computers，2008，57（3）：404-417.

[7]Vachhani L，Sridharan K，Meher P K.Efficient CORDIC algorithmsand architecturesforlow area and high throughputimplementation[J].IEEE Transactions on Circuits&Systems-II：Express Briefs，2009，56（1）：61-65.

[8]Oruklu E，Xiao X，Saniie J.Reduced memory and low power architectures for CORDIC-based FFT processors[J]. Journal of Signal Processing Systems，2012（66）：129-134.

[9]劉桂雄，唐文明，譚大基.基于多級(jí)半帶濾波器的超聲相控陣聚焦延時(shí)技術(shù)[J].光學(xué)精密工程，2014，22（6）：168-173.

[10]劉桂雄，李籌，唐文明，等.基于相關(guān)性延遲分析的SAFT算法[J].中國(guó)測(cè)試，2014，40（1）：62-65.

[11]Meyer-Baese U.數(shù)字信號(hào)處理的FPGA實(shí)現(xiàn)[M].北京：清華大學(xué)出版社，2011.

4 結(jié)束語(yǔ)

本文針對(duì)現(xiàn)代工業(yè)檢測(cè)精度高、速度快的要求，提出自動(dòng)光譜測(cè)試分篩方法，并介紹其系統(tǒng)結(jié)構(gòu)和工作原理。研究了光譜曲線重合度算法，包括重合度函數(shù)法、尋峰法和固定點(diǎn)特征值法，同時(shí)還研究了利用色差值進(jìn)行顏色判定的方法，給出了自動(dòng)光譜測(cè)試分篩的判定方法。實(shí)驗(yàn)結(jié)果表明：系統(tǒng)的測(cè)量準(zhǔn)確度在納米級(jí)，錯(cuò)誤率＜0.5%，滿足自動(dòng)光譜測(cè)試分篩系統(tǒng)高效率高精度的要求。

參考文獻(xiàn)

[1]王小輝，范衛(wèi)星，曹一鳴，等.光學(xué)薄膜元器件外觀特性機(jī)器視覺(jué)檢測(cè)系統(tǒng)[J].自動(dòng)化與信息工程，2011，32（6）：32-33，37.

[2]齊向東，撖芃芃，潘明忠，等.凸面光柵成像光譜儀的光譜定標(biāo)[J].光學(xué)精密工程，2011，19（12）：2870-2876.

[3]張少剛.一種光譜信號(hào)檢測(cè)技術(shù)的應(yīng)用研究[J].自動(dòng)化與儀器儀表，2011（5）：90-91，96.

[4]黎國(guó)梁，蹇華麗，姚志湘，等.微小型光纖光譜儀在過(guò)程監(jiān)測(cè)中的應(yīng)用[J].現(xiàn)代科學(xué)儀器，2008（4）：126-130.

[5]Lee B.Review of present status of optical fiber sensors[J]. Optical Fiber Technology，2003（9）：57-79.

[6]Wild G，Hinckley S.Acousto-ultrasonic optical fiber sensors：overview and state-of-He-Art[J].Sensors Journal IEEE，2008，8（7）：1184-1193.

[7]尉志武，苑龍水.函數(shù)曲線之間符合程度的評(píng)價(jià)[J].計(jì)算機(jī)與應(yīng)用化學(xué)，2001，18（2）：102-104.

[8]王文珂，李思昆.三次B樣條曲線的重合判斷算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2013，25（5）：674-678.

[9]黃虎，程建，蒲恬.基于機(jī)器視覺(jué)的工業(yè)品色差檢測(cè)系統(tǒng)[J].兵工自動(dòng)化，2010，29（7）：78-81.

CORDIC algorithm on FPGA for general formula of sine&cosine based on complement method

LIN Ruo-bo1，2，LIU Gui-xiong2，TANG Wen-ming2
（1.Jieyang Vocational and Technical College，Jieyang 522051，China；2.South China University of Technology，Guangzhou 510640，China）

Aiming at the problems of classic CORDIC algorithm on FPGA，CORDIC algorithm for the general formula of sine&cosine was discussed using mathematical induction method to deduce the formula.Firstly，it calculated the fixed rotation angle variables，and used complement method to calculate angle variables，determined the rotation direction，and realized the calculation of sine &cosine function on shift and addition operation of the rotation direction.Simulation results show that the require registers of general formula method is only 1/6 of pipelined method at 13 bit-width of input angle and the calculating time is the same as pipelined method，but the initial-delay is only 3 clock，far less than the traditional iterative method and pipelined method with the initialdelay are 11 clock.Calculation error of cosine function is about 0.8 percent of its true value.It has the characteristics of little initial-delay and speed calculation and low memory resource，which is suitable for application on real-time signal processing.

CORDIC algorithm；complement；rotation direction；sine&cosine；FPGA

TN431.2；TP301.6；TP391.97；TN911.7

：A

：1674-5124（2014）04-0102-05

10.11857/j.issn.1674-5124.2014.04.026

2014-01-13；

：2014-02-25

國(guó)家重大科學(xué)儀器設(shè)備開(kāi)發(fā)專項(xiàng)（2013YQ230575）

林若波（1974-），男，廣東揭陽(yáng)市人，副教授，碩士，主要從事機(jī)電一體化研究與教學(xué)工作。