姚亞峰， 鄒凌志， 王 巍， 鐘 梁

(中國地質(zhì)大學(武漢) 機械與電子信息學院， 武漢430074)

低消耗免查找表CORDIC算法

姚亞峰， 鄒凌志， 王 巍， 鐘 梁

(中國地質(zhì)大學(武漢) 機械與電子信息學院， 武漢430074)

為減少傳統(tǒng)流水線型CORDIC(Coordinate Rotation Digital Computer)算法的硬件資源消耗和輸出時延，在包含查找表的三階段CORDIC算法實現(xiàn)基礎上，提出一種免去查找表環(huán)節(jié)的CORDIC算法實現(xiàn)方法. 提出的改進算法直接使用四次移位相加的迭代運算替換查找表結構從而顯著降低寄存器消耗，同時通過合并迭代降低迭代次數(shù)進而有效減少最大輸出時延，并綜合運用角度二極化重編碼(Binary To Bipolar Recoding, BBR)方法和角度區(qū)間折疊技術保證了輸出精度. 使用Verilog HDL語言在ISE14.2軟件平臺上對三種算法進行具體實現(xiàn)，利用XST工具對其進行綜合，并通過MATLAB建模計算得到算法的正余弦值輸出誤差. 仿真實驗結果表明：在輸出位寬均設置為16位的情況下，免查找表CORDIC算法能夠有效地輸出正余弦值；與傳統(tǒng)流水線型算法相比，免查找表算法的寄存器資源消耗減少大約74.42%，計算所需的時鐘周期降低68.75%，其輸出精度也有明顯改善；與三階段算法相比，免查找表算法的寄存器消耗減少大約43.3%. 本文提出的免查找表CORDIC算法具有實時性強、輸出精度高、硬件資源消耗少等優(yōu)勢，更適用于高速實時的現(xiàn)代數(shù)字通信系統(tǒng)應用.

坐標旋轉數(shù)字計算機；免查找表；二極化重編碼；可編程邏輯門陣列；數(shù)字信號處理

隨著現(xiàn)代數(shù)字通信系統(tǒng)集成化程度和精度的不斷提高，許多學者對CORDIC算法提出改進方案. 文獻[8]提出一種貪婪搜索算法，采用跳過若干旋轉角度和重復某些旋轉角度的方法進行迭代，迭代次數(shù)有一定減少，但硬件復雜度明顯增加. 文獻[9]采用一種混合結構，將旋轉角度分為兩部分處理，與傳統(tǒng)流水線型CORDIC算法相比提高運算速度，但仍存在硬件消耗大、輸出精度低的問題. 文獻[10]中的免縮放因子雙步旋轉算法免去縮放因子，減少迭代次數(shù)，但雙步旋轉的硬件實現(xiàn)結構較為復雜. 文獻[11]提出免縮放自適應CORDIC算法，雖然硬件資源消耗和誤差有所減少，但是計算所需的時鐘周期太長. 文獻[12-13]提出一種三階段CORDIC算法，第一階段通過查找表得到若干次迭代后的值，第二階段采用移位相加的蝶形迭代運算，第三階段進行合并迭代，相比于傳統(tǒng)的流水線型CORDIC算法在精度和硬件消耗上都有一定改善，計算所需的周期少，具有一定代表性和優(yōu)越性.

本文在文獻[12-13]的基礎上結合角度二極化重編碼(Binary To Bipolar Recoding , BBR)、角度區(qū)間折疊、合并迭代等手段提出一種免查找表CORDIC算法，將三階段縮減為兩階段實現(xiàn). 在典型的三階段CORDIC實現(xiàn)方法基礎上，將第一階段的查找表直接替換為有限的幾步移位相加迭代運算，有效減少寄存器消耗. 此外，將第二階段和第三階段合并為一步迭代，大幅減少輸出時延. 用幾步迭代運算代替查找表，使輸出延時有所增加，但第二階段的合并迭代只需要一個時鐘周期，同時省去原有的蝶形運算階段，整體只需要5個時鐘周期就能得到輸出結果，整體延時還有所降低. 同時在綜合采用角度二極化重編碼和角度區(qū)間折疊技術后，改進算法的精度相比于傳統(tǒng)實現(xiàn)方法也有一定改善.

