低时延CORDIC 算法计算平方根电路设计研究

侯强，彭玉龙，王育新，付东兵

（1.中国地质大学机械与电子信息学院，湖北武汉 430074；2.中国电子科技集团公司第24研究所模拟集成电路国家重点实验室，重庆 400060）

开平方运算是一种应用范围广泛的数学运算，比如通信信号解调时计算信号包络需要进行开平方运算，正交调制信号提取相位信息时也需要开平方运算，它也是很多数字校正算法如功率放大器数字预失真参数提取算法中的关键运算［1］.而平方根运算的精度和速度是开平方电路的主要性能指标.坐标旋转数字计算机（Coordinate Rotation Digital Com⁃puter，CORDIC）算法［2-3］是提高平方根运算精度和速度的一种新颖方法，CORDIC算法在其计算过程中只涉及移位操作和加减操作，因此非常适合硬件特别是FPGA 实现［4］.该方法最初用于进行三角函数求值和产生正余弦波形，经过一定推广后也可用于计算双曲线函数［5］，采用CORDIC 算法在双曲线旋转下的向量模式，可以计算平方根.

文献［6，7］对基本CORDIC 算法计算平方根进行了详细阐述，它是一种循环迭代的计算方法，通过迭代运算不断逼近所要旋转的角度.但由于迭代次数过多存在时延偏大的缺陷，同时每次迭代方向必须等待上一次迭代结束，由上次迭代剩余角度符号决定本次迭代旋转方向，限制了算法的运算速度.文献［8］虽然对模校正因子进行了简化，但最终精度稍有损失，另外还有其他一些改进方法求平方根.

本文在前人对CORDIC 算法进行优化基础上提出了一种改进算法求取平方根，将查找表法、单向旋转、合并迭代和基本CORDIC 算法相结合，只需进行单向迭代运算，避免了每次旋转方向的不确定，消去了缩放因子［9］，从而有效提高了算法的工作速度.同时把迭代运算划分为两个阶段完成：第一阶段迭代通过移位运算和减法运算直接实现，第二阶段迭代通过简化蝶形递归运算一步完成.这样大大减少了迭代运算的次数，降低了延时，特别适合实时性要求高的应用场合.本改进算法在XILINX 公司xc6vlx75t-3ff484 型号FPGA 芯片进行了验证，结果表明：在保证与基本CORDIC 算法精度相同的情况下，能够有效计算平方根，不但显著减少了算法迭代次数，还有效提高了算法运算速度，本改进算法应用在计算平方根方面的综合性能有了较明显提升和改善.

1 基本CORDIC算法

CORDIC 算法最早是由J.Volder 提出的，它是一种只需通过移位-相加运算不断迭代逼近目标值的计算方法［10］.在XY坐标平面上将向量（x0，y0）旋转角度θ后得到向量（x1，y1），如图1所示.

图1 向量旋转示意图Fig.1 Vector rotation diagram

两向量间坐标变换关系如式（1）：

如果去除cosθ项，可得到向量的伪旋转方程如式（2）：

CORDIC 算法核心在于把旋转θ角分解为N个递减的小旋转角θi进行N步迭代旋转，即限定旋转角度θ，使tanθ=di·2-i，其中di=1或-1，表示旋转的方向，从而可以通过简单移位来完成由tanθ引入的乘法运算.任意角度的旋转可通过一系列θ=tan-1（2-i）的角度旋转迭代完成，在这里引入了角度累加器：zi+1=zi–di·θi用来在每次迭代过程中追踪累加后剩余的旋转角度，该剩余的旋转角度确定旋转的方向，若zi＞0，di=1；否则di=-1.那么第i+1 次角度的向量伪旋转方程可表示为式（3）：

正如前面所述，如果消去了cosθi项，迭代方程（2）就只有移位和加减操作.当cosθi项经过N步旋转后可得到模校正因子Kn，当N确定时Kn就是一个常量，而常数项Kn可以在系统的其他地方进行补偿，Kn表达式如式（4）：

