雙向預判免縮放因子CORDIC算法

鄒家軒，揭 燦，王 棟，晏承榮，程雪峰

(1.西安電子科技大學 微電子學院，西安 710000；2.中國電子科技集團第五十八研究所，江蘇 無錫 214000)

坐標旋轉數字計算機(CORDIC)算法的基本思想是運用旋轉迭代等方法，采用運算基數角度不斷逼近目標角度[1]，只使用簡單的移位和加減操作，即可計算三角函數、反三角函數和雙曲函數等超越函數[2-3].該算法具有易于實現、可移植性強、精度可調等特點[4]，常應用于數字頻率合成、數字圖形處理、機器人學、矩陣計算等領域，因而受到眾多科研院校的廣泛研究[5-6].

為了適應于現代數字系統的需要，開發高性能的CORDIC算法，眾多學者對其提出了改進方案.文獻[7]中傳統的流水線型CORDIC算法雖然具有一定的精度，但所需的迭代單元級數和迭代次數較多，且需要通過上級迭代剩余角度的符號判斷下級旋轉迭代的方向，當輸出位寬增大時，硬件資源消耗將大幅增加.文獻[8]中提出的混合型CORDIC算法雖然可以快速調節旋轉角度基數，但是其以較多的迭代次數來保證輸出精度，且調整方程系數的電路結構復雜，存在硬件資源消耗過多的問題.文獻[9]中設計的免迭代CORDIC算法采用合并迭代結構將多次迭代合并為一次迭代旋轉，具有輸出時延短的特點，但是運算精度卻有待提高.文獻[10]中基于離散傅里葉變換的并行補償型CORDIC算法對縮放因子進行補償計算，具有一定的輸出精度，但是電路結構復雜，需要消耗額外的硬件資源用于補償和存放縮放因子.文獻[11]中提出的基于直接旋轉的CORDIC算法雖然避免了縮放因子的計算，但是其只能逆時針旋轉逼近輸入角度，仍然具有較大的迭代運算量.

本文在文獻[11]的基礎上對CORDIC算法進行優化與改進，提出了雙向預判免縮放因子CORDIC算法，其通過角度二進制編碼后的碼值即可預判每次的旋轉迭代方向.此算法將輸入角度分解為兩個階段處理，在第1階段中利用查找表一步旋轉到初始角度，然后在第2階段中根據二進制編碼后碼值中1的個數，選擇恒定順時針或逆時針方向進行免縮放因子旋轉迭代，減少了迭代單元級數和迭代次數，提高了輸出精度，最后通過角度區間折疊方法將運算角度覆蓋到整個圓周，確保了運算范圍.

1 雙向預判免縮放因子旋轉

1.1 角度二進制編碼

對于輸入角度為[0,π/4)內的角度θ0，采用n位二進制小數表示為

(1)

式中bk為0或1.將θ0前4位按位展開后為

(2)

當式(2)中bk的值為1時，則需要進行逆時針旋轉2-k弧度；當bk為0時，則不需要進行任何角度的旋轉[12].經過角度編碼后的旋轉向量無需根據上次的迭代結果判斷下次的旋轉方向，避免了迭代方向的不確定性.若式(1)中k增大時，則tan(2-k)-2-k的絕對值越來越小，且當k≥n/3時，有|tan(2-k)-2-k|<2-n，因此tan(2-k)與2-k之間的誤差小于n位二進制小數能夠表示的精度，計算誤差可以忽略不計.則可用2-k近似表示tan(2-k)，只需要通過移位和加減運算即可實現，避免進行乘法運算.

1.2 建立小容量正余弦值查找表

本文采用13位二進制數表示[0,π/4)內的輸入角度，而[π/4,2π)內輸入角度的正弦和余弦函數值可以通過三角函數公式變換后獲得，則只需要輸入[0,π/4)內的角度值即可.此時n值為13，帶入公式(2)可知，當k<13/3時，不可用2-k近似表示tan(2-k)，否則將會引入較大的計算誤差，因此建立小容量正余弦值查找表(見表1)，用以保證輸出精度，且所消耗的寄存器也較少.

表1 小容量正余弦值查找表

根據[0,π/4)內輸入角度的前4位分別為0000到1101，且后9位全為0時的初始角度η，建立14個14位的正余弦值查找表，表中將cosη和sinη值的輸出位寬擴展1位，用于減小計算中的截斷誤差.

1.3 角度區間折疊

