编码-二进制

编码

说起编码,在脑海中第一时间想到的肯定是什么 UTF-8GBK 等等等等,但是我们这里的编码指的并不是这些编码类型,而是指定一本书的书名。

这本书的文笔很特殊,它不像那些讲原理的书里面全是代码。也不像那些讲理论的书里面全是文字。在这本书中作者通过直接而又简单的例子,为我们诠释了编码的奥秘。

很推荐没看过这本书的人去看看这本书,相信会有不少收获,本篇博客会总结一下书中的部分内容,内容主要讲的是计算的的语言-二进制。

交流

人与人之间,如果想要交流可以通过很多种方式,而最简单的方式就是说话,比如中国人说的就是中文,美国人说的就是英语,只要你听得懂对面说的语言,就能和对方交流。

然而声音的传播范围是有限制,如果你想和一个离你很远的人交流,就必须要考虑使用别的方式,最简单的方式就是写信。写信本质就是将上面说到语言转换成文字并写在纸上,最后通过邮局寄给你想要寄的人。

一次简单的交流

这是一个关于交流的故事,从前有个小孩,他的好朋友就住在他的对面,他们的窗户是相对的。每当到了晚上,它俩总喜欢在睡觉前扯扯闲话,开开玩笑。

在刚开始的时候,他们可以通过一些简单的肢体来传达信息,不过前提是房间的灯是亮的,随着时间一点一点的推移,他们的父母会宣布关灯,这时他们没法在通过先前的方式进行交流了,于是他们又想到了一个新的交流方式。

手电筒,基本上每个房间里面都会有东西,方便在没电的时候应急使用。这个时候他俩决定通过使用手电筒来进行交流,通过在空气中笔画出想要说的话,对方就能看见。

不得不说这是一个不错的交流方式,有效的解决了在没有灯的情况下也能交流这里目的。但是如果先要说的话比较复杂,就很难在通过这种方式来表达了

这个故事是不是很像某些电影中的情节,具体就是通过控制灯的开光状态,调整开与关之间间隔来传递信息。

摩尔斯电码

很显然,通过使用手电筒在空气中笔画出我们想要表达的信息是一种不现实的方法,于是我们可以摩尔斯电码与手电筒进行结合,来让我们的手电筒交流变的更加高效。

在摩尔斯电码中,有两个关键的表达方式,分别为 dot 和 dash,翻译过来就做。下面是 26 个音文字母通过 dot 和 dash 的表示方式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
A -> dot dash
B -> dash dot dot
C -> dash dot dash dot
D -> dash dot dot
E -> dot
F -> dot dot dash dot
G -> dash dash dot
H -> dot dot dot dot
I -> dot dot
J -> dot dash dash dash
K -> dash dot dash
L -> dot dash dot dot
M -> dash dash
N -> dash dot
O -> dash dash dash
P -> dot dash dash dot
Q -> dash dash dot dash
R -> dot dash dot
S -> dot dot dot
T -> dash
U -> dot dot dash
V -> dot dot dot dash
W -> dot dash dash
X -> dash dot dot dash
Y -> dash dot dash dash
Z -> dash dash dot dot

//例子
Hello -> dot dot dot dot dot dot dash dot dot dot dash dot dot dash dash dash

我们可以通过打开打开手电筒过一秒在关闭手电筒的方式来表示一个 dot,在通过打开手电筒过两秒在关闭手电筒来表示一个 dash。

像我们都知道的国际救援信号 SOS,它并不是某三个单词的缩写而是摩尔斯码中 dot dot dot dash dash dash dot dot dot 的意识。因为标示简单所有被用作为国际救援信号,翻译过来就是 SOS。

假设在日常的生活中我们的语言变成了摩尔斯电码,那么我们听到的只有点和划这两个字了,这到底是变的简单还是复杂了呢?

解码

通过上面的字母对照关系,我们可以开始的写出我们想要表达的信息的摩尔斯电码,但是如果给你一段摩尔斯电码要你转成字母,就会比较麻烦,所以我们还需要一个专门用来解码的对照表:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//通过 dot dash 的个数来区分

