Infomation and Entropy (2) Codes

Posted on Edited on In , ,

Abstract. 上一章中我们提到了传输信息的过程中有涉及到 Setup 和 Outcome 两个过程，对应的是对信息的编码和解码。

这一章我们主要谈编码。

然而这一章还是非常宝宝巴士，知识基本上是初赛的真子集。

一些常见的编码。

  • Letters: BCD, EBCDIC, ASCII, Unicode, Morse Code
  • Integer: Binary, Gray, 2’s complement（二进制补码）
  • Numbers: Floating-Point
  • ……

Symbol Space Size

即字符集大小。依次考虑下面几种：

  • $2^t, t \in \mathbb{N}$，使用 $t$ 个 bit。
  • 有限，将其 ceil 到最近的一个 $2^t$，然后用 $t$ 个 bit。但是容易发现这样会剩下一些空间（spare capacity），关于这部分我们下一节进行讨论。
  • 可数无穷大，可以直接编码标号。
  • 不可数无穷大，并没有什么办法来做精确的编码。一个必要的过程是离散化（discretization），将某种层面上近似相等的对象视为同一个，然后进行编码。注意离散化的过程是不可逆的，所以没法还原。但是可用的 bit 越多，就能得到越精确的近似。

Use of Spare Capacity

这五个作用英文非常直观，但是翻译到中文反而不知道怎么处理，所以直接保留。

  • Ignore（忽略）
  • Map to other values（映射到其他值）
  • Reserve for future expansion（保留变化）
  • Control Codes（控制语句）
  • Common Abbreviations（通用缩写？）

以下面五个东西为例。第五个好像没有涉及到，它的意思是，比如说在压缩完所有小写字母之后空间还有剩余，那么可以用剩余中的一个来表示 “the” 之类的高频词。

Binary Coded Decimal（BCD）

四位当一位，A~F 都没有用到。直接 ignore 掉自然是一种办法，但是对于这六个编码我们可以想到其他几种平凡的处理方法：

  • 检查错误。如果出现了 A~F 表明出现了 transmission error。
  • 近似到 9（map to other values）
  • 忽略第一位，用来存储 2~7，这使得编码带上一定的简并性（map to other values）

Genetic Code

熟知 64 个密码子和氨基酸的对应关系不是双射的（map to other values），这样提升了编码的简并性。

同时有起始子和终止子（Control Codes）。

Telephone Area Codes

感性理解就是他知道 Telephone Area Code 这个东西以后还会有扩充，所以在编码时预留了一些位置（Reserve for future expansion）。

IP Address

Reserve for future expansion。

ASCII

里面有很多控制字符，如 \n, \t, \b 之类（Control Codes）。

Extension of Codes

很多编码被设计之初都被用来表示一些简单的东西，但是随着编码的发展它可能会被拓展，造成一些设计之初没有考虑到的偏差。

例如 ASCII 码（最初设计来用在打孔纸带上）中有下面两组例子：

  • NUL（0000000）和 DEL（1111111），NUL 最开始是被忽略的，DEL 最开始单纯表示删除，在现在的操作系统中对这两个的处理方法出现了差异。
  • CR 和 LF，也就是我们熟悉的 \r\n 的问题。

Fixed-Length and Variable-Length Codes

各有其优点。

定长编码可以方便地支持串行传输。

为了避免读错位，可以在相邻字符之间插入 1~2 个 stop bit（0），这样如果解码方读到了一个他原本期望是 stop bit 的 1，他就知道自己错位了，然后就可以尝试重新同步。

Morse Code

经典的变长编码。

解码方可以通过 · 和 - 之间的间隔大小识别一个符号的终止。

Detail: ASCII

7 位的定长编码。

从 0x80 到 0xFF 的部分在不同的系统中有不同的用处。

事实上现在的字符集是非常大的（参考汉字），所以一般都是用 2 byte 来存储信息，比如说 unicode。

Detail: Integer Codes

称最高位为 MSB（most significant bit），最低位为 LSB（least significant bit）。

下面是一些例子。

Binary Code

直接的二进制编码

Gray Code

编码无符号整数，满足 $\mathrm{popcount}(G(i)\oplus G(i+1)) = 1$。

构造方法是归纳，先构造 $n-1$ 位的格雷码 $G_{n - 1}$，然后令

$$
G_n = 0G_{n-1} + 1\overline{G_{n-1}}
$$

2’s Complement

即补码，没什么好说的。

为什么是取反后 $+1$？考虑如下事实（位数为 $S$）：

$$
\neg x = （2^S - 1) - x
$$

在 $\mathcal{Z}_{2^S}$ 下面表示一个数的相反数，有

$$
-x \equiv 2^S - x = \neg x + 1 \pmod {2^S}
$$

Sign/Magnitude

取 MSB 作为符号位，后面用 Binary Code。

1’s Complement

反码。

容易发现后面两个实际上非常垃圾，代数上性质没有补码好，而且会有 $+0$ 和 $-0$。事实上也没有什么应用场景。

Detail: The Genetic Code / IP Addresses / IP Addresses

没什么东西，不看了。