2.0 编码 Codes

本章核心问题

如何用 比特数组（不止一个比特，而是多个比特组合）来表示复杂的对象（symbols）

典型通信模型

• 输入（Symbols）：原始对象（例如字母、数字、图片片段）
• 编码器（Coder）：将输入转化为比特数组
• 信道（Channel）：比特数组在空间或时间上传输
• 解码器（Decoder）：再把比特数组还原成原始符号
• 输出（Symbols）：恢复的对象

这就是最简单的通信系统模型

后续会讨论的对象种类

文字：BCD, EBCDIC, ASCII, Unicode, Morse
整数：二进制、格雷码、二进制补码
实数：浮点数表示
生物学：遗传密码（Genetic Code）
通信：电话区号、国际代码
网络：以太网地址、IP 地址、域名
多媒体：TIFF, GIF, JPEG（图像），MP3（音频），MPEG（视频）

2.1 符号空间大小 Symbol Space Size

定义

所谓 符号空间大小，就是 需要表示的符号（symbols）的总数

类似于大模型中的"词表大小"吧

情况分类

1. 符号数 = 1

• 特殊情况：只有一个符号 → 不需要任何比特
• 因为没有不确定性（uncertainty）

2. 符号数 = 2

• 可以用 1 bit 来表示
• 例如：
  • 硬币（正/反）
  • 开关（开/关）

3. 符号数 = 2 的幂

• 如果符号总数 = 2ⁿ，就可以用 n 个比特 唯一表示
• 举例：
  • 4 个符号（2² = 4）→ 需要 2 bits，例如扑克牌花色（♣♦♥♠）
  • 32 个符号（2⁵ = 32）→ 需要 5 bits，例如 32 名学生的编号
• 一般公式：$所需比特数=log_{2}⁡(符号总数)$

4. 符号数 = 有限，但不是 2 的幂

• 需要用比特数 = ⌈log₂N⌉（向上取整），但会有 冗余比特模式（unused code）
• 举例：
  • 10 个数字（0–9）：需要 4 bits（2⁴ = 16），其中有 6 种模式没用
  • 骰子（6 面）：需要 3 bits（2³ = 8），多出 2 个没用
  • 扑克牌点数（13 种）：需要 4 bits（2⁴ = 16），多出 3 个没用
  • 英文字母（26 个）：需要 5 bits（2⁵ = 32），多出 6 个没用
• 这就引出了 2.2 Use of Spare Capacity：如何处理这些没用的比特组合

5. 符号数 = 无限可数（Countably Infinite）

• 比如整数集合
• 问题：有限长度的比特串只能表示有限范围
  • 例如 4-bit 编码最多表示 0–15
  • 如果结果超出范围，就产生 overflow（溢出）
• 解决：必须增加比特数，或用特殊方式处理溢出

6. 符号数 = 无限不可数（Uncountable Infinite）

• 例如：电压的所有可能值、声音压力的连续值
• 无法用有限比特精确表示 → 需要 离散化（discretization）
  • 举例：把 [0,1] 区间的实数，用 2 bits 离散为四个代表值：
    • [0,0.25) → 0.125
    • [0.25,0.5) → 0.375
    • [0.5,0.75) → 0.625
    • [0.75,1.0] → 0.875
• 这本质上是“量化”（Quantization）
• 注意：离散化 不可逆（decode 时无法恢复原始值，只能得到近似值）
  • 但如果比特数足够大，近似结果通常“够用”
  • 浮点数表示就是基于这种思想

我的问题: 为什么比特不能是小数?

虽然平均信息量可以是小数，但在实际编码中：

• 一个具体符号 必须对应 一个确定的比特串
• 而比特串的长度必须是 整数个比特（你不能有“半个比特”）
  • 因为物理层面上传输的就是一串 0/1 电压脉冲，每个脉冲就是一整个 bit
  • 没有“0.5 个电压位宽”这种物理实现
    因此，符号的最小编码长度一定是整数比特

2.2 冗余容量的使用 Use of Spare Capacity

