三角函数/爱好者/CORDIC 算法

它是什么

CORDIC（COordinate Rotation DIgital Computer 的缩写）是一种简单高效的算法，用于计算三角函数。它只需要以下运算：

• 加法，
• 减法，
• 乘以 2 和除以 2，以及
• 查表（一个包含 64 个数字的表格足以用于手持计算器可以计算的所有余弦和正弦）。

因为计算机内部使用二进制运算，所以乘以 2 和除以 2 操作非常快且易于执行。因此，CORDIC 算法允许使用相对简单的 CPU 高效地计算三角函数。

应用

CORDIC 特别适合手持计算器，对于这种应用，成本（例如芯片门数必须最小化）远比速度重要。此外，用于三角函数和双曲函数的 CORDIC 子例程（在三角函数第 2 册中描述）可以共享大部分代码。

操作模式

CORDIC 可以用来计算许多不同的函数。本解释展示了如何使用 CORDIC 的旋转模式来计算角度的正弦和余弦，并假设所需的角度以弧度表示，并以定点格式表示。为了确定角度 $\beta$ 的正弦或余弦，必须找到与所需角度相对应的单位圆上一个点的 y 坐标或 x 坐标。使用 CORDIC，我们将从向量 $v_{0}$ 

$v_{0}={\begin{pmatrix}1\\0\end{pmatrix}}$

在第一次迭代中，该向量将逆时针旋转 45 度，得到向量 $v_{1}$。后续的迭代将以逐渐减小的步长，沿一个或另一个方向旋转该向量，直到达到所需的角度。第 i 步的大小为 Artg(1/(2^(i-1)))，其中 i 为 1、2、3 等。

CORDIC 算法正在进行的插图。

更正式地说，每次迭代都会计算一个旋转，该旋转通过将向量 $v_{i-1}$ 与旋转矩阵 $R_{i}$ 相乘来完成。

$v_{i}=R_{i}v_{i-1}$

旋转矩阵 R 由以下公式给出：

$R_{i}=\left({\begin{array}{rr}\cos(\gamma _{i})&-\sin(\gamma _{i})\\\sin(\gamma _{i})&\cos(\gamma _{i})\end{array}}\right)$

使用以下两个三角恒等式：

${\begin{aligned}\cos(\alpha )&=&{\frac {1}{\sqrt {1+\tan ^{2}(\alpha )}}}\\\sin(\alpha )&=&{\frac {\tan(\alpha )}{\sqrt {1+\tan ^{2}(\alpha )}}}\end{aligned}}$

旋转矩阵变为

$R_{i}={1 \over {\sqrt {1+\tan ^{2}\gamma _{i}}}}{\begin{pmatrix}1&-\tan \gamma _{i}\\\tan \gamma _{i}&1\end{pmatrix}}$

旋转后的向量 $v_{i}=R_{i}v_{i-1}$ 的表达式变为

$v_{i}={1 \over {\sqrt {1+\tan ^{2}\gamma _{i}}}}{\begin{pmatrix}x_{i-1}&-&y_{i-1}\tan \gamma _{i}\\x_{i-1}\tan \gamma _{i}&+&y_{i-1}\end{pmatrix}}$

其中，$x_{i-1}$ 和 $y_{i-1}$ 是 $v_{i-1}$ 的分量。限制角度 $\gamma _{i}$ 使得 $\tan \gamma _{i}$ 取值 $\pm 2^{-i}$ ，则与正切的乘法可以替换为除以2的幂，这在使用位移的数字计算机硬件中可以高效地完成。表达式变为

$v_{i}=K_{i}{\begin{pmatrix}x_{i-1}&-&\sigma _{i}2^{-i}y_{i-1}\\\sigma _{i}2^{-i}x_{i-1}&+&y_{i-1}\end{pmatrix}}$

其中

$K_{i}={1 \over {\sqrt {1+2^{-2i}}}}$

