1.3 扩展学习：计算思维的价值在哪里

计算思维有什么价值呢？学好计算思维有助于创新想法，并将创新想法变为现实。下面类比“小白鼠问题”做一个测试：判断数据传输是否有错误。

大家都知道，计算机中所有的信息都展现为01串，如1001110010010111，并且需要不断地进行传输，如从一台计算机传输到另一台计算机，或者从一台计算机上传到网络中，那么有没有可能传输错误呢？当然是有可能的。那怎么判断并纠正错误呢？首先分析0和1的特性，然后再探讨判断并纠正错误的方法。

1.3.1 0和1及其特性

二进制算术运算是位相关运算，即逢二进一、借一当二，有规则如下。

1.加法运算规则

0＋0 = 0; 0＋1 = 1; 1＋0 = 1; 1＋1 = 0（本位为0，进位为1）。

2.减法运算规则

0－0 = 0; 0－1 = 1（借位为1）; 1－0 = 1; 1－1 = 0。

示例2 X=10111,Y=10011，则X+Y = 101010。

解：

示例3 X=10101,Y=11011，则X+Y = 110000。

解：

示例4 X=10111,Y=10011，则X－Y = 00100。

解：

10111－) 10011 00100

示例5 X = 11001,Y=10110，则X－Y = 00011。

解：

如果仅做1位的加法，加数、被加数与和均为1位，所有进位将被自动舍掉，则n个1的累加和也只能是1位，其结果依赖于n是偶数，还是奇数。若n是偶数，则累加和为0，若n是奇数，则累加和为1。这一特性很重要，可以看出：判断一个01串中1的个数是偶数还是奇数，只需将该01串的各位逐位累加即可，依据其累加和为0，还是1即可判断。

为更严格地表述，下面引入异或运算。

3.异或运算规则

异或运算“⊕”是一种位运算，规则为“相同为0，不同为1”：

为叙述方便，定义一个新的运算：按位异或和，该运算用以判断一个01串中1的个数是奇数还是偶数。

4.按位异或和

一个01串（又称比特串），其按位异或和，即是将该01串的每一位实施异或运算得到的结果。该结果依赖于01串所包含的1的个数：如果包含奇数个1，则其按位异或和为1；如果包含偶数个1，则其按位异或和为0。（此可由异或运算规则予以证明，证明过程略。）

按位异或和得到的结果与仅做1位运算的按位累加和结果是一致的，所不同的是按位异或和没有产生任何进位，而按位累加和是舍掉了所有的进位。这两个操作的目的都是判断一个01串中1的个数是奇数还是偶数。

示例6 01串1011的按位异或和，即1⊕0⊕1⊕1 = 1（奇数个1，其按位异或和为1）。

示例7 01串1001的按位异或和，即1⊕0⊕0⊕1 = 0（偶数个1，其按位异或和为0）。

人在计算的过程中通过统计1的个数即可以获知1011 0110 1011 0110 1110 1001 1101 1010的按位异或和为0（其包含了20个1，偶数个1）。再例如1011 0111 1111 1110 1111 1101 1101 1010的按位异或和为1（其包含了25个1，奇数个1）。

1.3.2 偶校验：判断数据传输有无错误

下面用对比的方式进行讨论。

小白鼠问题：有n瓶水，其中仅可能有1瓶水有毒，如果不考虑是哪一瓶有毒，而仅考虑是否有有毒的瓶，该怎样检测呢？

传输校验问题：对于一个n位的01串010…1101，如果在传输过程中仅可能有1位发生错误，如果不考虑是哪一位错误，而仅考虑是否有传输错误，该怎样检测呢？

小白鼠问题解决方案：仅判断是否有有毒的水，则只需1只小白鼠。将这n瓶水让小白鼠每瓶都喝一滴。如果小白鼠死亡，则表示有有毒的水；而如果小白鼠未死亡，则表示没有有毒的水。

传输校验问题解决方案：仅判断有无传输错误，则只需增加1位校验位P（小白鼠，只是P的值也只能是0或1）。传输前，P如何产生呢？

假设制定一规则：传输前01串中1的个数，与传输后01串中1的个数始终都保持偶数，则为传输正确。

因此，在传输前应使待校验01串S与校验位P所形成的新01串S’中1的个数为偶数。则P的产生规则为：P为S的按位异或和，即如01串S中1的个数为奇数，则P为1；如01串S中1的个数为偶数，则P为0。

这样无论S是怎样的01串，带校验位的01串S’中1的个数始终为偶数。

