编码 隐匿在计算机软硬件背后的语言

$$
\begin{array}{c} \begin{array} { r l } { \mathrm { d } \hat { \mathbf { u } } \oplus } & { \stackrel { \mathrm { d e f } } { = } \frac { \boldsymbol { u } } { \mathrm { d } z } \le \boldsymbol { g } \le \boldsymbol { g } } \\ { \mathrm { u b l i d } } & { \stackrel { \mathrm { R e l } } { = } \left\{ \begin{array} { l l } { \hat { \mathbf { u } } } & { \hat { \mathbf { u } } } \\ { \hat { \mathbf { u } } \oplus \hat { \mathbf { u } } \oplus \hat { \mathbf { x } } } \\ { \hat { \mathbf { u } } \oplus \hat { \mathbf { u } } } \end{array} \right. } \\ { \mathrm { c o n d ~ i n d a t i } } \\ { \mathrm { d e t ~ t h e t i n t } } \\ { \mathrm { d e t ~ t h e t i n t } } \\ { \mathrm { c o s e ~ t i m i t i n g } } \\ { \mathrm { d e t ~ t h e t i n t } } \\ { \mathrm { d e t ~ t h e t i n t } } \\ { \mathrm { d e t ~ t h e t i n t } } \end{array} \} , \quad & { \hat { \mathbf { u } } \oplus \hat { \mathbf { u } } \oplus \hat { \mathbf { v } } \oplus \hat { \mathbf { u } } } \\ { \mathrm { d } \hat { \mathbf { u } } \oplus \hat { \mathbf { u } } \oplus \hat { \mathbf { v } } \oplus \hat { \mathbf { u } } } \\ { \mathrm { d } \hat { \mathbf { u } } \oplus \hat { \mathbf { u } } \oplus \hat { \mathbf { v } } \oplus \hat { \mathbf { u } } } \\ { \mathrm { d } \hat { \mathbf { u } } \oplus \hat { \mathbf { u } } \oplus \hat { \mathbf { v } } \oplus \hat { \mathbf { u } } } \\ { \mathrm { d } \hat { \mathbf { u } } \oplus \hat { \mathbf { v } } \oplus \hat { \mathbf { u } } } \end{array}
$$

中间护线后面仍然是6组比特串，每组中含有7个比特位。之后是最右边的护线，最右边的护线通常都为101。最右边的护线可以实现UPC的反向扫描（也就是从右到左扫描)，这一点我们将在后面解释。

因此，整个UPC对12个数字进行了编码。UPC的左边含有6个编码数字，每个数字占有7个比特位。你可以利用如下的表格来解码。

左边的编码

$$
\begin{array} { r l r l } & { 0 0 1 1 0 1 = 0 } & & { 0 1 1 0 0 0 1 = 5 } \\ & { 0 0 1 1 0 0 1 = 1 } & & { 0 1 0 1 1 1 = 6 } \\ & { 0 0 1 0 0 1 1 = 2 } & & { 0 1 1 0 1 1 = 7 } \\ & { 0 1 1 1 1 0 1 = 3 } & & { 0 1 1 0 1 1 1 = 8 } \\ & { 0 1 0 0 0 1 1 = 4 } & & { 0 0 0 1 0 1 1 = 9 } \end{array}
$$

注意，这里每个7位编码都是以0开头，以1结尾的。如果扫描仪遇到了一个位于左边的7位编码，这个编码是以1开头以0结尾的，那么它就知道自已没有将UPC正确地读入或者条形码被篡改了。另外我们还注意到每组编码都仅有两组连续为1的比特位，这就暗示每个数字对应着UPC码中的两个垂直条纹。

你也会发现，上表中每组编码都含有奇数个1。这是另一种检查错误和一致性的方法，称为奇偶校验。如果一组比特位中含有偶数个1，它就称为偶校验；如果含有奇数个1，那么它就称为奇校验。这样看来，所有这些编码都拥有奇校验。

编码隐匿在计算机软硬件背后的语言

84

破解右边的6组7位编码要用到下表。

右边的编码

$$
1 1 1 0 0 1 0 = 0 \quad
$$

$$
1 0 0 1 1 1 0 = 5
$$

$$
1 1 0 0 1 1 0 = 1
$$

$$
1 0 1 0 0 0 0 = 6
$$

$$
1 1 0 1 1 0 0 = 2
$$

$$
1 0 0 0 1 0 0 = 7 \ \AA
$$

$$
1 0 0 0 0 1 0 = 3
$$

$$
1 0 0 1 0 0 0 = 8
$$

$$
1 0 1 1 1 0 0 = 4
$$

$$
1 1 1 0 1 0 0 = 9
$$

