4.1 扩展的系统模型（Extension of System Model）

核心思想

• 在原有的通信/存储/计算模型中加入 信道编码 (Channel Coding)
• 做法：在压缩后的比特序列上 增加冗余比特
  • 目的：在传输或存储时即使发生错误，也能检测甚至纠正
• 系统结构：
  源编码器 → 压缩器 → 信道编码器 → [有噪声信道] → 信道解码器 → 解压器 → 源解码器

历史/直观类比

• 类似于寄快递时，除了写地址（信息本身），还会加“校验码”或“包装缓冲”来保证信息不被损坏
• 在古代电报里，常常会加上“确认码”或“冗余字母”防止误抄

数学直觉

• 信道编码器：把 $k$ 个数据比特扩展为 $n$ 个比特（$n>k$）
• 多出来的 $n-k$ 个是 冗余位，它们使得合法码字之间有足够大的“距离”（后面会用汉明距离来刻画）
• 解码器收到数据后：
  • 如果落在“合法区域” → 直接解码
  • 如果落在“非法区域” → 检测错误 / 找到最近合法码字进行纠错

优缺点

✅ 优点

• 即使有噪声，原始信息也能被保留或恢复
• 为后续的“错误检测与纠错”打下基础
  ⚠️ 缺点
• 增加了额外的比特，降低有效传输率（码率 < 1）
• 信道编码器/解码器的设计复杂度更高

4.2 错误是怎么发生的（How do Errors Happen?）

核心思想

• 错误来源多样：无论是通信、存储还是计算，都会引入错误
• 统一抽象：把所有错误统一建模为 比特翻转 (0↔1)

我的问题: 那比特丢失了咋办呢?

• 在 比特翻转模型 中：接收端不知道哪一位错了 → 只能靠冗余来检测/纠正
• 在 比特擦除模型 中：接收端知道“哪一位不可靠”，但不知道它的值 → 更容易恢复，因为只需推断那一位的内容
  例如：
• 若用 汉明码 (7,4,3)，它可以纠正 1 位翻转错误；
• 在擦除信道下，同样的码可以恢复 2 位擦除，因为位置是已知的

常见物理原因

• 通信链路：电话线噪声、无线干扰
• 存储介质：CD/DVD 被划伤，磁盘坏道
• 硬件电路：存储单元失效，逻辑门因电源电压波动而出错

错误模式

• 独立错误 (Independent errors)
  • 假设每个比特独立发生翻转
  • 数学上处理方便，是最常见的理论模型
• 突发错误 (Burst errors)
  • 邻近比特倾向于同时出错，原因往往是同一个物理事件（如划痕、串扰）
  • 在工程上更常见，也更难处理

数学直觉

• 输入码字 $x$，输出码字 $\hat{x}$
• 汉明距离 $d(x,\hat{x})$ 用来度量错误个数：
  • $d=0$ → 无错误
  • $d=1$ → 单比特错误
  • $d=k$ → $k$ 个比特错误
• 如果错误不是独立的，就需要专门的编码策略（如交织、里德–所罗门码）来对抗突发错误
  好的 👍 那我来整理 4.3 检测 vs. 纠错 (Detection vs. Correction) 成笔记格式：

4.3 检测 vs. 纠错（Detection vs. Correction）

核心思想

• 面对错误有两条路：
  1. 检测 (Detection)：发现有错 → 通知系统/用户重传
  2. 纠错 (Correction)：发现有错并直接修复
• 这两种方法都依赖在消息中加入 冗余比特

为什么需要冗余？

• 如果所有 $n$ 位比特串都合法，那么任何错误都会把一条合法消息变成另一条合法消息 → 无法察觉
• 解决办法：限制合法码字集合
  • 让大部分比特模式变成“非法”
  • 出错后，高概率落入非法模式 → 可检测
  • 如果非法模式距离某个合法码字最近 → 可以纠正成该合法码字