1 CORDIC算法基本原理

CORDIC算法通過一系列旋轉角不斷逼近輸入角度，由移位相加迭代得到輸入角度的正余弦值. 圖1為向量旋轉圖，在平面直角坐標系中將初始向量OA=(x1,y1)逆時針旋轉角度θ到向量OB=(x2,y2)，則坐標之間的關系為

圖1 向量旋轉示意

(1)

(2)

2 免查找表CORDIC算法

2.1角度二極化重編碼

2.2免查找表與合并迭代原理

根據(jù)CORDIC算法的基本原理，可通過式(3)迭代得到輸入角度的正余弦值

(3)

式中k代表迭代次數(shù).

在三階段CORDIC算法中，對于輸出N位的CORDIC算法，當k

(4)

那么式(3)中乘以正切項就可視為移位相加運算，其中k=3對應的結構見圖2.

(a)移位相加結構示意1

(b)移位相加結構示意2

圖2中(a)和(b)分別代表式(3)中的兩個子式. 通過這種近似方法，將查找表替換為移位相加的蝶形運算結構，從而減少寄存器消耗.

2.3區(qū)間角度折疊及映射關系

對于(π/8,π/4]內(nèi)的角度，存在式(5)所示的三角函數(shù)關系式

(5)

通過上式(5)可將(π/8,π/4]內(nèi)的角度折疊到[0,π/8]內(nèi)，有

(6)

從式(6)看出，只要得到[0,π/8]內(nèi)角度的正余弦值，進行一次加減法運算和2/2縮放就可得到(π/8,π/4]內(nèi)的正余弦值. 通過類似的三角函數(shù)關系式，可將角度擴展到[0,2π]范圍內(nèi). 表1是具體的角度映射和正余弦轉換關系，其中θ′是輸入角度經(jīng)過區(qū)間角度折疊預處理后所得到的角度.

將角度折疊到[0,π/8]可以省掉三階段算法中第二階段的蝶形運算過程，只需要進行第一階段的移位相加迭代和第三階段的合并迭代，隨后根據(jù)角度映射和轉換關系即可還原輸出正余弦值.

表1 角度映射和正余弦轉換關系

3 算法實現(xiàn)

(7)

圖3 程序整體結構

4 仿真結果及分析

用Verilog HDL語言對傳統(tǒng)流水線型CORDIC算法，三階段CORDIC算法和免查找表CORDIC算法進行具體實現(xiàn)，在相同輸出位寬的前提下，選用Xilinx公司的xc7k325t-2ffg900型號FPGA，利用ISE14.2自帶的XST工具進行電路綜合，得到寄存器和LUTs消耗情況以及最大輸出時延見表2.

表2三種算法的寄存器和LUTs消耗、最大輸出時延

Tab.2 Register and LUTs consumption, maximum output delay for three algorithms

算法類型輸出數(shù)據(jù)位寬N=16消耗的寄存器個數(shù)消耗的LUTs個數(shù)最大輸出時延流水線型CORDIC算法77883616三階段CORDIC算法3516796免查找表CORDIC算法1996965

寄存器的消耗主要取決于查找表的大小和迭代次數(shù)，最大輸出時延與迭代次數(shù)有關. 改進算法通過四次迭代替換查找表，又通過合并迭代減少大量的迭代，整體只需要5個時鐘周期就能得到輸出結果. 比較三種算法使用的寄存器數(shù)量和最大輸出時延可看出，改進算法使用的寄存器數(shù)量僅為流水線算法的25.58%，相比于三階段算法節(jié)省了43.3%的寄存器消耗，最大輸出時延相比于流水線型算法減少了68.75%.