当S’传输过去后，对传输过去的S’再计算其按位异或和P'：如果P'=1（相当于小白鼠死亡），则传输错误；而如果P'=0（相当于小白鼠未死亡），则无传输错误。即如果传输过去，S’中1的个数仍旧为偶数，则表明没有传输错误；而如果传输过去，S’中1的个数为奇数，则表明有传输错误。

偶校验：通过增加一位校验位P，使得待传输01串S与P组合形成的新的01串S'中1的个数始终为偶数。通过判断传输中S’中1的个数是否仍为偶数来判断数据是否传输错误的方法就是偶校验。

示例8 传输01串1001 1010，若采用偶校验，则其校验位P的值应为 。

解：P = 1⊕0⊕0⊕1⊕1⊕0⊕1⊕0 = 0。

示例9 传输01串1111 1010 1011，若采用偶校验，则其校验位P的值应为 。

解：P = 1⊕1⊕1⊕1⊕1⊕0⊕1⊕0⊕1⊕0⊕1⊕1= 1。

示例10 假设01串1001 1110 1101，传输后变为1001 1010 1101，假设校验位传输无错误，若采用偶校验，请叙述其检测过程。

解：S为1001 1110 1101,P = 1⊕0⊕0⊕1⊕1⊕1⊕1⊕0⊕1⊕1⊕0⊕1= 0。

传输前S’应为1001 1110 1101 0。

传输后S’为1001 1010 1101 0,P' = 1⊕0⊕0⊕1⊕1⊕0⊕1⊕0⊕1⊕1⊕0⊕1⊕0 = 1。

因P'=1，故传输有错误。

示例11 已知接收到的01串为1101 1111 1011 0，采用偶校验，请判断是否传输错误。

解：P' = 1⊕1⊕0⊕1⊕1⊕1⊕1⊕1⊕1⊕0⊕1⊕1⊕0 = 0。故此传输无错误。

基于前述规则，可以发现，偶校验是能够检测出单数位数的数据传输错误，即当传输过程中有1位传输错误，或有3位传输错误，或有5位传输错误时，偶校验是可以判断出传输发生错误的。而当有偶数位数的传输错误，偶校验则发现不了。这是为什么？

1.3.3 类比小白鼠问题判断哪一位出错

1.3.2小节讨论的是判断数据传输过程中有无错误，而并不能确定是哪一位出错。那如何判断哪一位出错呢？还是对比小白鼠问题进行讨论。

小白鼠问题：有7瓶水，其中仅可能有1瓶水有毒，例如，第6瓶水有毒，怎样判断出是第6瓶水有毒呢（从右向左，或者说从低位向高位编号）？

传输校验问题：对于一个7位的01串1101101，如果在传输过程中仅可能有1位发生错误，例如，传输后变为1001101，怎样判断出是第6位出错呢（从右向左，或者说从低位向高位编号）？

小白鼠问题解决方案：将7瓶水按十进制编号为1,…,7。然后将十进制编号转换为二进制编号，分别为001,010,011,100,101,110,111。可见编号需要3位二进制位，因此需要3只小白鼠，编号为P4P2P1。P1小白鼠喝二进制编号第20位为1的瓶中的水（即第1,3,5,7瓶水）;P2小白鼠喝二进制编号第21位为1的瓶中的水（即第2,3,6,7瓶水）;P4小白鼠喝二进制编号第22位为1的瓶中的水（即第4,5,6, 7瓶水）。然后等待小白鼠是否死亡：哪一只小白鼠死亡，则其为1，未死亡，则其为0。依题，P4P2P1=110，还原为十进制则为6，说明第6瓶水有毒。

传输校验问题：如图1.4所示，将7位的01串S 1101101按从低位向高位（自右向左）编号为1,…,7；然后将十进制编号转换为二进制编号，分别为001,010,011, 100,101,110,111。可见编号需要3位二进制位，因此需要3位校验位，编号为P4P2P1。采取偶校验，则校验位的产生规则（类似于小白鼠如何喝的规则）为：P1负责使二进制编号第20位为1的那些位中1的个数为偶数（即使第1,3,5,7位中1的个数为偶数）;P2负责使二进制编号第21位为1的那些位中1的个数为偶数（即使第2,3,6,7位中1的个数为偶数）;P4负责使二进制编号第22位为1的那些位中1的个数为偶数（即第4,5,6,7位中1的个数为偶数）。

可表示为：

P4= 第7位⊕第6位⊕第5位⊕第4位（即编号的22位为1的那些位的按位异或和）；

P2= 第7位⊕第6位⊕第3位⊕第2位（即编号的21位为1的那些位的按位异或和）；

P1= 第7位⊕第5位⊕第3位⊕第1位（即编号的20位为1的那些位的按位异或和）。