这些编码都是之前编码的补码：之前出现0的地方，现在都换成了1，反之亦然。这些编码都是以1开头，以0结尾的。除此之外，每组编码都含有偶数个1，属于偶校验。

现在，我们就可以解读UPC了。运用以上两个表格，我们可以确定，Campbell公司的103/4盎司罐装鸡汁面汤包上的12个数字为：

0 51000 01251 7

太令人失望了。就如你所看到的，这与UPC下面印刷的数字完全相同（这样做是很有意义的，在扫描仪由于某种原因无法解读出条形码时，收银员就可以手动输入这些数字，毫无疑问你也看到过这一幕)。我们没有必要了解解码的全部过程，况且，我们也无法从中解码出任何秘密信息。不过，关于UPC的解码工作已经没有什么可做了，那30根竖条已经变成了12个数字。

第一个数字（在这里是0）被称为数字系统符。0意味着这是一个常规的UPC。如果UPC出现在杂货店中那些需要称重的商品上，例如肉、农产品，这个编码就会是2。票券的UPC的第一个数字通常是5。

接下来的5个数字表示制造商编码。这种情况下，51000就是Campbell公司的编码。所有Campbell公司的产品都有这个编码。后面的5位代码（01251）是这个公司的某种商品的编码，上例中这个数字就是指103/4盎司罐装鸡汁面。只有和制造商编码同时出现的时候这个编码才有意义。另一个公司的鸡汁面会有另外一个编码，01251在另外一个公

9 二进制数

85

司可能是指一种完全不同的产品。

与大家通常的想法相反，UPC不包含物品的价格信息。价格信息可以从商店使用的与该扫描仪相连的计算机中检索到。

最后一个数字（在这里是7）称为模校验字符。这个字符可用来进行另外一种错误检验。为了了解它是如何工作的，我们将前11个数字（在这个例子中是05100001251）各用一个字母来代替：

A BCDEF GHIJK

然后，计算下式的值：

$$
3 \times ( \mathbf { A } + \mathbf { C } + \mathbf { E } + \mathbf { G } + \mathbf { I } + \mathbf { K } \mathbf { \Omega } ) + ( \mathbf { B } + \mathbf { D } + \mathbf { F } + \mathbf { H } + \mathbf { J } )
$$

从离这个值最近并且大于或等于它的一个10的整倍数中减去它，其结果称为模校验字符(modulo check character)。在 Campbell 鸡汁面的例子中，有：

$$
3 \times ( 0 + 1 + 0 + 0 + 2 + 1 ) + ( 5 + 0 + 0 + 1 + 5 ) = 3 \times 4 + 1 1 = 2 3
$$

紧挨23并大于或等于23的10的整倍数是30，因此：

$$
3 0 - 2 3 = 7
$$

这就是印在外包装上并以UPC形式编码的模校验字符，这是一种冗余措施。如果扫描仪没有扫描到与计算机计算结果相同的模校验字符，那么计算机就视这个UPC无效。

通常情况下，要表示0\~9的十进制数字只需要4个比特位就足够了。UPC中每个数字用了7个比特位。这样，UPC总共用了95个比特位来表示11个有效的十进制数。实际上，UPC中还有空白位置（相当于9个0比特)，它们位于左、右护线的两侧。这就意味着，整个UPC需要113个比特位来编码11个十进制数，平均每个十进制数所用的比特位超过了10个！

如我们所看到的，有部分冗余对于检错来讲是必要的。这种商品编码如果能够被顾客用笔轻易地改动，那么这种产品编码措施也就没有任何意义了。

UPC可以从两个方向读，这一点是非常方便的。如果扫描装置解码的第一个数是符合偶校验（即7位编码中有偶数个1）的，扫描仪就会知道，它正从右向左扫描UPC码。

编码——隐匿在计算机软硬件背后的语言

86

计算机就会使用如下表来解码。

逆向扫描时右边數字的編码

$$
0 1 0 0 1 1 1 = 0
$$

$$
0 1 1 1 0 0 1 = 5
$$

$$
0 1 1 0 0 1 1 = 1
$$

$$
0 0 0 0 1 0 1 = 6
$$

$$
0 0 1 1 0 1 1 = 2
$$

$$
0 0 1 0 0 0 1 = 7
$$

$$
0 1 0 0 0 0 1 = 3
$$

$$
0 0 0 1 0 0 1 = 8
$$

$$
0 0 1 1 1 0 1 = 4
$$

$$
0 0 1 0 1 1 1 = 9
$$

以下是对左边数字的解码表。

逆向扫描时左边數字的編码

$$
1 0 1 1 0 0 0 = 0
$$

$$
1 0 0 0 1 1 0 = 5
$$

$$
1 0 0 1 1 0 0 = 1
$$

$$
1 1 1 1 0 1 0 = 6
$$