多余比特模式

在这种情况中, 会有空码
这些空码（unused patterns）既可能导致歧义，也可能被“合理利用”

常见处理方式

怎么感觉跟 tokenization 那么像
或者说 tokenization 本来就是一种 encode

文档里给了几种策略：

1. 忽略（Ignore）
   • 如果遇到空码，直接报错或视作无效输入
   • 好处：实现简单；坏处：传输错误时更容易出错
2. 映射（Map to other values）
   • 把空码强行映射到某个已有符号
   • 好处：节省空间，提升健壮性；坏处：可能引入歧义
3. 预留（Reserve for future expansion）
   • 把空码保留下来，以后可以增加新的符号
   • 好处：扩展性强；坏处：初期会浪费

词表里的留白

4. 作为控制码（Use for control codes）
   • 把空码用于特殊功能，而不是数据
   • 例如“停止符”“换行符”“错误信号”

比如 special token?

5. 用于缩写（Use for common abbreviations）
   • 高频符号或常用组合用空码来表示，提升效率
   • 类似于压缩编码

比如 BPE 是不是就是这种🤔

具体示例

2.2.1 二进制编码十进制 Binary Coded Decimal (BCD)

• 用 4 bits 表示十进制数字 0–9
• 表：0000 = 0, 0001 = 1, …, 1001 = 9
• 剩下的 6 种（1010–1111）没用
• 可能的策略：
  • 遇到它们 → 报错（忽略）
  • 或者 → 映射到 9（近似容错）
  • 或者 → 作为特殊符号（扩展）

2.2.2 遗传编码 Genetic Code

• DNA/RNA 里有 4 种碱基（A、C、G、T/U）
• 三联体（codon）= 3 个碱基 → 64 种组合
• 需要编码的氨基酸只有 20 种 → 存在冗余
• 处理方式：
  • 一个氨基酸对应多个 codon（提高容错率）
  • 例如 Alanine (Ala) 对应 4 个密码子（GC*）
  • 其中有些“冗余位”相当于“don’t care”
• 特殊用途：
  • AUG = 起始码（start）
  • UAA/UAG/UGA = 停止码（stop）

2.2.3 电话区号

• 1947 年 AT&T 定义美国/加拿大三位区号：
  • 规则限制：
    • 第一位 ≠ 0/1
    • 第二位 = 0/1
    • 最后一位 ≠ 相同数字
  • 这样只有 144 种有效组合（比理论 1000 少很多）
• 保留未用号码，用于后续扩展（后来确实扩展了）
  👉 这是典型的 预留扩展

2.2.4 IP Addresses

• IPv4 地址：32 bits，形式 x.x.x.x（每个 x ∈ [0,255]）
• 4,294,967,296 种组合，但部分 保留不用：
  • 私有地址（10.* / 192.168.* ）
  • 保留未来扩展
• 后来 IPv4 不够用，发展出 IPv6（128 bits），预留了极大空间（甚至“幽默地”预留给外星人）

2.2.5 ASCII

• ASCII 是 7-bit → 共 128 种
• 其中 33 个是控制符，不是字符
  • 例如 NUL（空）、BEL（响铃）、CR（回车）、LF（换行）
• 剩余 95 个才是可打印字符
• 相当于把“冗余”拿来当控制码
  👉 ASCII 的这种设计方式影响了后续所有计算机系统

2.3 编码的扩展 Extension of Codes

基本观点

• 许多编码是 人为设计的
• 一开始它们往往很简单、实用，专注于解决一个小问题
• 但随着使用场景扩大，人们不断 “挪用”或“扩展” 原有编码，结果：
  • 有的扩展依然保持了简洁、鲁棒、可扩展；
  • 有的扩展则带来了复杂性和兼容性问题
• 这种“扩展过程中的偏见”（biases from the original context）有时只是好玩，但有时会非常麻烦

ASCII 中的偏见

(1) NUL 与 DEL

