應用補碼的通項式正余弦CORDIC算法FPGA實現

林若波劉桂雄唐文明

（1.揭陽職業技術學院，廣東 揭陽 522051；2.華南理工大學，廣東 廣州 510640）

應用補碼的通項式正余弦CORDIC算法FPGA實現

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

（1.揭陽職業技術學院，廣東 揭陽 522051；2.華南理工大學，廣東 廣州 510640）

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

CORDIC算法；補碼；旋轉方向；正余弦；FPGA技術

0 引 言

坐標旋轉數字計算（coordinate rotation digital computer，CORDIC）算法是1959年由Volder J提出[1]，通過一系列固定的與運算基數有關角度不斷偏擺迭代以逼近所需旋轉角度，由簡單加法、移位操作即可完成三角函數、指數函數、對數函數等超越函數的計算[2]。1971年Walther J D[3]把圓周旋轉、雙曲旋轉和直線旋轉統一成標準CORDIC迭代方程，進一步增加算法運算功能。CORDIC算法具有規則化、結構簡單的特點，容易通過硬件方法實現。流水線法、

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

1 通項式的正余弦CORDIC算法機理

通項式的正余弦CORDIC算法基于經典CORDIC算法。對于如圖1所示的直角坐標系旋轉向量圖，單位向量p0（x0，y0）旋轉角θ到pn（xn，yn），可表示為[1]

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

由于經過n次旋轉后變量zn+1→0，令校模因子則有：

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

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

1.1 通項式的CORDIC算法

該式可用數學歸納法加以證明。

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

（2）假設i=n-1時等式成立，即：

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

1.2 應用補碼的通項式CORDIC算法FPGA實現

根據zi大小判斷下次di，設固定旋轉角度φi位寬為w，zi符號位以及擴展到w位分別表示為Czi、| Czi|w，第i次旋轉固定角度φi的原碼、補碼及反碼分別表示為[φi]原、[φi]補、[φi]反，那么有：

（1）對于zi＞0情況，Czi=0，需順時針旋轉φi，再通過zi+1=zi-[φi]原求出下次zi+1，[φi]原由|Czi|w與φi異或求得；

（2）對于zi＜0情況，Czi=1，需逆時針旋轉φi，由zi+1=zi+[φi]原=zi-[φi]補求出zi+1，[φi]補先由|Czi|w與φi異或得[φi]反再加Czi得到。

綜合以上分析，可得如下表達式：

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

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

其FPGA實現代碼為：

可以看出，采用一條數據鏈連續迭代n次，即可獲得運算結果xn+1=cosθ，yn+1=sinθ。

2 仿真試驗與結果分析

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

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

圖2為θ=0°～360°輸入下迭代法、流水線、通項法3種方法cosθ計算實時輸出顯示波形圖。可以看出，通項法在采取僅流水線所需1/6左右寄存器情況下，通項法、流水線輸出波形幾乎同步，而迭代法則慢得多。

若輸出直接采用數字方式表示，選擇θ=0°作為觀察對象，圖3為迭代法、流水線、通項法3種方法cosθ實時輸出數字表示方式時延圖，圖中4097處表示cosθ=1、時鐘周期為T。可以看出，通項法的初始時延3T明顯優于傳統迭代法、流水線法的初始時延11T。

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

盡管通項法在占用資源、運算速度以及初始時延方面具有很好的綜合特性，但運算精度能否滿足實際要求是關乎該方法應用價值的關鍵。

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

3 結束語

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

（2）已知一系列固定旋轉角角度φi以及初始角度z0、迭代次數n情況下，應用補碼方法，可獲得下次旋轉方向di+1，用一條數據鏈可連續求出n位旋轉方向d1、d2、…、dn，計算坐標值（xi+1、yi+1）。

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

項法使用的寄存器僅為流水線的1/6，初始時延僅為3T，遠小于傳統迭代法、流水線法的初始時延11T；cosθ迭代值與cosθ函數真值的差值約0.8%的計算誤差，在一定要求下可以接受。

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

[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]常柯陽，曾岳南，陳平，等.CORDIC算法在正余弦函數中的應用及其FPGA實現[J].計算機工程與應用，2013，49（7）：140-143.

[5]段文偉，于龍洋，李署堅.一種改進的CORDIC算法及其FPGA實現[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].光學精密工程，2014，22（6）：168-173.

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

[11]Meyer-Baese U.數字信號處理的FPGA實現[M].北京：清華大學出版社，2011.

4 結束語

本文針對現代工業檢測精度高、速度快的要求，提出自動光譜測試分篩方法，并介紹其系統結構和工作原理。研究了光譜曲線重合度算法，包括重合度函數法、尋峰法和固定點特征值法，同時還研究了利用色差值進行顏色判定的方法，給出了自動光譜測試分篩的判定方法。實驗結果表明：系統的測量準確度在納米級，錯誤率＜0.5%，滿足自動光譜測試分篩系統高效率高精度的要求。

參考文獻

[1]王小輝，范衛星，曹一鳴，等.光學薄膜元器件外觀特性機器視覺檢測系統[J].自動化與信息工程，2011，32（6）：32-33，37.

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

[3]張少剛.一種光譜信號檢測技術的應用研究[J].自動化與儀器儀表，2011（5）：90-91，96.

[4]黎國梁，蹇華麗，姚志湘，等.微小型光纖光譜儀在過程監測中的應用[J].現代科學儀器，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]尉志武，苑龍水.函數曲線之間符合程度的評價[J].計算機與應用化學，2001，18（2）：102-104.

[8]王文珂，李思昆.三次B樣條曲線的重合判斷算法[J].計算機輔助設計與圖形學學報，2013，25（5）：674-678.

[9]黃虎，程建，蒲恬.基于機器視覺的工業品色差檢測系統[J].兵工自動化，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

國家重大科學儀器設備開發專項（2013YQ230575）

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