最终旋转表达式如式（5）：

CORDIC 算法也可以用于投影计算，当将向量（x，y）投影到x轴时，此时旋转方向由yi确定.若yi＜0，di=1；否则di=-1.迭代的最终值为式（6）：

扩展迭代方程式，CORDIC算法可以用于计算双曲线方程，扩展后的向量伪旋转方程为式（7）：

对于平方根运算采用的是双曲线方程，而且迭代模式为投影模式，迭代的最终值为式（8）：

如果要求值a的平方根，只需要将x、y分别赋值为a+1和a-1，带入式（8）可得xn=，再将其除以2即为.

2 改进的低时延CORDIC算法

2.1 确定旋转方向

低时延CORDIC 算法核心在于确定了每次迭代的旋转方向，这样就使合并迭代成为可能.与基本CORDIC 算法令每次旋转角度为θ=tanh-1（2-i）不同，这里令每次旋转角度为θ=2-i.任意角度的旋转可通过一系列θ=2-i的角度旋转迭代完成，总旋转角度为，将总旋转角度使用二进制表示，若二进制数为1，则进行tanh（2-i）的迭代旋转；否则不进行第i次迭代旋转.这里令x0和y0皆为正数，那么第i+1次角度的向量伪旋转方程可表示为式（9）：

2.2 建立输入值查找表

根据输入的x0和y0建立反双曲正切查找表［11］.查找表中存储对应的以15 位二进制数表示的值，用来作为旋转迭代的方向.

进行角度编码确定旋转方向并不占用硬件资源，只是使每次迭代方向由输入角二进制表示时的各位的位值直接确定，避免了CORDIC 基本算法中迭代方向需由剩余角度计算结果决定的不足［12］，从而提高了CORDIC算法的运行速度.

基于此，可以将角度预处理后得到的二进制补码表示的15 位角度值分两个阶段处理.第一阶段，使用查找表得到的旋转方向进行单向旋转，通过移位运算和减法运算直接得到结果.此时未旋转的角度只剩7 至15 位的小数部分，在第二阶段直接进行合并迭代.

2.3 单向旋转

由于FPGA 中不能直接求取tanh（2-i），所以这里通过移位运算求取.首先在MATLAB 中求得tanh(2-i)具体值后，如表1 所示，将其转换为二进制.此时不需要再预先存储θi的值，同时省去剩余角度存储，直接根据输入二进制的前6 位进行处理.可以将原来的双向旋转表达式化为单向旋转，对应输入二进制数的相应位若为1 时，就取di=-1 进行顺时针旋转，若为0，则不旋转直接传递x、y的值［13］，即保证了精度要求又使得最终的剩余旋转角为0.这样先根据输入角度前（N-1）/2位进行直接旋转，然后进行一步合并迭代运算便可求得平方根.

表1 旋转角度对照表Tab.1 Rotation angle comparison table

2.4 合并迭代

根据基本CORDIC算法有迭代公式（10）：

进行两步迭代有式（11）：

可见，当i≥（N-1）/2 时，基本算法中的蝶形迭代结构便可完全由一个移位-连加结构替代.低时延算法在确定了迭代的旋转方向后，对于输出小数位宽为N的系统，根据泰勒展开式tanh（2-i）=2-i-1/3·2-3i+2/15·2-5i-…，在i≥N/3 时可作θi=tanh（2-i）≈2-i的近似前提下，可直接由图2 所示的移位-连加的合并迭代结构替代基本算法中的蝶形迭代结构，而当i＜（N-1）/2 时可直接通过移位运算得到迭代结果.通过观察表1 中的弧度值，对于15 位二进制小数表示的弧度，当i≥N/3即i≥5时，θi=tanh（2-i）≈2-i，印证上述推导结论［14］.

图2 合并迭代结构图Fig.2 Merged iteration structure diagram

2.5 免除补偿因子

在CORDIC 算法中coshθi可由泰勒级数展开如式（12）：