對于流水線型CORDIC算法，雖然隨著迭代次數的增多，其運算范圍也隨之增加，但是當迭代次數趨近于無窮大時，最大運算范圍接近[-1.744,1.744]rad，而無法覆蓋整個圓周[13].但正弦函數與余弦函數都具有對稱性，因此可以將[0,2π)的角度劃分為8個區間，利用三角公式變換將整個圓周內的角度折疊映射到[0,π/4)內，角度區間轉化如表2所示.

表2 角度區間轉化

在本文的雙向預判免縮放因子型CORDIC算法的實現過程中，首先計算[0,π/4)內的正弦值和余弦值，然后比較3位角度區間編碼值，最后通過角度區間折疊轉換到不同的角度區間，輸出相應的運算結果.3位編碼值中的次高位和第3位相同與否決定了余弦值與正弦值是否需要進行交換，如果相同則無需交換，否則需要進行交換；余弦值和正弦值是否需要翻轉取反取決于編碼值中的第3位，若第3位的值為0時，則無需翻轉取反；但當第3位為1時，則進行翻轉取反輸出；若最高位的值為0，則正弦值輸出為正值，否則為負值；當最高位與次高位不同時，則余弦值輸出為負值，反之為正值.采用角度區間折疊技術，保證了運算范圍，同時減少了查找表所需要存儲的正余弦值的個數.

1.4 雙向免縮放因子旋轉

下面首先介紹免縮放因子旋轉的基本原理.在流水線型CORDIC算法中，將正弦和余弦函數用泰勒級數展開式表示可得

(3)

(4)

令式(3)和(4)中的θ0=2-i，則sinθ0中的三次項可以表示為

(5)

當正弦函數和余弦函數的輸出位寬設定為N位，且最高位為符號位時，則式(5)中i的最大值為N-1.若3i+2.59≥N-1，可得i的取值范圍為

(6)

單向免縮放因子旋轉可以省略縮放因子的計算，且迭代方向與角度二進制編碼后的位值相對應，避免了流水線型需要不斷順時針和逆時針旋轉修正角度的問題，同時也不會因為去掉了縮放因子而影響輸出精度[15].然而當角度二進制編碼后碼值中相應位為0時，雖然不需要進行旋轉迭代，但是并不能保證下一個碼值在此位的值還是為0，且只能進行恒定逆時針免縮放因子旋轉，所以需要消耗一個時鐘周期進行此位的旋轉判斷，無法跳躍此位為0時的旋轉判斷，需要較多的迭代單元級數和次數以保證輸出精度.但本文設計的CORDIC算法既可以恒定逆時針或順時針免縮放因子旋轉，也可以跳躍不需要旋轉的角度，減少電路的迭代次數，提高了運算精度，其雙向旋轉示意見圖1.

圖1 雙向旋轉示意

在上圖中，根據表1中設立的14個初始角度值將[0,13/16)弧度范圍內的角度均分為13等份，每一份弧度都為1/16.當由初始角度η0逆時針旋轉到目標角度ηθ時，則ηθ可以表示為

則由η0和η1旋轉到目標角度的迭代次數分別為

λ0=b5+b6+…+b13,

(7)

λ1=10-(b5+b6+…+b13)=10-λ0.

(8)

通過式(7)和(8)可知，當λ0≥λ1時，則λ0≥10-λ0，得λ0≥5，因此當輸入角度二進制編碼后碼值中1的個數≥5時，此時用η1旋轉迭代的次數比η0少；當λ0<λ1時，則λ0<10-λ0，得λ0<5，若二進制編碼后碼值中1的個數<5時，此時用η0旋轉迭代的次數比η1少.因此與單向免縮放因子型和流水線型CORDIC算法相比，迭代單元的級數分別減少了4級和8級，降低了電路的硬件資源消耗.采用13位二進制小數表示π/4 rad可為1100100011110，對于圖1中0000到1100這12個分區和1100到π/4區間而言，根據相應的迭代次數對應的種類，單向免縮放因子型CORDIC算法在初始角度η0的基礎上進行恒定逆時針旋轉時，由排列組合相關知識可得每個分區間的迭代次數Ld和總迭代次數Nunid分別為：

上式中，m為建立4位查找表后剩余的二進制編碼的位數，其值為n-4.當根據碼值中1的個數合理選擇η0和η1進行雙向預判免縮放因子旋轉迭代時，對m進行分奇偶數討論后，可得在單向免縮放因子型基礎上減少的總迭代次數為

對于最高位為符號位的N位流水線型CORDIC算法，其總迭代次數為

Npipel=(N-1)×2(N-1).

相比于單向免縮放因子型和流水線型CORDIC算法的總迭代次數，其降低率分別為

