极客工场

Appearance

共 1,450 字预计阅读约 5 分钟

CORDIC：移位和加减算三角函数 ​

更新时间：2026-09-12。本文是「集成电路大类 · 芯片设计」进阶层（intermediate）数字逻辑第四十七篇。想在硬件里算 sin/cos，直觉是大乘法器 + 查表/泰勒。这一篇讲一个 1959 年为导航计算机发明、如今活在无数 FPGA IP 里的优雅算法——CORDIC，它把三角/双曲/开方统统化归成移位加加减。

本文要回答的问题 ​

  • 为什么「一串精心选角度的微旋转」最后能转到任意角？
  • 旋转模式怎么算出 cosθ/sinθ？向量模式怎么算模长和 atan2？
  • 每次迭代为什么只是移位 2⁻ⁱ 和加减？常量 arctan(2⁻ⁱ) 存哪？
  • 增益 K 从哪来、要不要补偿？收敛范围和象限怎么处理？
  • 迭代多少遍才够精度，和查表插值、乘法泰勒比谁划算？

一、核心：把一次大旋转拆成「已知小角」的和 ​

旋转一个向量 (x,y) 角度 θ 的标准式含 cosθ/sinθ 和乘法。CORDIC 的巧思：只从一个固定的小角表 α(i)=arctan(2⁻ⁱ) 里，每次选正或负做一次微旋转。因为 tan α(i)=2⁻ⁱ，乘 2⁻ⁱ 在二进制里就是右移 i 位，于是微旋转的坐标更新不含真正的乘法：

bash
x(i+1) = x(i) − d(i)·(y(i) >> i)
y(i+1) = y(i) + d(i)·(x(i) >> i)
z(i+1) = z(i) − d(i)·α(i)      // α(i)=arctan(2^-i)，常量

其中 d(i)=±1 是这一步的方向。所有「重活」只有移位、加减，加上一个存常量角的小表——这正是它在小硬件上的杀手锏。

代价是这些微旋转每次都额外乘了一个因子 1/cos α(i)，N 次累计出固定增益 K=∏cos α(i)≈0.60725（反向缩放 1/K≈1.6468），是个与角度无关的常数，事后一次性补偿即可。

二、两种模式：旋转与定向 ​

  • 旋转模式（rotation）：给定目标角 z0=θ，每步选 d=sign(z)（角还没到就继续往同方向），让 z 收敛到 0。初值设 (x0,y0)=(K,0)，N 步后 xN→cosθ、yN→sinθ；
  • 向量模式（vectoring）：给定向量 (x0,y0)、z0=0，每步选 d=−sign(y)（努力把 y 转到 0），最后向量被转到 x 轴：xN→K·√(x0²+y0²)（模长，除掉 K），zN→atan2(y0,x0)（角度）。

角表能表示的总转角范围约 ±99.9°（∑arctan 2⁻ⁱ），覆盖 ±90°；要支持全平面，先做象限预处理（按符号把输入折进第一象限、记下象限，输出再映射回去）。

三、可综合迭代结构 ​

一次迭代组合逻辑可在多拍复用（面积换吞吐），也可把每级寄存器展开成流水线（吞吐换面积）：

verilog
// 单级概念（N 级展开或在状态机里迭代 N 次）
// 旋转模式：d = (z>=0) ? +1 : -1
if (z >= 0) begin
  x <= x - (y >>> i);
  y <= y + (x >>> i);
  z <= z - atan_table[i];   // 常量，定点
end else begin
  x <= x + (y >>> i);
  y <= y - (x >>> i);
  z <= z + atan_table[i];
end

实现要点：全定点、每级多保留 guard bit 防移位丢精度（最后再饱和/截断）；注意同时更新要用旧 x、y（并行非阻塞赋值天然满足）；>>> 是算术右移，i 较大后移位量超过位宽，该级贡献可忽略或按零处理。

四、精度、迭代次数与方案取舍 ​

  • 精度：每迭代一级约增加 1 bit 有效精度，要 b bit 结果大致迭代 b 次（角表也按此位宽存）；误差主要来自角量化和定点舍入。
  • 增益补偿：旋转模式用 x0=K 预置即把增益吸收进初值，省掉显式乘法；向量模式结果除以 K（常数，可转成移位-加）。
  • 和别的方案比：直接查大表（LUT）快但面积随精度指数；LUT+线性/二次插值折中；乘法泰勒精度高但要若干乘法器。CORDIC 的甜区是没有/很少乘法器、要求面积功耗小、能接受 N 拍延迟的场景，如低端 FPGA、电机控制（ Park/Clarke 变换、atan2）、数字下变频、早期 GPU/计算器。现代 FPGA 有大量 DSP block 时，乘法插值或专用 CORDIC IP 常更省整体资源。
  • 双曲/线性模式：改一下坐标更新式和角表，CORDIC 还能算双曲函数、指数对数、乘法除法，是一套统一的「初等函数迭代机」。

与现有篇目的衔接 ​

总结 ​

一句话总结：CORDIC 用一串固定的微旋转逼近目标角，每次只在 ±arctan(2⁻ⁱ) 间选方向，由于 tan 值恰为 2⁻ⁱ，坐标更新全是右移加加减、角表是常量，从而在没有乘法器的硬件上算初等函数；旋转模式以 (K,0) 起步把角度累加器 z 转到 0，得到 cos/sin，向量模式反向把 y 转到 0，得到除增益后的模长 √(x²+y²) 与 atan2；微旋转累计的固定增益 K≈0.6073 与角度无关，可吸收进初值或常数补偿，收敛约 ±99.9°，全平面靠象限预处理；一级约换 1 bit 精度、b bit 结果迭代约 b 次，用 guard bit 和算术右移保证定点精度，可多拍复用也可全流水；相比大查表和乘法泰勒，它在乘法器稀缺、面积功耗敏感、能接受 N 拍延迟时最划算，换更新式还能覆盖双曲、乘除等函数。