5.1 CORDIC算法原理

坐标旋转数字计算机（Coordinate Rotation Digital Computer,CORDIC）算法可以追溯到1957年由J·Volder发表的一篇文章。20世纪50年代，在大型计算机中实现移位相加受到了当时条件的限制，所以使用CORDIC算法变得非常有必要。到了20世纪70年代，惠普公司和其他公司生产了手持计算器，许多计算器使用一个内部CORDIC单元来计算所有的三角函数（那时计算一个角度的正切值需要大约1s的延迟）。

20世纪80年代，随着高速度乘法器和带有大存储量的通用处理器的出现，CORDIC算法变得无关紧要了。然而，对于各种通信技术和矩阵算法而言，仍然是需要执行三角函数和均方根等运算的。

在21世纪的今天，对于FPGA而言，CORDIC一定是在数字信号处理应用中（如多输入多输出（MIMO）、波束形成和其他自适应系统）计算三角函数的必备技术。

5.1.1 圆坐标系旋转

在xy坐标平面内将点（x ₁ ,y ₁ ）旋转θ角度后到达点（x ₂ ,y ₂ ），如图5.1所示，其关系用下式表示：

其中，坐标x ₁ 和y ₁ 与x ₂ 和y ₂ 满足下面的关系，即

其中，R为半径。

将上述过程称为平面旋转、向量旋转或者线性（矩阵）代数中的吉文斯旋转。

上面的方程组可写成矩阵向量的形式：

例如，一个90°的相移表示为

一个45°的相移表示为

通过提取公共因子cosθ，式（5.2）可写成下面的形式：

如果去除cosθ项，则得到伪旋转方程式：

旋转的角度是正确的，但是x与y的值增加1/cosθ，如图5.2所示。由于1/cosθ>1，所以模的值变大。

例如，在R=1时，(x ₁ ,y ₁ )=(0.34,0.94)，经过45°旋转后，(x ₂ ,y ₂ )=(0.91,0.43)。然而，对于伪旋转而言， ，则 表示为

并不能通过适当的数学方法去除cosθ项。然而，随后发现去除cosθ项可以简化坐标平面旋转的计算操作。

CORDIC算法的核心是伪旋转角度，其中tanθ=2 ^-i ，故方程可表示为

CORDIC算法中，每个迭代i的旋转角度（精确到9位小数）如表5.1所示。

这里，把变换改成了迭代算法。将各种可能的旋转角度加以限制，使得能够通过一系列连续小角度的旋转迭代i来完成对任意角度的旋转。旋转角度遵循法则tan（θ ⁱ ）=2 ^-i ，乘以正切项则就变成了移位操作。

前几次迭代的形式为：第1次迭代旋转45°，第2次迭代旋转26.6°，第3次迭代旋转14°等。

很明显，每次旋转的方向都影响最终要旋转的累积角度。在-99.7°≤θ≤99.7°的范围内，可以旋转任意角度，满足法则的所有角度的总和 。对于该范围之外的角度，可使用三角恒等式转化成该范围内的角度。当然，角度分辨率的数据位数与最终的精度有关。13次的迭代结果如表5.2所示。

旋转13次后，旋转向量增量为

因此，最终伪旋转向量的长度应该除以1.6467602，也就是乘以常数(1/K _n )=0.60725941。更进一步，推广：

当n→∞时，K _n =1.6467602；n→∞时，1/K _n =0.60725941。

在前面提到，所有CORDIC角度的和趋向于99.7°，读者很容易想到，如果旋转角度大于99.7°，如124°，如何处理该问题呢？

根据式（5.3）可知，那是90°旋转时横坐标和纵坐标之间的关系。因此，通过90°旋转和CORDIC操作，在360°范围内可以实现任何期望的角度旋转。使用90°旋转用于保证向量在CORDIC算法的收敛区域内，如图5.3所示。

例如，将一个向量以顺时针方向旋转124°。首先，通过一个简单的象限操作将向量旋转90°，然后使用CORDIC旋转剩余的（124°-90°=34°）角度，如图5.4所示。

从图5.3可知，当一个向量位于第二象限时，则可以通过顺时针旋转90°进入第一象限的收敛区域；当一个向量位于第三象限时，则可以通过逆时针旋转90°进入第四象限的收敛区域。

对于FPGA而言，通过向量的x坐标和y坐标的MSB（符号位）就可以判断出该向量位于第几象限。

（1）当向量位于第一象限时，（x） _MSB =0，且（y） _MSB =0。

（2）当向量位于第二象限时，（x） _MSB =1，且（y） _MSB =0。

（3）当向量位于第三象限时，（x） _MSB =1，且（y） _MSB =1。

（4）当向量位于第四象限时，（x） _MSB =0，且（y） _MSB =1。

注 ：象限映射操作隐含说明实际上的CORDIC操作要求在-90°~+90°范围内，而不是前面所说的-99.7°~+99.7°范围内。

对于每次迭代而言，前面所示的伪旋转现在可以表示为

式（5.7）中，符号d _i =±1，它是一个判决算子，用于确定旋转的方向，即顺时针旋转或逆时针旋转。

