Cordic算法原理详解

目录

坐标旋转分析

Cordic算法原理

应用举例1：求sin值与cos值

应用举例2：求反正切值

cosθ的还原补偿

坐标旋转数字计算机CORDIC(COordinate Rotation DIgital Computer)算法，通过移位和加减运算，能递归计算常用函数值，如Sin，Cos，Sinh，Cosh等函数，由J. Volder于1959年提出，首先用于导航系统，使得矢量的旋转和定向运算不需要做查三角函数表、乘法、开方及反三角函数等复杂运算。J. Walther在1974年用它研究了一种能计算出多种超越函数的统一算法。

坐标旋转分析

已知：OA逆时针旋转θ角度后得到OB，线段OA=OB，∠AOB=θ，A 点坐标（x1,y1）,B 点坐标（x2,y2）；

求证：x2=x1*cosθ – y1*sinθ；y2=x1*sinθ+ y1*cosθ

假设OA=OB=m；

假设点B在第一象限，

x1=m*cosα，y1=m*sinα。

x2=m*cos(α+θ)=m*(cosαcosθ- sinαsinθ)

=m*(cosαcosθ- cosαtanαsinθ)

=m*cosα*(cosθ- tanαsinθ)

=x1*(cosθ- tanαsinθ)

=x1*cosθ-x1* tanαsinθ

=x1*cosθ-y1* sinθ

y2=m*sin(α+θ)=m*(sinαcosθ+ cosαsinθ)

=m*sinαcosθ+ m*cosαsinθ)

=y1cosθ+x1sinθ

假设点B在第四象限，

x1=m*cosα，y1=m*sinα。

x2=m*cos(360°-(θ+α))=m*cos(-(α+θ))=

=m*cos(α+θ)=m*(cosαcosθ- sinαsinθ)

=m*(cosαcosθ- cosαtanαsinθ)

=m*cosα*(cosθ- tanαsinθ)

=x1*(cosθ- tanαsinθ)

=x1*cosθ-x1* tanαsinθ

=x1*cosθ-y1* sinθ

y2=-m*sin(360°-(θ+α))=-m*sin(-(θ+α))

=m*sin(α+θ)=m*(sinαcosθ+ cosαsinθ)

=m*sinαcosθ+ m*cosαsinθ)

=y1cosθ+x1sinθ

同理，无论A在第几象限，B旋转到第几象限，公式都成立。

Cordic算法原理

将坐标关系写成矩阵形式：

继续旋转第二次：

旋转第i次：

提取出cosθ便得到了初步的cordic算法公式：

如果将上式中的cosθ忽略掉，则称该旋转过程为伪旋转，角度正确，但是模长变化，即：

由于硬件比较容易通过移位实现2的乘法与除法，我们固定取第i次（从0开始计数）旋转的角度为 ，也就是

参考下表，一般设置旋转16次，既可以认为得到比较精准的逼近值。

Cordic 算法的思想是通过迭代的方法，不断的旋转特定的角度，使得累计旋转的角度无限接近某一设定的角度，每次旋转的角度的θ = arctan( 1/(2^n) )；

以目标角度α=30°为例，可以经过如下迭代得到：

应用举例1：求sin值与cos值

当z(0)=30°时，计算sin z(0),cos z(0).

迭代计算方法如下表，其中z(i)表示第i次迭代前和目标角度的差值；di表示z(i)的正负；θ(i)表示第i次迭代发生旋转的角度；y(i)为第i次迭代前的纵坐标；x(i)为第i次迭代前的横坐标；

迭代过程中，根据下式计算x(i+1)与y(i+1)的值，tanθ直接调用上一节表格中的值进行计算。

迭代过程如下：

通过cordic算法后，得到sin30°=0.5006，cos30°=0.8657。

结果没有问题，但是x(0)为什么取0.6073呢？继续往下看吧～答案就在后面～

应用举例2：求反正切值

当y(0)=2，x(0)=1，求 .

z(i)表示第i次旋转前总共旋转的角度；θ(i)表示第i次迭代发生旋转的角度；y(i)表示第i次旋转前的纵坐标；di表示θ(i)的正负方向，在下表中省略。

通过cordic算法后，得到 。

cosθ的还原补偿

前面分析cosθ时讲到了伪旋转，每旋转1次，模长缩小了cosθi，我们如果最终须要恢复原有模长的话，就需要在最后的结果上乘以补偿系数An。

设Ai为第i次旋转的补偿系数，，根据三角函数及勾股定理可得：

补偿因子An：

旋转的次数越多，旋转的角度趋近于0°，Ai趋近于1，经过计算，当n趋于无穷大时，An趋近于0.607252935。

即，当i趋于无穷大时：