$$
1 1 0 0 1 0 0 = 2 \ \AA
$$

$$
1 1 0 1 1 1 0 = 7 \ \qquad
$$

$$
1 0 1 1 1 1 0 = 3
$$

$$
1 1 1 0 1 1 0 = 8
$$

$$
1 1 0 0 0 1 0 = 4
$$

$$
1 1 0 1 0 0 0 = 9
$$

所有这些7位编码都与由左向右扫描时得到的UPC完全不同。这里不会有模棱两可的现象存在。

在这本书中我们是从莫尔斯码开始接触编码的，莫尔斯码是由点和划组成的，且点和划之间由一定的时间间隔分开。尽管莫尔斯码乍看上去并不像是由0和1组成的，然而它们却是等价的。

回顾一下莫尔斯码的编码规则：划的长度等于点长度的三倍；单个字母内，点或划之间以长度与点相等的空格来分开；单词内的各个字母之间用长度等于划的空格分隔；各单词之间由长度等于两倍的划的空格分开。

让我们将分析简化一些，假设一个划的长度是点长度的两倍，而不是三倍。这就意味着一个点就是一个值为1的比特位，一个划是两个值为1的比特位，空格则是值为0的比特位。

下面是第2章中莫尔斯码的基本表。

9 二进制数

87

以下是转化为比特的结果。

注意，这里所有编码都是以1开头，以两个0结尾。结尾处的两个0代表单词内各个字母之间的空格。单词之间的空格编码则是另外一对0。因此，在莫尔斯码中“hithere’通常是这样表示的：

但是，当莫尔斯码采用比特来表示的时候，看起来就像UPC的一个截面。

101010100101000011001010101001001011010010000

用比特的形式表示布莱叶盲文比表示莫尔斯码容易得多。布莱叶盲文是6位编码。其中的每一个字母都是由6个点组成的，这些点可能是凸起的，也可能是不凸起的。就如同在第3章中所提到的那样，这些点通常用数字1\~6编号。

编码隐匿在计算机软硬件背后的语言

88

O O 4 O O O O 6

例如，单词“code”用布莱叶盲文可以这样表示：

如果突起的点代表1，平坦的点代表0，则在布莱叶盲文中，每个符号都可以用6个比特的二进制代码来表示。单词“code”中的四个布莱叶字母符号可以简单地写成：

100100 101010 100110 100010

这里，最左边的一位对应编号为1的位置，最右边的一位对应编号为6的位置。

在本书后面的章节可以看到，比特可以表示文字、图片、声音、音乐、电影，也可以表示产品编码、胶片速度、影评结果、英国军队的入侵，以及心爱之人的意图。但是，从根本来说，比特是数字。在用比特表示其他信息的时候我们所要做的就是计算有多少种可能性。这决定了我们需要的比特位数，以便每种可能性都可以分配到一个编号。

比特在逻辑学中也很重要。逻辑学是哲学和数学的奇特融合，其主要目的就是确定某个陈述是真还是假。真和假同样可以表示为1和0。

9 二进制数

89

逻辑与开关

什么是真理？亚里士多德认为真理是与逻辑相关的某种事物。《工具论》(可以追溯到公元前4世纪）这本书收集了他的理论，这也是最早在逻辑上做出全面阐述的著作。对于古希腊人来说，逻辑是在追求真理的过程中的一种分析方法，因此它被人们认为是一种哲学形式。亚里士多德的逻辑学基础是三段论法。最著名的三段论法（但是这个三段论却并没有出现在亚里士多德的著作中）是：

所有男人都必有一死；

苏格拉底是男人；

因此，苏格拉底必有一死。

在三段论中，首先假定两个条件是正确的，然后再通过这两个条件推断出结论。

苏格拉底之死这种结论似乎太简单了，然而，三段论的形式其实是多种多样的。例如，以下两个由19世纪的数学家查尔斯·道奇森（也被人们称为刘易斯·卡罗尔）提出的条件：

所有哲人都是符合逻辑的；

一个没有逻辑的人总是非常顽固的。

10

上述条件的推论一点也不明显（结论是“一些顽固的人不是哲人。”注意，这里“一些”这个词的出现完全是意料之外的)。

在过去的两千多年里，数学家们都压制着亚里士多德的逻辑学，并试图用数学符号和算子限制它的发展。19世纪前期，唯一涉足这个领域的人就是莱布尼茨（1648-1716），他早年涉足了逻辑学，而后转移到了其他兴趣上（例如，与牛顿在同一时期，独立发明微积分)。

而后乔治·布尔出现了。

