【13：循环码的编码与译码】 https://www.bilibili.com/video/BV1CV4y1c7nw/?share_source=copy_web&vd_source=27abef6992749c2b76e3f7b2a2c835b5

第五章 纠错编码 (Error-Correction Coding)

纠错编码的基本思想是在信息序列中引入冗余位（监督位），利用这些冗余位与信息位之间的代数关系来检测或纠正传输过程中的差错。

1. $(n, k)$ 分组码基础

1.1 基本定义

• $k$：信息位的位数。
• $n$：码字的总长度（信息位 + 监督位）。
• $r = n - k$：监督位（校验位）的位数。
• 码率 $R$：$R = \frac{k}{n}$，衡量编码效率。

1.2 线性分组码 (Linear Block Codes)

线性分组码的特点是：码字中的监督位是信息位的模-2 和（即异或 $\oplus$ 运算）。

例：$(7, 3)$ 分组码 设信息位为 $m = \{m_1, m_2, m_3\}$，码字为 $C = \{c_1, c_2, c_3, c_4, c_5, c_6, c_7\}$。 如果规定前 3 位为信息位（$c_1=m_1, c_2=m_2, c_3=m_3$），后 4 位为监督位，且满足：

$\begin{cases} c_4 = c_1 \oplus c_3 \\ c_5 = c_1 \oplus c_2 \\ c_6 = c_1 \oplus c_2 \oplus c_3 \\ c_7 = c_2 \oplus c_3 \end{cases}$

一部分是信息位一部分是校验位

1.3 系统码 (Systematic Codes)

系统码是指码字可以明确划分为信息位和校验位两个部分。

• 形式 1：$[ \text{信息位} \mid \text{校验位} ]$
• 形式 2：$[ \text{校验位} \mid \text{信息位} ]$ (笔记中提到“一刀切”，前面校验，后面信，这也是一种常见形式)

1.4 Parity codes

本身就是奇偶校验码

Even parity就是模二和

Odd parity 就是对模二和取反而已

1.5 水平垂直奇偶校验码（Horizontal and Vertical Parity Check Code）

📊 水平垂直奇偶校验码：给数据画“十字准星”

它的核心思想是：不仅每行要检查，每列也要检查。

3×4=12ビットの情報 (0,1,1,0,1,0,1,1,0,0,0,1)を送信する

1. 符号化（编码阶段）：给数据加“边框”

想象我们要发送 12 位信息。图片中把它们排成了一个 3 行 4 列 的矩阵。

• 步骤 A：水平校验（行校验）
  • 看第一行（$x_1$ 到 $x_4$）：数据是 0, 1, 1, 0。
  • 这里有 2 个“1”。为了凑成偶数（偶校验），我们在末尾加一个 0（即 $w_{13}$）。
  • 看第二行：1, 0, 1, 1。有 3 个“1”。为了凑成偶数，我们在末尾加一个 1（即 $w_{14}$）。
  • 这就是图片右侧黄色区域第一列（$w_{13}, w_{14}, w_{15}$）的由来。
• 步骤 B：垂直校验（列校验）
  • 看第一列（从上往下）：数据是 0, 1, 0。
  • 有 1 个“1”。为了凑成偶数，我们在最下面加一个 1（即 $w_{16}$）。
  • 这就是黄色区域最下面一行（$w_{16}, w_{17}, w_{18}, w_{19}$）的由来。
• 步骤 C：右下角的“终极校验”（$w_{20}$）
  • 它是对所有校验位再次进行的校验，确保整张表的逻辑闭环。

2. 复号（解码与纠错）：锁定目标

当接收方收到数据后，会计算 校验子（Syndrome），也就是图片右下角的 $s_1$ 到 $s_9$。

• $s_1$ 到 $s_4$：检查每一行是否依然是偶数。
• $s_5$ 到 $s_8$：检查每一列是否依然是偶数。

💡 它是如何纠错的？（十字准星原理）

假设在传输过程中，中间的一个比特翻转了（比如 $y_6$ 从 0 变成了 1）：

