📘 第 2 章：计算机算法

这一篇在干嘛？

FPGA 里怎么”算数”：定点数/浮点数的表示、加法器/乘法器/除法器的电路实现、CORDIC 算开方与三角函数——一切 DSP 运算的地基。 原书代码为 VHDL，本篇所有代码已改写为 Verilog。

• 计算机算法
• 2.1 计算机算法概述
• 2.2 数字表示法
• 1. 无符号整数(Unsigned Integer)
• 2. 有符号数值(Signed-Magnitude, SM)
• 3. 二进制补码(Two’s Complement, 2C)
• 4. 二进制反码(也称作1的补码，One’s Complement, 1C)
• 5. 减 1 系统(Diminished one System, D1)
• 6. 偏差系统(Bias System)
• 1. 有符号数字(Signed Digit Number, SD)
• 例2.1 SD编码
• 算法 2.1: 经典 CSD 编码
• 例2.2 经典CSD编码
• 算法 2.2: 最佳 CSD 编码
• 2. 分数(CSD)编码
• 例2.3 分数CSD编码
• 3. 自由进位加法器
• 4. 乘法器-加法器图(Multiplier Adder Graph, MAG)
• 5. 对数系统(Logarithmic Number System, LNS)
• 例2.5 LNS编码
• 6. 余数系统(Residue Number System, RNS)
• 例2.6 RNS算法
• 7. 索引乘法器(Index Multiplier)
• 例2.7 索引编码
• 例2.8 索引乘法
• 8. 索引域中的加法
• 定义 2.9: Zech 对数
• 例2.10 Zech对数
• 9. 利用 QRNS 计算复数乘法
• 例2.12 QRNS乘法
• 例 2.13 (1,6,5) 浮点格式
• 例2.14 12位浮点数和定点数表示方法
• 2.3 二进制加法器
• 例 2.15 31 位流水线加法器的 VHDL 设计
• 2.4 二进制乘法器
• 1. 半分方形乘法器
• 2. 四分之一平方乘法器
• 2.5 二进制除法器
• 例 2.16 8 位还原除法器
• 例2.17 牛顿算法
• 算法 2.18: 收敛除法
• 例 2.19 Anderson-Earle-Goldschmidt-Powers 算法
• 2.6 定点算法的实现
• 2.7 浮点算法的实现
• 例2.20：一个32位浮点运算单元
• 2.8 MAC与SOP
• 例 2.22 无符号 DA 卷积
• 例2.23 有符号DA的内积
• 2.9 利用CORDIC计算特殊函数
• CORDIC 体系结构
• 例 2.25 向量化模式中的圆周 CORDIC
• 2.10 用MAC调用计算特殊函数
• 例2.26 $\arctan (x)$ 函数的逼近
• 算法2.27：切比雪夫函数逼近
• 例 2.28 $\ln (1+x)$ 函数的逼近
• 例2.29 平方根函数的逼近
• 2.11 快速幅度逼近
• 练习

---

自测一下

有符号数为什么用补码而不是原码？

补码把减法统一成加法（a-b 等价于 a 加上 -b 的补码），加法器电路无需区分加减；且 0 只有唯一表示。原码加减需要先比较符号再决定加减，电路复杂。

定点数的量化误差与什么有关？

与小数位宽（字长）有关：字长每增加 1 位，误差约减半（信噪比提高约 6dB）。舍入（round）比截断（trunc）误差更小且无直流偏置。

布斯（Booth）乘法器为什么快/省？

它把乘数按 0/1 串编码，连续 1 段只需一次加减法，减少了部分积数量，从而减少加法器树层数——既省面积又缩短关键路径。

CORDIC 为什么只需要加减和移位？

它把三角/双曲函数计算迭代分解为固定角度的微旋转，每次旋转的 cos/sin 系数是 2 的负幂，乘它只需移位。用牺牲迭代次数（时钟拍数）换取电路极简。

计算机算法

2.1 计算机算法概述

在用 FPGA 实现数字信号处理之前，必须先回答一个问题：数字在硬件里到底怎么表示？运算又怎么实现？ 这就是”计算机算法”要解决的两条基本设计准则——数字表示法（定点数还是浮点数）和代数运算的实现（加法器、乘法器，以及求平方根、CORDIC、MAC 计算三角函数等更复杂运算的高效实现）。

