4. CORDIC算法原理
CORDIC（Coordinate Rotation Digital Computer，坐标旋转数字计算机）算法是硬件实现超越函数（三角函数、双曲函数、指数、对数、开方等）的经典方法。其核心思想是将复杂的坐标旋转分解为一系列固定的、易于在硬件中实现的角度微旋转（每次旋转角度满足 tan(θ) = 2⁻ⁱ），通过迭代逼近目标角度或目标向量。与查找表或多项式展开相比，CORDIC仅需移位和加法运算，非常适合FPGA/ASIC中的流水线实现。本章将深入剖析其数学原理、两种工作模式（旋转模式与向量模式）、迭代推导、收敛性边界以及关键的增益补偿问题。
4.1 坐标旋转的数学基础与CORDIC核心思想
在笛卡尔坐标系中，将向量 (x, y) 逆时针旋转角度 θ 得到新向量 (x', y')，其数学表达式为：
x' = x·cosθ - y·sinθ
y' = x·sinθ + y·cosθ直接实现上述运算需要乘法器和三角函数查找表，在硬件中成本较高。CORDIC 算法的巧妙之处在于：将 θ 分解为一系列预先定义好的微小角度 αᵢ = arctan(2⁻ⁱ) 的代数和。由于 tan(αᵢ) = 2⁻ⁱ，旋转公式可改写为：
xᵢ₊₁ = cos(αᵢ) · (xᵢ - σᵢ · yᵢ · 2⁻ⁱ)
yᵢ₊₁ = cos(αᵢ) · (yᵢ + σᵢ · xᵢ · 2⁻ⁱ)其中 σᵢ ∈ {+1, -1} 决定旋转方向。提取公因子 cos(αᵢ) 后，括号内的运算仅包含移位和加减法。每次迭代的 cos(αᵢ) 乘积构成一个常数增益 Aₙ，可在迭代结束后统一补偿。这一"先旋转、后补偿"的策略是 CORDIC 能在硬件中高效实现的关键。
4.2 旋转模式与向量模式：两种工作模式详解
CORDIC 算法根据迭代过程中控制变量（角度累加器 z 或 y 坐标）的不同，分为两种基本工作模式。理解这两种模式的区别与联系，是灵活运用 CORDIC 解决实际问题的前提。
| 特性 | 旋转模式 (Rotation Mode) | 向量模式 (Vectoring Mode) |
|---|---|---|
| 迭代目标 | 使角度累加器 z → 0 | 使 y 坐标 → 0 |
| 旋转方向 σᵢ | σᵢ = sign(zᵢ)，即 zᵢ ≥ 0 时逆时针旋转 | σᵢ = -sign(yᵢ)，即 yᵢ ≥ 0 时顺时针旋转 |
| 输入 | x₀ = 1/Aₙ, y₀ = 0, z₀ = θ | x₀ = x, y₀ = y, z₀ = 0 |
| 输出 | xₙ = cosθ, yₙ = sinθ, zₙ ≈ 0 | xₙ = Aₙ·√(x²+y²), zₙ = atan(y/x) |
| 典型应用 | 正弦/余弦发生器、DDS、坐标旋转 | 反正切计算、向量模长、极坐标转换 |
在旋转模式中，初始向量通常设置为 (1/Aₙ, 0)，经过 n 次迭代后，x 和 y 输出即为 cosθ 和 sinθ。在向量模式中，输入任意向量 (x, y)，迭代使 y 趋近于 0，此时 z 累加器中的值即为向量与 x 轴的夹角 atan(y/x)，而 x 输出为向量模长的 Aₙ 倍。两种模式共享相同的迭代硬件结构，仅需改变 σᵢ 的生成逻辑和初始值设置。
4.3 迭代公式推导与硬件实现映射
从基本旋转公式出发，推导 CORDIC 迭代方程的过程如下：
- 角度分解： 将目标角度 θ 表示为 θ = Σ σᵢ · αᵢ + ε，其中 αᵢ = arctan(2⁻ⁱ)，ε 为残差。
- 旋转矩阵分解： 每次旋转可表示为 R(αᵢ) = cos(αᵢ) · [1, -tan(αᵢ); tan(αᵢ), 1]。
- 代入 tan(αᵢ) = 2⁻ⁱ： 得到迭代核心 xᵢ₊₁ = xᵢ - σᵢ·yᵢ·2⁻ⁱ，yᵢ₊₁ = yᵢ + σᵢ·xᵢ·2⁻ⁱ。
- 角度累加器： zᵢ₊₁ = zᵢ - σᵢ·αᵢ，用于跟踪剩余角度。
- 增益分离： 每次旋转的 cos(αᵢ) 因子从迭代中提取，最终统一乘以 Aₙ = Π cos(αᵢ)。
在 FPGA 中实现时，迭代方程直接映射为硬件结构：
// 伪代码：CORDIC 单级迭代（旋转模式）
always @(posedge clk) begin
if (z_reg < 0) begin
x_next <= x_reg + (y_reg >>> i); // 右移 i 位
y_next <= y_reg - (x_reg >>> i);
z_next <= z_reg + atan_table[i];
end else begin
x_next <= x_reg - (y_reg >>> i);
y_next <= y_reg + (x_reg >>> i);
z_next <= z_reg - atan_table[i];
end
end硬件实现时，每级迭代包含两个桶形移位器（或硬连线移位）、两个加法器/减法器和一个角度查找表（ROM）。流水线结构中，每级使用独立的寄存器组，可达到很高的时钟频率。迭代次数 n 决定了精度：每增加一次迭代，精度约提升 1 bit。
4.4 收敛性分析与角度范围扩展
CORDIC 算法的收敛性取决于两个条件：角度覆盖范围和迭代残差递减性。对于 n 次迭代，可表示的最大角度为 Σᵢ₌₀ⁿ⁻¹ arctan(2⁻ⁱ)。当 n → ∞ 时，该和趋近于约 99.88°。这意味着基本 CORDIC 只能处理 [-99.88°, +99.88°] 范围内的角度，无法直接覆盖完整的 360°。
为解决这一问题，工程中通常采用角度粗旋转（Coarse Rotation）预处理：
- 象限映射： 根据输入角度 θ 的高 2 bit 判断所在象限，将其映射到第一象限 [0°, 90°] 内。
- 符号恢复： 迭代完成后，根据原始象限信息恢复输出结果的符号。
- 多周期扩展： 对于超过 90° 的角度，可先减去 90°、180° 或 270°，再进入 CORDIC 核。
收敛性的另一个重要方面是迭代残差。可以证明，经过 i 次迭代后，剩余角度 |zᵢ| ≤ arctan(2⁻ⁱ⁺¹)，即残差以指数速率递减。因此，迭代次数 n 与输出精度直接相关：n 次迭代后，角度误差约为 2⁻ⁿ 弧度，对应约 0.607·2⁻ⁿ 的幅度误差（考虑增益补偿后的量化效应）。
4.5 增益因子与缩放补偿策略
增益因子 Aₙ = Πᵢ₌₀ⁿ⁻¹ √(1 + 2⁻²ⁱ) 是 CORDIC 算法中不可回避的常数。当 n 足够大时，Aₙ 收敛于 1.646760258...。这个因子使得迭代后的 x、y 坐标被放大了 Aₙ 倍。根据应用场景不同，有三种补偿策略：
| 补偿策略 | 实现方式 | 适用场景 | 优缺点 |
|---|---|---|---|
| 预缩放 | 输入乘以 1/Aₙ | 旋转模式计算 sin/cos | 简单，但引入额外乘法 |
| 后缩放 | 输出乘以 1/Aₙ | 向量模式计算模长 | 与预缩放类似，需乘法器 |
| 常数乘法器 | 使用 CSD 编码或移位加法实现 | 高吞吐率流水线 | 节省 DSP 资源，但逻辑略复杂 |
| 免补偿 | 在后续处理中吸收增益 | FFT 蝶形、迭代算法 | 减少运算，但需全局考虑 |
在 FFT 实现中，CORDIC 常用于蝶形运算的旋转因子乘法。此时增益因子 Aₙ 可以在每一级蝶形中统一补偿，或者将补偿因子合并到下一级的旋转因子中，从而避免额外的乘法器开销。这种"增益吸收"策略是 CORDIC 在复杂算法中高效应用的关键技巧。
4.6 实战案例：基于CORDIC的FFT蝶形运算单元
在 64 点 FFT 处理器设计中，我们需要为每个蝶形运算提供旋转因子 W = e^(-j2πk/N) 的复数乘法。传统方法需要 4 个实数乘法器和 2 个加法器，而使用 CORDIC 旋转模式可将复数乘法转化为角度旋转操作。
案例背景与约束： 设计一个支持 16-bit 复数输入的 FFT 蝶形单元，要求时钟频率 ≥ 200 MHz，资源消耗尽量少。初始方案使用 DSP48E1 乘法器，消耗 4 个 DSP 块，逻辑延迟约 5 ns。
优化方案： 改用 CORDIC 旋转模式实现旋转因子乘法。具体步骤如下：
- 角度预处理： 将旋转因子 W 的相位角 θ 归一化到 [-π, π] 范围，并转换为 16-bit 定点角度值。
- 象限映射： 根据 θ 的高 2 bit 进行象限粗旋转，将有效角度压缩到 [0, π/2]。
- CORDIC 迭代： 使用 14 级流水线 CORDIC 核，每级包含移位和加减法，角度查找表存储 arctan(2⁻ⁱ) 的定点值。
- 增益补偿： 将补偿因子 1/Aₙ 合并到 FFT 下一级的旋转因子中，避免额外乘法。
- 输出组合： 将 CORDIC 输出的 cosθ 和 sinθ 与输入复数相乘，得到旋转后的结果。
结果对比： 优化后蝶形单元消耗 0 个 DSP 块，仅使用 LUT 和 FF，逻辑延迟降低至 3.2 ns，时钟频率提升至 312 MHz。代价是增加了 14 级流水线延迟（约 45 ns），但在 FFT 的流式处理中，流水线延迟可通过多通道交织隐藏。
复盘经验： CORDIC 在 FFT 中的应用并非"免费午餐"。它用时间（流水线延迟）换取资源（DSP 块）。在资源紧张但延迟容忍度高的场景（如通信基带处理）中，CORDIC 是理想选择；而在延迟敏感且 DSP 资源充裕的场景中，传统乘法器可能更合适。设计者需要根据系统级约束做出权衡。