类比：自然语言

• 英文中的冗余度估计有 50%
• 即使少几个字母、词顺序错误，人类也能理解
• 这就是“自然冗余”带来的错误检测/纠错能力

信息论视角

• 信道编码器：增加冗余，保持信息可逆
• 有噪声信道：引入“错误信息”
• 信道解码器：丢弃噪声信息，保留原始信息 → 不可逆（因为丢掉了错误细节）

4.4 汉明距离（Hamming Distance）

核心思想

• 定义：两个等长比特串之间，不同位的个数
  • 例：0110 和 1110 的汉明距离 = 1
  • 相同的串距离 = 0
• 意义：度量“两个码字之间有多远”，是错误检测与纠错能力的核心指标

为什么不用“数值差”？

• 表面直觉：0110 (6) 和 0111 (7) 数值差 1，好像很接近
• 但 0110 和 1110 数值差 8，却只改了一位
• 所以信息论里不看“数值差”，只看 位错数量

与错误的关系

• 如果输入码字 $x$，输出码字 $\hat{x}$：
  • 无错：$d(x,\hat{x}) = 0$
  • 单错：$d(x,\hat{x}) = 1$
  • $k$ 个错：$d(x,\hat{x}) = k$
• 编码器的设计目标：
  • 检错：任意两个合法码字间距离 ≥ 2（否则 1 位错可能把一个合法码字变成另一个合法码字）
  • 纠 1 错：合法码字间距离 ≥ 3（这样接收端可以找到“最近邻码字”来恢复）

详细展开

1. 先看“合法码字”的概念

• 我们只允许某些比特串作为合法消息（码字），别的比特串都算“非法”
• 这样做的目的是：如果信道出错，把合法码字推到“非法区”，接收端就能发现异常

2. 检错条件：距离 ≥ 2

• 假设有两个合法码字 $A=000$，$B=111$，它们的汉明距离是 3
• 如果发生 1 位错误：
  • $000 \to 001$，这个新串不在合法集合中 → 立刻检测到错误a
• 为什么要求“距离 ≥ 2”？
  • 如果两个合法码字只差 1 位（距离 = 1），那一位翻转后，$A$ 就会变成 $B$，接收端以为它收到了一个完全合法的消息，错误就无法被发现
    👉 结论：
    只要合法码字之间的最小距离 ≥ 2，就能检测单比特错误。

3. 纠 1 错条件：距离 ≥ 3

• 还是 $A=000$，$B=111$，距离 3
• 如果 $000$ 传输过程中 1 位错了 → 比如收到 001：
  • 它距离 $000$ 是 1，距离 $111$ 是 2
  • 接收端可以说：“更靠近 $000$，所以应该纠正成 $000$”
• 为什么要求“距离 ≥ 3”？
  • 如果两个合法码字只差 2 位（距离 = 2），那出现 1 位错误后，新串同时距离两边都只有 1 → 模棱两可，无法唯一确定原来是谁
    👉 结论：
    要能唯一确定并修正 1 位错误，合法码字之间的最小距离必须 ≥ 3。

类比理解

• 几何直觉：
  • 想象每个码字是 $n$ 维立方体的一个顶点
  • 汉明距离就是“走多少条边才能从一个点走到另一个点”
  • 距离越大 → “安全半径”越大 → 错误容忍度越高

4.5 单比特（Single Bits）

核心思想

• 最简单的错误控制：重复发送同一个比特
• 利用“冗余 + 多数表决”来实现检错或纠错

双重冗余（Double Redundancy）

• 编码：
  • 0 → 00
  • 1 → 11
• 解码：
  • 如果接收端得到 01 或 10 → 检测到错误
• 局限：
  • 如果刚好两位都出错（00→11 或 11→00），错误无法被检测
• 码率：$1/2 = 0.5$

三重冗余（Triple Redundancy）

• 编码：
  • 0 → 000
  • 1 → 111