//一个
dot -> E
dash -> T

//两个
dot dot -> I
dash dot -> N
dot dash -> A
dash dash -> M

//三个
dot dot dot -> S
dot dot dash -> U
dot dash dot -> R
dot dash dash -> W
dash dot dot -> D
dash dot dash -> K
dash dash dot -> G
dash dash dash -> O

//四个
dot dot dot dot -> H
dot dot dot dash -> V
dot dot dash dot -> F
dot dot dash dash -> 德语 U
dot dash dot dot -> L
dot dash dot dash -> 德语 A
dot dash dash dot -> P
dot dash dash dash -> J
dash dot dot dot -> B
dash dot dot dash -> X
dash dot dash dot -> C
dash dot dash dash -> Y
dash dash dot dot -> Z
dash dash dot dash -> Z
dash dash dot dash -> Q
dash dash dash dot -> 德语 O
dash dash dash dash -> 德语 S

通过上面的对照表,我们就可以通过摩尔斯电码的个数快速知道其表示的字母是什么。

观察上面的对照表的个数,你会发现一个规律,通过这规律我们可以找摩尔电码的个数和字母个数的关系,如下:

点和划的个数 可表示的字母个数
1 2
2 4
3 8
4 16

或者

点和划的个数 可表示的字母个数
1 2
2 2 x 2
3 2 x 2 x 2
4 2 x 2 x 2 x 2

通过上面表格的规律,我们可以算出如果有 5 个点或划,那么一共可以表示 32 个字母。

除了通过摩尔斯电码的个数来进行解码,我们还可以通过下面这个树形图来让界面变的更快,如下:

  • dot -> E
    • dot -> I
      • dot -> S
        • dot -> H
        • dash -> V
      • dash -> U
        • dot -> F
        • dash -> 德语 U
    • dash -> A
      • dot -> R
        • dot -> L
        • dash -> 德语 A
      • dash -> W
        • dot -> P
        • dash -> J
  • dash -> T
    • dot -> N
      • dot -> D
        • dot -> B
        • dash -> X
      • dash -> K
        • dot -> C
        • dash -> Y
    • dash -> M
      • dot -> G
        • dot -> Z
        • dash -> Q
      • dash -> O
        • dot -> 德语 O
        • dash -> 德语 S

通过上面这个树形结构,就可以非常快速的知道一个位数小于等于四的摩尔斯电码所表示是的字母。

扩展

通过上面的分析,我们知道了四位的摩尔是电码最多能表示 2 + 4 + 8 + 16 = 30 个字母,而如果想要表示更多的信息,如阿拉伯数字,表达符号等等,我么那就需使用五位或者六位的摩尔斯电码。

摩尔斯电码的位数和能表示信息的公式如下:

2摩尔斯电码位数 = 表示信息的个数

例子:

点和划的个数 可表示的字母个数
1 21 = 2
2 22 = 4
3 23 = 8
4 24 = 16
5 25 = 32
6 26 = 64
7 27 = 128
8 28 = 256
9 29 = 512
10 210 = 1024

小结

通过上面的内容,不难看出摩尔斯电码就是一种编码,只不过里面只有 dot 和 dash。这种编码和我们说的话,写的字的作用是一样的。

在上面的解码中,使用的方法在数学上叫做组合学,类似的例子有很多,比如抛硬币,掷骰子等等。在算法中的二分查找和那么树形图有点类似。

布莱叶盲文

上面说到了人们为了让自己表达的信息能够传递的更远,会把文字写在纸上然后寄出去,而如果对方是个盲人该怎么知道纸上的文字呢?

历史上发明编码的人有很多,上面的摩尔斯电码只是其中的一种,而有一种专门为盲人设计的编码,那就是布莱叶盲文。

路易·布莱叶与 1809 年生于法国的库普雷,小时候因为顽皮不小心导致双目失明。按照当时的情况,布莱叶将会在无知和平困中度过自己的一生,但是布莱叶不服气,在他 10 岁的时候被送去了巴黎皇家盲人学院学习。