1. 行检查会报错：包含 $y_6$ 的那一行（第二行）的 $s_2$ 会变成 1（表示这一行出错了）。
2. 列检查也会报错：包含 $y_6$ 的那一列（第二列）的 $s_6$ 会变成 1（表示这一列出错了）。
3. 锁定位置：接收方发现第二行报错、第二列也报错。行与列的交叉点就是 $y_6$。
4. 修复：把 $y_6$ 反转回来，数据就修好了！

3. 优缺点总结

• 优点：
  • 能纠错：普通的奇偶校验只能发现错误，但这种二维校验能精确定位并修复单个比特的错误。
  • 直观：像坐标系一样，哪里坏了点哪里。
• 局限性：
  • 如果同一行坏了两个点，行校验就看不出来了（因为两个 1 抵消了），虽然列校验还能发现，但可能无法精确定位。

总结一句话：

水平垂直校验就像是在数据的行和列都装了探照灯，当某个数据变坏时，横向和纵向的灯光会在那个错误点交汇，从而让我们一眼发现并修好它。

2. 生成矩阵 $G$ (Generator Matrix)

生成矩阵的作用是：已知信息位 $m$，通过 $G$ 生成码字 $C$。

$C = m \cdot G$

其中，$m$ 是 $1 \times k$ 向量，$G$ 是 $k \times n$ 矩阵。

如果我们需要编码，那么我们就需要求出生成多项式

2.1 典型形式（系统码）

若 $G = [I_k \mid P]$，其中 $I_k$ 是 $k \times k$ 单位阵，$P$ 是 $k \times r$ 校验矩阵，则生成的码字是系统码。

我一开始一直在疑惑，p是什么 其实这就是一个信息分组码，也就是p是通过前面的messegee code 部分进行组合得到的Parity code

• 注：非系统码可以通过初等行变换转化为系统码。

例题

给定 $G = [I \mid P] = \begin{bmatrix} 1 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 0 & 1 \end{bmatrix}$

每一行都是一个合法的码字。

如何获得一个生成矩阵，准确说p如何获得

在信道编码（尤其是线性分组码，如 Hamming 码或 LDPC 码）中，生成矩阵 $G$ 通常被写成系统形式：

$G = [I_k \mid P]$

其中 $I_k$ 是一个 $k \times k$ 的单位矩阵（用于直接保留原始信息位），而 $P$ 是一个 $k \times (n-k)$ 的生成矩阵的校验部分。

$P$ 的具体获得方式取决于你想要构建什么样的码字，通常遵循以下逻辑：

1. 基于校验矩阵 $H$ 的定义

在线性分组码中，校验矩阵 $H$ 的标准形式通常定义为：

$H = [P^T \mid I_{n-k}]$

因为线性分组码必须满足 $G \cdot H^T = 0$，根据矩阵乘法分块规则：

$[I_k \mid P] \cdot \begin{bmatrix} P \\ I_{n-k} \end{bmatrix} = I_k \cdot P + P \cdot I_{n-k} = P + P = 0$

(注：在二进制域 $GF(2)$ 下，$P + P = 0$ 恒成立)。

因此，如果你先有了校验方程（即 $H$ 矩阵），$P$ 就是从 $H$ 矩阵的左侧部分转置过来的。

---

2. 基于监督方程（校验方程）

$P$ 矩阵的每一列实际上决定了监督位（Check Bits）是如何由信息位线性组合生成的。

假设信息位向量为 $m = [m_1, m_2, \dots, m_k]$，生成的码字为 $c = m \cdot G$。

那么：

$c = [m_1, \dots, m_k \mid c_{k+1}, \dots, c_n]$

其中校验位 $c_{k+i}$ 的计算公式为：

$c_{k+i} = \sum_{j=1}^{k} m_j \cdot p_{j,i}$

这里的 $p_{j,i}$ 就是矩阵 $P$ 中第 $j$ 行第 $i$ 列的元素。

---

3. 具体例子：(7, 4) Hamming 码

如果你想构造一个能纠正 1 位错的 Hamming 码，通常会先确定监督方程。例如：