为什么 FPGA 在这件事上有优势？因为 FPGA 是位级可编程的结构，你可以为每个信号单独选择合适的位宽：一个滤波器系数可能 12 位就够了，而累加器可能需要 20 位，位宽按需分配，一点不浪费。这恰好与 PDSP（可编程数字信号处理器）相反——PDSP 的乘累加内核位宽是出厂固定的（比如 16×16→40 位），你只能迁就它。如果在 FPGA 设计中仔细选择位宽，就能从本质上节约资源（LE、布线、功耗都省下来）。反过来想：如果不去管位宽，一律用最宽的位宽”图省事”，资源消耗会成倍增长，时钟频率也会因进位链变长而下降——这就是”不用会怎样”的代价。

2.2 数字表示法

项目的早期阶段就要决定：用定点数还是浮点数？一般的经验是：

• 定点数：速度更快、成本更低，但动态范围小，而且设计者要自己操心”换算”（缩放）问题；
• 浮点数：动态范围大、不需要换算，对复杂算法有吸引力，但速度慢、硬件开销大。

图 2-1 给出了传统和非传统定点数、浮点数表示法的整体框架。两套系统各自涵盖多种标准，必要时也可以定义专有格式。

图 2-1 数字表示法的框架

2.2.1 定点数

定点数家族里最常用的是整数表示法。表 2-1 用 3 位编码对比了 5 种有符号整数的表示方法，下面逐个展开。

表 2-1 有符号二进制数的常规编码

二进制数	2C	1C	D1	SM	偏差
011	3	3	4	3	0
010	2	2	3	2	-1
001	1	1	2	1	-2
000	0	0	1	0	-3
111	-1	-0	-1	-3	4
110	-2	-1	-2	-2	3
101	-3	-2	-3	-1	2
100	-4	-3	-4	-0	1
1000	-	-	0	-	-

1. 无符号整数（Unsigned Integer）

$N$ 位无符号数的取值范围是 $[0,2^N-1]$，表示方法为：

$$X=\sum _{n=0}^{N-1}{x}_n{2}^n\text{\hspace{1em}(2-1)}$$

$x_0$ 是最低有效位（LSB），权重相当于”个位”；$x_{N-1}$ 是最高有效位（MSB），权重是 $2^{N-1}$。

代入算一遍：3 位无符号数 $101_2$，$X=1\times 2^2+0\times 2^1+1\times 2^0=5$。范围是 $[0,7]$。

2. 有符号数值（Signed-Magnitude, SM）

SM 就是”原码”：MSB 单独当符号位，剩下 $N-1$ 位表示数值大小：

