EE6309 VLSI Systems 中文复习笔记（持续更新）
EE6309 VLSI Systems 课程复习笔记
当前只覆盖已有课程回放的 Week 1。合并课件中的 CRC、M-out-of-N，以及另一份课件中的噪声内容尚未授课，因此不在本章范围内。
第 1 章（Week 1）：从缩放到可靠数据编码
本章的主线是“怎样把数字数据可靠地从一个位置送到另一个位置”。VLSI（Very-Large-Scale Integration，超大规模集成）让一个系统容纳越来越多的晶体管，但系统同时受到功耗密度、互连噪声、器件故障和时序裕量的约束。数据编码不消除物理噪声，而是在原始消息之外加入结构化冗余，使接收端能够判断数据是否仍属于合法码字集合，必要时进一步定位并纠正错误。
本章按以下顺序建立模型：
- 先用缩放定律理解性能、能量和功耗密度为什么互相牵制；
- 再定义码字、自检与奇偶校验；
- 用二维奇偶校验说明“多次、重叠检查”怎样带来定位能力；
- 用最小 Hamming 距离统一解释检测和纠错能力；
- 最后完整构造 Hamming 码与 SECDED（Single-Error Correction, Double-Error Detection，单错纠正、双错检测），并评估冗余代价。
1.1 缩放：更快、更密集，却不一定更容易散热
Moore 定律是经验观察：单芯片晶体管数大约每 18–24 个月翻倍。对电路分析更直接的问题是：若所有线性尺寸缩小，延迟、功耗和能量按什么比例变化？
设缩放因子 \(\kappa>1\)，器件长度、宽度、氧化层厚度等线性尺寸均变为原来的 \(1/\kappa\)。以下结论属于课程采用的经典比例模型，忽略速度饱和、漏电、互连主导效应和工艺离散性；它用于比较趋势，不应直接当作先进工艺的精确预测。
恒电场缩放（constant-field scaling）
尺寸和电源电压都缩小 \(1/\kappa\)，掺杂浓度提高到 \(\kappa\) 倍，因此电场 \(E\sim V/L\) 保持不变。
电容满足 \(C=\varepsilon A/t\)。面积 \(A\) 缩为 \(1/\kappa^2\)，介质厚度 \(t\) 缩为 \(1/\kappa\)，所以
\[C' = \frac{C}{\kappa}.\]
在经典长沟道比例模型中，电流缩为 \(I'=I/\kappa\)。于是
\[\begin{aligned} t_d' &\sim \frac{C'V'}{I'} =\frac{(C/\kappa)(V/\kappa)}{I/\kappa} =\frac{t_d}{\kappa},\\ P' &\sim V'I'=\frac{P}{\kappa^2},\\ E_{\mathrm{sw}}' &\sim C'(V')^2 =\frac{E_{\mathrm{sw}}}{\kappa^3}. \end{aligned}\]
单位面积能放入 \(\kappa^2\) 倍器件，因此电路密度变为 \(\kappa^2\) 倍，而功耗密度比例为
\[\frac{P'}{A'}=\frac{P/\kappa^2}{A/\kappa^2}=\frac{P}{A}.\]
这就是恒电场缩放的吸引力：速度提高、单器件功耗下降，同时理想功耗密度不增加。
恒电压缩放（constant-voltage scaling）
尺寸仍缩小 \(1/\kappa\)，但电源电压不变。此时电场增为 \(\kappa\) 倍，经典模型给出 \(C'=C/\kappa\)、\(I'=\kappa I\)，所以
\[\begin{aligned} t_d' &\sim \frac{C'V}{I'}=\frac{t_d}{\kappa^2},\\ P' &\sim VI'=\kappa P,\\ E_{\mathrm{sw}}' &\sim C'V^2=\frac{E_{\mathrm{sw}}}{\kappa},\\ \left(\frac{P}{A}\right)'&=\kappa^3\frac{P}{A}. \end{aligned}\]
它换来更激进的速度提升，却使电场可靠性和散热迅速恶化。这解释了为什么处理器不能只靠提高时钟频率延续性能增长，而转向多核、专用加速器和更严格的能量管理。
完整数值例题：\(\kappa=2\)
已知缩放前某逻辑块的延迟为 \(100\ \mathrm{ps}\)，单次切换能量为 \(0.10\ \mathrm{pJ}\)，功耗为 \(1.0\ \mathrm{mW}\)。比较两种缩放策略。
恒电场缩放：
\[\begin{aligned} t_d'&=100\ \mathrm{ps}/2=50\ \mathrm{ps},\\ P'&=1.0\ \mathrm{mW}/2^2=0.25\ \mathrm{mW},\\ E_{\mathrm{sw}}'&=0.10\ \mathrm{pJ}/2^3=0.0125\ \mathrm{pJ},\\ \end{aligned}\]
电路密度倍率为 \(2^2=4\)，功耗密度倍率为 \(1\)。
恒电压缩放：
\[\begin{aligned} t_d'&=100\ \mathrm{ps}/2^2=25\ \mathrm{ps},\\ P'&=2(1.0\ \mathrm{mW})=2.0\ \mathrm{mW},\\ E_{\mathrm{sw}}'&=0.10\ \mathrm{pJ}/2=0.050\ \mathrm{pJ},\\ \end{aligned}\]
电路密度倍率为 \(4\)，功耗密度倍率为 \(2^3=8\)。
量纲检查：延迟仍为时间、功耗仍为能量/时间、切换能量仍为能量；缩放因子本身无量纲。极限检查：\(\kappa=1\) 时所有倍率都回到 1。
1.2 数据编码的基本模型
设原始消息有 \(m\) bit，编码器增加 \(r\) 个检查位，形成 \(n=m+r\) bit 的码字（codeword）。所有允许发送的码字构成合法集合 \(\mathcal C\)。若接收向量 \(\mathbf y\notin\mathcal C\)，接收端便知道传输或电路中出现了错误。
常见错误源包括噪声信道、器件失效和电源扰动。课程首先采用硬连线数字系统的简化假设：单 bit 错误比多个独立 bit 同时出错更常见。因此应以最低硬件代价覆盖单错，再按系统可靠性需求决定是否增强多错检测。
错误检测与错误纠正的区别是：
- 检测只需证明“收到的不是合法码字”；
- 纠错还要从冗余信息中定位最可能的原码字，因此需要更大的码字间隔或更多检查关系。
下面的比较不是按课件条目照抄，而是从“接收端究竟拿什么证据做判决”来整理。它可作为后续选择编码方法的总索引：
| 方案 | 接收端使用的约束 | 最低保证能力 | 能否定位/纠正 | 开销与适用场景 | 关键盲区 |
|---|---|---|---|---|---|
| 一维奇偶校验 | 全码字 XOR 的奇偶性 | 检测任意奇数个 bit 翻转 | 不能定位 | 每组只加 1 bit；适合低成本错误告警 | 任意偶数个翻转可能漏检 |
| 二维奇偶校验 | 每一行和每一列各自的奇偶性 | 纠正单错、检测任意双错 | 单错可由失败行列的交点定位 | 需按块缓存并增加行列检查位；适合矩阵化数据 | 矩形四角同时翻转可能全部抵消 |
| Hamming SEC | 每个位置独有的二进制检查签名 | 纠正单错 | 非零综合征直接给出单错位置 | 校验位数满足 \(2^r\ge m+r+1\)；效率随分组增大而提高 | 双错可能产生另一个非零综合征并被误纠正 |
| 扩展 Hamming SECDED | Hamming 综合征 + 全局奇偶性 | 单错纠正、双错检测 | 能区分无错、单错、全局位错和双错 | 比 SEC 再多 1 bit；常用于存储器与总线保护 | 检出双错不等于知道两个错误位置 |
自检电路
自检（self-checking）是在正常功能运行期间自动检查输出是否符合某种码字约束。两个重要定义是：
- fault-secure（故障安全）：给定故障集合中的任何故障都不会产生另一个错误但仍合法的码字；
- self-testing（自测试）：给定故障集合中的每个故障，至少会在某个合法输入下产生非码字输出。
同时满足两者的电路称为 totally self-checking（完全自检）。必须注意，这些性质总是相对于“给定的故障集合”和“允许的输入集合”而言，不是对一切故障的绝对保证。
双轨检查器（two-rail checker）把每个逻辑量表示为一对互补信号。若所有输入对都互补，两个输出也应互补；输出为 \(00\) 或 \(11\) 则表示输入码字或检查器本身异常。讲课中明确指出原课件第 22 页的一条逻辑表达式有笔误，因此复习时应以“合法输入对与合法输出均互补”的真值条件和实际门级连线为准，不应死记该式。
若平衡树需要检查 \(q\) 对输入、每个基本模块合并两组检查结果，则模块数为
\[N_{\mathrm{module}}=q-1,\]
理想平衡深度为
\[L=\left\lceil\log_2 q\right\rceil.\]
例如 \(q=6\) 时需要 \(5\) 个模块，深度为 \(\lceil\log_2 6\rceil=3\) 级。模块数给面积趋势，级数给关键路径趋势。
1.3 一维奇偶校验：一个 XOR 就能建立约束
XOR（exclusive OR，异或）在输入中有奇数个 1 时输出 1，有偶数个 1 时输出 0。对消息 \((b_{m-1},\ldots,b_1,b_0)\)，偶校验位为
\[p_{\mathrm{even}}=b_{m-1}\oplus b_{m-2}\oplus\cdots\oplus b_1\oplus b_0.\]
这样消息与校验位合计必有偶数个 1。奇校验位则为
\[p_{\mathrm{odd}}=\overline{b_{m-1}\oplus b_{m-2}\oplus\cdots\oplus b_1\oplus b_0}.\]
接收端可以把“检查通过”统一定义为错误标志 \(E=0\)：
\[\begin{aligned} E_{\mathrm{even}}&=y_{m-1}\oplus\cdots\oplus y_0\oplus p_{\mathrm{even}},\\ E_{\mathrm{odd}}&=\overline{y_{m-1}\oplus\cdots\oplus y_0\oplus p_{\mathrm{odd}}}. \end{aligned}\]
若传输期间恰有奇数个 bit 翻转，整体奇偶性改变，\(E=1\)；若有偶数个 bit 翻转，奇偶性不变，错误可能漏检。因此它保证检测任意奇数重量的错误图样，但不能保证检测偶数重量错误。
例题：偶校验与奇校验
已知 \(8\) bit 数据为 \(11010100\)，其中有四个 1。
偶校验：
\[\begin{aligned} p_{\mathrm{even}} &=(1\oplus1\oplus0\oplus1)\\ &\quad\oplus(0\oplus1\oplus0\oplus0)=0. \end{aligned}\]
最终码字有四个 1。奇校验需要把总数变为五个 1，因此
\[p_{\mathrm{odd}}=1.\]
课件中的门级练习使用数据 \(1000\)。它已有一个 1，所以偶校验位为 1，奇校验位为 0。若无传输错误，偶校验 XOR 检查和奇校验 XNOR 检查都输出 \(E=0\)。
图 1 偶校验的生成与检测（来源：EE6309 Week 1 课件第 30 页，裁切并并排整理）。左侧把数据 \(1000\) 逐级 XOR，得到 \(P_{\mathrm{even}}=1\)；右侧把收到的数据和原校验位一起 XOR，输出错误标志 \(E\)。
图中两侧其实是同一个不变量的两种用途。发送端选择 \(P_{\mathrm{even}}\)，使“数据 XOR 校验位”为 0；右侧示例的数据从 \(1000\) 变为 \(1001\)，但随帧发送的校验位仍为 1，于是总 XOR 变为 1，错误标志 \(E=1\)。检测器只知道奇偶约束被破坏，并不知道哪一位发生了翻转。
串行与并行实现
并行发送时可以用平衡 XOR 树一次计算校验位，理想逻辑深度约为 \(\lceil\log_2 m\rceil\)。串行发送时则可用一个触发器保存运行奇偶值：每来一位便执行一次 XOR，最后发送校验位。后者复用硬件且不会在帧尾堆叠 \(m-1\) 级组合延迟，但需要状态复位，并依赖明确的 bit 顺序和帧边界。
图 2 串行帧中的奇偶位与 XOR 累积（来源：EE6309 Week 1 课件第 31 页，裁切）。左图沿时间轴给出起始位、数据位、奇偶位和停止位；右图说明偶校验取所有数据位的 XOR，奇校验再取反。
图 2 的可考结论是“校验计算隐藏在数据发送时间内”：运行奇偶值在每个数据位到达时更新，到奇偶位时隙开始前已经就绪。帧开始必须清零状态，数据位顺序虽然不改变 XOR 的最终值，却决定接收端何时结束累计；停止位不参与本帧奇偶计算。右侧串接门画法用于展示逻辑关系，实际高速并行实现通常改成平衡树以缩短关键路径。
| 计算阶段 | 发送端动作 | 接收端动作 | 当步不变量/检查点 | 常见错误 |
|---|---|---|---|---|
| 帧开始 | 把运行奇偶寄存器清零 | 同步识别起始位并清零本地状态 | 上一帧状态不能带入本帧 | 忘记复位，导致连续帧结果相关 |
| 数据位到达 | 对每个数据位执行 \(q\leftarrow q\oplus b_i\) | 对收到的每个数据位执行同样累计 | XOR 交换律保证最终奇偶值与遍历方向无关 | 把 XOR 当普通加法，或把停止位算进去 |
| 奇偶位时隙 | 偶校验发送 \(p=q\)；奇校验发送 \(p=\overline q\) | 把收到的 \(p\) 纳入最终检查 | 合法偶校验帧总 XOR 为 0，合法奇校验帧总 XOR 为 1 | “偶校验”误写成 \(p=0\) |
| 判决与收尾 | 进入停止位并等待下一帧 | 把最终值映射为统一错误标志 \(E\) | 本章约定合法帧均输出 \(E=0\) | 偶/奇校验使用同一表达式却忘记取反 |
若把每一种非零错误图样视为等可能，\(n\) bit 码字共有 \(2^n-1\) 种非零错误图样，其中奇数重量图样有 \(2^{n-1}\) 种，所以覆盖率为
\[\frac{2^{n-1}}{2^n-1}\approx 50\%.\]
“约 50%”是组合计数结论，不代表真实信道中每种错误图样真的等概率。
1.4 二维奇偶校验：用行列综合征定位单错
二维奇偶校验（2-D parity check，也称 block check code）把数据排成矩阵，并为每一行、每一列分别添加校验位。一个数据 bit 同时参与一条行约束和一条列约束；单错会唯一地让一行和一列失败，两条失败约束的交点就是错误位置。
图 3 二维奇偶校验的单错定位（来源：EE6309 Week 1 课件第 35 页，裁切）。黄色区域是数据，橙色和蓝色分别保存行、列校验；红色行综合征和深蓝色列综合征同时为 1，其交点标出错误 bit。
读取这张图时，应把右侧红列和下方深蓝行看成两组“失败标志”，而不是新的数据。只有第 3 行检查失败且第 3 列检查失败，所以候选位置唯一为 \((3,3)\)。若两个错误落在同一列，两个受影响行会失败，但该列翻转两次后可能仍通过；此时图样仍被检测，却失去唯一交点，不能纠正。
完整练习：\(4\times4\) 数据块
采用偶校验，原始数据为
\[D= \begin{bmatrix} 0&1&1&0\\ 1&1&0&0\\ 1&1&1&0\\ 0&0&0&0 \end{bmatrix}.\]
逐行 XOR 得行校验向量
\[\mathbf p_r= \begin{bmatrix} 0&0&1&0 \end{bmatrix}^{\mathsf T},\]
逐列 XOR 得列校验向量
\[\mathbf p_c= \begin{bmatrix} 0&1&0&0 \end{bmatrix}.\]
若第 3 行第 3 列从 1 翻为 0，接收数据为
\[D'= \begin{bmatrix} 0&1&1&0\\ 1&1&0&0\\ 1&1&0&0\\ 0&0&0&0 \end{bmatrix}.\]
把接收行/列重新计算的奇偶值与已发送校验位 XOR，得到综合征
\[\begin{aligned} \mathbf s_r&= \begin{bmatrix}0&0&1&0\end{bmatrix}^{\mathsf T},\\ \mathbf s_c&= \begin{bmatrix}0&0&1&0\end{bmatrix}. \end{aligned}\]
因此错误唯一位于 \((3,3)\)，把该 bit 再翻转即可恢复。
若第 2 行第 3 列和第 3 行第 3 列同时翻转，则
\[\begin{aligned} \mathbf s_r&= \begin{bmatrix}0&1&1&0\end{bmatrix}^{\mathsf T},\\ \mathbf s_c&= \begin{bmatrix}0&0&0&0\end{bmatrix}. \end{aligned}\]
这说明第 2、3 行各有异常，却不能从列综合征确定是哪一列，所以只能检测、不能纠正。二维奇偶校验保证检测任意双 bit 错误；但四个错误若恰好位于某个矩形的四个角，每个受影响行列都翻转两次，可能完全漏检。由此可见“可检测多 bit 错误”不是“可检测任意数量、任意图样的错误”。
1.5 Hamming 距离：统一描述检测与纠错
两个等长二进制向量 \(\mathbf a\) 与 \(\mathbf b\) 的 Hamming 距离为不同位置的数量：
\[d_H(\mathbf a,\mathbf b)=\operatorname{wt}(\mathbf a\oplus\mathbf b),\]
其中 \(\operatorname{wt}(\cdot)\) 是 1 的个数。一个码的最小距离是任意两个不同合法码字间的最小距离：
\[d_{\min}=\min_{\mathbf c_i\ne\mathbf c_j\in\mathcal C}d_H(\mathbf c_i,\mathbf c_j).\]
核心结论：
- 只要求检测时，最多可保证检测 \(d_{\min}-1\) 个错误；
- 最近码字译码可保证纠正 \(\left\lfloor(d_{\min}-1)/2\right\rfloor\) 个错误；
- 若要同时纠正至多 \(t\) 个错误，并把额外的至多 \(s\) 个错误识别为“不可纠正”，需要 \(d_{\min}\ge 2t+s+1\)。
直觉上，每个合法码字周围半径 \(t\) 的“纠错球”不能重叠。若球重叠，同一接收向量会同样接近两个合法码字，译码器无法唯一选择。
完整距离练习
以 \(A=11111111\) 为参考，比较下列码字和接收结果：
| 码字 | 与 \(A\) 的距离 | 接收示例 | 能力与结论 |
|---|---|---|---|
| \(B=11111011\) | 1 | \(B_{\mathrm{err}}=11111111=A\) | 错误直接落到另一合法码字，连单错也不能保证检测 |
| \(C=11101011\) | 2 | \(C_{\mathrm{err}}=11111011\) | 与 \(A,C\) 都相距 1，可检测但不能唯一纠正 |
| \(D=10101011\) | 3 | \(D_{\mathrm{err}}=11101011\) | 与 \(D\) 相距 1、与 \(A\) 相距 2，可纠正为 \(D\) |
| \(E=10101010\) | 4 | \(E_{\mathrm{err}}=11101011\) | 与 \(A,E\) 都相距 2，双错可检测但不能唯一纠正 |
距离为 4 的码也可选择“放弃纠错、只做检测”，此时理论上能检测最多 3 bit 错误；SECDED 则选择纠正 1 bit、检测 2 bit。
1.6 Hamming 码：从检查矩阵到错误位置
设有 \(m\) 个消息位，需要 \(r\) 个 Hamming 校验位。综合征共有 \(2^r\) 种状态，其中一个状态表示“无错误”，其余状态至少要覆盖 \(m+r\) 个单错位置，因此
\[2^r\ge m+r+1.\]
这是本章需要熟练掌握的数量条件。取满足不等式的最小整数 \(r\)，再把校验位放在位置
\[1,2,4,8,\ldots,2^{r-1}.\]
位置从最低有效端开始编号。位置编号的二进制表示同时决定它参加哪些校验组：编号第 \(j\) 个二进制位为 1，就参加第 \(j\) 组校验。因此接收端各组校验失败位拼起来，正好就是错误位置的二进制编号。
图 4 Hamming \((7,4)\) 的综合征生成网络（来源：EE6309 Week 1 课件第 53 页，裁切）。三棵 XOR 树分别产生 \(b_2,b_1,b_0\)；每棵树只接入位置编号相应二进制位为 1 的接收位。
例如 \(b_0\) 检查奇数位置 \(1,3,5,7\)，\(b_1\) 检查位置 \(2,3,6,7\)，\(b_2\) 检查位置 \(4,5,6,7\)。若只有位置 \(i\) 翻转，它参与的校验树恰好由 \(i\) 的三位二进制编号决定，因此 \((b_2b_1b_0)_2=i\)。这也是“综合征直接等于错误位置”成立的电路原因，而不是需要额外背诵的巧合。
| 步骤 | 手算动作 | 正确性检查 | 典型扣分点 |
|---|---|---|---|
| 1. 求校验位数 | 从 \(r=1\) 起找满足 \(2^r\ge m+r+1\) 的最小整数 | \(2^r-1\) 个非零综合征至少覆盖全部 \(m+r\) 个位置 | 忘记右侧还包含 \(r\) 个校验位和“无错”状态 |
| 2. 安排位置 | 把 \(P_1,P_2,P_3,\ldots\) 放在 \(1,2,4,\ldots\) | 总位置数必须等于 \(m+r\)，位置从 1 开始 | 从位置 0 编号，或消息位高低位顺序未声明 |
| 3. 生成码字 | 按位置编号的二进制位逐组 XOR，采用题目指定的偶/奇校验 | 完整码字重新过每组检查，综合征应为 0 | 漏掉校验位自身，或把组成员凭记忆写错 |
| 4. 译码 | 按同一组计算 \((b_{r-1}\cdots b_0)_2\) | 单错假设下，数值必须落在 \(1\) 到 \(m+r\) | 综合征高低位颠倒，定位到错误位置 |
| 5. 纠错与抽取 | 仅在能力范围内翻转被定位 bit，再按原顺序抽取消息位 | 纠错后综合征归零，并与重新编码结果一致 | 普通 Hamming 遇到双错仍盲目翻转；SECDED 未先看全局奇偶位 |
完整例题：把消息 \(0110\) 编成 Hamming \((7,4)\) 码
已知：\(m=4\)，偶校验，消息按 \((M_4M_3M_2M_1)=0110\) 解释。
先求校验位数：
\[\begin{aligned} r=2:&\quad 2^2=4<4+2+1=7,\\ r=3:&\quad 2^3=8\ge4+3+1=8. \end{aligned}\]
故 \(r=3\)。位置 1、2、4 放 \(P_1,P_2,P_3\)，位置 3、5、6、7 放 \(M_1,M_2,M_3,M_4\)：
| 位置 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|---|---|
| 内容 | \(M_4\) | \(M_3\) | \(M_2\) | \(P_3\) | \(M_1\) | \(P_2\) | \(P_1\) |
| 数值 | 0 | 1 | 1 | ? | 0 | ? | ? |
三个偶校验位分别覆盖：
\[\begin{aligned} P_1&=M_1\oplus M_2\oplus M_4=0\oplus1\oplus0=1,\\ P_2&=M_1\oplus M_3\oplus M_4=0\oplus1\oplus0=1,\\ P_3&=M_2\oplus M_3\oplus M_4=1\oplus1\oplus0=0. \end{aligned}\]
所以按位置 \(7\rightarrow1\) 写出的码字为
\[\boxed{0110011}.\]
量纲检查在这里变成“位数检查”：4 个消息位加 3 个校验位等于 7 bit；每个消息位至少参加两个校验组，所以单错能产生唯一的非零综合征。
接收、定位与纠正
假设位置 3 在传输中由 0 翻为 1，接收字为 \(0110111\)。令 \(Y_i\) 表示接收位置 \(i\) 的 bit，偶校验综合征为
\[\begin{aligned} b_0&=Y_1\oplus Y_3\oplus Y_5\oplus Y_7=1,\\ b_1&=Y_2\oplus Y_3\oplus Y_6\oplus Y_7=1,\\ b_2&=Y_4\oplus Y_5\oplus Y_6\oplus Y_7=0. \end{aligned}\]
因此
\[(b_2b_1b_0)_2=(011)_2=3.\]
综合征直接指出位置 3。把 \(Y_3\) 再翻转，恢复 \(0110011\)，随后抽取位置 7、6、5、3，得到原消息 \(0110\)。硬件上，XOR 网络生成综合征，\(r\)-to-\(2^r\) 译码器选择错误位置，再用 XOR 控制该 bit 是否翻转。
普通 Hamming \((7,4)\) 码不能安全处理双错。例如从 \(0110011\) 出发，若位置 5 与位置 3 同时翻转，收到 \(0100111\)，计算得到综合征 \(110_2=6\)。位置 6 实际没有错；若译码器盲目翻转位置 6，反而会制造第三个错误。
1.7 SECDED：给 Hamming 码再加一层总奇偶性
扩展 Hamming 码在原 Hamming 码之外增加一个全局偶校验位 \(P_0\)，使整个扩展码字的 1 数为偶数，最小距离从 3 提升到 4。令
- \(\mathbf s\) 为原 Hamming 校验产生的综合征；
- \(q\) 为包含 \(P_0\) 在内的全局偶校验结果，\(q=1\) 表示总体奇偶检查失败。
判决表如下：
| \(\mathbf s\) | \(q\) | 含义 | 动作 |
|---|---|---|---|
| \(0\) | 0 | 无错误 | 直接接收 |
| 非零 | 1 | 原 Hamming 部分有单 bit 错误 | 按综合征定位并翻转 |
| \(0\) | 1 | 只有全局校验位 \(P_0\) 出错 | 数据可直接使用；需要时修正 \(P_0\) |
| 非零 | 0 | 双 bit 错误 | 报告不可纠正，禁止盲目翻转 |
关键逻辑是：单错改变总体奇偶性，双错不改变总体奇偶性。普通 Hamming 综合征只说明“某些校验组失败”，全局奇偶位负责把单错和双错区分开。
1.8 课件综合练习：7 bit 消息的 SEC 与 SECDED
题目：数字通信链路发送 7 bit 消息 \((M_7,\ldots,M_1)=1010110\)，采用偶校验。构造能够单 bit 纠错的 Hamming 码，并进一步构造能够单错纠正、双错检测的扩展码。
第 1 问：需要多少个 Hamming 校验位？
\[\begin{aligned} r=3:&\quad 2^3=8<7+3+1=11,\\ r=4:&\quad 2^4=16\ge7+4+1=12. \end{aligned}\]
所以最少需要 \(r=4\) 个校验位，码长 \(n=7+4=11\)。
第 2 问：安排消息位并计算偶校验位
位置 1、2、4、8 放 \(P_1,P_2,P_3,P_4\)，其余位置依次放 \(M_1\) 到 \(M_7\)：
| 位置 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 内容 | \(M_7\) | \(M_6\) | \(M_5\) | \(P_4\) | \(M_4\) | \(M_3\) | \(M_2\) | \(P_3\) | \(M_1\) | \(P_2\) | \(P_1\) |
| 数值 | 1 | 0 | 1 | ? | 0 | 1 | 1 | ? | 0 | ? | ? |
逐组计算：
\[\begin{aligned} P_1&=Y_3\oplus Y_5\oplus Y_7\oplus Y_9\oplus Y_{11} \\ &=(0\oplus1\oplus0)\oplus(1\oplus1)=1,\\ P_2&=Y_3\oplus Y_6\oplus Y_7\oplus Y_{10}\oplus Y_{11} \\ &=(0\oplus1\oplus0)\oplus(0\oplus1)=0,\\ P_3&=Y_5\oplus Y_6\oplus Y_7 \\ &=1\oplus1\oplus0=0,\\ P_4&=Y_9\oplus Y_{10}\oplus Y_{11} \\ &=1\oplus0\oplus1=0. \end{aligned}\]
因此 11 bit 单错纠正码为
\[\boxed{10100110001}.\]
交叉检查：这个码字在每个校验组内都应有偶数个 1；把对应组重新 XOR，四个综合征位均为 0。
第 3 问：扩展为 SECDED
上述 11 bit 码字共有五个 1。为使全局奇偶性为偶数，增加
\[P_0=1.\]
若约定把 \(P_0\) 写在最左端，则 12 bit SECDED 码字为
\[\boxed{110100110001}.\]
最终位数检查：7 个消息位 + 4 个 Hamming 校验位 + 1 个全局校验位 = 12 bit。接收端用上一节的四行判决表区分无错、Hamming 部分单错、\(P_0\) 单错和双错。
1.9 编码效率、冗余与分组大小权衡
对 \(m\) 个消息位和 \(r\) 个检查位，编码效率与冗余比例分别为
\[\begin{aligned} \eta&=\frac{m}{m+r},\\ \rho&=\frac{r}{m+r},\\ \eta+\rho&=1. \end{aligned}\]
单错纠正 Hamming 码的典型结果为：
| 消息位 \(m\) | 最小校验位 \(r\) | 总位数 | 效率 \(\eta\) | 冗余 \(\rho\) |
|---|---|---|---|---|
| 4 | 3 | 7 | \(4/7\approx0.571\) | \(3/7\approx0.429\) |
| 8 | 4 | 12 | \(8/12\approx0.667\) | \(4/12\approx0.333\) |
| 16 | 5 | 21 | \(16/21\approx0.762\) | \(5/21\approx0.238\) |
| 32 | 6 | 38 | \(32/38\approx0.842\) | \(6/38\approx0.158\) |
| 64 | 7 | 71 | \(64/71\approx0.901\) | \(7/71\approx0.099\) |
把多个小消息合并成大分组能提高效率，因为 \(r\) 的增长远慢于 \(m\)。但教师在课堂问答中特别强调：是否应该扩大分组，必须结合信道误码率判断。
若假设各 bit 独立、单 bit 错误概率为 \(p\)，长度为 \(n\) 的码字出现至少两个错误的概率为
\[P_{\ge2}=1-(1-p)^n-np(1-p)^{n-1}.\]
当 \(p\ll1\) 时，用二项式展开得到
\[P_{\ge2}\approx\binom{n}{2}p^2.\]
例如 \(p=10^{-6}\)：
\[\begin{aligned} P_{\ge2}(12)&\approx\binom{12}{2}10^{-12}\\ &=6.6\times10^{-11},\\ P_{\ge2}(71)&\approx\binom{71}{2}10^{-12}\\ &=2.485\times10^{-9}. \end{aligned}\]
大分组仍可能非常可靠，但多错概率约增加 \(37.7\) 倍。若 bit 错误相关、会形成 burst error（突发错误），独立模型还会低估风险。设计时必须在带宽效率、译码延迟、缓存大小与不可纠正错误概率之间取舍。
第 1 章复习页
题型判据速查
| 题目线索 | 第一动作 | 核心判据 | 最多可以下的结论 | 禁止越界 |
|---|---|---|---|---|
| “求偶/奇校验位” | 先数 1 或逐位 XOR | 偶校验总 XOR 为 0；奇校验总 XOR 为 1 | 得到 1 个校验位 | 不能由校验失败定位错误位置 |
| “二维校验收到一个块” | 分别重算所有行、列综合征 | 单错对应唯一失败行与失败列 | 唯一交点时可翻转该 bit | 多个失败行列时不要任意配对纠错 |
| “码的检测/纠错能力” | 先求合法码字集合的 \(d_{\min}\) | 检测 \(d_{\min}-1\)，纠正 \(\lfloor(d_{\min}-1)/2\rfloor\) | 报告保证能力而非某个偶然样例 | 不能只算接收字到一个参考字的距离 |
| “构造 Hamming 码” | 写明位序，再求最小 \(r\) | \(2^r\ge m+r+1\)，校验位在 2 的幂位置 | 在单错假设下完成定位与纠正 | 普通 Hamming 不保证双错检测 |
| “SECDED 接收判决” | 同时计算 \(\mathbf s\) 与全局奇偶 \(q\) | 四种 \((\mathbf s,q)\) 组合分别判决 | 区分无错、单错、\(P_0\) 错、双错 | 双错只能报告不可纠正，不能按 \(\mathbf s\) 翻转 |
| “分组越大是否越好” | 同算效率与至少双错概率 | \(\eta=m/(m+r)\)，低 BER 时 \(P_{\ge2}\approx\binom n2p^2\) | 讨论效率、延迟和可靠性的权衡 | 不能只看冗余下降而忽略相关或突发错误 |
必会公式与变量
| 公式 | 变量与用途 |
|---|---|
| \(t_d\sim CV/I\) | 一阶门延迟模型；\(C\) 为等效电容，\(V\) 为摆幅，\(I\) 为驱动电流 |
| \(E_{\mathrm{sw}}\sim CV^2\) | 切换能量比例；常数因子和活动率不影响本章缩放倍率 |
| \(p_{\mathrm{even}}=\bigoplus_i b_i\) | 生成偶校验位 |
| \(d_H(\mathbf a,\mathbf b)=\operatorname{wt}(\mathbf a\oplus\mathbf b)\) | 计算两个码字的不同 bit 数 |
| \(t=\lfloor(d_{\min}-1)/2\rfloor\) | 最小距离为 \(d_{\min}\) 时可保证纠正的错误数 |
| \(2^r\ge m+r+1\) | \(m\) 个消息位所需的最少 Hamming 校验位 \(r\) |
| \(\eta=m/(m+r)\) | 编码效率 |
| \(P_{\ge2}=1-(1-p)^n-np(1-p)^{n-1}\) | 独立 bit 错误模型下，一个 \(n\) bit 码字出现至少双错的概率 |
典型计算流程
- 明确消息位顺序、位置编号方向、偶/奇校验约定；
- 用 \(2^r\ge m+r+1\) 找最小 \(r\)；
- 在 \(1,2,4,8,\ldots\) 放校验位，其余位置按约定放消息位；
- 用位置编号的二进制位确定每个校验组，逐组 XOR；
- 接收端按相同分组计算综合征，并把综合征按正确高低位顺序转成十进制位置；
- 普通 Hamming 码只在单错假设下翻转该位置；SECDED 必须先结合全局奇偶结果分类；
- 抽取消息位，并用重新计算综合征为 0 做交叉检查；
- 最后计算效率、冗余以及目标信道下的多错风险。
练习结果速查
| 练习 | 最终结果 |
|---|---|
| \(11010100\) 的偶/奇校验位 | \(p_{\mathrm{even}}=0\)，\(p_{\mathrm{odd}}=1\) |
| \(4\times4\) 二维校验单错 | 第 3 行、第 3 列失败，错误在 \((3,3)\) |
| \(0110\) 的 Hamming \((7,4)\) 编码 | \(0110011\) |
| 收到 \(0110111\) | 综合征 \(011_2=3\)，翻转位置 3 |
| 7 bit 消息 \(1010110\) 的 SEC 码 | \(10100110001\) |
| 同一消息的 SECDED 码（\(P_0\) 左置） | \(110100110001\) |
常见易错点与适用假设
- “偶校验”指消息与校验位合计有偶数个 1，不是校验位固定为 0。
- XOR 的结果反映 1 的奇偶性，不是普通加法的和。
- 一维奇偶校验能检测所有奇数重量错误，但会漏掉所有偶数重量错误。
- 二维奇偶校验能纠正单错、检测任意双错，但不能纠正双错，也不能保证检测所有更高重量图样。
- Hamming 距离讨论的是合法码字集合；只计算某个接收字与一个参考字的距离，不能替代最小距离分析。
- Hamming 位置从 1 开始编号，位置 0 不存在；全零综合征表示无 Hamming 部分错误。
- 综合征非零并不自动等于“可纠正单错”。普通 Hamming 码遇到双错可能误纠正；SECDED 必须同时看全局奇偶位。
- 扩大分组会提高效率，也会增加同一码字内出现多错的机会；\(\binom n2p^2\) 近似依赖独立、低误码率假设。
- 缩放表是经典理想模型。先进工艺中的漏电、速度饱和、互连和热约束会改变精确倍率。
综合题答题顺序
先写清消息位顺序和校验协议，再求校验位数与位置；随后列出每个校验组、逐项 XOR、写出完整码字。接收题先算综合征，再根据是否有全局奇偶位决定“纠正、只报告还是无错”，不能先凭肉眼翻 bit。最后用重新编码或综合征归零交叉检查，并报告码长、效率及系统意义。这样可以同时避免位序错误、校验约定错误和双错误纠正。
本章的核心设计思想是：冗余不是越多越好，而要让每个额外 bit 提供可区分的新信息。简单奇偶校验只回答“奇偶性是否改变”，二维校验用两个维度定位单错，Hamming 码则让每个位置拥有唯一的二进制检查签名；SECDED 再加入一个全局约束，把单错与双错分开。后续课程将从物理互连和噪声出发，解释这些错误究竟怎样产生。
Comments