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。

解：

示例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”：

0⊕0=0；　0⊕1=1；　1⊕0=1；　1⊕1=0。

為敘述方便，定義一個新的運算：按位異或和，該運算用以判斷一個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位上，其余位自右至左排列數據位。這樣再按類似前述方法產生校驗位的值、傳輸和校驗即可。

本節類比“小白鼠問題”探究了數據傳輸的檢錯問題解決方案，這種思想就是計算機領域的一種偉大思想“漢明碼”，也稱為“海明碼”，但請注意本節并不是讓讀者學習漢明碼，而只是通過該示例使讀者體會計算思維的偉大之處。因此，關于漢明碼檢錯糾錯的原理還有很多內容，讀者如感興趣，可自主查閱資料。