李健偉，李志強(qiáng)，朱文明，杜吉慶

0 引言

CORDIC算法［1-2］是一種用于計(jì)算一些常用的基本運(yùn)算函數(shù)和算術(shù)操作的循環(huán)迭代算法，可計(jì)算的函數(shù)包括乘、除、平方根、正弦、余弦、反正切、向量旋轉(zhuǎn)、坐標(biāo)變換、指數(shù)運(yùn)算以及 FFF、DHT、DFT、DCT、DST等技術(shù)函數(shù)，其基本思想是用一系列只與運(yùn)算基數(shù)相關(guān)的角度的不斷偏擺從而逼近所需旋轉(zhuǎn)的角度，它不需要硬件乘法器，所有運(yùn)算通過(guò)移位相加和循環(huán)迭代完成，節(jié)約了硬件資源，并可使用流水線方法，提高了計(jì)算速度，這樣同時(shí)兼顧了精度、速度和資源消耗，是一種很高效的實(shí)現(xiàn)方法。

由于CORDIC算法本身具有眾多的優(yōu)點(diǎn)，目前，已經(jīng)廣泛應(yīng)用于數(shù)字通信領(lǐng)域［3-7］。本文針對(duì)傳統(tǒng)CORDIC算法在數(shù)字通信中應(yīng)用存在無(wú)法覆蓋完整周期和迭代次數(shù)多、收斂速度慢的不足，從計(jì)數(shù)角度覆蓋范圍和計(jì)算復(fù)雜度上對(duì)傳統(tǒng)CORDIC算法進(jìn)行了優(yōu)化，相比傳統(tǒng)CORDIC，其性能得到顯著改善。

1 CORDIC算法原理

設(shè)向量為 ( x1，y1)，旋轉(zhuǎn)角 θ1后得到新的向量為 ( x2，y2)，向量轉(zhuǎn)換過(guò)程如圖1所示，根據(jù)坐標(biāo)變換規(guī)則，兩者有如下關(guān)系:

圖1 向量轉(zhuǎn)換示意

將旋轉(zhuǎn)角θ分解為N個(gè)遞減的小旋轉(zhuǎn)角θi之和，即:

式中，θi≥0，θi順時(shí)針旋轉(zhuǎn)時(shí) δi=-1，逆時(shí)針旋轉(zhuǎn)時(shí)δi=1。對(duì)每一次小旋轉(zhuǎn)有:

令 θi=arctan(2-i)，i=0，1，2，…，N-1 即 tanθi=2-i，則有:

由式(3)和式(4)可得:

于是，向量 ( x1，y1)經(jīng)過(guò)N步旋轉(zhuǎn)后得到新的向量 ( xN，yN)，可以表示為:

設(shè)

K為模校正因子，且為常量。由式(6)和式(7)則有:

這樣，向量旋轉(zhuǎn)式的計(jì)算問(wèn)題可以轉(zhuǎn)換為如下迭代運(yùn)算:

迭代運(yùn)算時(shí)，為了跟蹤已經(jīng)旋轉(zhuǎn)的角度，需引入新變量，定義為:

zi+1=zi-δiarctan(2-i)，i=0，1，2，…，N-1(10)式中，zi+1表示第 i次旋轉(zhuǎn)后剩余未旋轉(zhuǎn)角度。式(10)中arctan(2-i)需預(yù)先求出(見表1)，保存在寄存器中。CORDIC算法在每一級(jí)迭代中都需要取出事先預(yù)存好的arctan(2-i)值［7-10］。

表1 旋轉(zhuǎn)角度值計(jì)算

經(jīng)過(guò)N次旋轉(zhuǎn)后，使得yN=0，這時(shí)

由式(9)和式(10)，經(jīng)過(guò)N次旋轉(zhuǎn)后得:

則有zN=arctan(y0/x0)，即求出了向量 x0，y( )0的反正切函數(shù)值。

2 CORDIC算法的優(yōu)化

2． 1 計(jì)算角度范圍的優(yōu)化