• NUL (0000000)
  • 最初在纸带传输里，表示“带子开头的空白”
  • 读入时应忽略
  • 后来进入计算机，不同系统处理方式不同：
    • Unix 把 NUL 视作“字符串结束符”
    • 这导致数值处理、字符串操作等出现差异
• DEL (1111111)
  • 在打孔纸带上，原意是“把所有孔都打掉”，相当于删除一位
  • 后来进入计算机，有的系统把它当成“向后删除”，有的当成“向前删除”，有的干脆忽略
  • 这种差异导致兼容性问题

(2) CR 与 LF

• CR (Carriage Return, 回车)：打印头回到行首
• LF (Line Feed, 换行)：纸张向上走一行
• 在电传打字机时代，两者是独立的机械操作
• 但进入计算机后，不同系统选择了不同组合：
  • Unix 系统：只用 LF 表示换行；
  • 早期 Mac（OS X 前）：只用 CR；
  • Windows / DOS：要求 CR+LF 一起
    👉 结果：不同平台间文件传输经常出现“换行符错乱”的 bug
    尤其在 FTP 文本/二进制模式转换时，会导致非常麻烦的错误

启示

• 一个编码在设计时，往往考虑了当时的硬件背景（如纸带、打字机）
• 随着应用环境的变化，这些历史遗留设计可能会变成“兼容性噩梦”
• 因此，好的编码应该：
  • 简单（减少歧义）
  • 可扩展（预留空间）
  • 鲁棒（抗误差）
  • 跨平台一致（避免历史包袱）

2.4 定长与变长编码 Fixed-Length and Variable-Length Codes

基本问题

设计编码时要决定：

• 是用 定长编码（所有符号都用相同数量的比特）？
• 还是用 变长编码（高频符号用短码，低频符号用长码）？
  这会影响 实现复杂度、存储效率、解码难度、传输可靠性

定长编码 (Fixed-Length Codes)

• 特点：每个符号占用相同的 bit 数
• 优点：
  • 实现简单，解码容易
  • 编码和解码都不需要分隔符或边界标记
  • 易于并行传输（例如 8-bit 并行总线）
• 缺点：
  • 如果符号分布不均匀，高频符号也要占用和低频符号一样多的比特 → 效率低
  • 浪费存储与带宽
    例子：
• ASCII → 7 bits（后来扩展到 8 bits）
• Unicode（UTF-32）→ 32 bits 固定表示一个字符

变长编码 (Variable-Length Codes)

• 特点：不同符号用的 bit 数不同
  • 高频符号 → 短码
  • 低频符号 → 长码
• 优点：
  • 更接近熵（平均码长更短）
  • 提高存储和传输效率
• 缺点：
  • 解码需要知道边界：一个符号的码字结束后，下一个符号从哪里开始？
  • 容易产生 framing error（帧同步错误）
  • 需要设计“前缀码”或分隔符来保证无歧义
    常见应用：
• Huffman 编码、Arithmetic 编码
• Morse Code（摩斯电码）

解码的挑战：Framing Error

• 在串行传输时，解码器必须“对齐”
• 如果丢了一位或者开始错位，就会把后续码字全都读错
• 解决方法：
  • 定长码：天然无歧义
  • 变长码：通常用“前缀码”设计 → 保证任何码字都不是另一个码字的前缀
  • 串行传输中还常加 stop bits（停止位）来帮助同步
    例子：
• ASCII 在串口通信里，常加 1–2 个 stop bits
  • 如果解码器不同步，它会在“停止位应为0”的地方读到 1，从而发现错误并重新对齐

例子：Morse Code

摩斯电码是典型的 变长编码：

• 符号：点（·）、划（—）
• 高频字母 → 短码（如 E = “·”，T = “—”）
• 低频字母 → 长码（如 Q = “—·—·”）
• 单词之间的间隔也用时长来区分：
  • 点之间间隔 = 1 单位
  • 字母之间间隔 = 3 单位
  • 单词之间间隔 = 7 单位
    👉 好处：平均传输速度更快；坏处：需要额外的“时间分隔”规则，增加了同步复杂度

2.5 ASCII