并且 $\sigma _{i}$ 可以取值为 -1 或 1，用于确定旋转方向：如果角度 $\beta _{i}$ 为正，则 $\sigma _{i}$ 为 1，否则为 -1。

我们可以忽略 $K_{i}$ 在迭代过程中，然后通过缩放因子在之后应用它

$K(n)=\prod _{i=0}^{n-1}K_{i}=\prod _{i=0}^{n-1}1/{\sqrt {1+2^{-2i}}}$

这可以提前计算并存储在一个表中，或者如果迭代次数是固定的，则存储为一个常量。这种校正也可以提前进行，通过缩放 $v_{0}$ 并且因此节省了乘法。此外，可以注意到

$K=\lim _{n\to \infty }K(n)\approx 0.6072529350088812561694$

以允许进一步减少算法的复杂度。在足够多的迭代之后，向量的角度将接近于想要的角度 $\beta$。对于大多数普通用途，40 次迭代 (n = 40) 足以获得小数点后第 10 位的正确结果。

剩下的唯一任务是确定每次迭代时旋转应该是顺时针还是逆时针（选择 $\sigma$ 的值）。这可以通过跟踪每次迭代我们旋转了多少并从想要的角度减去它来完成，然后检查 $\beta _{n+1}$ 是正的，我们需要顺时针旋转，还是如果它是负的，我们必须逆时针旋转，以便更接近想要的角度 $\beta$。

$\beta _{i}=\beta _{i-1}-\sigma _{i}\gamma _{i}.\quad \gamma _{i}=\arctan 2^{-i},$

的值 $\gamma _{n}$ 也必须预先计算并存储。但对于小角度，$\arctan(\gamma _{n})=\gamma _{n}$ 在定点表示中，减少了表的大小。

如上图所示，角度 $\beta$ 的正弦是最终向量 $v_{n}$ 的 y 坐标，而 x 坐标是余弦值。

• 参见 维基百科上的 CORDIC 以获取更多信息，包括软件实现。

硬件实现

在硬件实现中，CORDIC 算法的主要用途是避免耗时的复杂乘法器。复数相位的计算可以使用硬件描述语言轻松实现，仅使用加法器和移位器电路，绕过笨重的复数乘法器。制造技术一直在稳步改进，现在可以以不高的时间、功耗或过大的芯片空间成本直接处理复数，因此在许多应用中，CORDIC 技术的使用不像以前那么关键。

相关算法

CORDIC 属于“移位-加”算法类别，就像从亨利·布里格斯（Henry Briggs）作品中衍生出来的对数和指数算法一样。另一种可用于计算许多基本函数的移位-加算法是 BKM 算法，它是对数和指数算法在复平面的推广。例如，BKM 可用于通过计算$0+ix,$ 的指数来计算实数角度$x$（以弧度为单位）的正弦和余弦，即$\cos x+i\sin x.$。BKM 算法比 CORDIC 稍微复杂，但它不需要缩放因子（K）。

起源

现代 CORDIC 算法由杰克·E·沃尔德（Jack E. Volder）于 1959 年首次描述。它是在康维尔（Convair）的航空电子部门开发的，旨在替代 B-58 轰炸机导航计算机中的模拟解算器。

尽管 CORDIC 与亨利·布里格斯（Henry Briggs）早在 1624 年发表的数学技术类似，但它针对低复杂度有限状态 CPU 进行了优化。

惠普（Hewlett-Packard）的约翰·斯蒂芬·沃尔特（John Stephen Walther）进一步推广了该算法，使其能够计算双曲函数和指数函数、对数、乘法、除法和平方根。

最初，CORDIC 使用二进制数值系统实现。在 20 世纪 70 年代，十进制 CORDIC 在袖珍计算器中得到广泛使用，这些计算器大多使用二进制编码十进制 (BCD) 而不是二进制。

硬件

当硬件乘法器不可用（例如，在基于微控制器的系统中）或需要将实现其支持的函数所需的栅极数量降至最低（例如，在 FPGA 中）时，CORDIC 通常比其他方法更快。