• 解码（多数表决）：
  • 接收到 3 位，若不一致 → 取出现次数最多的那个
  • 例如收到 001 → 判定为 0
• 性能：
  • 能够纠正 1 位错误
  • 或者用来检测 2 位错误（但不能两者兼得）
• 码率：$1/3 ≈ 0.33$

四重冗余及更多

• 四重冗余可以同时做到“检测 3 错”或“纠正 1 错 + 检测 2 错”
• 冗余越多，可靠性越强，但码率越低（效率下降）

数学直觉

• 码率定义：$R = \dfrac{\text{原始比特数}}{\text{编码后比特数}}$
  • 双重冗余：$R = 1/2$
  • 三重冗余：$R = 1/3$
• 适用场景：
  • 错误概率低 → 少量冗余即可
  • 错误概率高 → 即便三重冗余也可能失败（比如突发错）

工程局限

• 三重冗余对 独立随机错误 很有效
• 但若是 突发错误（如 CD 划痕导致连续比特丢失），可能一整个块都错 → 冗余再多也难以恢复
  好的 👍 下面整理 4.6 多比特（Multiple Bits）：

4.6 多比特（Multiple Bits）

当传输的不是单个比特，而是一整段比特串时，需要更强的编码方法。常见思路是在多个位置加校验位，让错误能被检测甚至纠正

4.6.1 奇偶校验（Parity）

• 方法：给 8 位数据加 1 位奇偶校验位
  • 规则：让整个 9 位串中 “1 的个数”为偶数（偶校验）
• 解码：数一数 1 的个数，如果是奇数 → 检测到错误
• 特点：
  • 能检测 奇数位错误（1 位、3 位…）
  • 不能定位错误、也不能纠错
  • 如果校验位本身出错，数据部分其实是对的
  • 码率：$8/9 \approx 0.89$
• 应用：内存校验、早期通信协议

4.6.2 矩形码（Rectangular Codes）

• 构造：把 8 个数据位排成 $2 \times 4$ 矩阵
  • 每行加一个行校验位
  • 每列加一个列校验位
  • 最后再加一个总校验位
  • 一共 15 位
• 解码：
  • 检查 3 行 + 5 列的奇偶性
  • 若只有一位错误：某行、某列都出错 → 锁定交点，翻转即可 → 单错纠正
  • 若有两位错误：出现特殊的错位模式 → 能检测到，但不能纠正
  • 若有三位错误：可能“伪装成”单错 → 会被误纠正
• 本质：利用二维排列定位错误位置

4.6.3 汉明码（Hamming Codes）

• 目标：用最少的校验位实现单错纠正
• 原理：
  • 每个校验位检查一组特定位置的比特
  • 解码时，根据哪几组检查失败 → 得到错误比特的二进制编号
  • 翻转该位即可恢复
• 例子：$(7,4,3)$ 汉明码
  • 7 位码：4 位数据 + 3 位校验
  • 最小汉明距离 $d=3$ → 能纠正 1 位错误，并能检测 2 位错误
• 扩展：
  • $(15,11,3)$、$(31,26,3)$ …
  • 码率越来越高，但依旧只能纠正 1 位错误
• 优点：结构优雅，被称为“完美码”

汉明码具体示例

1. 位的位置

我们有 7 个位置：

1
2

位置： 1 2 3 4 5 6 7
类型： P P D P D D D

• P = parity（校验位）
• D = data（数据位）
• 数据放在 3,5,6,7
• 校验位放在 1,2,4

2. 编码规则

• 校验位 1 (P1)：检查所有位置编号二进制里最低位 = 1的比特（1,3,5,7）
• 校验位 2 (P2)：检查编号二进制里次低位 = 1的比特（2,3,6,7）
• 校验位 4 (P4)：检查编号二进制里第三位 = 1的比特（4,5,6,7）

3. 举例：编码

假设 4 个数据位是 d3=1, d5=0, d6=1, d7=1
我们先把它们放好：