依题，P4= 1⊕0⊕1⊕1 = 1;P2= 0⊕1⊕1⊕1 = 1;P1= 1⊕1⊕0⊕1 = 1。

由此产生新的01串S’为1101101 111。

依题，传输过去后，S’变为1001101 111。按照偶校验的规则产生P'4P'2P'1（类似于确认小白鼠是否死亡）。

P'4= 第7位⊕第6位⊕第5位⊕第4位⊕P4= 1⊕0⊕0⊕1⊕1 = 1；

P'2= 第7位⊕第6位⊕第3位⊕第2位⊕P2= 1⊕0⊕1⊕0⊕1 = 1；

P'1= 第7位⊕第5位⊕第3位⊕第1位⊕P1= 1⊕0⊕1⊕1⊕1 = 0。

P'4P'2P'1=110，还原为十进制则为6，说明第6位出错。

依题，传输过去后，S’如变为1101001 111。按照偶校验的规则产生P'4P'2P'1（类似于确认小白鼠是否死亡）。

P'4= 第7位⊕第6位⊕第5位⊕第4位⊕P4= 1⊕1⊕0⊕1⊕1 = 0；

P'2= 第7位⊕第6位⊕第3位⊕第2位⊕P2= 1⊕1⊕0⊕0⊕1 = 1；

P'1= 第7位⊕第5位⊕第3位⊕第1位⊕P1= 1⊕0⊕0⊕1⊕1 = 1。

P'4P'2P'1=011，还原为十进制则为3，说明第3位出错。

示例12 待传输01串为1001111，若采用偶校验，需增加几位校验位才能判断出哪一位传输错误，若传输过去变为01串为1011111，则如何判断出是哪一位出错？

解：因22< 数据位数7 < 23，故需增加3位校验位，记为P4P2P1。其中P4P2P1产生如下：

P4= 1⊕0⊕0⊕1 = 0;P2= 1⊕0⊕1⊕1 = 1;P1= 1⊕0⊕1⊕1=1。

S’串为1001111 011。

依题S’串传输过去后变为1011111 011。按照偶校验的规则产生P'4P'2P'1。

P'4= 第7位⊕第6位⊕第5位⊕第4位⊕P4= 1⊕0⊕1⊕1⊕0 = 1；

P'2= 第7位⊕第6位⊕第3位⊕第2位⊕P2= 1⊕0⊕1⊕1⊕1 = 0；

P'1= 第7位⊕第5位⊕第3位⊕第1位⊕P1= 1⊕1⊕1⊕1⊕1 = 1。

P'4P'2P'1=101，还原为十进制则为5，说明第5位出错。

示例13 待传输01串为1111，若采用偶校验，需增加几位校验位才能判断出哪一位传输错误？若传输过去01串变为1011，则如何判断出是哪一位出错？

解：因22< 数据位数4 < 23，故需增加3位校验位，记为P4P2P1。其中P4P2P1产生如下：

P4= 1;P2= 1⊕1 = 0;P1= 1⊕1=0。

S’串为1001 100。

依题，S’串传输过去后变为1011 100。按照偶校验的规则产生P'4P'2P'1。

P'4= 第4位⊕P4= 1⊕1 = 0；

P'2= 第3位⊕第2位⊕P2= 0⊕1⊕0 = 1；

P'1= 第3位⊕第1位⊕P1= 1⊕0⊕0 = 1。

P'4P'2P'1=011，还原为十进制则为3，说明1011第3位出错。

需要注意：前面的讨论仅考虑数据位传输错误，而假设校验位没有传输错误，因此，若校验位传输错误，则不能被正确判断。如考虑校验位错误也能被判断，则在增加校验位时需将数据位和校验位一并进行二进制编码来确定所需校验位的位数。例如，数据为D7D6D5D4D3D2D1，而校验位就需要4位（即23 <（数据位数7+校验位数4）< 24），即P8P4P2P1，数据位和校验位的二进制编码次序为：使校验位始终位于第2i位上，排列出来如D7D6P8D5D4D3P4D1P2P1，即校验位始终位于第1,2,4,8位上，其余位自右至左排列数据位。这样再按类似前述方法产生校验位的值、传输和校验即可。

本节类比“小白鼠问题”探究了数据传输的检错问题解决方案，这种思想就是计算机领域的一种伟大思想“汉明码”，也称为“海明码”，但请注意本节并不是让读者学习汉明码，而只是通过该示例使读者体会计算思维的伟大之处。因此，关于汉明码检错纠错的原理还有很多内容，读者如感兴趣，可自主查阅资料。

0和1与数值性信息