將m=9和N=14代入上式計算后可得，總迭代次數降低率分別為15.9%和76.8%.總迭代次數的降低減少了旋轉迭代運算過程中誤差的累積，提高了算法的輸出精度.

2 算法實現

本文提出的雙向預判免縮放因子CORDIC算法的整體結構框圖見圖2.根據結構框圖，在MATLAB工具上進行算法建模與仿真，并與單向免縮放因子型和流水線型CORDIC算法進行精度對比與分析，同時采用Verilog HDL硬件描述語言對各模塊以及整體電路進行自頂向下的RTL級設計，最后在Xilinx公司的XC7X200t-3fbg484型號FPGA上進行電路實現，比較分析3種算法的硬件資源消耗等性能參數.

3 仿真結果與分析

在相同的14位輸出位寬的情況下，使用MATLAB軟件對3種算法建模分析.輸入角度以2-13的分辨率遍歷第一象限，并且與標準正余弦函數分別相減后得到其絕對誤差，同時在絕對誤差圖中標識最大值點和最小值點，然后將取絕對值后的絕對誤差進行算術平均以獲得平均誤差，最后采用相應的函數分別計算出標準差與方差，比較分析3種算法的輸出精度.第一象限內3種算法的余弦函數絕對誤差結果如圖3所示，其精度對比見表3，并進行了精度對比分析.

圖2 新型CORDIC算法整體結構框圖

表3 3種算法余弦函數的精度對比

圖3 3種算法余弦函數的絕對誤差

通過圖3與表3可以看出，與流水線型和單向免縮放因子型相比，本文提出的CORDIC算法的平均誤差分別降低了47.5%和18.8%，絕對誤差的最大值以及取絕對值后絕對誤差的方差和標準差都具有一定的降低，提高了算法的輸出精度.主要原因在于即使流水線型CORDIC算法中的旋轉向量旋轉到了目標角度，但如果未完成13次迭代，則還需要順時針或者逆時針旋轉不同角度，直到完成13次迭代，因此輸出誤差較大.單向免縮放因子型CORDIC算法雖然避免了不必要的旋轉迭代，但是其迭代次數還是較多，運算過程中產生的累積誤差較大.而改進算法能夠根據角度二進制編碼后碼值中1的個數，在準確的初始角度的正余弦值基礎上，進行恒定順時針或逆時針免縮放因子旋轉迭代，減少了總迭代次數，降低了運算過程中誤差的累積，提高了算法的輸出精度.

在相同的時序、面積和電路環境屬性等約束條件下，使用Vivado軟件對3種算法進行綜合，對寄存器消耗量、查找表消耗量等硬件資源消耗參數，以及最大輸出時延進行對比分析，邏輯綜合結果如表4所示.同時，在表5中列出了本文提出的雙向預判免縮放因子型CORDIC算法與近年來國內外部分CORDIC算法文獻的精度對比.

表4 三種算法的邏輯綜合結果

表5 CORDIC算法的精度對比

從表4中可以看出本文提出的CORDIC算法相比于流水線型和單向免縮放因子型CORDIC算法，硬件資源消耗具有一定的下降.雖然本文的算法增設了雙向預判選擇單元，消耗了少量的寄存器和查找表，但是迭代單元級數由流水線型的13級和單向免縮放因子旋轉型的9級縮減到了5級，使硬件資源消耗有所下降.從表5中可知，與文獻[9-11]相比，CORDIC算法的平均誤差分別降低了7.8%、15.5%、57.2%，同時在絕對誤差的最大值和最大輸出延時方面也都具有較大幅度的降低.

4 結 論

針對流水線型CORDIC算法的運算精度低、輸出時延長等問題，本文結合角度二進制編碼和角度區間折疊等手段，建立了小容量正余弦值查找表，提出并實現了雙向免縮放因子CORDIC算法.提出的CORDIC算法對于某一輸入目標角度，根據角度二進制編碼后碼值中1的個數，選擇初始角度并預判迭代旋轉方向，避免了每次旋轉迭代方向的不確定性，減少了迭代單元級數和迭代次數，最短在兩個時鐘周期內即可輸出運算結果.在相同的14位位寬的情況下，對比流水線型和單向免縮放因子型CORDIC算法的運算精度，則分別提高了47.5%、18.8%，最大輸出時延分別降低了53.8%、40.0%，算法實現電路的寄存器和查找表的消耗量也有所下降，接下來還可以采用格雷碼對角度區間碼值進行編碼，降低相鄰狀態轉換時出錯的可能性.本文設計的CORDIC算法在輸出精度與輸出時延等方面具有顯著的優勢，適用于實時性強、高精度、低功耗的現代數字通信系統.