编码理论

编码理论描述如何表示、传输和恢复符号。在软件系统中，“编码”可能指压缩、错误码、线级信号或成帧约定。这些机制相互作用，但解决的问题各不相同。

信源编码与信道编码 #

信源编码使用信息内容所允许的最少比特来表示信源。无损压缩器消除统计冗余，并且必须精确还原原始字节；有损编解码器则根据特定于应用的失真模型丢弃信息。

信道编码在传输或存储之前添加结构化冗余。接收方使用这些冗余检测损坏或纠正错误。奇偶校验位只能检测部分错误模式。重复码可通过多数表决纠正错误，但会消耗大量带宽。汉明码以及现代分组码或卷积码能够在相同开销下提供更实用的距离。

因此，压缩与信道编码具有相反的比特预算：

压缩减少冗余，因为它假设信道可靠；
信道编码增加冗余，因为它假设信道存在噪声。

在纠错码之后应用压缩器通常找不到多少冗余。在压缩之后应用纠错则很有效，因为压缩后的数据流仍然需要保护。

汉明距离、冗余与码率 #

两个等长比特串之间的汉明距离是它们取值不同的位置数。分组码的最小距离 d 是任意两个有效码字之间的最小距离。解码器总能检测最多 d - 1 个比特错误，而有界距离解码器最多能纠正 floor((d - 1) / 2) 个错误。

如果一种编码将 k 个信息比特映射为 n 个传输比特，其码率为 R = k/n。其余 n - k 个比特是冗余。提高最小距离通常会降低 R，因此实现需要选择符合信道错误模型的码率和解码器。校验和或 CRC 同样会增加冗余，但其设计目标是检错而非纠错：校验失败仅表明接收到的消息无效，却不能确定原始比特。

线路编码与跳变行为 #

线路编码将比特映射为物理信号电平或跳变。它会影响时钟恢复、频谱和基线行为；它既不标识消息边界，也不修复比特错误。

不归零制（NRZ） #

在 NRZ 电平约定中，一个比特值在整个比特间隔内选择一种信号电平，另一个值选择另一种电平。因此，连续出现相同比特时不会发生跳变。接收方必须通过独立时钟、跳变丰富的编码或位填充等规则来恢复时序。

“NRZ”也可以描述跳变约定，而不是某一种通用映射，因此协议规范必须明确其极性和时序规则。实现不能仅凭名称推断映射关系。

反向不归零制（NRZI） #

NRZI 将一个比特值编码为一次跳变，将另一个值编码为无跳变。USB 使用的一种常见约定如下：

输入比特	信号行为
`0`	切换电平
`1`	保持前一电平

其他协议会反转比特含义。初始电平确定后，NRZI 与极性无关，但它不能消除长时间无跳变的情况：连续的“保持”比特仍需要时钟规则。因此 USB 使用位填充。NRZI 也不提供成帧、错误检测或错误纠正。

保持各层职责分离 #

一个健壮的链路可以包含以下所有层：

物理信号传输将比特转换为电压、光学符号或跳变。
成帧标记边界、地址，有时还包括长度字段。
信源编码压缩有效载荷。
完整性校验（例如 CRC）检测意外改变。
信道编码增加允许检错或纠错的冗余。

各层具有不同的失效模式。跳变规则无法确定帧在何处结束，帧分隔符无法纠正有效载荷中翻转的比特，压缩器也无法验证字节是否在传输后保持完整。明确说出所在层，可以避免将 NRZI、CRC 和霍夫曼编码视为可互换的“编码”。

参考资料 #

C. E. Shannon, “通信的数学理论”，Bell System Technical Journal，1948。
R. W. Hamming, “检错与纠错码”，Bell System Technical Journal，1950。
通用串行总线规范 2.0 修订版，关于 NRZI 和位填充的章节。