• $c_5 = m_1 \oplus m_2 \oplus m_3$
• $c_6 = m_2 \oplus m_3 \oplus m_4$
• $c_7 = m_1 \oplus m_2 \oplus m_4$

那么对应的 $P$ 矩阵（$4 \times 3$）就是：

$P = \begin{bmatrix} 1 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix}$

第一行 $[1, 0, 1]$ 表示第一个信息位 $m_1$ 参与了第 1 和第 3 个校验位的运算。

总结

• 设计阶段：根据码距（纠错能力）要求，设计校验方程，从而填入 $P$ 的数值。
• 已知 $H$ 时：通过 $H = [P^T \mid I]$ 的对应关系直接提取 $P$。
• 功能上：$P$ 的每一行代表了该行对应的信息位将“贡献”给哪些校验位。

3. 校验矩阵 $H$ (Parity-Check Matrix)

校验矩阵用于验证接收到的码字是否正确。 若 $G = [I_k \mid P]$，则对应的校验矩阵为 $H = [P^T \mid I_r]$。 满足关系：$G \cdot H^T = 0$。

3.1 伴随式 (Syndrome) $S$

设接收到的码字为 $Y$，则伴随式为：

$S = Y \cdot H^T$

• 若 $S = 0$：接收无误（或发生了不可检测的差错）。
• 若 $S \neq 0$：接收有误。
• 检错规律：若 $S$ 等于 $H$ 矩阵的第 $i$ 列，通常预示着第 $i$ 位发生了错误。

4. 纠错与检错能力

4.1 最小汉明距离 $d_{min}$

【3：最小码距与检纠错性能】 https://www.bilibili.com/video/BV16e4y1L7Wc/?share_source=copy_web&vd_source=27abef6992749c2b76e3f7b2a2c835b5

最小汉明距离是码组中任意两个码字之间对应位不同的最小个数。

• 对于线性分组码，$d_{min} = \text{最小非零码字的汉明重量 } w_{min}$。
• 在校验矩阵 $H$ 中，$d_{min}$ 等于 $H$ 中线性相关的列向量的最少个数。

4.2 纠检错公式

通信原理板块——纠错编码最小码距与纠错能力的计算

1. 检测 $e$ 个错：$d_{min} \ge e + 1$

2. 纠正 $t$ 个错：$d_{min} \ge 2t + 1$

3. 纠正 $t$ 个错且检测 $e$ 个错 ($e > t$)：$d_{min} \ge t + e + 1$

例题1:现有 一种重复码 000 （晴天） ， 111（雨天）

最小码距是3

可以检测 2

​ 比如 000 变成 001 可以判断出来

​ 000 变成 110 可以判断出来 有错误

未触达目标：当你发送 000 时，如果错位 1 位变成 100，或者错位 2 位变成 110，由于 110 并不是合法的码字（不是 000 也不是 111），接收端能够识别出这是一个“非法”组合，从而实现检错。

如果 000 错了 3 位变成了 111，接收端会认为你发送的就是合法的 111，此时系统无法发现错误，这就是所谓的“误判”。

例题2:现有 一种重复码 00000 （晴天） ， 11111（雨天）

最小码距5，检错能力为2

和谁比较接近就是谁

5. 汉明码 (Hamming Codes)

一道例题彻底记住海明码【包括编码与检验】

汉明码是一种能纠正单个随机错误的线性分组码。

• 参数：$n = 2^m - 1, r = m, k = 2^m - 1 - m$。
• 构造：$H$ 矩阵的每一列由除全 0 外的所有 $m$ 位二进制向量组成。

6. 循环码 (Cyclic Codes)

6.1 特点

码字具有循环移位特性：若 $C$ 是一个码字，则其循环移位后的序列也是码字。

因为原本的 $C(X)$就能整除 $G(X)$,移位只是相当于乘以了一个 $X$

6.2 多项式表示