起源

• 诞生时间：1963 年，由 ANSI（American National Standards Institute）提出
• 目的：提供一种统一的方式来表示英文文本字符，取代当时混乱的厂商自定义码
• 设计思想：
  • 只用 7 bits（= 128 种模式），足够表示英文字母、数字、标点符号、少量控制符
  • 留出一部分给“控制符”，方便设备交互（打印机、打字机、通信线路）

字符范围

ASCII 是 7-bit 编码，共 128 个符号：

• 33 个控制字符（0–31 + 127）
• 95 个可打印字符（32–126）

(1) 控制字符（0–31, 127）

• 功能性指令，不对应可见字符
• 例如：
  • NUL (0)：空字符（最早表示纸带开头的空白；在 C 语言里用作字符串终止符）
  • BEL (7)：响铃
  • BS (8)：退格
  • HT (9)：水平制表符（tab）
  • LF (10)：换行（Unix 系统）
  • CR (13)：回车（Mac 旧系统）
  • ESC (27)：转义
  • DEL (127)：删除（纸带上打满孔，表示“废掉这一位”）

(2) 可打印字符（32–126）

• 空格（32）
• 数字 0–9
• 大写字母 A–Z
• 小写字母 a–z
• 标点符号（, . ! ? : ; - 等）

Beyond 8-bit → Unicode

随着计算机走向全球化，8-bit ASCII 远远不够：

• 中文、日文、韩文等需要成千上万个字符。
• Unicode（16-bit / 32-bit）应运而生，目标是“一统天下”：
  • UTF-8：变长编码，兼容 ASCII（前 128 个字符保持一致）。
  • UTF-16：大部分字符用 2 字节，部分扩展用 4 字节。
  • UTF-32：定长 4 字节，直接对应 Unicode 编码点。

2.6 整数编码

基本问题

整数在计算机中最终都要用比特串表示
但不同的编码方式会影响：

• 能表示的范围（正数/负数）
• 是否存在冗余表示（例如 +0/-0）
• 算术运算是否简便（加减法是否可以直接在二进制硬件里实现）

常见编码方法

编码方式详解

无符号二进制 (Unsigned)

• 最简单：
  • 4 bits → 表示 0 到 15
  • LSB = 奇偶性标志
    • LSB : least significant bit, 有效最低位, 最右侧
    • MSB : most significant bit, 有效最高位, 最左侧
• 用途：内存地址、数组下标、计数器等
• 局限：无法表示负数

格雷码 (Gray Code)

• 定义：相邻整数的二进制表示只相差 1 bit
• 举例:

1
2
3
4
5
6
7
8

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

• 优点：
  • 在机械旋转编码器或模数转换时，避免“毛刺”
  • 因为一次只改变一位，不会出现 011 → 100 这种“中间状态全错”
• 缺点：不方便做算术运算

二进制补码 (2’s Complement)

• 最常用的有符号整数表示
• 生成方法：
  • 取正数的二进制表示 → 按位取反 → +1 → 得到负数

1
2

+5 = 0101
-5 = 1011   （0101 取反 1010，加 1 得 1011）

• 特点：
  • 表示范围 = $[-2^{n-1}, 2^{n-1}-1]$，4-bit → -8 ~ +7
  • 运算统一：加减法都可以用同一个加法器实现，不需要单独区分正负
  • 只有一个 0（0000），避免 ±0 二义性
• 缺点：负数的最小值（例如 -8）没有对应的正数（溢出问题）

我的问题: 为什么要+1

我们希望负数能和正数一样，用同一个电路（加法器）来做运算

• 如果只是简单“取反”（变成 一补码），会出现 两个零：+0 (0000) 和 -0 (1111)
• 为了避免这种歧义，并且让加法更自然，就多加了一步 +1

2.8 IP Addresses（互联网协议地址编码）

基本定义

• IP 地址是互联网中给每一个主机、路由器分配的唯一数值标识符
• 它是一种 编码系统：把“互联网上的设备”映射到“一个整数空间”
• 类比：就像电话号码编码了用户，IP 地址编码了设备

