目录

坐标旋转分析

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θ

a65c127b79384b838a0cd1f46ba58372.jpeg

假设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算法原理

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

209cc9b68f704d39bb32caae4809525a.png

继续旋转第二次:

2b48b0723f6c4bc8b4f509e87f911ec3.png

旋转第i次:

0efe7b0870a74db3be243425098d15d7.png

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

3eb70cba66b0490d9657b8d1c3f11b83.png

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

9601c2bcc4ae41db950789fba9ef06ea.png

由于硬件比较容易通过移位实现2的乘法与除法,我们固定取第i次(从0开始计数)旋转的角度为fcf856ff724b4753ae545d8f00138d02.png ,也就是5154eb93da344873a87a718dc828d6fe.png

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

第i次旋转

tanθi

角度

旋转弧度

0

2^-0

45°

0.78539

1

2^-1

26.565°

0.46365

2

2^-2

14.036°

0.24498

3

2^-3

7.1250°

0.12435

4

2^-4

3.5763°

0.06241

5

2^-5

1.7899°

0.03123

6

2^-6

0.8951°

0.01562

7

2^-7

0.4476°

0.00781

8

2^-8

0.2238°

0.00391

9

2^-9

0.1119°

0.00195

10

2^-10

0.0559°

0.00098

11

2^-11

0.0279°

0.00049

12

2^-12

0.0139°

0.00024

13

2^-13

0.0069°

0.00012

14

2^-14

0.0035°

0.00006

15

2^-15

0.0017°

0.00003

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

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

de063b0e81004237984d355f0d245483.png

 

应用举例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θ直接调用上一节表格中的值进行计算。

c63a7f9ac3304f588aa03baf0fb428fa.png

迭代过程如下:

4c20a07a15b04a52a2b37ea350485814.jpeg

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

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

 

应用举例2:求反正切值

当y(0)=2,x(0)=1,求37f16fa2969b4fdba40652ae46e56b36.png .

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

0f01356f028448ab82c9f2aa3c8ba497.jpeg

通过cordic算法后,得到ce2ae55fbf8f4b9f92ae1f73bdc32982.png

 

cosθ的还原补偿

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

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

a7b4e1f135644bc48d2be915a7fc7872.png

补偿因子An:

5a6cd93c41194498a2693ead04c797be.png

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

即,当i趋于无穷大时:

67e137e16cd7489a86d5f86cd3055954.png

 

Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