Cordic算法的FPGA实现之原理学习随记

落日映苍穹つ 2022-05-20 04:49 181阅读 0赞

一、Cordic算法原理

CORDIC（COordinate Rotation DIgital Computer）算法是坐标旋转数字计算机的简称，由Jack Volder 于1959年在设计美国航空控制系统过程中首先提出，主要解决导航系统中三角函数、反三角函数、开方等实时计算问题。

CORDIC算法应用十分广泛，在DFT、DCT、各种滤波及矩阵的奇异值分解中都可应用CORDIC算法，CORDIC算法提供了一种数学计算的逼近问题，由于它最终可以分解为一系列的加法和移位运算，所以非常适合硬件实现。

CORDIC算法有3种旋转系统：圆周系统、线性系统以及双曲系统。每种系统下都有两种工作模式：旋转模式和向量模式。博主主要讨论的是圆周系统下的两种模式。

1.1 笛卡尔坐标系下的平面旋转

在 xy 坐标平面上将点 ( x1,y1)旋转θ角度到点（x2，y2）的标准方法如下所示:

[![Cordic算法的FPGA实现之原理学习随记][Cordic_FPGA]][Cordic_FPGA_Cordic_FPGA] [![Cordic算法的FPGA实现之原理学习随记][Cordic_FPGA 1]][Cordic_FPGA_Cordic_FPGA 1]

这被称为是平面旋转、向量旋转或者线性 ( 矩阵) 代数中的 Givens 旋转。

通过提出因数cosθ，方程可写成下面的形式 :

x2 = x1cosθ – y1sinθ = cosθ(x1 – y1 tanθ)

y2 = x1sinθ + y1cosθ = cosθ(y1 + x1 tanθ)

如果去除项cosθ，就可以得到伪旋转方程式 :

x2 = x1 – y1 tanθ

y2 = y1 + x1 tanθ 虽然x 与 y 的值增加1/cosθ倍，但是旋转的角度是正确的。

在 xy 坐标平面中: [![Cordic算法的FPGA实现之原理学习随记][Cordic_FPGA 2]][Cordic_FPGA_Cordic_FPGA 2]

因此经过伪旋转之后，向量 R 的模值将增加1 ⁄ cosθ倍，向量旋转了正确的角度 , 但模值出现错误。

CORDIC 方法的核心是 ( 伪) 旋转角度，其中不妨规定![Cordic算法的FPGA实现之原理学习随记][Cordic_FPGA 3] 那么方程就变成：  
[![Cordic算法的FPGA实现之原理学习随记][Cordic_FPGA 4]][Cordic_FPGA_Cordic_FPGA 4] 很显然在这里，把变换改成了迭代算法。我们将各种可能的旋转角度加以限制，使得对任意角度的旋转能够通过一系列连续小角度的旋转迭代i 来完成。旋转角度遵循一定的法则，这样乘以正切项变成了移位操作。整个坐标旋转变换变成了移位加减操作。

很显然，每次旋转的方向都影响到最终要旋转的累积角度。在–99.7 ≤ θ ≤ 99.7的范围内的任意角度都可以旋转。对于该范围之外的角度， 可使用三角恒等式转化成该范围内的角度。  
那么前面所示的伪旋转现在可以表示为（对每次迭代） :

[![Cordic算法的FPGA实现之原理学习随记][Cordic_FPGA 5]][Cordic_FPGA_Cordic_FPGA 5] 这里引入第三个方程，被称为角度累加器，用来在每次迭代过程中追踪累加的旋转角度:  
[![Cordic算法的FPGA实现之原理学习随记][Cordic_FPGA 6]][Cordic_FPGA_Cordic_FPGA 6]

其中符号di 是一个判决算子，用于确定旋转的方向。

上述三个方程式为圆周坐标系中用于角度旋转的 CORDIC 算法的表达式。

1.2 伸缩因子

伸缩因子是伪旋转的副产物，当简化算法以允许伪旋转时，cosθ项被忽略。然而，该简化引发了负面效应输出值 x(n) 和 y(n)被乘以一个因子Kn，该因子被称为伸缩因子，这里:

[![Cordic算法的FPGA实现之原理学习随记][Cordic_FPGA 7]][Cordic_FPGA_Cordic_FPGA 7] 如果我们已知了将被执行的迭代次数，我们便可以预先计算出 1/Kn 的值，并通过将 1/Kn 与 x(n)和 y(n)  
相乘来校正x(n)和y(n)的最终值。

经过n 次迭代后我们得到:

[![Cordic算法的FPGA实现之原理学习随记][Cordic_FPGA 8]][Cordic_FPGA_Cordic_FPGA 8] 通过设置x(0) = 1/Kn 和 y(0) = 0 可以计算 cos z(0) 和 sin z(0)。

因此只要输入x(0)和z(0)（目标角度）(y(0) = 0)，然后通过迭代使z(n)取值趋近于0。

下面通过一个例子来说明：

![Cordic算法的FPGA实现之原理学习随记][Cordic_FPGA 9]1.3 圆周系统下的向量模式

在向量模式中选择:di=-sign(x(i)y(i))； y(i)趋于0  
经过n 次迭代后 :

[![Cordic算法的FPGA实现之原理学习随记][Cordic_FPGA 10]][Cordic_FPGA_Cordic_FPGA 10]  
通过设定x(0)=1 和z(0）=0 来计算arctan y(0)。

因此, 输入x(0)和 y(0)(z(0) = 0)，并通过迭代使 y(0)取值趋近于 0。

[Cordic_FPGA]: http://s12.sinaimg.cn/small/0020H20Fgy6ExIpzL8nfb&690
[Cordic_FPGA_Cordic_FPGA]: http://photo.blog.sina.com.cn/showpic.html#blogid=6dd2a5990101gnl4&url=http://album.sina.com.cn/pic/0020H20Fgy6ExIpzL8nfb
[Cordic_FPGA 1]: http://s9.sinaimg.cn/small/0020H20Fgy6ExI4iRBe48&690
[Cordic_FPGA_Cordic_FPGA 1]: /images/20220520/9bc8266a6a4641a381e03e8ea50feeb9.png
[Cordic_FPGA 2]: http://s14.sinaimg.cn/bmiddle/0020H20Fgy6ExJeEXOB6d&690
[Cordic_FPGA_Cordic_FPGA 2]: /images/20220520/0ef211558f704d41b6c9208c7c3c278a.png
[Cordic_FPGA 3]: /images/20220520/ed48a56510bd4cb8ba21796c35897739.png
[Cordic_FPGA 4]: http://s8.sinaimg.cn/bmiddle/0020H20Fgy6ExJQo6lp67&690
[Cordic_FPGA_Cordic_FPGA 4]: /images/20220520/fb0795db6bf040eca01825f0a22fdb2d.png
[Cordic_FPGA 5]: http://s3.sinaimg.cn/mw690/0020H20Fgy6ExKlTsmS12&690
[Cordic_FPGA_Cordic_FPGA 5]: /images/20220520/62230d0b49784b8e8465f14456f015c2.png
[Cordic_FPGA 6]: http://s2.sinaimg.cn/bmiddle/0020H20Fgy6ExKq2kmtd1&690
[Cordic_FPGA_Cordic_FPGA 6]: /images/20220520/7c249f6c692f4e709b33be98f23771f5.png
[Cordic_FPGA 7]: http://s6.sinaimg.cn/bmiddle/0020H20Fgy6ExKJWAgR25&690
[Cordic_FPGA_Cordic_FPGA 7]: /images/20220520/528cec293b0047858fd25d0c99b568b8.png
[Cordic_FPGA 8]: http://s7.sinaimg.cn/bmiddle/0020H20Fgy6ExKSGjlA16&690
[Cordic_FPGA_Cordic_FPGA 8]: /images/20220520/4b49879fb993414a9eaf76a2a6163820.png
[Cordic_FPGA 9]: /images/20220520/cb6baa9b24614c4caae97859de4b2ff8.png
[Cordic_FPGA 10]: http://s15.sinaimg.cn/bmiddle/0020H20Fgy6ExLtTiUe5e&690
[Cordic_FPGA_Cordic_FPGA 10]: /images/20220520/5ef8f5ea61e04c60a3e2e7441926c6b1.png