扩展因子预编码的两阶段CORDIC旋转算法2S-PCS  

A Two-Step CORDIC Rotation Algorithm with Pre-Coded Scale Factors

作　　者：牟胜梅[1] 杨晓东[2] 

机构地区：[1]海军工程大学计算机工程系,武汉430033 [2]国防科技大学计算机学院,长沙410073

出　　处：《计算机学报》2011年第4期729-737,共9页Chinese Journal of Computers

基　　金：海军工程大学自然科学基金(HGDQNJJ10028)资助

摘　　要：CORDIC算法常用于高效地用硬件实现向量旋转操作,如何减少迭代次数并保持扩展因子计算与补偿的简单性是算法的难点.文中提出一种表驱动的2S-PCS算法,其流水线较短且扩展因子可预先计算并优化编码.算法首先将[-π,π]内的旋转角映射到[0,π/4]内,并产生初值调整和旋转方向控制信号.之后的旋转过程分为两阶段,步1进行扩展因子可变的大角度旋转,使剩余旋转角进入步2的收敛域.步1的迭代系数和扩展因子均由映射后旋转角的高字段作为地址查表获得.步2扩展因子恒为1,迭代系数直接由旋转角的二进制编码决定.整个过程不需z通道和扩展因子计算通道,节省了面积开销.2S-PCS利用角度分解算法生成步1的迭代系数,约束非零系数的位置,并对扩展因子进行基4-Booth编码,同时合并相邻的计算量小的迭代,以减少流水线级数.2S-PCS算法利用CSA实现三数累加,同时忽略超出精度表示范围的表达式,以减少延迟、降低复杂性.短流水线还可减少计算通路的圆整(rounding)误差,提高精度.2S-PCS算法克服了全字段查表可扩展性差的问题,入口数随数据精度的增加而缓慢增长,可扩展性好.当采用28位数据通路时,与常规CORDIC算法相比,2S-PCS算法的流水线级数减少约38%,面积减少约27.9%,精度提高3位左右,具有明显的性能优势.CORDIC algorithm has been widely used for efficient implementation of vector rotation operations in hardware.However,it＇s hard to achieve small iteration numbers while not compromising the ease of scale factor computing and compensation.This paper proposes a novel table-driven CORDIC rotation algorithm with predictable scale factors and short pipelines.It maps the input angle during into and generates signals to modify the initial iteration value and control the rotation direction.The rotation process is composed of two steps.The coefficients and scale factors of step1 are acquired through lookup table indexed by the MSB（Most Significant Bits） of the mapped angle.After large-angle rotations of step1,the residual angle is brought into the convergence region of step2.The iteration of step2 is scaling-free,with the coefficients directly gotten from the binary representation of the residual angle.During such two processes,no further arithmetic computation in the angle approximation（z datapath） and scale factor computing datapath is required.The coefficients of step1 are generated by our angle decomposition algorithm,with two coefficients in one group,at most one non-zero value each group,and the scale factors are pre-computed and coded with radix-4 Booth recoding algorithm.In addition,some adjacent simple micro rotations are combined into one.All these techniques effectively reduce the iteration number,which is also beneficial to high accuracy due to less rounding errors.Moreover,the algorithm uses carry-save adders to accumulate three operands and omits expressions of machine zero,which reduces the latency and complexity of the system greatly.The MSB indexed lookup table gets over the poor scalability of full-word indexed lookup table,and entries grow slowly with accuracy.When using 28-bit datapath,the algorithm requires 38% less pipeline stages and 27.9% less area consumption compared to those of the conventional CORDIC,while achieving 3 more bits accuracy,which shows great performance superiority.

关 键 词：向量旋转 CORDIC算法 查找表 免扩展 角度重编码 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]