利用MATLAB對三種算法進行建模和誤差分析，輸入角度以2-15分辨率遍歷[0,π/2]，計算得到絕對誤差. 表3、 4分別列出三種算法正余弦誤差的最大值、最小值以及平均絕對誤差值，其中三種算法的余弦值絕對誤差如圖4所示，其中紅色點代表的是絕對誤差的最大值與最小值. 通過比較三種算法的平均絕對誤差值，可看出改進算法與流水線型算法的平均絕對誤差處于同一數(shù)量級，但改進算法的平均絕對誤差相對較小. 和三階段算法相比，改進算法的平均絕對誤差相差一個數(shù)量級，其主要原因是在中間數(shù)據(jù)位寬較少時式(4)的近似誤差較大，這一誤差可通過采用更大的中間數(shù)據(jù)位寬來減小.

表3 三種算法的正弦值誤差

表4 三種算法的余弦值誤差

(a) 流水線型CORDIC算法的余弦值絕對誤差

(b) 三階段CORDIC算法的余弦值絕對誤差

(c) 免查找表CORDIC算法的余弦值絕對誤差

5 結 論

針對傳統(tǒng)流水線型CORDIC算法實現(xiàn)中存在的硬件資源消耗多、輸出時延大等問題，結合角度二極化重編碼、合并迭代以及角度區(qū)間折疊等技術提出了一種免查找表CORDIC算法. 該算法將三階段算法中的查找表替換為移位相加的迭代結構并省去了蝶形運算階段，隨后直接進行合并迭代，并根據(jù)角度映射關系還原輸出結果. 結果表明：與傳統(tǒng)流水線型算法相比，免查找表算法的寄存器消耗減少了約74.42%，計算所需的時鐘周期降低了68.75%. 本文提出的免查找表CORDIC算法在實時性、輸出精度、硬件資源消耗方面具有優(yōu)勢，適合高速實時的現(xiàn)代數(shù)字通信系統(tǒng)應用.

[1] VOLDER J E. The CORDIC trigonometric computing technique [J]. IRE Transactions on Electronic Computers, 1959, EC-8(3): 330-334.