在这里引入第3个方程，将其称为角度累加器，用于在每次的迭代过程中追踪累加的旋转角度：

式（5.7）和式（5.8）为圆周坐标系中用于角度旋转的CORDIC算法的表达式。例如，初始的输入为0°，当旋转+45°、-26.6°、-14°、+7.1°、-3.6°后，角度累加器将保持每次迭代后的值，如表5.3所示。

CORDIC算法提供了两种操作模式，即旋转模式和向量模式。工作模式决定了控制算子d _i 的条件。在旋转模式中，将一个输入向量旋转一个期望的角度；在向量模式中，将一个输入向量旋转到x轴。

注 ：本章的后续部分还将介绍在其他坐标系中如何使用CORDIC算法，通过使用这些坐标系可以计算更多的函数。

1.旋转模式

在旋转模式中选择：

也就是d _i 取决于z _i 的符号。旋转的目标是使 z _i →0。经过n次迭代后得到：

假设任意起始点的坐标为(x ₀ ,y ₀ )=(0.9,-2.1)，并且期望旋转的角度z ₀ 为52°，具体的迭代过程如表5.4所示，旋转过程如图5.5所示。

此外，通过设置下面的条件：

可以计算cosz ₀ 和sinz ₀ 。因此，输入x ₀ 和z ₀ (y ₀ =0)，然后通过迭代使z _i+1 趋近于0。

当z ₀ =30°时，计算sinz ₀ 和cosz ₀ 的迭代过程如表5.3所示。从表5.3中可知，该迭代过程遵循式（5.7），角度变化的过程如图5.6所示。从表5.3中可知：

2.向量模式

在向量模式中选择：

目标是使 经过n次迭代后，用下式表示：

通过设置x ₀ =1和z ₀ =0来计算arctany ₀ 。

当y ₀ =2并且x ₀ =1时，计算arctan(y ₀ /x ₀ )的过程如表5.6所示。

从表5.6可知，z ₈ =63.4°≈arctan(2)。

此外，从式（5.11）可知，CORDIC算法的向量模式可以得到输入向量的幅度（模）。当使用向量模式旋转后，向量就与x轴重合。因此，向量的幅度就是旋转向量的x值。幅度结果由K _n 增益标定，即表示为

5.1.2 线性坐标系旋转

本节将介绍线性坐标系下的旋转模式和向量模式。

1.旋转模式

线性坐标系下的旋转模式如图5.7所示，迭代过程表示为

在旋转模式下，选择d _i =sign(z _i )，使得z _i →0。n 次迭代后得到：

该等式类似于实现一个移位-相加的乘法器。

从式（5.13）可知，对于乘法计算而言，将y ₀ 设置为0。

2.向量模式

在向量模式下，选择d _i =-sign(x _i y _i )，使得y _i →0。经过n 次迭代后，用下式表示：

这个迭代式可以用于比例运算。当只使用除法运算时，将z ₀ 设置为0。

注 ：在线性坐标系中，增益固定，所以不需要进行任何标定。

5.1.3 双曲线坐标系旋转

本节将介绍双曲线坐标系下的旋转模式和向量模式。

1.旋转模式

双曲线坐标系下的旋转模式如图5.8所示，迭代过程表示为

在旋转模式下，选择d _i =sign(z _i )，使得z _i →0。n 次迭代后得到：

在双曲线坐标系下旋转时，伸缩因子K _n 与圆周旋转因子有所不同。双曲伸缩因子 可表示为

且当n→∞时， 。

从式 （5.16） 可知，当设置 和y ₀ =0时，可以得到cosh z和sinh z的值。

2.向量模式

在向量模式下，选择d _i =-sign(x _i y _i )，使得y _i →0。经过n次迭代后，用下式表示：

从式（5.18）可知，当设置x ₀ =1，且z ₀ =0时，可以计算arctanhy ₀ 。

注 ：双曲线坐标系下的坐标变换不一定收敛。根据文献，当迭代系数为4,13,40,k,3k+1…时，该系统是收敛的。

根据三角函数之间的关系，可以通过CORDIC算法的计算得到下面的函数值：

5.1.4 CORDIC算法通用表达式

从前几节内容可以看出，在圆周坐标系、线性坐标系和双曲线坐标系下，CORDIC算法的表达式相似。因此，可以给出一个通用的表达式，然后通过选择不同的模式变量就可以得到CORDIC算法的通用公式。其通用公式表示为

式（5.20）中，e _i 用于在给定的旋转坐标系内确定迭代i次所给出的旋转初角。对于圆坐标系而言，e _i =arctan（2 ^-i ）,μ=1；对于线性坐标系而言，e _i =2 ^-i ,μ=0；对于双曲线坐标系而言，e _i =arctanh（2 ^-i ）,μ=-1。

注 ：对于圆坐标系而言，当n→∞时，最大的角度为99.7°；对于线性坐标系而言，当n→∞时，最大的角度为57.3°；对于双曲线坐标系而言，当n→∞时，最大的角度为65.7°。 87RplEAr8AouA1zjJoU2Wb1MUM5E+Qx/awA9WufWfTg/HNvcGjIT/AEvwuNpVwpI