1
2

位：   1 2 3 4 5 6 7
值：   ? ? 1 ? 0 1 1

• P1 检查 (1,3,5,7)：目前 3,5,7 = 1+0+1=2（偶数），所以 P1=0
• P2 检查 (2,3,6,7)：目前 3,6,7 = 1+1+1=3（奇数），所以 P2=1（凑成偶数）
• P4 检查 (4,5,6,7)：目前 5,6,7 = 0+1+1=2（偶数），所以 P4=0
  最终码字：

1

0 1 1 0 0 1 1

4. 解码与纠错

假设传输后收到：

1

0 1 1 1 0 1 1

和原来相比，第 4 位错了（0→1）
我们让解码器重新做三个校验：

• 校验 1 (检查位 1,3,5,7)：得到 0+1+0+1=2（偶数） ✅
• 校验 2 (检查位 2,3,6,7)：1+1+1+1=4（偶数） ✅
• 校验 4 (检查位 4,5,6,7)：1+0+1+1=3（奇数） ❌
  错误综合症是：

1

P4 错，P2 对，P1 对 → 二进制 100 = 4

→ 出错位置是第 4 位。我们把第 4 位翻转回 0，就恢复了原始数据。

5. 扩展理解

• 如果有 两个错误，比如第 4 位和第 5 位同时错了，那么综合症可能会指向“一个完全错误的位置”，所以汉明码只能保证纠正 1 位错，检测 2 位错。
• $(15,11,3)$ 就是相同原理：11 数据位 + 4 校验位 → 共 15 位，可以纠正 1 位错。

为什么是 1,2,4 位?

1. 汉明码的目标

• 我们要能用若干个 校验位 唯一标识出 出错的位置（包括“无错”）
• 对 $(7,4,3)$：
  • 总共有 7 位
  • 可能出错的位置：1–7（共 7 种），再加上“无错误”这种情况 → 共 8 种
  • 所以至少需要 3 个校验位（因为 $2^3=8$，刚好能编码 8 种情况）

2. 为什么选 1,2,4？

这是因为 1,2,4…（2 的幂次位置） 在二进制里有独特的作用：

• 位置编号：

• 1 2 3 4 5 6 7

  1 → 001 2 → 010 3 → 011 4 → 100 5 → 101 6 → 110 7 → 111

• 这三个二进制位正好可以用来表示“校验结果”
  于是规定：
• P1 负责检查所有“编号二进制里最低位 = 1”的位置 → 覆盖 1,3,5,7
• P2 负责检查所有“编号二进制里次低位 = 1”的位置 → 覆盖 2,3,6,7
• P4 负责检查所有“编号二进制里第三位 = 1”的位置 → 覆盖 4,5,6,7

3. 解码时怎么用？

• 收到消息后，重新计算三组奇偶校验
• 把“哪几组失败了”写成一个三位二进制数：
  • 000 → 无错
  • 001 → 第 1 位错
  • 010 → 第 2 位错
  • 011 → 第 3 位错
  • 100 → 第 4 位错
  • 101 → 第 5 位错
  • 110 → 第 6 位错
  • 111 → 第 7 位错

总结对比

4.7 分组码（Block Codes）

核心思想

• 我们可以把编码后的比特看作定长分组（block）
• 一个分组中包含：
  • $k$ 个 数据位 (payload)
  • $n-k$ 个 冗余位 (parity bits)
• 记作 $(n,k)$ 分组码

最小汉明距离 $d$

• 除了 $(n,k)$，还常常写成 $(n,k,d)$，其中：
  • $n$ = 总码长
  • $k$ = 数据位数
  • $d$ = 任意两个合法码字的最小汉明距离
• $d$ 决定了码的能力：
  • 检错能力：最多检测 $d-1$ 位错误
  • 纠错能力：最多纠正 $\lfloor \tfrac{d-1}{2} \rfloor$ 位错误