• 码字多项式：$C(x) = c_{n-1}x^{n-1} + c_{n-2}x^{n-2} + \dots + c_1x + c_0$
• 生成多项式 $g(x)$：阶数为 $r = n - k$。所有码字多项式都能被 $g(x)$ 整除。

6.3 系统循环码的编码 (SOP)

1. 将信息多项式 $m(x)$ 左移 $r$ 位：$m(x) \cdot x^r$。
2. 求余数：$r(x) = [m(x) \cdot x^r] \mod g(x)$。
3. 合成码多项式：$C(x) = m(x) \cdot x^r \oplus r(x)$。

🔒 循环码的“保险柜”设计指南：通俗易懂版

循环码就像是一种特殊的“数据保险柜”。为了保证里面的数据不被损坏（或者坏了能发现），设计这个保险柜时必须遵守几个数学硬规则。

1. 为什么“长度”不能随便定？ (n vs p)

【核心规则】：保险柜的门（码长 $n$）不能做得比合页的转动周期（周期 $p$）还要长。

• 通俗解释： 想象你在一个圆形的转盘上刻记号。如果转盘转一圈是 7 个格（$p=7$），但你非要在上面记 10 个格的数据（$n=10$），那么第 8、9、10 格就会重叠在第 1、2、3 格上。
• 后果： 这种“重叠”会导致两个完全不同的密码，长得极其相似（只有 2 处不同）。
• 例子： 假设由于 $n > p$，出现了一个只有 2 位不同的坏码字。
  • 正确码字：0000000
  • 坏码字： 1001000 (只有 2 位是 1)
  • 危险点：如果传输中只错了一位，比如变成了 1000000。它距离正确码字差 1 位，距离坏码字也只差 1 位。接收方会彻底懵掉：这到底是原来的 0 错了一位，还是那个坏码字错了一位？
• 结论：只要保证 $n \le p$，数学上就能保证任何两个码字之间至少有 3 位不同（$d_{min} \ge 3$），这样错 1 位时，它依然离“正确答案”最近。

2. 完美的“拼图” (汉明码)

【核心概念】：这一页讲的是一种叫“循环汉明码”的高效率设计。

• 通俗解释： 如果我们把所有的可能组合看作是一个巨大的拼图，汉明码就是把这块拼图切割得最科学、最严丝合缝的方法。
• 它的厉害之处：
  • 它能精确保证 $d_{min}=3$。
  • 球形填充比喻：想象每个正确的码字周围都带了一个“保护罩”（范围是 1 位错误）。汉明码的设计让这些保护罩刚好铺满整个空间，既不重叠，也没有空隙。
• 例子： 对于 $m=3$ 的情况，总长度是 $2^3 - 1 = 7$。 在这 7 位里，有 4 位是真数据，3 位是用来纠错的校验位。 这种结构非常完美：任何 1 位出错，它都会掉进唯一一个正确码字的“保护罩”里，我们能 100% 把它抓回来并修好。

3. 专门对付“连环杀手” (突发错误检测)

【核心规则】：生成多项式的次数 $m$ 决定了它能识破多长的“连环错误”。

• 什么是“突发错误”（Burst Error）？ 数据传输中，错误往往不是零星出现的。比如电磁干扰或者划痕，会一下子导致连续好几位数据都变乱。这就叫“突发错误”。
• 通俗解释： 假设你用了 $m$ 个校验位。只要这串连续错误的长度 $l$ 不超过 $m$，这套系统就百分之百能发现它。
• 数学直觉： 错误就像是一串数字 $E(x)$。要让系统发现不了，这串错误必须能正好被你的生成多项式 $G(x)$ “整除”。但如果错误太短（长度 $\le m$），它就像一个小个子，根本没法被大个子 $G(x)$ 整除（除非全是 0）。
• 例子： 如果你设计了 16 位的校验位（比如 CRC-16）：
  • 哪怕传输中连续 16 位全部由于干扰变乱了，系统也一定会弹出一个大大的红灯：“数据损坏！”
  • 这就是为什么你在网上下载大文件或者看视频时，数据哪怕被干扰了一小块，播放器也能立刻知道并请求重发。