由式(10)和式(11)，可知對(duì)于不同計(jì)算迭代次數(shù)N時(shí)，傳統(tǒng)CORDIC算法計(jì)算可覆蓋的角度為:

由式(15)可得，對(duì)于不同計(jì)算迭代次數(shù)N時(shí)，傳統(tǒng)CORDIC算法計(jì)算的最大角度(如表2所示)。當(dāng)N→∞時(shí)，可得算法計(jì)算可覆蓋的最大角度為:

表2 不同N值對(duì)應(yīng)的角度范圍

由以上分析可知，傳統(tǒng)CORDIC算法計(jì)算可覆蓋的角度為 θ∈ [ -99．88°，99．88°]，無(wú)法覆蓋完整的周期 ( -180°，180°)。

根據(jù)三角函數(shù)的對(duì)稱性，可知[0，π/4)的正弦值和余弦值，可以表示一個(gè)完整周期[0，2π)內(nèi)的所有正弦值和余弦值，這樣，可以通過(guò)對(duì)輸入的向量進(jìn)行預(yù)處理，把輸入角度限制在[0，π/4)范圍內(nèi)，輸出時(shí)再還原為對(duì)應(yīng)的角度，可以有效的擴(kuò)大CORDIC算法覆蓋的角度范圍。

最高位決定輸入向量縱坐標(biāo) yN，最高位為0時(shí)，表示yN≥0，輸入角度z0∈[0，π);最高位為1時(shí)，表示yN≤0，輸入角度z0∈ [π，2π)。

第二位決定輸入向量縱坐標(biāo) xN，最高位為0時(shí)，表示xN≥0，輸入角度z0∈ [ -π/2，π/2);最高位為1時(shí)，表示xN≤0，輸入角度 z0∈ [ π /2，3π/2)。

第三位決定輸入向量橫坐標(biāo)xN和縱坐標(biāo)yN關(guān)系，最高位為0時(shí)，表示 xN≥yN，輸入角度范圍為 z0∈ [ -π/4，π/4 )∪ [ 3π/4，5π/4);最高位為1時(shí)，表示 xN≤ yN，輸入角度范圍為 z0∈[ π /4，3π/4 )∪ [ -3π/4，-π/4);

相位累加器輸出的高三位表示把一個(gè)周期[0，2π)分成8份，相位累加器高三位對(duì)應(yīng)的角度范圍如表3所示。具體的輸入向量預(yù)處理規(guī)則如表4所示。

表3 相位累加器高三位對(duì)應(yīng)的角度范圍

表4 輸入向量預(yù)處理規(guī)則

2． 2 計(jì)算復(fù)雜度的優(yōu)化

傳統(tǒng)的CORDIC算法無(wú)論輸入向量中變量x0和y0的關(guān)系如何，一律從i=0開始向量旋轉(zhuǎn)，當(dāng)輸入向量對(duì)應(yīng)的角度較小時(shí)，則需要旋轉(zhuǎn)多次才能接近正確的值。若在向量輸入前，首先對(duì)x0和y0的關(guān)系進(jìn)行判決，一步將向量角度旋轉(zhuǎn)至合適的最小角度區(qū)間，后續(xù)的每次迭代運(yùn)算前，先對(duì)xi和yi的關(guān)系進(jìn)行判決，選擇合適的最小角度區(qū)間。這樣，優(yōu)化后的CORDIC算法的運(yùn)算迭代次數(shù)將顯著減少，具體步驟如下:

將變量x0和y0進(jìn)行歸一化到0，[]1區(qū)間，則x0可以表示為:

其中ai，bi∈0，{}1。設(shè)x0中ai=1的最小下標(biāo)imin，y0中 bi=1的最小下標(biāo) jmin，則:

式中:

謝彥君教授曾提出鄉(xiāng)村旅游可持續(xù)發(fā)展的新理念應(yīng)像呵護(hù)“姆庇之家”一樣，不應(yīng)隨意“造假”，應(yīng)打造具備自身特色和認(rèn)同感的活性鄉(xiāng)村文化體驗(yàn)[9]。竇志萍等揭示現(xiàn)今旅游消費(fèi)者的一種新型需求動(dòng)機(jī)——“鄉(xiāng)愁旅游”，尋找鄉(xiāng)愁、發(fā)現(xiàn)鄉(xiāng)愁、留住鄉(xiāng)愁、享受鄉(xiāng)愁成為現(xiàn)階段的一種旅游時(shí)尚；留住鄉(xiāng)愁與享受鄉(xiāng)愁是鄉(xiāng)村旅游的一個(gè)重要環(huán)節(jié)，即“鄉(xiāng)居”[10]。

則有:

每一次迭代運(yùn)算前，可得: x

則有:

定義角度區(qū)間 Ωi∈［arctan(2-(i-1))，arctan(2-i)］

由

將向量一步旋轉(zhuǎn)到區(qū)間Ωγi+1上，zi+1記錄旋轉(zhuǎn)的角度值，重復(fù)迭代運(yùn)算至得到要求精度的結(jié)果。

3 性能分析

當(dāng)向量每一次旋轉(zhuǎn)至Ωi+1上，若準(zhǔn)確角度為θ，則計(jì)算的角度誤差為:

當(dāng)要求計(jì)算誤差 ei+1≤2-A時(shí)，則 i≥A-1。

由式(22)可知，當(dāng)要求計(jì)算精度為2-A時(shí)，只需要將向量旋轉(zhuǎn)至區(qū)間ΩA即可。同時(shí)可知改進(jìn)算法的迭代次數(shù)最小1次，最大A次。

仿真分析，當(dāng)?shù)螖?shù)最大為A=8時(shí)，計(jì)算輸入不同向量時(shí)，傳統(tǒng)算法與改進(jìn)算法的角度誤差精度;在相同精度要求下，計(jì)算輸入不同向量時(shí)，傳統(tǒng)算法與改進(jìn)算法的迭代次數(shù)情況。

圖2為旋轉(zhuǎn)角度θ∈(0，π/4]時(shí)，傳統(tǒng)算法與改進(jìn)算法在相同的角度誤差精度下( e≤2-8)，所進(jìn)行的迭代次數(shù)對(duì)比。圖3為旋轉(zhuǎn)角度 θ∈(0 ，π/4]時(shí)，傳統(tǒng)算法與改進(jìn)算法的角度誤差情況對(duì)比。圖4為旋轉(zhuǎn)角度 θ∈(π/4，π/2]時(shí)，傳統(tǒng)算法與改進(jìn)算法在相同的角度誤差精度下( e≤2-8)，所進(jìn)行的迭代次數(shù)對(duì)比。圖5為旋轉(zhuǎn)角度θ∈(π/4，π/2]時(shí)，傳統(tǒng)算法與改進(jìn)算法的角度誤差情況對(duì)比。

圖3 θ∈0，π(]/4時(shí)角度誤差對(duì)比

圖4 θ∈π/4，π(]/2時(shí)迭代次數(shù)對(duì)比

圖5 θ∈π/4，π(]/2時(shí)角度誤差對(duì)比

由圖2、圖3、圖4、圖5可見，在相同的計(jì)算精度下，改進(jìn)算法較傳統(tǒng)算法運(yùn)算迭代次數(shù)大幅減小。表5給出了在相同的角度誤差精度時(shí)，傳統(tǒng)算法與改進(jìn)算法在不同旋轉(zhuǎn)角度范圍內(nèi)的運(yùn)算迭代次數(shù)情況。

表5 傳統(tǒng)算法與改進(jìn)算法的性能對(duì)比

4 結(jié)語(yǔ)