另一方面，当硬件乘法器可用（例如，在 DSP 微处理器中）时，查表法和幂级数通常比 CORDIC 快。近年来，CORDIC 算法被广泛用于各种生物医学应用，尤其是在 FPGA 实现中。

软件

许多具有仅整数 CPU 的旧系统在一定程度上在其 IEEE 浮点库中实现了 CORDIC。由于大多数现代通用 CPU 都有浮点寄存器，并具有常见的运算（如加、减、乘、除、正弦、余弦、平方根、log10、自然对数），因此在其中使用软件实现 CORDIC 的需求几乎不存在。只有微控制器或特殊的安全和时间约束软件应用程序需要考虑使用 CORDIC。

历史

沃尔德（Volder）受到 1946 年版 CRC 化学和物理手册中以下公式的启发

${\begin{aligned}K_{n}R\sin(\theta \pm \phi )&=R\sin(\theta )\pm 2^{-n}R\cos(\theta )\\K_{n}R\cos(\theta \pm \phi )&=R\cos(\theta )\mp 2^{-n}R\sin(\theta )\end{aligned}}$

其中$K_{n}={\sqrt {1+2^{-2n}}},\tan(\phi )=2^{-n}.$。

CORDIC 的一些早期突出应用包括康维尔导航计算机 CORDIC I 到 CORDIC III、惠普（Hewlett-Packard）的 HP-9100 和 HP-35 计算器、英特尔（Intel）的 80x87 协处理器系列（直到英特尔 80486）和摩托罗拉（Motorola）的 68881。

十进制 CORDIC 最初由赫尔曼·施密特（Hermann Schmid）和安东尼·博加茨基（Anthony Bogacki）提出。

参考文献

• Jack E. Volder，CORDIC 算法三角函数计算技术，IRE 电子计算机学报，第 330-334 页，1959 年 9 月
• Daggett，D. H.，CORDIC 中的十进制-二进制转换，IRE 电子计算机学报，第 EC-8 卷第 5 期，第 335-339 页，IRE，1959 年 9 月
• John S. Walther，基本函数的统一算法，春季联合计算机会议论文集，第 379-385 页，1971 年 5 月
• J. E. Meggitt，伪除法和伪乘法过程，IBM 杂志，1962 年 4 月
• Vladimir Baykov，基于逐位（CORDIC）技术的初等函数求值问题，博士论文，列宁格勒国立电气工程大学，1972 年
• Schmid，Hermann，十进制计算。纽约，Wiley，1974 年
• V.D.Baykov，V.B.Smolov，计算机中基本函数的硬件实现，列宁格勒国立大学，1975 年，96 页。*全文
• Senzig，Don，计算器算法，IEEE Compcon 阅读摘要，IEEE 目录号 75 CH 0920-9C，第 139-141 页，IEEE，1975 年。
• V.D.Baykov，S.A.Seljutin，微型计算器中的基本函数求值，莫斯科，无线电与 связи，1982 年，64 页。
• Vladimir D.Baykov，Vladimir B.Smolov，专用处理器：迭代算法与结构，莫斯科，无线电与 связи，1985 年，288 页
• M. E. Frerking，通信系统中的数字信号处理，1994 年
• Vitit Kantabutra，关于计算指数和三角函数的硬件，IEEE 计算机学报 45 (3)，328-339 (1996)
• Andraka，Ray，基于 FPGA 的计算机的 CORDIC 算法综述
• Henry Briggs，对数算术。伦敦，1624 年，对开本
• CORDIC 文献目录网站
• 算法的秘密，Jacques Laporte，巴黎 1981 年
• 逐位方法，Jacques Laporte，巴黎 2006 年
• Ayan Banerjee，基于 CORDIC 的生物医学信号处理 FFT 处理器的 FPGA 实现，卡拉格布尔，2001 年

鸣谢

• 此页面最初是从CORDIC 算法在维基百科创建的。