则当i≥（N-1）/2 时，在保证系统精度的情况下coshθi≈1.对于15 位小数系统，当i≥7 时，迭代旋转可直接消去coshθi项.通过表1 观察coshθi，计算知：当i≥7时，≈1.000 040≈1，所以7到15级迭代在不进行模校正时（即免除缩放因子），在10-5以上的数量级能够保证系统精度［15］.

2.6 算法的FPGA实现

根据以上原理描述，用Verilog HDL 语言对其进行了实现，整个程序分4 个模块，分别为查找表、CORDIC 算法单向旋转、CORDIC 算法合并迭代、还原输出.设计实例程序总体框图如图3.

图3 设计实例总体框图Fig.3 Overall block diagram of design example

在设计实例中，首先使用y0进行查表，确定总旋转角度即迭代旋转次数，当i＜（N-1）/2（即i＜7）时，进行单向旋转.当i≥（N-1）/2（即i≥7）时，进行合并迭代.

3 仿真结果及其分析

在XILINX 公司的xc6vlx75t-3ff484 型号FPGA上对以上电路进行了实现，在ISE14.2 软件环境下利用其自带工具XST 进行综合，并且与基本CORDIC实现方法进行了比较.在用XST 工具综合后得到电路最高工作频率和最大时延等数据，综合结果对比如表2.

表2 综合结果对比Tab.2 Comparison of comprehensive results

从表2中可以看出：改进的CORDIC 算法比基本CORDIC 算法的最高运行频率提高了5.49%，其原因是改进算法只需进行单向迭代运算，避免了每次旋转方向的不确定，从而有效提高了算法的工作速度.通过对比两种算法综合后寄存器和LUT 单元消耗量，可以看出改进算法相比基础算法寄存器有所减少，LUT 单元使用量相对较多，但平均资源消耗两者接近.同时改进CORDIC 算法输出时延比基本CORDIC 算法少了8 个时钟周期，也就是节省了50%的时钟周期，其综合性能有了较大提升.

使用Xpower 进行功耗分析，在40 MHz、70 MHz和100 MHz 频率值上进行了测试，功率数据对比如表3.通过表3 对比得到改进CORDIC 算法比基本CORDIC算法的功耗有所减少，并且随着运行频率的增加，功耗下降比率增大.

表3 功耗分析表Tab.3 Power consumption analysis table

将改进CORDIC 算法和基本CORDIC 算法用MATLAB 语言仿真，并与理论值对比进行误差分析.在此处为了方便观察比较，遍历求取了［3，5］部分的平方根，得到求取平方根误差的绝对值分析结果如图4.

从图4 中看出：基本算法误差绝对值的最大值为8.198×10-4，改进算法误差绝对值的最大值为2.558×10-4，改进算法比基本算法在精度上提高了一些.分别对误差绝对值进行统计平均计算，基本算法平均误差为2.435×10-4，改进算法平均误差为8.413×10-5.可见在平均误差上改进算法比基本算法也有所改善，主要原因在于改进算法中di可取0值，可以避免不必要的迭代，而基本算法对输入角度为特殊角度如θ刚好为tanh-12-i时仍进行迭代旋转，从而增加了算法平均误差.

图4 输出误差对比Fig.4 Error comparison of output

4 结论

本文针对基本CORDIC 算法计算平方根中迭代次数较多，时延较长等局限提出了相应改进方法.在保证与基本CORDIC 算法精度数量级相同的情况下，减少了迭代次数，避免了每次旋转方向的不确定性，消去了缩放因子，有效降低了时延，并且最高运行频率也有所提升.用MATLAB 对该改进算法和基本算法计算平方根建模并进行了性能的比较和分析，同时在XILINX 公司的xc6vlx75t-3ff484 型号的FPGA 上对该改进算法和基本算法计算平方根进行具体的设计和实现.仿真结果表明：改进算法输出时延减少了50%，最高运行频率提高了5.49%，并且输出精度稍优于基本算法.和基本CORDIC 算法相比，改进CORDIC 算法在计算平方根应用场景下的综合性能有了明显提升和改善.