$$X=\{\begin{array}{ll}\sum _{n=0}^{N-2}{x}_n{2}^n,& X⩾0\\ -\sum _{n=0}^{N-2}{x}_n{2}^n,& X<0\end{array}\text{\hspace{1em}(2-2)}$$

范围是 $[-(2^{N-1}-1),2^{N-1}-1]$。优点是直观、对称（$\pm 0$ 之外没有多余的负数），有助于防止溢出；致命缺点是加法麻烦：两个异号数相加时，硬件必须先比较谁的绝对值大，再用大的减去小的，还要判断结果符号——加减法器要分成两套逻辑，这就是为什么实际 DSP 系统几乎不用它。

3. 二进制补码（Two’s Complement, 2C）

$N$ 位二进制补码的定义是：

$$X=\{\begin{array}{ll}\sum _{n=0}^{N-2}{x}_n{2}^n,& X⩾0\\ -2^{N-1}+\sum _{n=0}^{N-2}{x}_n{2}^n,& X<0\end{array}\text{\hspace{1em}(2-3)}$$

范围是 $[-2^{N-1},2^{N-1}-1]$。它是 DSP 领域最流行的有符号数系统，核心原因是：累加多个有符号数时，只要最终结果落在 $N$ 位范围内，中间过程的溢出可以完全忽略——所有运算都是模 $2^N$ 意义下的。

计算示例：3 位数 $3+(-2)$：

$$\begin{array}{ccc}{3}_{10}& \leftrightarrow & 011_{2C}\\ -2_{10}& \leftrightarrow & 110_{2C}\\ 1_{10}& \leftrightarrow & 1.001_{2C}\end{array}$$

注意 $011+110=1001$，共 4 位，最高位的进位 1 被丢掉（“1.”表示丢弃的进位），剩下 $001$，正好是 $1_{10}$。溢出被忽略了，结果正确。

再看一个”中间值溢出但最终结果正确”的例子：计算 $2+2-3$。第一步 $010+010=100_{2C}$，按补码解读这是 $-4_{10}$——中间值已经”错”了！但继续算 $100-011=100+101=1001$，丢掉进位得 $001_{2C}$，即 $+1$，结果正确。这就是模 $2^N$ 运算的魅力：中间值可能无法正确表示，但只要最终值有效，结果就一定对。这个性质在设计 CIC 滤波器（第 5 章）时会被直接利用，算法不需要做任何改动。

4. 二进制反码（One’s Complement, 1C）

$N$ 位反码的范围是 $[-(2^{N-1}+1),2^{N-1}-1]$。负数就是正数”按位取反”，因此 0 有两种表示（$000$ 和 $111$，即 $+0$ 和 $-0$），这是它的冗余缺陷。定义如下：

$$X=\{\begin{array}{ll}\sum _{n=0}^{N-2}{x}_n{2}^n,& X⩾0\\ -2^{N-1}+1+\sum _{n=0}^{N-2}{x}_n{2}^n,& X<0\end{array}\text{\hspace{1em}(2-4)}$$

计算示例：$3+(-2)$ 在反码下进行：

$$\begin{array}{cccccc}{3}_{10}& \leftrightarrow & & 0& 1& 1_{1C}\\ -2_{10}& \leftrightarrow & & 1& 0& 1_{1C}\\ 1_{10}& \leftrightarrow & 1.& 0& 0& 0_{1C}\\ \text{进位回绕}& & \hookrightarrow & \to & \to & 1\\ 1_{10}& \leftrightarrow & & 0& 0& 1_{1C}\end{array}$$

直接相加得 $000$ 并产生一个最高位进位。反码的规则是**“进位回绕”**：把最高位冒出来的进位再绕回来加到最低位上，$000+001=001$，即 $+1$，正确。

虽然多了一步回绕，但反码能不做任何校正地实现模 $2^N-1$ 运算。因此在特定 DSP 算法（例如整数环 $2^N-1$ 上的 Mersenne 变换）中，反码有特殊价值。

5. 减 1 系统（Diminished One System, D1）

D1 是一种”有偏差”的系统：正整数比补码表示少 1（即存的是”真值减 1”）。$N+1$ 位 D1 数的范围是 $[-2^{N-1},2^{N-1}]$，不含 0——0 用专门的编码 $2^N$（如 $10000$）表示。编码规则：

$$X=\{\begin{array}{ll}\sum _{n=0}^{N-2}{x}_n{2}^n+1,& X⩾0\\ -2^{N-1}+\sum _{n=0}^{N-2}{x}_n{2}^n,& X>0\\ 2^N,& X=0\end{array}\text{\hspace{1em}(2-5)}$$

验证一下：$3_{10}$ 的 4 位 D1 编码是 $3+1=4=0100$？按书中的 3 位有效写法是 $010_{D1}$（内部存 $3-1=2$）；$-2_{10}$ 存 $-2$，即 $110_{D1}$。

计算示例：D1 加法需要”取反进位”处理：

$$\begin{array}{cccccc}{3}_{10}& \leftrightarrow & & 0& 1& 0_{D1}\\ -2_{10}& \leftrightarrow & & 1& 1& 0_{D1}\\ 1_{10}& \leftrightarrow & 1.& 0& 0& 0_{D1}\\ \text{进位取反}& & \hookrightarrow & \boxed{\mathrm{NOT}}& \to & 0\\ 1_{10}& \leftrightarrow & & 0& 0& 0_{D1}\end{array}$$

与反码类似，但这里最高位进位取反后再加到最低位。D1 数同样能不加改动地实现模 $2^N+1$ 运算，第 7 章将据此在 $2^N+1$ 计算环中实现费尔马 NTT。

6. 偏差系统（Bias System）

偏差系统给所有数统一加一个偏差。偏差通常取范围中点：偏差 $=2^{N-1}-1$。对 3 位数，偏差 $=2^{3-1}-1=3$。$N$ 位偏差数的范围是 $[-2^{N-1}-1,2^{N-1}]$，0 的编码恰好就是偏差本身。定义：

$$X=\sum _{n=0}^{N-1}{x}_n{2}^n-\text{偏差}\text{\hspace{1em}(2-6)}$$

计算示例：$3_{10}+(-2_{10})$，先各自加偏差编码：$3\to 110_{\text{偏差}}$（$6-3=3$），$-2\to 001_{\text{偏差}}$（$1-3=-2$）。两码直接相加：$110+001=111$，解读为 $7-3=4$——比真值 $1$ 多了一个偏差！所以必须再减一次偏差：$111-011=100_{\text{偏差}}$，即 $4-3=1$，正确。

规律总结：每次加法要多减一个偏差，每次减法要多加一个偏差。偏差系统的最大好处是让”数值比较”变成简单的无符号比较（编码顺序与真值顺序一致），这一性质被用来编码浮点数的指数（见 2.2.3 节）。

2.2.2 非传统定点数