第2章 编码与组合

莫尔斯码（Morse Code）是由塞缪尔·莫尔斯发明的（1791-1872），在本书的其他章节中我们还将频繁地提到他。莫尔斯码其实是伴随着电报机的问世而被发明的，关于电报机，我们在后面也将做详细的探讨。正如通过研究莫尔斯码我们可以很方便地理解编码的本质一样，通过电报机来了解计算机硬件也是个不错的途径。

大多数人都会发现莫尔斯码的发送比接收更为简单。即使你并没有熟记莫尔斯码，也可以很方便地使用下面这张按字母表顺序排列的表格。

比起发送莫尔斯码，接收编码并进行解码要费时费力很多，因为译码者不得不根据一串由“点”、“划”组成的晦涩的编码序列来反查字母。例如，如果你接收到一串形如“划-点-划-划”的编码，那么你就必须从表的第一个字母开始逐个搜寻，直到找到与这串编码相符的字母 “Y” 为止。

问题就出在这里，因为我们现在只有一张提供“字母 → 莫尔斯码”的编码表，而缺少一张可以实现反向查询的“莫尔斯码 → 字母”译码表。在开始学习莫尔斯码的初级阶段，如果有这样的一个表无疑将是很方便的。但是要建立这样一张表，谈何容易。似乎这些字母对应的“点-划”序列并没有什么规律。

所以忘掉字母序列吧。或许根据编码中所包含点、划的多少来对其进行分组，是一个更好的组织这些编码的方法。例如，一个仅包含一个点或一个划的莫尔斯码只能代表两个字母：“E” 或 “T”。

一组含有 2 个点或划的编码组合，可以给我们呈现出4个字母——I，A，N 和 M。

一组含有 3 个点或划的莫尔斯码可以为我们表示更多的字母。

最后（如果我们不想考虑存在数字和标点符号的莫尔斯码的情况），一串由4个点或划组成的莫尔斯码就可以表示 16 个字符。

综合以上数据来看，这四张表包含了 2+4+8+16 组码字，总共表示了 30 个字母，比拉丁字母表的26字母还要多出 4 个。所以，你会注意到最后一个表中有 4 组编码是用来表示重音字母的。

当有人给你发送莫尔斯码的时候，上述四张表可能会让你的解码工作变得轻松很多。当接收到某一代表特定字母的码字后，你就可以知道其中所包含的“点”和“划”的数目，那么你至少可以很快找到对应的表格去进行查找。每个表格都组织得很规整，全部是“点”的码字被排在左上角，而全部是“划”的则被排在右下角。

你发现这四张表格在大小上的规律了么？注意看，每个表格所包含的码字数目都是前一张的两倍。这其实很好理解：每个表格所含有的码字，可以看成是在前一张表格所包含的全部码字上再加一个“点”，或者再加一个“划”而组成的新码字。

我们可以用如下这样一个列表来总结这个有趣的规律。

点和划的数目	码字的数目
1	2
2	4
3	8
4	16

在这四个表中，每张表的码字数都是前一张表码字数量的两倍，因此如果第一张表含有 2 个码字，那么第二张表则含有 2 x 2 个码字，而第三个表就有 2 x 2 x 2 个码字。下面用另一种方式呈现这个规律。

点和划的数目	码字的数目
1	2
2	2 × 2
3	2 × 2 × 2
4	2 × 2 × 2 × 2

当然，如果我们遇到了数字的自乘，就可以通过幂的方式来表示它。例如 2 x 2 x 2 x 2 就可以记作 2⁴（2 的 4 次幂）。数字 2、4、8 和 16 都是以 2 为底数的幂值，因为你可以通过使其自身乘 2 来得到它们。由此我们的总结列表也可以写成下面这种样子。

点和划的数目	码字的数目
1	2¹
2	2²
3	2³
4	2⁴

现在这个表已经变得很简洁了。如果知道了码字中“点”和“划”的数目，那么以这个数目为指数的 2 的幂运算结果就是其总共可以表示的码字数。我们可以用下面这个简单的公式来概括上述表格所表示的内容：

码字的数目 = 2^{“点”和“划”的数目}

使用 2 的幂值的形式可以表示很多码字，在下一章中，我们还将接触另外一个例子。

为了让莫尔斯码的解码过程更加简单，或许画张图会有所帮助，例如下面这张树型图。

这张图给出了所有字母及其所对应的由“点”和“划”组成的连续序列。当对一串码字进行解码时，我们需要沿着箭头从左向右进行搜寻。以“点-划-点”的码字为例来说，当你需要找出这串码字所代表的字母时，应首先从图的左边开始，选择“点”的分支；然后继续沿着箭头向右选择“划”，接着又是一个“点”。找到最后一个“点”时结果就会紧随其后出现了，没错就是字母 “R”。

如果仔细想一想，你就会发现构建这样一个表对于定义莫尔斯码规范来说是很有必要的。首先，它确保了我们不会对不同的字母定义相同的码字。其次，通过这个表我们可以用尽可能短的码字来表示所有的字母，而避免产生编码长度上的浪费。

我们可以继续加长码字至 5 位或者更长，不过这可能超出页面打印边界。一串由 5 个“点”或“划”组成的编码串可以为我们提供 32（ 2 x 2 x 2 x 2 x 2，或 2⁵ ）种扩展的码字。对于莫尔斯码中定义的 10 个数字和 16 个标点符号来说，通常这已经足够了，而实际上数字确实就是使用 5 位的莫尔斯码来表示的。但是在很多其他编码方式中，5 位码字常用来表示重音字母而不是标点符号。

为了把所有的标点符号也包含进去，编码系统必须要扩展到 6 位！扩展后将为我们提供 64（ 2 x 2 x 2 x 2 x 2 x 2，或 2⁶ ）种新增的码字，这样总共的码字就达到了 2 + 4 + 8 + 16 + 32 + 64，也就是 126 种！这对莫尔斯码来说有点太多了，甚至还留下了很多“未定义”的码字。这里“未定义”用来表示那些不代表任何字符的码字。如果你在接收莫尔斯码的时候收到了一个未定义码字，可以肯定发送方一定是出了差错。

我们很容易就能得到这样一个小公式：

码字的数目 = 2^{编码的位数}

利用它就可以继续计算出更长位数的点划序列所能表示的码字数目了。

点和划的数目	码字的数目
1	2¹
2	2²
3	2³
4	2⁴
5	2⁵
6	2⁶
7	2⁷
8	2⁸
9	2⁹
10	2¹⁰

幸运的是，我们并不需要写出所有可能的码字来计算码字的总数目。我们需要做的只是让 2 不断地与自己相乘。

莫尔斯码也被称作二进制码（ Binary Code ），因为这种编码的组成元素只有两个——“点”和“划”。这跟硬币有些类似，因为硬币落到地上只能是正面朝上或反面朝上。二元对象（例如硬币）和二进制码（例如莫尔斯码）常常使用 2 的乘方来进行描述。

上面所做的关于二进制编码的分析工作，其实是数学的一个分支，称作“组合学”或“组合分析”，而我们所作的分析则只能说是一个简单的练习。传统意义上来说，因为组合分析涉及类似像扔硬币、掷骰子这样的需求对其组合数目进行推算的问题，所以它经常被应用到概率和统计学中。但是它对于我们理解码字的组合与分解也是十分有帮助的。