本文針對(duì)傳統(tǒng)CORDIC算法在數(shù)字通信中應(yīng)用存在的不足，從計(jì)算角度覆蓋范圍和計(jì)算復(fù)雜度兩個(gè)方面，對(duì)傳統(tǒng)CORDIC算法進(jìn)行了優(yōu)化。優(yōu)化后的傳統(tǒng)CORDIC算法能夠覆蓋完整的周期，且仿真結(jié)果表明:在相同的角度誤差精度下( e≤2-8)，改進(jìn)的CORDIC算法的運(yùn)算迭代次數(shù)，在輸入向量角度θ∈(0，π/4]時(shí)，比傳統(tǒng)的CORDIC算法的運(yùn)算迭代次數(shù)減少 4次，在輸入向量角度為 θ∈( π /4，π/2]時(shí)，比傳統(tǒng)的CORDIC算法的運(yùn)算迭代次數(shù)減少3次。

［1］ Volder J E．The CORDICTrigonometric Computing Technique［J］．IRE Transactions on Electronic Computers，1959，8(3):330-334．

［2］ Walther J S．A Unified Algorithm for Elementary Functions［J］．AFIPSSpring Joint Computer Conference，197l，38:379-385．

［3］ 鞠建波，別慶，杜愛(ài)國(guó)．基于改進(jìn) CORDIC算法的QDDS的FPGA實(shí)現(xiàn)及精度分析［J］．電訊技術(shù)，2007，47(01):112-116．

JU Jian-bo，BIE Qing and DU Ai-guo．FPGA Implementation and Accuracy Analysis of QDDS based on A-meliorated CORDIC Algorithm［J］．Telecommunication Engineering，2007 47(01):112-116．

［4］ 鄧強(qiáng)．利用CORDIC算法計(jì)算平方根及其 FPGA實(shí)現(xiàn)［J］．通信技術(shù)，2013，45(07):129-131．

DENG Qiang．Square-Root Solution and FPGA Implementation based on CORDICAlgorithm［J］．Communications Technology，2013(07):129-131．

［5］ Juang Tso-Bing，Tsai Ming-Yu．Para-CORDIC:Parallel CORDIC Rotation Algorithm［J］．IEEE Transactions on Circuits and Systems，2004，51(8):1515-1524．

［6］ 龔耀寰，李航，茍仲文．基于CORDIC的無(wú)開方 GIVENS旋轉(zhuǎn)處理方法［J］．電子科技大學(xué)學(xué)報(bào)，1997，26(06):565-569．

GONG Yao-huan，LI Hang and GOU Zhong-wen．No Prescription GIVENS Rotation Processing Method based CORDIC［J］．University of Electronic Science and Technology Journal，1997，26(06):565-569．

［7］ 李滔，韓月秋．基于CORDIC算法的雷達(dá)信號(hào)坐標(biāo)變換處理器［J］．現(xiàn)代雷達(dá)，1999，4(02):45-49．

LI Tao，HAN Yue-qiu．A New CORDIC-based Radar Signal Coordinate Conversion Processor［J］．Modern Radar，1999，4(2):45-49．

［8］ Uwe Meyer Baese著．Digital signal processing with field programmable gate arrays［M］．劉凌，胡永生譯．北京:清華大學(xué)出版社，2003．

Written by Uwe Meyer Baese，Digital Signal Processing with Field Programmable Gate Arrays［M］．Translated by LIU Nin，HU Yong-sheng．Beijing:Tsinghua University Press，2003．

［9］ 熊承義，高志榮，田金文．常系數(shù)乘法器的VLSI高效設(shè)計(jì)［J］．軍民兩用技術(shù)與產(chǎn)品，2003(09):37-42．

XIONG Cheng-yi，GAO Zhi-rong and TIAN Jinwen．High Efficient VLSI Implementation for Fixed-Coefficient Multipliers［J］．Top Technology ＆ Products，2003(09):37-42．

［10］ 龔耀寰．自適應(yīng)濾波．［M］．第2版．北京:電子工業(yè)出版社，2003:251-253．

GONG Yao-huan．Adaptive Filter．Second Edition［M］．Beijing:Electronic Industry Press，2003，7:251-253．