雙向預(yù)判免縮放因子CORDIC算法

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

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

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

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

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

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

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

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

(1)

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

(2)

當(dāng)式(2)中bk的值為1時(shí)，則需要進(jìn)行逆時(shí)針旋轉(zhuǎn)2-k弧度；當(dāng)bk為0時(shí)，則不需要進(jìn)行任何角度的旋轉(zhuǎn)[12].經(jīng)過角度編碼后的旋轉(zhuǎn)向量無需根據(jù)上次的迭代結(jié)果判斷下次的旋轉(zhuǎn)方向，避免了迭代方向的不確定性.若式(1)中k增大時(shí)，則tan(2-k)-2-k的絕對(duì)值越來越小，且當(dāng)k≥n/3時(shí)，有|tan(2-k)-2-k|<2-n，因此tan(2-k)與2-k之間的誤差小于n位二進(jìn)制小數(shù)能夠表示的精度，計(jì)算誤差可以忽略不計(jì).則可用2-k近似表示tan(2-k)，只需要通過移位和加減運(yùn)算即可實(shí)現(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)的角度值即可.此時(shí)n值為13，帶入公式(2)可知，當(dāng)k<13/3時(shí)，不可用2-k近似表示tan(2-k)，否則將會(huì)引入較大的計(jì)算誤差，因此建立小容量正余弦值查找表(見表1)，用以保證輸出精度，且所消耗的寄存器也較少.

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

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

1.3 角度區(qū)間折疊

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

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

在本文的雙向預(yù)判免縮放因子型CORDIC算法的實(shí)現(xiàn)過程中，首先計(jì)算[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時(shí)，則無需翻轉(zhuǎn)取反；但當(dāng)?shù)?位為1時(shí)，則進(jìn)行翻轉(zhuǎn)取反輸出；若最高位的值為0，則正弦值輸出為正值，否則為負(fù)值；當(dāng)最高位與次高位不同時(shí)，則余弦值輸出為負(fù)值，反之為正值.采用角度區(qū)間折疊技術(shù)，保證了運(yùn)算范圍，同時(shí)減少了查找表所需要存儲(chǔ)的正余弦值的個(gè)數(shù).

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

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

(3)

(4)

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

(5)

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

(6)

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

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

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

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

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

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

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

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

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

2 算法實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

表5 CORDIC算法的精度對(duì)比

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

4 結(jié) 論

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