乔治·布尔于1815年出生于英格兰，降临到了这个对于他来说充满不公的世界。乔治的父亲是个鞋匠，母亲曾经做过女佣，因此，按常理在当时英国森严的等级制度下，他基本上不会做出什么有别于父辈们的事业。但是他凭借着勇于探究的精神以及父亲的帮助（乔治的父亲对科学、数学和文学都有浓厚的兴趣)，乔治在年少的时候就接受了良好的教育，而这本应是上流社会中的男孩子们才能享有的特权。他学习了拉丁语、希腊语和数学。1849年，布尔凭借着他早期在数学研究上的论文成为了爱尔兰利克市皇后书院的数学系首席教授。

布尔于1854年所发表著作，其书名就彰显了一种雄心壮志。因为理性的人总是通过逻辑去进行思考，如果我们找到了一种利用数学来描述逻辑的方法，也会找到一种用数学方法来描述大脑是如何工作的。当然，现在这种观点显得很是天真（然而在那个时代这确实是非常先进的思想)。

10 逻辑与开关

91

布尔发明了一种代数，这种代数看上去与传统代数非常相似，而且运算规则也非常类似。在传统的代数中，操作数（通常为字母）代表数字，算子（通常为“+”和“×”）则用来指示这些数字之间如何运算。通常，我们应用传统代数来解决可能像这样的问题：安雅有3磅豆腐。贝蒂的豆腐是安雅的2倍。卡门的豆腐比贝蒂多5磅。迪尔得丽的豆腐是卡门的3倍。试问迪尔得丽有多少豆腐？

在解决这个问题时，我们首先要将文字叙述转化为数学语言，下面用四个字母分别表示每个人所拥有的豆腐有多少磅：

$$
\begin{array} { l } { A = 3 } \\ { B = 2 \times A } \\ { C = B + 5 } \\ { D = 3 \times C } \end{array}
$$

将以上4个表达式带入同一式子中合并，最终可以得到一个加法和乘法混合运算的式子：

$$
\begin{array} { l } { D = 3 \times C } \\ { D = 3 \times ( B + 5 ) } \\ { D = 3 \times ( ( 2 \times A ) + 5 ) } \\ { D = 3 \times ( ( 2 \times 3 ) + 5 ) } \\ { D = 3 3 } \end{array}
$$

当进行传统代数运算的时候，我们会遵循一定的规则。这些规则在实际中可能非常根深蒂固，以至于我们不再认为它们是规则，甚至可能忘记它们的名字。但规则确实是任何形式数学运算的基础。

首先是加法和乘法的交换律(commutative)。意思就是，在运算符两边的操作数可以任意调换：

$$
\begin{array} { l } { { A + B = B + A } } \\ { { \ } } \\ { { A \times B = B \times A } } \end{array}
$$

相反，减法和除法则是无法应用交换律的。

编码——隐匿在计算机软硬件背后的语言

92

加法和乘法也遵循结合律（associative)，如下：

$$
A + ( B + C ) = ( A + B ) + C
$$

$$
A \times ( B \times C ) = ( A \times B ) \times C
$$

最后，乘法遵循加法分配率（distributive）:

$$
A \times ( B + C ) = ( A \times B ) + ( A \times C )
$$

传统代数的另一个特点就是，它是处理数字的，例如，豆腐的重量、鸭子的数量、火车行驶的距离或家庭成员的年龄。布尔的天才之处就在于他把代数从数的概念中抽离出来而使其更加抽象。在布尔代数（Boole'salgebra，现在也这样叫）中，操作数不是数字而是类（class）。简单说，一个类就是一个事物的群体，它后来也被称为集合（set)。

以猫为例。猫可以分为公猫与母猫。为了简便，用字母M代表公猫，字母F代表母猫。记住，这两个符号代表的不是数字。公猫与母猫的数量会随着小猫的出生和老猫的死去而发生变化。这两个字母分别表示两类猫一有特定特征的猫的群体。当我们提到公猫的时候，就可以使用M。

我们也可以用别的字母代表猫的颜色，例如：T可以代表褐色的猫，B可以代表黑猫，W代表白猫，O代表不在T、B或W集合中的其他颜色的猫。

仍以此为例，猫还可以分为已被绝育的和未被绝育的。我们用字母N来表示已被绝育的猫，字母U表示未被绝育的猫。

在传统的（数字的）代数中，符号“+”和“×”用来表示加法和乘法。在布尔代数中，也有“+”和“×”这样的符号，这很可能造成混淆。所有人都知道在传统代数中如何将数字相加或相乘，但是我们如何将类相加或相乘呢？

然而，在布尔代数中，并没有实际意义上的加或乘。而符号“+”和“×”表示的是完全不同的意义。

在布尔代数中，符号“+”表示两个集合的并集。两个集合的并集的意思就是指第一个集合中的所有元素与第二个类中所有元素的集合。例如，B+W表示的就是所有黑猫和白猫的集合。

10 逻辑与开关

93