盲人在学习中,最大的障碍就是无法阅读书籍。为了解决这个问题,巴黎皇家盲人学院的创始人发明了一种在纸由凹凸的点组成的文字系统。但是这种文字系统因为设计上的缺陷,用起来比较困难。

原因在于,巴黎皇家盲人学院的创始人自身并不是一个盲人,他会被自身的感知模式所禁锢。比如一个字母 A 通过他发明的盲人文字系统写作为:

1
2
3
4
    1
1 1
1111111
1 1

正如前面所说的,因为他自身不是盲人,所以他认为就算要发明一种文字系统给盲人,那么这种系统就必须要和现有的文字系统长的一样

在 1821 年,一名加夏尔·巴比尔的退伍军人来到布莱叶他的学校,像他们展示了自己发明的一种文字系统,这种文字系统用与军队在黑夜中交流,因为没有光线所以只能通过手来触摸凸起来的点。通过这些凸起来的点就可以传递信息。

不过这种文字系统非常复杂,但是布莱叶很快就学会了,并且布莱叶很喜欢这种用凸起来的点来表达的方式。3 年以后,布莱叶就基于这些凸起来的点发明了他自己的文字系统。

在日常的生活中处处充满了这些凸起来的点比如在电梯楼层按钮上,这些都要归功于布莱叶,因为就是因为有了这些点,盲人才能够像正常人一样做电梯。

在布莱叶盲文中,没有文字(包括字母,数字,标点符号),都是由 6 个点组成,每个点有凸起和没有凸起两种状态。具体如下:

1
2
3
4
5
6
7
8
9
1 -> 点点 <- 4
2 -> 点点 <- 5
3 -> 点点 <- 6

//例子
10
01
10
//136 为凸起,246是平的

在布莱叶盲文中,每个点只会有凸起和不凸起这两种状态,这和我们前面的摩尔斯电码中的 dot 和 dash 是一样的,所以通过公式我们可以算出由六个点组成的布莱叶盲文可以表示 26 = 64 个文字。

下面是使用布莱叶盲文表示 25 个英文字母,如下:

1 表示凸起的点,0 表示没有凸起来的点。

行数\字母 a b c d e f g h i j
第一行 10 10 11 11 10 11 11 10 01 01
第二行 00 10 00 01 01 10 11 11 10 11
第三行 00 00 00 00 00 00 00 00 00 00
行数\字母 k l m n o p q r s t
第一行 10 10 11 11 10 11 11 10 01 01
第二行 00 10 00 01 01 10 11 11 10 11
第三行 10 10 10 10 10 10 10 10 10 10
行数\字母 u v x y z
第一行 10 10 11 11 10
第二行 00 10 00 01 01
第三行 11 11 11 11 11

这里没有 w 的原因不知道是为什么,不过在下面的表中有 w。

通过广场上面的表格,可以找出一个规律,那就是字母 k ~ t 的布莱叶盲文只不过是 a ~ j 的布莱叶盲文的基础上将第三行左边的点改为了 1。同理,u ~ z 就是在 k ~ o 的基础上把第三行右边的点改成了 1。

通过这个规律我们可以扩展出更多多的布莱叶盲文,比如我们可以在 a ~ t 的基础上,将第三右边的点设置成 1,然后久了新的意思,具体如下:

行数\字母串 ch gh sh th wh ed er ou ow w(will)
第一行 10 10 11 11 10 11 11 10 01 01
第二行 00 10 00 01 01 10 11 11 10 11
第三行 01 01 01 01 01 01 01 01 01 01

比如我们想要用布莱叶盲文表示 about 这个单词,可以这么写:

行数\字母 a b ou t
第一行 10 10 10 01
第二行 00 10 11 11
第三行 00 00 01 10

换挡码 (shfit codes)

除了上面的改变方式,在布莱叶盲文中,我们可以使用特定的前缀来改变后面盲文的含义,比如在布莱叶盲文中是这么表示数字的,如下:

行数\数字 1 2 3 4 5 6 7 8 9 0
第一行 10 10 11 11 10 11 11 10 01 01
第二行 00 10 00 01 01 10 11 11 10 11
第三行 00 00 00 00 00 00 00 00 00 00
行数\特殊字符 st (/) ing ble (#) ar com (_)
第一行 01 01 01 01 00
第二行 00 00 01 01 00
第三行 10 11 11 10 11

数字 256 用布莱叶盲文表示为:

行数\数字 ble 2 5 6
第一行 01 10 10 11
第二行 01 10 01 10
第三行 11 00 00 00

可以看多,数字 1 ~ 6 的布莱叶盲文其实就是字母 a ~ j,只不过在表示数字的时候需要加 ble 这个前缀。

这种通过添加前缀来改变后面编码的含义的手段,叫做换挡码

逃逸码 (escape codes)

除了上面说到的换挡码之外,还有一种被称作逃逸码的东西,表示方式和上面一样,不过逃逸码只能改变跟随特殊字符的一个字母,具体如下:

行数\特殊字符 大写字母
第一行 00
第二行 00
第三行 01

使用这个特殊符号,我们可以将布莱叶名字表示为:

行数\字母 大写字母 l ou i s 分隔 大写字母 b r a i l l e
第一行 00 10 10 01 00 10 10 10 01 10 10 10
第二行 00 10 11 10 00 10 11 00 10 10 10 01
第三行 01 10 01 00 01 00 10 00 00 10 10 00

意思为:Louis Braiile

在使用二进制对书面语言进行编码时,换挡码和逃逸码是非常常见的。

数字

通过上面的内容,应该对编码有了一定的理解。通过举一反三,数字也也可以被看做是一种编码,比如当我们看到数字 3,第一时间在脑海中想到的会是什么?三个苹果或者是三个别的什么东西,反正数目一定是三。那为什么我们在脑海中数字 11 不能和三个苹果关联起来呢?这个听上去有点拗口,因为这里涉及进制的不同。

小时候,老师都是教我们可以使用来数数,比如 2 用表示就是两个手指。而然在古代,那个时候可不是这样的,根据历史信息表明,在古时候是通过画画来计数的,比如通过画出两个狗来表示两条狗的意识。后来直接使用画线条来代替画狗,画俩个线条就是表示两条狗。

罗马数字

随着时间的推移,慢慢发明了数字系统。从远古时期流传到现在比较熟悉的就是罗马数字。比如现在电影都会拍好几部,而一般在电影标题的地方都是用罗马数字来表示当前是第几部。沿用到今天的罗马数字有如下几个:

I V X L C D M

其中 I 表示数字 1,V 表示数字 5,X 表示数字 10。L 表示数字 50,C 表示数字 100,D 表示数字 500,最后一个 M 表示数字 1000。
仔细观察,可以看出这几个字母之间的关系,就是后一个字母代表的数组等于前一个字母乘以五,比如五个 V 等于一个 X。这样设计的好处就是让罗马数字变的比较适合做加减法。

阿拉伯数字

我们现在所用的数字系统被叫做阿拉伯数字,这个数字系统之所以成为主流数字系统,主要是他有几个其他数字系统没有的有点。第一个有点就是在阿拉伯数字系统中,一个数字所在的位置不同则其表示的含义也不同。在前面说的的罗马数字中有专门用来表示数字十的符号,而在阿拉伯中没有这种符号。正因为如此,阿拉伯数字系统多了一个特殊的符号,那就是数字 0。

数字 0 不仅仅可以用它来表示零,跟多的情况是用它来表示一位。比如 10 和 10000 这两个数字看上去都是由 1 和 0 组成,但是我们都知道后者要远远大于前者,原因就在于后者的 0 比前者多。

另外一个优点体现在阿拉伯数字的读法上,比如数字 4396 读作四千三百九十六,用公式可以写成下面这几种方式:

  • 4000 + 300 + 90 + 6
  • 4 x 1000 + 3 x 100 + 9 x 10 + 6 x 1
  • 4 x 103 + 3 x 102 + 9 x 101 + 6 x 100

任何数的 0 次幂都是 1。

除了可以表示整数还可以用 . 来表示分数,比如小数 439.67 可以用记住下面几种方式:

  • 4 x 100 + 3 x 10 + 9 x 1 + 6 / 10 + 7 / 100
  • 4 x 100 + 3 x 10 + 9 x 1 + 6 x 0.1 + 7 x 0.01
  • 4 x 102 + 3 x 101 + 9 x 100 + 6 x 10-1 + 7 x 10-2

在书中第七章的最后一部分列出了两张表格,相信大家都不会陌生,一张表示九九加法表,另一张是九九乘法表。

不用十进制

正如上面开始说到的,人是因为有十根手指所以使用的是十进制作为数字系统的进制。如果人的手指个数是八个,这时候会发什么?换句话说当我们一共只有八根手指的时候我们该怎么用手指去表示 9 这个数字?

如果一共只有八根手指,可能就会诞生以八为基数的数字系统,称为八进制数字系统。

在这个八进制数字系统中,我们只需要使用 0 ~ 7 这八个符号,而数字八在八进制中表示为 10,读作一零而不是十。同理在八进制中 20 读作二零,对应到十进制中就是是 16。

为了方便书写,我们使用 TENEIGHT 来分别表示十进制和八进制。例如:

人类的手指个数是 10TEN 或 12EIGHT

通过分析我们可以得出无论是八进制还是十进制都和二进制有这一定关联,比如 100EIGHT,200EIGHT 和 400EIGHT 分别对应着十进制中的 64TEN,128TEN 和 256TEN。它们全是 2 的整数次幂。通过这一规律我们可以把 400EIGHT 分解成 4EIGHT 乘以 10EIGHT 乘以 10EIGHT。这些数恰恰都是 2 的整数次幂。可以得出下面这个结论:

任何 2 的整数次幂的数乘以另外一个 2 的整数次幂的结果依然是 2 的整数次幂。

下面这个表格表示一些的 2 的整数次幂分别用十进制和八进制表示的方式,如下:

2 的整数次幂 十进制 八进制
20 1 1
21 2 2
22 4 4
23 8 10
24 16 20
25 32 40
26 64 100
27 128 200
28 256 400
29 512 1000
210 1024 2000
211 2048 4000
212 4096 10000

可以看到八进制中的数字都是以 0 结尾的,这样的数字称作好数字(nice round number),这样的数字在进行运算的时候很方便。就好比我们看到 100 x 100 第一时间就知道结果是 10000,而 199 x 199 算起来就比较麻烦了。

八进制转十进制

一个八进制 10EIGHT 转成十进制就是 8TEN,这个过程很容易,原因在于这 10EIGHT 这个数本身很小,如果遇到一个比较大的八进制数,该怎么快速的将它转成十进制呢?

假设我们要把 4396EIGHT 转化成十进制数字,具体做法如下:

我们将 4396EIGHT 分解为 4000EIGHT + 300EIGHT + 90EIGHT + 6EIGHT

转换一下格式就是:4 x 1000EIGHT + 3 x 100EIGHT + 9 x 10EIGHT + 6 x 1EIGHT

在通过下面这个表格:

1EIGHT 10EIGHT 100EIGHT 1000EIGHT
1TEN 8TEN 64TEN 512TEN

最终得出的结果就是:4 x 512TEN + 3 x 64TEN + 9 x 8TEN + 6 x 1TEN = 1050190TEN

四进制

上面这套方法,同样适用用于四进制,比如我们想将一个四进制的数 3123FOUR 转成十进制。首先分解为 3 x 1000FOUR + 1 x 100FOUR + 2 x 10FOUR + 3 x 1FOUR

在通过下面这个表格:

1FOUR 10FOUR 100FOUR 1000FOUR
1TEN 4TEN 16TEN 64TEN

最终得出结果就是:3 x 64TEN + 1 x 16TEN + 2 x 4TEN + 3 x 1TEN = 219TEN

二进制

四进制并不是我们这里重点讨论的对象,而真正的主角是二进制。正如上面说看到的,在八进制中只有数字 0 ~ 7,而在四进制中只有数字 0 ~ 3,同理在二进制中只有数字 0 和 1。比如下面是数字 0 ~ 10 用二进制表示的方式:

0,1,10,11,100,101,110,111,1000,1001,1010

比起上面的八进制转十进制和四进制转十进制,二进制转十进制就简单的多。可以通过下面这个模板将任意一个八位的二进制转成十进制。

位数 操作 结果
- x1 -
- x2 -
- x4 -
- x8 -
- x16 -
- x32 -
- x64 -
- x128 -

比如我们填入 10011001TWO 这个二进制,结果为:

位数 操作 结果
1 x1 1
0 x2 0
0 x4 0
1 x8 8
1 x16 16
0 x32 0
0 x64 0
1 x128 128

最后将第三列记过相加,得出和为 153TEN

基于上面的分析,我们可以得出一个八位的二进制能表示的最大的十进制是 255TEN 即 11111111TWO

扯的题外话,在 Android 中涉及到 Bitmap 的地方,有一个参数叫做 Bitmap.Config.ARGB_8888,这里就有一个疑问为什么这个是 8888 而不是 7777 或者 9999。通过上面我们了解到一个八位的二进制只能表示 0 ~ 255 的十进制。等等是不是很熟悉?没错在定义颜色的 ARGB 的值的时候,其值的范围正好就是 0 ~ 255。原因在于十六进制颜色码使用的是两位的十六进制,如 #FFFFFF。所以我们可以算出一个 ARGB 中任意一个属性所占用的二进制就是八位,所以也就有了 ARGB_8888。



进一步讨论,一个像素使用的是 Bitmap.Config.ARGB_8888,那么它占用的内存就是 4 乘以 8 等于 32 位,转成字节就是 4 字节。

反之我们还可以设计出用于将一个小于等于 255 大于 0 的十进制数转换成二进制的模板,具体如下:

余数 操作
- /1 -
- /2 -
- /4 -
- /8 -
- /16 -
- /32 -
- /64 -
- /128 -

我们想要把 150TEN 这个十进制数转成二进制,将这个数带入上面的模板得到结果为:

需要从下往上填,结果也要从下往上读。

余数 操作
0 /1 0
2 /2 1
6 /4 1
6 /8 0
22 /16 1
22 /32 0
22 /64 0
150 /128 1

最终结果为 10010110TWO

二进制的运算

二进制的加法和乘法远比十进制的要简单的多,原因在于二进制中只有 0 和 1 这两个数。我们只需要记住下面两个表格我们就可以算出任意位数的二进制相加或相乘。

0 1
0 0 1
1 1 10
0 1
0 0 0
1 0 1

没有看错,仅仅只需要上面连个简单的表格就能算任意位数的二进制加法和乘法,并且算的过长也非常简单。

举个例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//加法
1100101
+0110110
----------
10011011

//乘法
1101
x1011
-----------
1101
1101
0000
1101
------------
10001111

二进制和十进制的规律

二进制数 十进制数
0000 0
0001 1
0010 2
0011 3
0100 4
0101 5
0110 6
0111 7
1000 8
1001 9
1010 10
1011 11
1100 12
1101 13
1110 14
1111 15

通过观察上面表格的第一列,从上往下看每一位我们可以找出以下规律:

  • 第一位总是 1 和 0 交替
  • 第二位总是 00 和 11 交替
  • 第三位总是 0000 和 1111 交替
  • 第四位总是 00000000 和 11111111 交替

通过上面的规律可以很容容易的写出后 16 个数字的表格:

二进制数 十进制数
10000 16
10001 17
10010 18
10011 19
10100 20
10101 21
10110 22
10111 23
11000 24
11001 25
11010 26
11011 27
11100 28
11101 29
11110 30
11111 31

书写格式

在生活中我们写一个位数比较的的数时,往往会按照一定的格式来书写,比如我们一般将 12000000 写作 1200,0000,这样做的好处就是方便我们阅读数字。

同理二进制也有它的书写格式,因为二进制的位数增长的很快,所以一般都是将一个二进制以每四位进行分隔。例如 1200,0000 的二进制位为 101101110001101100000000,为了方便阅读可以写作 1011-0111-0001-1011-0000-0000。

上面讲了十进制,八进制,四进制已经最重要的二进制。其中二进制和计算机有这非常紧密的联系,这个在书的后面有描述。大约在公元 1948 年,美国数学家约翰·威尔德·特克 意识到二进制会在未来的计算机领域发挥重要的重用。于是他发明了一个就像二进制一样简单纯粹的单词 bit。

这个名为约翰·威尔德·特克的美国数学家在网上找不出关于他的中文资料。不过既然在书中出现了他的名字,相信他应该和二进制有这密切的关系。

二进制的应用

上面讲了二进制的基本用法,下面来说说在生活有哪些关于二进制例子。比如抛出一枚硬币,只有可能是正面朝上或者反面朝上,再比如一些店铺会在门上挂一个只有两面的牌子,正面写着营业另一面写着休息。这些都可以用二进制来表示。

传递信息

上面说的这些关于二进制的例子,可以看做是使用二进制来传递信息,这并不代表必须要用二进制来传递。比如上面的抛硬币,我们在上面时候要抛硬币?比如在决定做或者不做某件的事情的时候可以通过抛硬币来决定。

注意这里的不做,一共只有两种可能。但是如果我们有了多种可能呢?比如我和朋友一起做,我一个人做,我要别的帮我做等等。这个时候可就不止两种了,所以我们就不能用抛硬币的方式来决定了。(这里的抛硬币指的是抛一枚)

在看看关于商铺在门上挂一个牌子的例子,这个牌子只有两面,所以它只能传递两种信息,如果我们想传递更多的信息比如老板有事马上回来或者本店正在营业不过老板不在买东西自己结账等等。这个时候我们就需要使用别的方式来传递信息了。

需要注意的是上面说的这两个例子其实并非不能使用二进制,比如抛硬币,抛一枚硬币只会有两种可能,那抛两枚是不是就有四种可能了呢?以此类推。不过往往当可能大于二之后会优先选择掷塞子而非是抛硬币。

下面说说书中提到的一个可以用二进制解释的现实案例。

他对他的朋友说:“今晚如果从镇里面来的的英国军队通过海路或陆路入侵,你就在北教堂钟楼的拱门处高高挂起等作为特殊信号-一盏灯表示英军从陆路进军,两盏灯表示英军从海路入侵…”

上面这段话通过二进制表示如下:

  • 00 = 英军今晚不会入侵
  • 01 = 英军正由陆路入侵
  • 10 = 英军正由陆路入侵
  • 11 = 英军正由海路入侵

上面这个故事利用两盏灯表示了三种可能性,和上面我们提到的二进制的例子是类似的。

总结上面这些例子的共同点,就是它们说要传递的信息的内容可能是有限次数中的某一种,换句话说所有可以被转换成两种或者两种以上可能想的信息都可以用二进制来表示。

很显然这条规则并不适用于人与人之间的交流,因为人与人之间的交流并不能用非黑即白来表示,就好比我们常说的不能用除了好人就是坏人来形容所有人。但是计算机却非常喜欢这种非黑即白的交流方式,这也为什么人无法直接与计算机交流的原因。

UPC 与二进制

另外一个和二进制相关的例子就是 UPC(Universal Product Code),中文意思为普通商品码。可能听上去比较陌生,不过如果我说条形码详细你应该不会陌生了。

每个商品基本上都有自己的 UPC 码,这些 UPC 码的主要作用是方便在结算的时候快熟识别出商品从而自动化的管理。UPC 码的原理其实非常简单,比如下面就是一个 UPC 码被扫描后的信息:

- - -- - -- - -- - -- - -- - -- - - - --- - -- -- -- -- - --- -- -- - - - -

这里表示的有点不太好,具体看书的 83 页

在上面这个信息中一个 - 表示 1,而一个空格表示 0,所以我们可以将上面那段信息写作:

10100011010110001001100100011010001101000110101010111001011001101101100100111011001101000100101

作为一个正常人肯定是看不懂上面这串 0101 是什么意思,不过计算却看得懂。上面这段 0101 可以分为下面几个部分:

  1. 开头的 101 和 101 是这段信息中的护线,其作用是表示开始和结尾
  2. 护线之后是 6 组 bit 串,没串有 7 个 bit 位
  3. 紧接着是一个 5 bit 位的中间护线,它和开头的 101 一样固定是 01010,主要作用是用来校验 UPC 有没有被修改或印错

上面就是一个 UPC 码的结构,将我们例子中的 UPC 码解析最终得到下面的内容:

比特 意义
101 最左边的护线
0001101 -
0110001 -
0011001 -
0001101 左边的数字
0001101 -
0001101 -
01010 中间的护线
1110010 -
1100110 -
1101100 -
1001110 右边的数字
1100110 -
1000100 -
010 最右边的护线

左边和右边数字可以通过下面两个表格来进行解码。

左边的数字:

比特 数字
0001101 0
0011001 1
0010011 2
0111101 3
0100011 4
0110001 5
0101111 6
0111011 7
0110111 8
0001011 9

右边数字:

比特 数字
1110010 0
1100110 1
1101100 2
1000010 3
1011100 4
1001110 5
1010000 6
1000100 7
1001000 8
1110100 9

仔细观察上面两个表格,左边的数字的比特位中 1 的数量总是为奇数而右边数字的比特位中 1 的数量总是偶数。这是用来做奇偶校验的。很显然左边数字采用的是奇校验,右边数字采用的是偶校验,一般用于检查错误和一致性的。

在仔细观察右边数字的比特位后,发现其实右边数字的比特位就是左边数字比特位的补码。所谓补码就是将原本的 1 变为 0,反之 0 变为 1。

通过上面的两张表格,最终上面例子的 UPC 码的解码结果为:

0 51000 01251 7

第一个数字 0 表示这个 UPC 码表示的商品的类型,后面五个数字 51000 表示商品制造商的编码,在后面的五个数字 01251 表示的是这个上面在制造商内部的编码,最后的数字 7 是模校验字符。

它的作用用于检查扫描的结果是否有错误,我们可以把上面那段扫描结果替换成字母,如下:

A BCDEF GHIJK

然后使用下面的公式:

3 x (A + C + E + G + I + K) + (B + D + F + H + J)

带入公式结果为:

3 x (0 + 1 + 0 + 0 + 2 + 1) + (5 + 0 + 0 + 1 + 5) = 3 x 4 + 11 = 23

最后算出大于并离 23 最近的 10 的整数倍的数是 30,最后用 30 减去 23 算出 7。计算机在扫描并计算出所有数字后,会进行上面的校验,如果最后一个数字不是 7 那么就表示扫描结果有误。

我们解析了例子中的 UPC 码,不过也发现了一个问题,一般情况下我们表示数字 0 ~ 9 应该只需要 4 个比特位就够了,而在 UPC 码中却是使用了 7 个比特位,加上护线整个 UPC使用了 113 个比特位。换言之 UPC 码使用 113 个比特位表示了 11 个十进制的数字。

这么做的原因在于 UPC 不仅可以从走往右解析,还可以从右往左扫。还记得上面我们说的奇偶校验吗?它的作用之一就是告诉计算机扫描器是从左往右扫还是从右往左扫的。

当从右往左扫描的时候就需要下面这两个表了解码,如下:

右边的数字:

比特 数字
0100111 0
0110011 1
0011011 2
0100001 3
0011101 4
0111001 5
0000101 6
0010001 7
0001001 8
0010111 9

左边数字:

比特 数字
1011000 0
1001100 1
1100100 2
1011110 3
1100010 4
1000110 5
1111010 6
1101110 7
1110110 8
1101000 9

我将之前解码前的内容从右往左对这上面的两个表,可以发现接触的内容其实和前面从左往右扫的内容是一样的。

总结

自此书中我认为的二进制基本内容就总结完了,可以看出布莱叶盲文和摩尔斯电码在思想上和二进制编码如出一辙。在看到现在生活中的例子,都与编码有这密不可分的关系,最最最重要的计算机则和二进制编码有这千丝万缕的关联。具体在后面的博客中会总结。