高精度雙向同步旋轉(zhuǎn)CORDIC算法設(shè)計(jì)與實(shí)現(xiàn)

鄭傳喜古元冬

(1.上海大學(xué)微電子學(xué)院,上海 201800;2.上海微技術(shù)工業(yè)研究院,上海 201800)

坐標(biāo)旋轉(zhuǎn)數(shù)字計(jì)算機(jī)(coordinate rotation digital computer,CORDTC)算法是硬件系統(tǒng)中非常重要的一種算法,主要用于三角函數(shù)、雙曲線函數(shù)、指數(shù)函數(shù)以及對(duì)數(shù)函數(shù)的運(yùn)算[1].在精密電機(jī)數(shù)控系統(tǒng)中存在大量的三角函數(shù)運(yùn)算,由于CORDIC算法具有較強(qiáng)的可移植性、實(shí)現(xiàn)簡(jiǎn)單以及精度可控等特點(diǎn)[2-4],被廣泛應(yīng)用于電機(jī)控制領(lǐng)域.

目前電機(jī)控制領(lǐng)域中CORDIC算法的設(shè)計(jì)通常為16位輸出精度的正余弦值輸出,平均誤差為10?5～10?4,但隨著精密電機(jī)控制領(lǐng)域中對(duì)Park變換精度要求越來(lái)越高,需要在16位位寬下得到更高精度的輸出.傳統(tǒng)CORDIC算法的改進(jìn)主要集中在縮放因子、角度收斂以及迭代方式等方面.Kulshreshtha等[5]通過(guò)滑動(dòng)離散傅里葉變換(discrete Fourier transform,DFT)與Hann窗相結(jié)合,對(duì)縮放因子進(jìn)行補(bǔ)償,提高了輸出精度,但硬件實(shí)現(xiàn)結(jié)構(gòu)較為復(fù)雜.Shukla等[6]提出了一種混合型算法,將雙步分支CORDIC算法和radix-4 CORDIC算法相結(jié)合,而Garrido等[7]舍棄了傳統(tǒng)CORDIC算法中使用的角度,引入了友角(friend angles),二者都提高了旋轉(zhuǎn)角度的收斂速度,但是輸出精度較低,需要通過(guò)增加額外的迭代次數(shù)來(lái)保證精度.徐成等[8]通過(guò)多步合并迭代降低了輸出時(shí)延,但精度并無(wú)明顯提升,姚亞峰等[9-10]通過(guò)大量查找表來(lái)降低輸出時(shí)延,但存在硬件資源消耗大等問(wèn)題,之后將旋轉(zhuǎn)過(guò)程分為粗旋轉(zhuǎn)以及細(xì)旋轉(zhuǎn),避免了縮放因子的引入,節(jié)省了資源消耗,但精度提升仍有限,

針對(duì)上述問(wèn)題,本研究對(duì)CORDIC算法存在的精度以及延時(shí)問(wèn)題進(jìn)行改進(jìn),設(shè)計(jì)了高精度雙向同步旋轉(zhuǎn)CORDIC算法.該算法先對(duì)角度進(jìn)行預(yù)處理,再根據(jù)查找表對(duì)輸入角度進(jìn)行雙向同步旋轉(zhuǎn),同時(shí),在迭代過(guò)程采用雙步旋轉(zhuǎn),以此減少輸出延遲和部分硬件資源消耗,最后通過(guò)誤差均衡和還原輸出,提高整個(gè)算法的穩(wěn)定性.仿真結(jié)果表明,本改進(jìn)算法具有低延遲、高精度以及穩(wěn)定等特點(diǎn),更適合對(duì)實(shí)時(shí)控制和精度有更高要求的精密電機(jī)控制系統(tǒng).

1 高精度雙向同步旋轉(zhuǎn)算法

CORDIC算法的基本原理是將目標(biāo)角度分解為若干角度,然后通過(guò)一系列的旋轉(zhuǎn)來(lái)接近目標(biāo)角度.引入,并對(duì)θi進(jìn)行一定的限制,令θi=arctan2?i,其中di={1,?1},di=1表示向量是逆時(shí)針旋轉(zhuǎn),di=?1表示向量是順時(shí)針旋轉(zhuǎn)[11].其迭代過(guò)程如下:

由式(1)可知,CORDIC算法只需通過(guò)簡(jiǎn)單移位和加法運(yùn)算便可實(shí)現(xiàn),而傳統(tǒng)算法存在輸出時(shí)延高、硬件資源消耗大以及運(yùn)算精度低等問(wèn)題.針對(duì)上述問(wèn)題,本工作提出高精度雙向同步旋轉(zhuǎn)算法,該算法首先對(duì)16位的輸入角度進(jìn)行重編碼和區(qū)間判斷,然后計(jì)算迭代目標(biāo)角度,并將其送入迭代器中進(jìn)行雙向同步旋轉(zhuǎn)和誤差均衡,最后根據(jù)區(qū)間編碼值對(duì)正弦和余弦進(jìn)行還原處理.

1.1 角度預(yù)處理與區(qū)間折疊

本改進(jìn)算法采用13位小數(shù)位、2位整數(shù)位、1位符號(hào)位共16位二進(jìn)制補(bǔ)碼表示輸入角度.對(duì)于傳統(tǒng)CORDIC算法,由于0≤sinθ≤1,0≤cosθ≤1,且{max(θ),min(θ)}≈{99.9?,?99.9?},因此無(wú)法覆蓋整個(gè)圓周.根據(jù)三角函數(shù)的周期性以及對(duì)稱性,可以只計(jì)算[0,π/4]的值便可覆蓋整個(gè)圓周[12].因?yàn)棣?4<1,且在θ∈[0,π/4]時(shí),0≤sinθ≤1,0≤cosθ≤1,因此迭代目標(biāo)角度可以采用13位無(wú)符號(hào)數(shù)表示,即,而最終輸出值則使用16位有符號(hào)數(shù)表示,這樣可以適當(dāng)減少寄存器的消耗.表1表示了從[0,π/4]映射到[0,2π]的過(guò)程,其中前3列表示了角度預(yù)處理的過(guò)程,后2列表示對(duì)結(jié)果的還原處理.

表1 角度預(yù)處理與區(qū)間折疊Table 1 Angle preprocessing and interval folding

對(duì)于區(qū)間編碼值和迭代輸出結(jié)果的關(guān)系,首先判斷區(qū)間編碼值(從右往左)的第1位和第2位,如果不同,則表示迭代計(jì)算完成后得到的正弦值和余弦值需要進(jìn)行交換,否則不需要交換;然后判斷第2位和第3位,如果不同,則余弦值取反,否則不取反;最后判斷第三位,如果為1,則對(duì)正弦值取反,否則不取反[13].通過(guò)采用區(qū)間折疊,可以大大減少查找表的大小,保證輸入角度能夠覆蓋整個(gè)圓周,增強(qiáng)了算法適用性.

1.2 查找表建立

通過(guò)角度預(yù)處理,可以將整個(gè)迭代區(qū)間壓縮至[0,π/4],用13位二進(jìn)制補(bǔ)碼表示輸入角度0X0000到0X1922.取區(qū)間前5位從00000到11001的角度,令后8位取0構(gòu)成逆時(shí)針旋轉(zhuǎn)表,令后8位取1構(gòu)成順時(shí)針旋轉(zhuǎn)表,其旋轉(zhuǎn)過(guò)程如圖1所示.將弧度[0,0.781 25]分成了25小區(qū)間,每一個(gè)小區(qū)間寬度僅有1/32弧度,查找表中分別存儲(chǔ)節(jié)點(diǎn)值對(duì)應(yīng)的正余弦值,以此進(jìn)行查表旋轉(zhuǎn).為減少查找表的消耗,對(duì)順時(shí)針旋轉(zhuǎn)時(shí)的正余弦值進(jìn)行分析.

圖1 雙向同步旋轉(zhuǎn)示意圖Fig.1 Bidirectional rotation diagram

設(shè)逆時(shí)針?lè)较蚪嵌惹?位00000～11001的角度為α0～α25,同理順時(shí)針?lè)较蚪嵌葹棣?～β25,則存在以下關(guān)系:

對(duì)于13位二進(jìn)制數(shù)表示的小數(shù),存在cos 2?13≈1,sin 2?13≈2?13,因此經(jīng)過(guò)化簡(jiǎn),最終可得

由式(3)可知,對(duì)于順時(shí)針旋轉(zhuǎn)表,只需在逆時(shí)針旋轉(zhuǎn)表中增加前5位為11010的角度的正余弦值便可得到,不需額外重新制表.表2為逆時(shí)針旋轉(zhuǎn)表.

表2 逆時(shí)針旋轉(zhuǎn)表Table 2 Counterclockwise rotation table

1.3 雙向同步旋轉(zhuǎn)原理和誤差均衡