总结：

1. 别太长：码长 $n$ 别超过周期 $p$，否则纠错能力会失效。
2. 至少 3 位：好代码要保证两个词之间至少差 3 位，这样错 1 位才能救回来。（汉明距离的纠错）
3. 看次数：校验位的个数（次数 $m$）直接决定了你能防住多长的连续干扰。

🛠️ 循环码“自动维修”指南：通俗易懂版

当接收方收到一串数据时，如果里面有一个比特（Bit）因为干扰翻转了（比如 0 变成了 1），循环码有一套非常优雅的方法来定位并修复它。

1. 核心思想：余数就是“犯罪现场的指纹”

【基本原理】： 在发送端，我们保证发出的数据多项式 $W(x)$ 能够被生成多项式 $G(x)$ 整除（余数为 0）。 如果接收到的数据 $Y(x)$ 除以 $G(x)$ 余数不为 0，说明出错了。

• 奇妙之处： 这个余数（数学上叫 校验子 Syndrome）不仅告诉我们“出错了”，它还携带了“错误发生在哪里”的信息。它就像是一个独特的“指纹”。

2. 解码三部曲（以幻灯片第一张为准）

我们可以把解码过程想象成一次“故障排查”：

1. 第一步：算余数（做体检） 把收到的那一长串 0 和 1（多项式 $Y(x)$）除以约定的 $G(x)$。得到的余数记为 $R(x)$。
   • 如果余数是 0：恭喜，数据很健康，直接取走。
   • 如果余数不是 0：警报！有错误发生。
2. 第二步：查手册（对指纹） 工程师手里有一张预先做好的“故障判定表”（第一张图右侧的表格）。
   • 表格左边是：错误发生的具体位置 $i$。
   • 表格右边是：那个位置出错时，会产生的唯一余数。
   • 动作：拿着你刚刚算出来的余数，去表里找对应的位置。
3. 第三步：翻转它（修好它） 找到了位置 $i$，说明第 $i$ 位变反了。你只需要把那一位“反转”一下（0 变 1，1 变 0），数据就修好了！

3. 具体例子：(15, 11) 循环码

我们拿第三张图里的例子来实际演练一下。

【设定】：

• 码长 $n=15$。
• 生成多项式 $G(x) = x^4 + x + 1$。
• 预备手册：我们先算出第 0 到 14 位分别出错时的余数（如下表部分内容）：
  • 第 0 位出错 $\rightarrow$ 余数是 $1$
  • 第 1 位出错 $\rightarrow$ 余数是 $x$
  • 第 2 位出错 $\rightarrow$ 余数是 $x^2$
  • …
  • 第 4 位出错 $\rightarrow$ 余数是 $x+1$ （因为 $x^4 \div (x^4+x+1)$ 余数是 $x+1$）

【实战演习】：

1. 收到数据：假设接收方收到了数据，一除以 $G(x)$，算出来的余数是 $x+1$。
2. 查手册：对照上面的手册，发现余数 $x+1$ 对应的是“第 4 位出错”。
3. 修理：于是接收方走到这串数据的第 4 个格子上，把那个数字改过来。
4. 搞定：修理完成，拿到了正确的数据。

4. 为什么这个方法这么灵？（第二张图的真相）

数学上为什么余数能精准定位？

• 接收到的数据 = 正确的数据 + 错误噪声
• 即：$Y(x) = W(x) + x^i$ （假设第 $i$ 位错了）
• 当你计算 $Y(x) \div G(x)$ 的余数时：
  • 第一部分 $W(x)$ 是能被整除的，余数是 0。
  • 所以最后的余数完全由 $x^i$（也就是错误发生的位置）决定！

这就是为什么余数就是“错误位置的唯一指纹”。

💡 总结一句话

“算一下除法的余数，去表里查一下这个余数对应哪一位，然后把那一位改过来，这就是循环码的自动纠错过程。”

7. 综合例题

例 1：汉明距离与纠错能力

已知一组码字，通过比较每两个码字之间的差异，找出最小距离 $d_{min}$。 若 $d_{min}=3$，则：

