基于自適應旋轉角度的CORDIC 算法的設計與仿真

(南京恩瑞特實業有限公司,江蘇南京 211100)

0 引言

CORDIC(Coordinated Rotation Digital Computer)算法只有移位和加減運算,便于在FPGA等硬件平臺上實現復雜的三角函數、雙曲函數、指數函數和復數求模等計算,廣泛的應用于數字上下變頻、波形產生、數字鑒相、快速傅里葉變換[1-2]等方面。

傳統的CORDIC算法旋轉的角度固定,通常需要較多的迭代次數才能實現較高的運算精度。近年來,大量學者在提高CORDIC算法運算精度、增加角度覆蓋范圍、減少迭代次數、降低資源消耗方面進行了大量的研究。文獻[3]結合區間折疊技術和雙步旋轉策略,減少了迭代次數且具有較高的運算精度,但時延很大。文獻[4]采用單向固定旋轉方式降低了算法的延遲時間和資源消耗,但該算法運算精度較低。文獻[5]提出將多種技術綜合起來,可以有效降低輸出時延,但硬件實現較為復雜。文獻[6]提出單向最優迭代的CORDIC算法,具有實時性強、資源消耗少的優點,但該方法迭代結束時間判定復雜,硬件實現困難,難以應用于高速系統。

在相同迭代次數下,CORDIC算法運算精度與算法可以遍歷的角度個數密切相關,但上述算法每一級的旋轉角度固定,算法可遍歷的角度個數較少。通常采用增加迭代次數、數據長度、存儲深度等方法來提高運算精度,代價是延遲時間的增加以及硬件資源的消耗。本文提出了一種自適應旋轉角度的CORDIC算法,根據輸入的角度自適應選擇每一級迭代的旋轉角度,不需要消耗大量存儲資源,具有收斂速度快,延遲時間短、可遍歷角度個數多、運算精度高的優點。

1 CORDIC算法

1.1 傳統的CORDIC算法

在直角坐標平面上將點(x1,y1)逆時針旋轉θ角度到點(x2,y2)的標準方法如式(1)所示:

CORDIC方法的核心是旋轉角度θ滿足tanθi=2-i。每次旋轉的表達式如式(2)所示:

式中z表示每次迭代累加的旋轉角度,符號di=±1是判決算子,決定旋轉方向。

CORDIC算法的旋轉角度限定在第一象限,且每次旋轉都會影響最終要旋轉的累積角度,因此僅在-99.7°≤θ≤99.7°的范圍內的任意角度可以旋轉。為了保證旋轉前后幅度不變,對CORDIC輸出的數據乘以一個系數A,如式(3)所示:

傳統的CORDIC算法實現較為簡單,但每次旋轉的角度固定,要實現較高精度的計算,需要多級流水線結構,多級流水線結構延遲大且會增加硬件成本。

1.2 改進的CORDIC算法

本文在傳統的CORDIC基礎上提出改進的CORDIC算法。根據輸入的角度自適應選擇每次旋轉的最優角度,僅需要消耗少量存儲資源且在旋轉次數較少的情況下即可實現較高精度的正余弦值計算,延遲時間短,實時性強。改進的五級旋轉CORDIC算法結構如圖1所示。

建立兩個數組CS、XX,CS存儲角度值,XX存儲對應的余弦值。根據每一級旋轉的剩余角度從CS與XX中選擇最優的旋轉角度與余弦值補償因子。角度表達式為:

式(4)中μ(i)∈{1,-1,0}決定第i次旋轉的方向,1表示逆時針旋轉;-1表示順時針旋轉;0表示旋轉已經達到最小精度值,剩余角度已經為0;ε為誤差值。a(s(i))表示第i次旋轉的度數,s(i)∈{0,1,2,…,n-1},i∈{1,2,3,…n-1},n為數組的長度,為便于計算機實現,令:

綜上可得迭代方程如式(6)為:

每一次旋轉中,比較剩余角度的絕對值與數組CS 中的角度判斷出此次旋轉的最優角度值,并記錄其余弦值,將每次旋轉記錄的余弦值相乘得到補償因子Pn。

改進后的CORDIC算法有以下優點:

(1)對于某些特殊角度如:45°,arctan(2-1),…只需要一次選轉即可使誤差為零,傳統算法旋轉多次后仍有較大誤差;

(2)量化位數、流水線級數相同時,改進后的CORDIC算法,跳過某些旋轉,可以達到的精度遠高于傳統算法;

(3)只需要4級迭代,就可覆蓋角度-π～π。

2 算法仿真與比較

本文將提出的自適應旋轉角度CORDIC算法與傳統的基于固定旋轉角度的CORDIC算法在計算精度、遍歷角度個數、收斂速度以及計算量方面進行仿真對比。

圖1 改進CORDIC 算法五級流水線結構Fig.1 Improved five-stage pipeline structure of CORDIC algorithm

首先對0-360°范圍的角度分別采用傳統CORDIC算法與改進的CORDIC算法計算正弦值,計算誤差如圖2所示。仿真過程中角度從0°變化到360°,步進1°,角度量化為12位,幅度量化為12位,兩種算法均采用五級迭代。從圖2可以看出,相同的迭代次數下,改進的CORDIC算法計算的正弦值更接近標準的正弦值。

圖2 0°-360°正弦值誤差比較Fig.2 0°-360° sine value error comparison

仿真中分別對兩種算法迭代3-7 次時能夠遍歷的角度個數進行比較,如圖3所示。從圖3可以看出兩種算法可以遍歷的角度個數均隨著迭代次數的增加而增加,迭代次數相同時改進的CORDIC 算法可以遍歷的角度個數明顯比傳統算法多。改進的CORDIC算法每一級旋轉可以選擇更多角度,因此可以準確計算的角度個數增加,從而提高了CORDIC算法計算正余弦值的精度。

圖3 兩種算法角度遍歷比較Fig.3 Comparison of angle traversal between two algorithms

圖4為兩種算法收斂速度的仿真比較。隨機產生0-90°的輸入角度,比較傳統算法與改進算法每一級迭代后的剩余角度,重復實驗1000次。從圖4可以看出兩種算法剩余角度均隨著迭代次數的增加而趨近0,但是改進后的算法收斂速度更快。

圖4 兩種算法收斂速度比較Fig.4 Comparison of the convergence speed of the two algorithms

傳統的CORDIC算法每次迭代過程需要進行一次角度判斷、兩次移位和三次加減法運算。改進的CO RDI C算法每次迭代過程需要進行一次角度比較、一次角度判斷、兩次移位和三次加減法運算。改進的算法比傳統的算法多一次角度的比較,具體的運算量由角度數組CS 的大小決定。改進的CORDIC算法以略復雜的角度比較換取更少的迭代次數與更高的精度。

3 結語

本文介紹了一種自適應旋轉角度的CORDIC算法,通過仿真從計算精度、角度遍歷與收斂速度等方面與傳統的CORDIC 算法進行性能比較。仿真結果表明改進的CORDIC算法,計算精度更高、占用資源較少,設計結構簡單,易于硬件實現。