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

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

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

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

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

1 雙向預(yù)判免縮放因子旋轉(zhuǎn)

1.1 角度二進(jìn)制編碼

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

(1)

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

(2)

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

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

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

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

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

1.3 角度區(qū)間折疊

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

表2 角度區(qū)間轉(zhuǎn)化

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

1.4 雙向免縮放因子旋轉(zhuǎn)

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

(3)

(4)

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

(5)

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

(6)

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

圖1 雙向旋轉(zhuǎn)示意

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

則由η0和η1旋轉(zhuǎn)到目標(biāo)角度的迭代次數(shù)分別為

λ0=b5+b6+…+b13,

(7)

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

(8)

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

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

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

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

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

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

2 算法實現(xiàn)

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

3 仿真結(jié)果與分析

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

圖2 新型CORDIC算法整體結(jié)構(gòu)框圖

表3 3種算法余弦函數(shù)的精度對比

圖3 3種算法余弦函數(shù)的絕對誤差

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

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

表4 三種算法的邏輯綜合結(jié)果

表5 CORDIC算法的精度對比

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

4 結(jié) 論

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