• 检测错误数 $e$: $3 \ge e+1 \to e=2$。
• 纠正错误数 $t$: $3 \ge 2t+1 \to t=1$。

例 2：已知 $H$ 求参数

已知 $H$ 为 $4 \times 9$ 矩阵。

• $n = 9$（列数），$r = 4$（行数）。
• $k = n - r = 5$。
• 编码率 $R = k/n = 5/9$。
• 通过行变换观察 $H$ 的线性相关性，求得 $d_{min} = 4$。

如何求汉明码的最小汉明距离，就是对矩阵求秩

例 3：汉明码编码过程

已知校验矩阵 $H = \begin{bmatrix} 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 \end{bmatrix}$ 这是一个系统码形式 $H = [P^T \mid I]$。

1. 写出 $G = [I \mid P]$。
2. 输入序列分段编码：$1101, 0110, 010 \dots$
3. 利用 $C = m \cdot G$ 分段求出对应的码序列并拼接。

例4 循环码

https://www.bilibili.com/video/BV1b1421r7vn?t=25540.8

**例题 **: 已知循环码 $g(x) = x^3 + x^2 + 1$，输入信息 $0110$。

1. $k=4, r=3 \to n=7$。信息位 $0110 \to m(x) = x^2 + x$。
2. $m(x) \cdot x^3 = x^5 + x^4$。
3. $(x^5 + x^4) \div (x^3 + x^2 + 1)$，余数为 $x^2$。
4. 码字多项式为 $x^5 + x^4 + x^2$，对应序列为 $0110100$。

注意，冗余位是从右下角开始写

例题：利用冗余多项式法求解循环码生成矩阵

题目描述

已知循环码的生成多项式为 $g(x) = x^3 + x^2 + 1$，输入信息码序列为 $0110$。 请使用求解冗余多项式的方法，求出该 $(7, 4)$ 循环码的系统码生成矩阵 $G$，并求出信息 $0110$ 对应的系统码字。

核心参数确定

1. 生成多项式： $g(x) = x^3 + x^2 + 1$，其阶数 $r = 3$。
2. 信息位长度： $k = 4$（对应输入 $0110$）。
3. 总码长： $n = k + r = 4 + 3 = 7$。
4. 生成矩阵结构： 系统生成矩阵 $G$ 为 $k \times n$ 矩阵，结构为 $G = [I_k \mid R]$。 其中 $I_k$ 是 $4 \times 4$ 的单位矩阵，$R$ 是由冗余多项式系数组成的 $4 \times 3$ 矩阵。

解题步骤

第一步：计算每行对应的冗余多项式 $r_i(x)$

根据公式 $r_i(x) = x^{n-i} \pmod{g(x)}$（其中 $i=1, 2, 3, 4$ 分别代表矩阵的第 1 到第 4 行）：

• 第 1 行 ($i=1$): 计算 $x^{7-1} = x^6 \pmod{x^3 + x^2 + 1}$

  $x^6 = (x^3 + x^2 + x) \cdot (x^3 + x^2 + 1) + (x^2 + x)$

  余数 $r_1(x) = x^2 + x$，对应系数向量为 $(1, 1, 0)$。

• 第 2 行 ($i=2$): 计算 $x^{7-2} = x^5 \pmod{x^3 + x^2 + 1}$

  $x^5 = (x^2 + x + 1) \cdot (x^3 + x^2 + 1) + (x + 1)$

  余数 $r_2(x) = x + 1$，对应系数向量为 $(0, 1, 1)$。

• 第 3 行 ($i=3$): 计算 $x^{7-3} = x^4 \pmod{x^3 + x^2 + 1}$

  $x^4 = (x + 1) \cdot (x^3 + x^2 + 1) + (x^2 + x + 1)$

  余数 $r_3(x) = x^2 + x + 1$，对应系数向量为 $(1, 1, 1)$。