[2] AGGARWAL S, MEHER P K, KHARE K. Concept, design, and implementation of reconfigurable CORDIC [J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2016, 24(4): 1588-1592.

[3] DAS A, DASH S, BABU B C, et al. CORDIC algorithm based novel phase detection system for all digital phase locked loop [J]. Journal of Computational Intelligence& Electronic Systems, 2012, 1(1): 23-30.

[4] KUMM M, KLINGBEIL H, ZIPF P. An FPGA-based linear all-digital phase-locked loop [J]. IEEE Transactions on Circuits & Systems I: Regular Papers, 2010, 57(9): 2487-2497.

[5] MEHER P K, VALLS J, JUANG T B, et al. 50 years of CORDIC: algorithms, architectures, and applications [J]. IEEE Transactions on Circuits & Systems I: Regular Papers, 2009, 56(9): 1893-1907.

[6] BOHER L, RABINEAU R, HELARD M. FPGAimplementation of an iterative receiver for MIMO-OFDM systems [J]. IEEE Journal on Selected Areas in Communications, 2008, 26(6): 857-866.

[7] HUANG Hai, XIAO Liyi. CORDIC based fast radix-2 DCT algorithm [J]. IEEE Signal Processing Letters, 2013, 20(5): 483-486.

[8] 梁源, 王興華, 向新,等. 一種基于貪婪算法的CORDIC改進算法[J]. 電訊技術, 2014, 54(3): 312-317.

LIANG Yuan, WANG Xinghua, XIANG Xin, et al. An improved CORDIC algorithm based on greedy algorithm [J]. Telecommunication Engineering, 2014, 54(3): 312-317.

[9] WANG Shaoyun, PIURI V, WARTZLANDER E E. Hybrid CORDIC algorithms [J]. IEEE Transactions on Computers, 1997, 46(11): 1202-1207.

[10]徐成, 秦云川, 李肯立, 等. 免縮放因子雙步旋轉CORDIC算法[J]. 電子學報, 2014, 42(7): 1441-1445.

XU Cheng, QIN Yunchuan, LI Kenli, et al. Double-step scaling free CORDIC [J]. Acta Electronica Sinica, 2014, 42(7): 1441-1445.

[11]MAHARATNA K, BANERJEE S, GRASS E, et al. Modified virtually scaling-free adaptive CORDIC rotator algorithm and architecture [J]. IEEE Transactions on Circuits & Systems for Video Technology, 2005, 15(11): 1463-1474.

[12]姚亞峰, 付東兵, 楊曉非. 基于CORDIC改進算法的高速DDS電路設計[J]. 華中科技大學學報自然科學版, 2009(2): 25-27.

YAO Yafeng, FU Dongbing, YANG Xiaofei. Implement of high speed DDS circuit design using improved CORDIC algorithm [J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2009(2): 25-27.

[13]MADISETTI A, KWENTUS A Y, WILLSON A N. A 100-MHz, 16-b, direct digital frequency synthesizer with a 100-dBc spurious-free dynamic range [J]. IEEE Journal of Solid-State Circuits, 1999, 34(8): 1034-1043.

[14]JUANG T B, HSIAO S F, TSAI M Y. Para-CORDIC: parallel CORDIC rotation algorithm [J]. IEEE Transactions on Circuits & Systems I: Regular Papers, 2004, 51(8): 1515-1524.

[15]牟勝梅, 李兆剛. 基于查找表和SF CORDIC的高精度正余弦函數(shù)求值方法[J]. 計算機與數(shù)字工程, 2014, 42(3): 359-363.

MOU Shengmei, LI Zhaogang. A computation method of high-accuracy sine & cosine function based on lookup-table and SF CORDIC algorithm [J]. Computer & Digital Engineering, 2014, 42(3): 359-363.

Low-consumptionandLUT-omittedCORDICalgorithm

YAO Yafeng，ZOU Lingzhi，WANG Wei，ZHONG Liang

(Faculty of Mechanicaland Electronic Information, China University of Geosciences, Wuhan 430074, China)

In order to reduce the hardware resource consumption and output delay in the conventional pipeline CORDIC (Coordinate Rotation Digital Computer) algorithm, a LUT-omitted CORDIC algorithm is proposed on the basis of the three-stage CORDIC with look-up table (LUT). The proposed new algorithm adopts 4 iterations of shifter-adder instead of LUT to reduce the register consumption apparently, and merges some iterations to decrease the output delay effectively, and guarantees the output resolution by using a combination of Binary to Bipolar Recoding (BBR) and angle range folding. The improved algorithm is specifically implemented using Verilog HDL on ISE 14.2 software platform and synthesized using XST tools, and is modeled to analyze the output errors through MATLAB. Simulation experiment results show that the register resource consumption of the new algorithm, producing sine/cosine effectively, is reduced by about 74.42% compared with the conventional one, while the output width is set to 16 equally. The computing clock periods are decreased by 68.75%, and the resolution is also improved obviously. Compared with the three-stage algorithm, the consumption of register is reduced by about 43.3%. The proposed algorithm has some advantages such as brilliant real-time performance, high resolution, and low consumption. And it is more applicable for modern digital communication systems that demand for high speed and promising real-time performance.

coordinate rotation digital computer; to omit look-up table; binary to bipolar recoding; field-programmable gate array; digital signal processing

10.11918/j.issn.0367-6234.201704019

TN492

A

0367-6234(2017)11-0109-07

2017-04-05

國家自然科學基金(61601334)

姚亞峰(1970—)，男，副教授，碩士生導師

王 巍，993164156@qq.com

(編輯苗秀芝)