高精度雙向同步旋轉CORDIC算法設計與實現

鄭傳喜古元冬

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

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

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

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

1 高精度雙向同步旋轉算法

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

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

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

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

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

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

1.2 查找表建立

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

圖1 雙向同步旋轉示意圖Fig.1 Bidirectional rotation diagram

設逆時針方向角度前5位00000～11001的角度為α0～α25,同理順時針方向角度為β0～β25,則存在以下關系:

對于13位二進制數表示的小數,存在cos 2?13≈1,sin 2?13≈2?13,因此經過化簡,最終可得

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

表2 逆時針旋轉表Table 2 Counterclockwise rotation table

1.3 雙向同步旋轉原理和誤差均衡

雙向同步旋轉可以看作對目標角度進行逐位雙向逼近的過程,在[0,π/4]內,n位二進制小數的角度θ可表示為2?1,2?2,2?3,···,2?(n?1),2?n的線性組合,即,其中ai={0,1},對應角度二進制小數位.根據余弦函數的性質

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

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

圖2為逆向旋轉硬件結構圖,其中Shifter表示移位器,ADD/SUB表示加法器/減法器,當為1時,從左向右分別為減法器和加法器.

圖2 逆時鐘旋轉硬件結構圖Fig.2 Counterclockwise rotation hardware structure diagram

順時針旋轉的過程是對角度二進制數小數位的逐項相減的過程,整個迭代過程以及硬件結構都與逆時針時相似.順時針迭代式為

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

在整個迭代過程中同時進行順時針旋轉和逆時針旋轉,然后對輸出結果進行誤差均衡處理,則最終結果可表示為

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

1.4 雙步旋轉策略

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

雙步迭代矩陣可以表示為

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

當i≥(L?1)/2時,上述參數又可簡化為α=ε=1,γ=?β=ai2?i+aj2?i?1,其中L為數據位寬.

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

2 硬件設計

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

圖3 硬件結構框圖Fig.3 Block diagram of hardware structure

3 仿真及實驗結果

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

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

從圖4可以看出,順向算法在經歷了一次查表旋轉后,其誤差將會逐漸降低,而逆向旋轉則剛好相反,正因為該特性,改進算法可以通過誤差均衡在單向算法的基礎上進一步提高精度.表3為余弦函數仿真誤差的對比.由表3可知:相比傳統(tǒng)算法和單向旋轉算法,改進算法的絕對誤差最大值分別降低了73.3%、60%,平均誤差分別降低了47.0%、45.3%,標準差分別降低了60.2%、55.5%.

表3 余弦函數仿真誤差對比Table 3 Cosine function simulation error comparison ×10?5

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

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

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

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

通過Vivado軟件對3種算法進行邏輯綜合,得到寄存器消耗個數、查找表消耗個數、最大輸出時延以及最高運行頻率,結果如表5所示.表6列出了近年來國內外部分文獻中CORDIC算法與本改進算法的精度對比.

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

表6 CORDIC算法精度的對比Table 6 Comparison of CORDIC algorithm accuracy

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

4 結語

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