雙向同步旋轉(zhuǎn)可以看作對(duì)目標(biāo)角度進(jìn)行逐位雙向逼近的過(guò)程,在[0,π/4]內(nèi),n位二進(jìn)制小數(shù)的角度θ可表示為2?1,2?2,2?3,···,2?(n?1),2?n的線性組合,即,其中ai={0,1},對(duì)應(yīng)角度二進(jìn)制小數(shù)位.根據(jù)余弦函數(shù)的性質(zhì)

可知,第k+1次迭代可表示為

令θ=2?i,由正弦泰勒展開(kāi)式可知,n位二進(jìn)制數(shù)能表示的精度是有限的.考慮正弦函數(shù)的三次項(xiàng),當(dāng)i滿足(i為整數(shù)),n=16時(shí),解得i≥5,表示由輸入角度小數(shù)位后8位計(jì)算的正弦值其精度已經(jīng)不能正確表示到三次項(xiàng)[14].角度值的前5位的旋轉(zhuǎn)可用查表法實(shí)現(xiàn),因此可以忽略對(duì)縮放因子的計(jì)算.令第k+1次逆向旋轉(zhuǎn)的余弦值和正弦值分別為,旋轉(zhuǎn)微角度為,對(duì)式(5)進(jìn)行化簡(jiǎn),得到如下逆時(shí)針迭代式:

圖2為逆向旋轉(zhuǎn)硬件結(jié)構(gòu)圖,其中Shifter表示移位器,ADD/SUB表示加法器/減法器,當(dāng)為1時(shí),從左向右分別為減法器和加法器.

圖2 逆時(shí)鐘旋轉(zhuǎn)硬件結(jié)構(gòu)圖Fig.2 Counterclockwise rotation hardware structure diagram

順時(shí)針旋轉(zhuǎn)的過(guò)程是對(duì)角度二進(jìn)制數(shù)小數(shù)位的逐項(xiàng)相減的過(guò)程,整個(gè)迭代過(guò)程以及硬件結(jié)構(gòu)都與逆時(shí)針時(shí)相似.順時(shí)針迭代式為

由式(6)、(7)和表2可知,逆向旋轉(zhuǎn)隨著角度增大,每進(jìn)行一次查表,其誤差都會(huì)達(dá)到更小.在兩次查表之間,每當(dāng)=1時(shí),余弦函數(shù)將會(huì)與·1進(jìn)行一次等效,其結(jié)果將大于真實(shí)值,因此,其誤差也會(huì)逐漸增大,而順向旋轉(zhuǎn)則相反.

在整個(gè)迭代過(guò)程中同時(shí)進(jìn)行順時(shí)針旋轉(zhuǎn)和逆時(shí)針旋轉(zhuǎn),然后對(duì)輸出結(jié)果進(jìn)行誤差均衡處理,則最終結(jié)果可表示為