• 第 4 行 ($i=4$): 计算 $x^{7-4} = x^3 \pmod{x^3 + x^2 + 1}$

  $x^3 = 1 \cdot (x^3 + x^2 + 1) + (x^2 + 1)$

  余数 $r_4(x) = x^2 + 1$，对应系数向量为 $(1, 0, 1)$。

第二步：构建生成矩阵 $G$

将单位矩阵与对应的冗余向量合并：

$G = \begin{bmatrix} 1 & 0 & 0 & 0 & \mathbf{1} & \mathbf{1} & \mathbf{0} \\ 0 & 1 & 0 & 0 & \mathbf{0} & \mathbf{1} & \mathbf{1} \\ 0 & 0 & 1 & 0 & \mathbf{1} & \mathbf{1} & \mathbf{1} \\ 0 & 0 & 0 & 1 & \mathbf{1} & \mathbf{0} & \mathbf{1} \end{bmatrix}$

例题：汉明码的编码与校验

题目背景：

• 待传输数据码： $101101$（共 6 位）
• 任务：
  1. 确定校验码位数并进行海明码编码。
  2. 若第 5 位发生错误，说明如何通过校验定位错误。

---

第一部分：海明码编码步骤

1. 确定校验码位数 $K$

根据海明不等式 $2^K \ge n + K + 1$（其中 $n$ 为数据位，$K$ 为校验位）：

• 已知 $n = 6$，代入公式：$2^K \ge 6 + K + 1$。
• 当 $K=4$ 时，$16 \ge 11$ 成立。因此需要 4 位校验码 ($P_1, P_2, P_3, P_4$)。

2. 确定位置与排列

校验码放置在 $2^{i-1}$ 的位置（即 1, 2, 4, 8 位），数据码按序填入剩余空位：

序号	1	2	3	4	5	6	7	8	9	10
内容	$P_1$	$P_2$	$D_1$	$P_3$	$D_2$	$D_3$	$D_4$	$P_4$	$D_5$	$D_6$
数值	$P_1$	$P_2$	$1$	$P_3$	$0$	$1$	$1$	$P_4$	$0$	$1$

3. 计算校验位数值

通过二进制位权分组（异或运算/偶校验）确定 $P_i$ 的值：

• $P_1$ (校验序号二进制末位为 1 的位: 1, 3, 5, 7, 9)：

  $P_1 \oplus 1 \oplus 0 \oplus 1 \oplus 0 = 0 \Rightarrow$ $P_1 = 0$

• $P_2$ (校验序号二进制倒数第二位为 1 的位: 2, 3, 6, 7, 10)：

  $P_2 \oplus 1 \oplus 1 \oplus 1 \oplus 1 = 0 \Rightarrow$ $P_2 = 0$

• $P_3$ (校验序号二进制倒数第三位为 1 的位: 4, 5, 6, 7)：

  $P_3 \oplus 0 \oplus 1 \oplus 1 = 0 \Rightarrow$ $P_3 = 0$

• $P_4$ (校验序号二进制倒数第四位为 1 的位: 8, 9, 10)：

  $P_4 \oplus 0 \oplus 1 = 0 \Rightarrow$ $P_4 = 1$

最终海明码： $0010011101$

---

第二部分：纠错校验步骤

场景：假设第 5 位出错（由 0 变为 1）

1. 重新计算校验和 $E_i$

将受影响的位重新进行异或运算：

• $E_1$ (位 1, 3, 5, 7, 9)： $0 \oplus 1 \oplus 1 \oplus 1 \oplus 0 = 1$
• $E_2$ (位 2, 3, 6, 7, 10)： $0 \oplus 1 \oplus 1 \oplus 1 \oplus 1 = 0$
• $E_3$ (位 4, 5, 6, 7)： $0 \oplus 1 \oplus 1 \oplus 1 = 1$
• $E_4$ (位 8, 9, 10)： $1 \oplus 0 \oplus 1 = 0$

2. 定位错误

按 $E_4 E_3 E_2 E_1$ 顺序排列所得二进制数：

• 结果为：$0101$
• 转换成十进制：$(0101)_2 = 5$

结论： 校验结果指示第 5 位出错。