IPv4

• 结构：32-bit → 分成 4 个“字节块”，每个 8-bit，写成 x.x.x.x 的形式，每个 x 在 0–255 之间
  • 例如：204.146.46.8
• 总容量：232=4,294,967,296232=4,294,967,296 个地址
• 分配机构：由 IANA（Internet Assigned Numbers Authority）负责分配和管理

地址的使用情况

• 部分保留不用（类似“冗余位”）：
  • 0.0.0.0：保留地址
  • 127.*.*.*：回环地址（localhost）
  • 10.*.*.*, 192.168.*.*：私有网络
• 这与 2.2 冗余容量的使用 呼应：部分编码空间被预留、保留或特殊用途化

问题

• 随着互联网爆炸式发展，IPv4 地址不够用了
• 一些大公司、大学最早分配到整块地址（如 MIT，IBM），后来被戏称为“囤积地址”
• IETF 意识到未来的设备规模远超预期（冰箱、汽车、传感器都要联网）

3. IPv6（版本6）

• 解决 IPv4 地址耗尽问题
• 结构：128-bit 地址 → 写成 8 组十六进制数，每组 16-bit
  • 例如：2001:0db8:85a3:0000:0000:8a2e:0370:7334
• 容量：21282128 ≈ 3.4×10383.4×1038，几乎无限。
• 设计思想：
  • 给每个设备、甚至每个传感器都能分配独立地址
  • 预留大量空间以便未来扩展（幽默说法：甚至为“外星人”预留了地址段）
  • 新增了更多层级化的编码结构，更利于路由

4. 编码思路与信息论联系

• 有限符号空间（IPv4 = 2³²）：逐渐耗尽 → 类似“词表不够用”
• 扩展码长（IPv6 = 2¹²⁸）：彻底解决空间不足 → 类似从 ASCII 升级到 Unicode
• 冗余利用：部分地址空间保留、预留、特殊用途
• 兼容性问题：
  • IPv6 地址比 IPv4 长，所有网络设备都需要升级
  • 类似 ASCII → Unicode 的过渡，存在历史兼容性挑战

2.9 摩斯电码 (Morse Code)

历史背景

• 发明人：Samuel F. B. Morse（1791–1872），原本是一名画家
• 1830s，他受到“电流可以瞬时传输信息”的启发，发明了摩斯电报系统
• 1844 年，第一条公开电报传送：“WHAT HATH GOD WROUGHT”，从华盛顿发到巴尔的摩，引起轰动
• 后来成为 19–20 世纪最重要的远距离通信工具之一，直到无线电、电话出现之前

摩斯电码的设计

摩斯电码用 点 (·) 和划 (—) 组成信号序列，区分字母、数字和符号

• 点：短脉冲（时长 1 单位）
• 划：长脉冲（时长 3 单位）
• 间隔：
  • 符号内元素之间：1 单位
  • 字母之间：3 单位
  • 单词之间：7 单位
    时间长短 + 间隔，一起构成了解码规则

变长编码的特点

• 高频字母 → 短码
• 低频字母 → 长码
• 这样能让平均传输时间更短，整体效率更高

举例（部分）：

• E = · （英语中最常见字母 → 最短）
• T = — （第二常见 → 也很短）
• Q = —·—· （低频字母 → 较长）

这与现代的 Huffman 编码 思想几乎一致

字母频率与码长对应

摩斯当时并没有做字母统计，而是去 印刷厂 数了活字架上每个字母的数量
结果发现印刷厂备的字母频率差不多就是英语字母的常见频率
这也是 “uppercase / lowercase” 术语的来源（大写字母放在上格，小写字母放在下格）

5. Morse Code 与信息论的联系

• 它是最早的 变长码 → 节省平均传输时间
• 但它不是 前缀码（prefix-free code），所以需要用“时间间隔”来消除歧义
• 和 ASCII 对比：
  • ASCII → 定长码，简单易处理；
  • Morse → 变长码，高效但复杂