雙向同步旋轉(zhuǎn)可以忽略對(duì)縮放因子的計(jì)算,引入逐位雙向逼近的概念,當(dāng)旋轉(zhuǎn)方向確定后,每次旋轉(zhuǎn)的角度和角度二進(jìn)制數(shù)每一位都相互對(duì)應(yīng),避免了傳統(tǒng)CORDIC算法在已經(jīng)旋轉(zhuǎn)到正確角度時(shí),由于每次旋轉(zhuǎn)角度已經(jīng)固定,依然會(huì)繼續(xù)旋轉(zhuǎn)而引入的誤差.傳統(tǒng)算法的精度和迭代次數(shù)正相關(guān),誤差主要取決于3點(diǎn):①將θ和tanθ進(jìn)行等效而帶來(lái)的誤差;②查找表帶來(lái)的截?cái)嗾`差;③旋轉(zhuǎn)因子引入的誤差[15].因此為了保證相應(yīng)的精度,傳統(tǒng)算法需要較多的迭代單元和迭代次數(shù),但本工作提出的改進(jìn)算法首先通過(guò)查表旋轉(zhuǎn)來(lái)避免旋轉(zhuǎn)因子的誤差,其次沒(méi)有將θ和tanθ進(jìn)行等效,而是利用泰勒展開(kāi)式直接對(duì)正余弦進(jìn)行等效,進(jìn)一步減少誤差.同時(shí),在旋轉(zhuǎn)迭代過(guò)程完成后,本改進(jìn)算法會(huì)對(duì)結(jié)果進(jìn)行誤差均衡處理,降低了誤差曲線抖動(dòng),提高了整個(gè)算法的精度和穩(wěn)定性.

1.4 雙步旋轉(zhuǎn)策略

雙步旋轉(zhuǎn)的基本原理基于輸入角度在迭代前便可以知道旋轉(zhuǎn)方向以及旋轉(zhuǎn)角度的大小,因此可以將兩次旋轉(zhuǎn)進(jìn)行合并,通過(guò)這種方式來(lái)達(dá)到減少迭代次數(shù)的目的,從而可以適當(dāng)減少資源消耗并降低輸出時(shí)延[8].對(duì)于逆時(shí)針旋轉(zhuǎn),假設(shè)兩次旋轉(zhuǎn)的角度分別為θi=ai2?i和θj=aj2?j(i

雙步迭代矩陣可以表示為

在本改進(jìn)算法中,令j=i+1,結(jié)合式(6),對(duì)式(9)進(jìn)行化簡(jiǎn),可得

當(dāng)i≥(L?1)/2時(shí),上述參數(shù)又可簡(jiǎn)化為α=ε=1,γ=?β=ai2?i+aj2?i?1,其中L為數(shù)據(jù)位寬.

通過(guò)上述推導(dǎo),可以將兩步迭代簡(jiǎn)化為一次,且只需通過(guò)加法和移位操作便可完成.在i≥(L?1)/2的情況下,算法的結(jié)構(gòu)可還以進(jìn)一步簡(jiǎn)化,因此相比單向旋轉(zhuǎn)算法,本算法可以極大的減少迭代次數(shù),進(jìn)而降低輸出時(shí)延.

2 硬件設(shè)計(jì)

本改進(jìn)算法的硬件實(shí)現(xiàn)主要包括預(yù)處理、雙向同步旋轉(zhuǎn)、結(jié)果輸出共3個(gè)模塊.預(yù)處理模塊主要完成對(duì)角度二進(jìn)制編碼,并對(duì)輸入角度進(jìn)行區(qū)間判定以及將輸入角度映射至[0,π/4].雙向同步旋轉(zhuǎn)模塊主要完成對(duì)角度進(jìn)行雙向迭代和誤差均衡,旋轉(zhuǎn)過(guò)程采用4級(jí)流水線設(shè)計(jì),最終產(chǎn)生經(jīng)過(guò)角度折疊后的正余弦值.結(jié)果輸出模塊主要根據(jù)區(qū)間對(duì)正余弦值進(jìn)行還原輸出.采用Verilog HDL語(yǔ)言進(jìn)行硬件設(shè)計(jì),圖3為算法的硬件結(jié)構(gòu)框圖.

圖3 硬件結(jié)構(gòu)框圖Fig.3 Block diagram of hardware structure

3 仿真及實(shí)驗(yàn)結(jié)果

首先結(jié)合表2和式(6)～(8),利用Matlab對(duì)改進(jìn)算法進(jìn)行建模仿真,并與傳統(tǒng)算法、單向旋轉(zhuǎn)算法進(jìn)行對(duì)比,結(jié)果如圖4所示.

圖4 第一象限余弦誤差算法仿真圖Fig.4 Algorithm simulation diagram of the first quadrant cosine error

從圖4可以看出,順向算法在經(jīng)歷了一次查表旋轉(zhuǎn)后,其誤差將會(huì)逐漸降低,而逆向旋轉(zhuǎn)則剛好相反,正因?yàn)樵撎匦?改進(jìn)算法可以通過(guò)誤差均衡在單向算法的基礎(chǔ)上進(jìn)一步提高精度.表3為余弦函數(shù)仿真誤差的對(duì)比.由表3可知:相比傳統(tǒng)算法和單向旋轉(zhuǎn)算法,改進(jìn)算法的絕對(duì)誤差最大值分別降低了73.3%、60%,平均誤差分別降低了47.0%、45.3%,標(biāo)準(zhǔn)差分別降低了60.2%、55.5%.

表3 余弦函數(shù)仿真誤差對(duì)比Table 3 Cosine function simulation error comparison ×10?5

為了驗(yàn)證改進(jìn)算法的實(shí)際性能,在Xilinx公司XC7K160T-1FBG676C型號(hào)的FPGA上對(duì)算法進(jìn)行實(shí)現(xiàn),并與傳統(tǒng)CORDIC算法、單向旋轉(zhuǎn)算法進(jìn)行對(duì)比分析.在16位的位寬條件下,對(duì)輸入角度以2?13的分辨率在第一象限進(jìn)行遍歷.圖5為3種算法的誤差分析結(jié)果,余弦函數(shù)誤差對(duì)比結(jié)果見(jiàn)表4.

由圖5和表4可以看出,相比傳統(tǒng)算法和單向旋轉(zhuǎn)算法,實(shí)際應(yīng)用場(chǎng)合下改進(jìn)算法的絕對(duì)誤差分別降低了73.6%和54.3%,平均誤差分別降低了76.3%和67.5%,標(biāo)準(zhǔn)差分別降低了73.5%和65.5%.主要原因是:改進(jìn)算法吸收了單向旋轉(zhuǎn)算法的優(yōu)點(diǎn),即當(dāng)di為0時(shí),可以避免不必要的旋轉(zhuǎn),減少誤差累積;利用順時(shí)針和逆時(shí)針旋轉(zhuǎn)的誤差特性進(jìn)行誤差均衡,彌補(bǔ)了單向旋轉(zhuǎn)算法因區(qū)間折疊而在[π/4,π/2]區(qū)間上導(dǎo)致絕對(duì)誤差的斷層,進(jìn)一步降低了平均誤差和標(biāo)準(zhǔn)差.

圖5 第一象限余弦絕對(duì)誤差分析Fig.5 Cosine absolute error analysis in the first quadrant

表4 3種算法的余弦函數(shù)誤差Table 4 Comparison of three cosine error algorithms 10?5

通過(guò)Vivado軟件對(duì)3種算法進(jìn)行邏輯綜合,得到寄存器消耗個(gè)數(shù)、查找表消耗個(gè)數(shù)、最大輸出時(shí)延以及最高運(yùn)行頻率,結(jié)果如表5所示.表6列出了近年來(lái)國(guó)內(nèi)外部分文獻(xiàn)中CORDIC算法與本改進(jìn)算法的精度對(duì)比.

表5 3種算法的邏輯綜合結(jié)果Table 5 Logical synthesis result of three algorithms

表6 CORDIC算法精度的對(duì)比Table 6 Comparison of CORDIC algorithm accuracy

由表5可以看出,改進(jìn)算法相對(duì)傳統(tǒng)算法,寄存器消耗個(gè)數(shù)下降了41.0%,查找表消耗個(gè)數(shù)下降了36.9%,最大輸出時(shí)延降低了71.4%.相對(duì)單向旋轉(zhuǎn)算法,由于改進(jìn)算法同時(shí)進(jìn)行了正向旋轉(zhuǎn)和逆向旋轉(zhuǎn),因此最高運(yùn)行頻率相比單向旋轉(zhuǎn)算法并無(wú)改善,但雙步迭代使得迭代單元由單向免旋轉(zhuǎn)算法的9級(jí)降低到了4級(jí),最大輸出時(shí)延降低了55.5%,而寄存器消耗量和查找表消耗量?jī)H增加了19.9%、23.6%.與文獻(xiàn)[5,8,10,13-14]提出的算法相比,本改進(jìn)算法的平均誤差降低是非常顯著的,同時(shí)絕對(duì)誤差最大值也有大幅度的下降(見(jiàn)表6).

4 結(jié)語(yǔ)

本研究主要針對(duì)精密電機(jī)數(shù)控領(lǐng)域中16位位寬CORDIC算法精度不足、時(shí)延較長(zhǎng)以及硬件資源消耗較大等局限做出改進(jìn),改進(jìn)算法首先通過(guò)區(qū)間折疊來(lái)擴(kuò)大角度計(jì)算范圍,然后通過(guò)查找表進(jìn)行一次查表旋轉(zhuǎn),再通過(guò)雙向同步旋轉(zhuǎn)和誤差均衡進(jìn)行迭代計(jì)算并以此降低誤差,旋轉(zhuǎn)過(guò)程中用雙步迭代降低迭代單元級(jí)數(shù),降低了輸出時(shí)延,最后根據(jù)角度區(qū)間進(jìn)行還原輸出.在硬件實(shí)現(xiàn)上,相比傳統(tǒng)算法和單向旋轉(zhuǎn)算法,運(yùn)算精度分別提高了76.3%和67.5%,最大輸出時(shí)延降低了71.4%和55.5%.在硬件資源消耗方面,改進(jìn)算法對(duì)比傳統(tǒng)算法在寄存器消耗和查找表消耗方面分別下降了41.0%和36.9%,而相對(duì)于單向旋轉(zhuǎn)算法,寄存器消耗和查找表消耗分別增加了19.9%和23.6%.本工作設(shè)計(jì)的改進(jìn)算法具有高精度低延時(shí)等特點(diǎn),因此更適合對(duì)精度和時(shí)延具有更高要求的電機(jī)數(shù)控系統(tǒng).