低消耗免查找表CORDIC算法
2017-11-08姚亚峰邹凌志
姚亚峰， 邹凌志， 王 巍， 钟 梁
(中国地质大学(武汉) 机械与电子信息学院， 武汉430074)
低消耗免查找表CORDIC算法
姚亚峰， 邹凌志， 王 巍， 钟 梁
(中国地质大学(武汉) 机械与电子信息学院， 武汉430074)
为减少传统流水线型CORDIC(Coordinate Rotation Digital Computer)算法的硬件资源消耗和输出时延，在包含查找表的三阶段CORDIC算法实现基础上，提出一种免去查找表环节的CORDIC算法实现方法. 提出的改进算法直接使用四次移位相加的迭代运算替换查找表结构从而显著降低寄存器消耗，同时通过合并迭代降低迭代次数进而有效减少最大输出时延，并综合运用角度二极化重编码(Binary To Bipolar Recoding, BBR)方法和角度区间折叠技术保证了输出精度. 使用Verilog HDL语言在ISE14.2软件平台上对三种算法进行具体实现，利用XST工具对其进行综合，并通过MATLAB建模计算得到算法的正余弦值输出误差. 仿真实验结果表明：在输出位宽均设置为16位的情况下，免查找表CORDIC算法能够有效地输出正余弦值；与传统流水线型算法相比，免查找表算法的寄存器资源消耗减少大约74.42%，计算所需的时钟周期降低68.75%，其输出精度也有明显改善；与三阶段算法相比，免查找表算法的寄存器消耗减少大约43.3%. 本文提出的免查找表CORDIC算法具有实时性强、输出精度高、硬件资源消耗少等优势，更适用于高速实时的现代数字通信系统应用.
坐标旋转数字计算机；免查找表；二极化重编码；可编程逻辑门阵列；数字信号处理
随着现代数字通信系统集成化程度和精度的不断提高，许多学者对CORDIC算法提出改进方案. 文献[8]提出一种贪婪搜索算法，采用跳过若干旋转角度和重复某些旋转角度的方法进行迭代，迭代次数有一定减少，但硬件复杂度明显增加. 文献[9]采用一种混合结构，将旋转角度分为两部分处理，与传统流水线型CORDIC算法相比提高运算速度，但仍存在硬件消耗大、输出精度低的问题. 文献[10]中的免缩放因子双步旋转算法免去缩放因子，减少迭代次数，但双步旋转的硬件实现结构较为复杂. 文献[11]提出免缩放自适应CORDIC算法，虽然硬件资源消耗和误差有所减少，但是计算所需的时钟周期太长. 文献[12-13]提出一种三阶段CORDIC算法，第一阶段通过查找表得到若干次迭代后的值，第二阶段采用移位相加的蝶形迭代运算，第三阶段进行合并迭代，相比于传统的流水线型CORDIC算法在精度和硬件消耗上都有一定改善，计算所需的周期少，具有一定代表性和优越性.
本文在文献[12-13]的基础上结合角度二极化重编码(Binary To Bipolar Recoding , BBR)、角度区间折叠、合并迭代等手段提出一种免查找表CORDIC算法，将三阶段缩减为两阶段实现. 在典型的三阶段CORDIC实现方法基础上，将第一阶段的查找表直接替换为有限的几步移位相加迭代运算，有效减少寄存器消耗. 此外，将第二阶段和第三阶段合并为一步迭代，大幅减少输出时延. 用几步迭代运算代替查找表，使输出延时有所增加，但第二阶段的合并迭代只需要一个时钟周期，同时省去原有的蝶形运算阶段，整体只需要5个时钟周期就能得到输出结果，整体延时还有所降低. 同时在综合采用角度二极化重编码和角度区间折叠技术后，改进算法的精度相比于传统实现方法也有一定改善.
1 CORDIC算法基本原理
CORDIC算法通过一系列旋转角不断逼近输入角度，由移位相加迭代得到输入角度的正余弦值. 图1为向量旋转图，在平面直角坐标系中将初始向量OA=(x1,y1)逆时针旋转角度θ到向量OB=(x2,y2)，则坐标之间的关系为
图1 向量旋转示意
(1)
(2)
2 免查找表CORDIC算法
2.1角度二极化重编码
2.2免查找表与合并迭代原理
根据CORDIC算法的基本原理，可通过式(3)迭代得到输入角度的正余弦值
(3)
式中k代表迭代次数.
在三阶段CORDIC算法中，对于输出N位的CORDIC算法，当k (4) 那么式(3)中乘以正切项就可视为移位相加运算，其中k=3对应的结构见图2. (a)移位相加结构示意1 (b)移位相加结构示意2 图2中(a)和(b)分别代表式(3)中的两个子式. 通过这种近似方法，将查找表替换为移位相加的蝶形运算结构，从而减少寄存器消耗. 2.3区间角度折叠及映射关系 对于(π/8,π/4]内的角度，存在式(5)所示的三角函数关系式 (5) 通过上式(5)可将(π/8,π/4]内的角度折叠到[0,π/8]内，有 (6) 从式(6)看出，只要得到[0,π/8]内角度的正余弦值，进行一次加减法运算和2/2缩放就可得到(π/8,π/4]内的正余弦值. 通过类似的三角函数关系式，可将角度扩展到[0,2π]范围内. 表1是具体的角度映射和正余弦转换关系，其中θ′是输入角度经过区间角度折叠预处理后所得到的角度. 将角度折叠到[0,π/8]可以省掉三阶段算法中第二阶段的蝶形运算过程，只需要进行第一阶段的移位相加迭代和第三阶段的合并迭代，随后根据角度映射和转换关系即可还原输出正余弦值. 表1 角度映射和正余弦转换关系 (7) 图3 程序整体结构 用Verilog HDL语言对传统流水线型CORDIC算法，三阶段CORDIC算法和免查找表CORDIC算法进行具体实现，在相同输出位宽的前提下，选用Xilinx公司的xc7k325t-2ffg900型号FPGA，利用ISE14.2自带的XST工具进行电路综合，得到寄存器和LUTs消耗情况以及最大输出时延见表2. 表2三种算法的寄存器和LUTs消耗、最大输出时延 Tab.2 Register and LUTs consumption, maximum output delay for three algorithms 算法类型输出数据位宽N=16消耗的寄存器个数消耗的LUTs个数最大输出时延流水线型CORDIC算法77883616三阶段CORDIC算法3516796免查找表CORDIC算法1996965 寄存器的消耗主要取决于查找表的大小和迭代次数，最大输出时延与迭代次数有关. 改进算法通过四次迭代替换查找表，又通过合并迭代减少大量的迭代，整体只需要5个时钟周期就能得到输出结果. 比较三种算法使用的寄存器数量和最大输出时延可看出，改进算法使用的寄存器数量仅为流水线算法的25.58%，相比于三阶段算法节省了43.3%的寄存器消耗，最大输出时延相比于流水线型算法减少了68.75%. 利用MATLAB对三种算法进行建模和误差分析，输入角度以2-15分辨率遍历[0,π/2]，计算得到绝对误差. 表3、 4分别列出三种算法正余弦误差的最大值、最小值以及平均绝对误差值，其中三种算法的余弦值绝对误差如图4所示，其中红色点代表的是绝对误差的最大值与最小值. 通过比较三种算法的平均绝对误差值，可看出改进算法与流水线型算法的平均绝对误差处于同一数量级，但改进算法的平均绝对误差相对较小. 和三阶段算法相比，改进算法的平均绝对误差相差一个数量级，其主要原因是在中间数据位宽较少时式(4)的近似误差较大，这一误差可通过采用更大的中间数据位宽来减小. 表3 三种算法的正弦值误差 表4 三种算法的余弦值误差 (a) 流水线型CORDIC算法的余弦值绝对误差 (b) 三阶段CORDIC算法的余弦值绝对误差 (c) 免查找表CORDIC算法的余弦值绝对误差 针对传统流水线型CORDIC算法实现中存在的硬件资源消耗多、输出时延大等问题，结合角度二极化重编码、合并迭代以及角度区间折叠等技术提出了一种免查找表CORDIC算法. 该算法将三阶段算法中的查找表替换为移位相加的迭代结构并省去了蝶形运算阶段，随后直接进行合并迭代，并根据角度映射关系还原输出结果. 结果表明：与传统流水线型算法相比，免查找表算法的寄存器消耗减少了约74.42%，计算所需的时钟周期降低了68.75%. 本文提出的免查找表CORDIC算法在实时性、输出精度、硬件资源消耗方面具有优势，适合高速实时的现代数字通信系统应用. [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的高精度正余弦函数求值方法[J]. 计算机与数字工程, 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 (编辑苗秀芝)
3 算法实现
4 仿真结果及分析
5 结 论