示例：汉明码 $(7,4,3)$

• $n=7$：每组 7 位
• $k=4$：其中 4 位是数据
• $d=3$：任意两个合法码字至少相差 3 位
• 性能：
  • 能纠正 1 位错误
  • 能检测 2 位错误

一般直觉

• 更多冗余位 → 更大的距离 $d$ → 更强的纠错能力
• 但同时 → 码率 $R=\tfrac{k}{n}$ 降低，效率变差
• 工程中要在“可靠性 vs. 效率”之间权衡

4.8 高级码（Advanced Codes）

背景

• 前面讲的汉明码 $(7,4,3)$ 等，最小距离 $d=3$ → 只能纠 1 位错，检 2 位错
• 如果要对抗更多错误（比如多位错误、突发错误），就需要设计更强的编码

BCH 码

• 全称：Bose–Chaudhuri–Hocquenghem 码
• 一类重要的循环码
• 能把最小距离 $d$ 提高到大于 3，从而纠正多个比特错误
• 在实际中常用于卫星通信、存储系统

Reed–Solomon (RS) 码

• 1960 年由 Reed 与 Solomon 提出（MIT Lincoln Lab）
• 特点：基于字节而不是比特来工作
• 常见参数：
  • $(256,224,5)$
  • $(224,192,5)$
• 应用：CD/DVD 播放器、二维码
  • 可以抵御突发错误（例如 CD 表面一大片划痕）
• 原理直觉：把数据看作有限域上的多项式，在多个点取值，错误恢复就变成“多项式插值”问题

卷积码（Convolutional Codes）

• 与分组码（block code）不同，卷积码不是按固定块处理，而是让编码器带有记忆
• 输出不仅依赖当前输入，还依赖前面若干位输入
• 优点：能更好地利用“上下文”来检测/纠错
• 应用：无线通信、卫星链路
• 一类重要的卷积码：栈形码 (Trellis Codes)，常用于调制解调器

总结

• BCH/RS 码：适合应对多个比特或突发错误
• 卷积/栈形码：适合流式通信，有记忆，纠错能力更强
• 工程难点：要在效率、纠错能力、实现复杂度、速度之间平衡

4.9 校验位（Check Digits）

核心思想

• 在 长编号（如银行卡号、书籍编号）里，常会额外加一个“校验位”
• 功能类似奇偶校验：
  • 能发现输入错误（如打错一位、相邻位交换）
  • 只能检错，不能纠错
• 常见于：信用卡、ISBN、ISSN、软件注册码

信用卡号码（Luhn 算法）

• 由 IBM 的 H. P. Luhn 在 1954 年提出
• 步骤（简化描述）：
  1. 取卡号的部分数字（隔一位取）
  2. 对这些数字做加和，部分再加权
  3. 把所有数字加起来
  4. 如果结果能被 10 整除 → 合法
• 性能：
  • 能检出 单个数字错误
  • 能检出大多数 相邻数字交换错误
• 应用：Visa、MasterCard、Amex 等

ISBN（国际标准书号）

• 唯一标识一本书
• 13 位版（2007 以后）：
  • 与超市的 UPC 条码兼容
  • 校验位算法：加权求和，取模 10
• 10 位版（2007 以前）：
  • 用模 11 校验
  • 校验位可能是 X（表示 10）
• 性能：
  • 能检出单个数字错误
  • 能检出大多数相邻交换错误

ISSN（国际标准连续出版物号）

• 8 位编号，用于期刊、杂志等
• 前 7 位是编号，第 8 位是校验位
• 算法：加权求和取模 11，余数 10 记作 X
• 保证输入错误或交换时能被检出

小结

• 这些日常编号的校验位，本质上就是 一种冗余
• 优点：
  • 算法简单，效率高，日常使用方便
• 局限：
  • 只能检测，不能自动纠错
  • 仍有一部分错误模式可能漏检