丁偉 宋道星

很多娛樂節(jié)目中都有一個名叫“傳聲筒”的游戲，在游戲中，由于受到各種因素的影響，參與人員在傳遞信息的過程中會使信息發(fā)生錯誤而產(chǎn)生喜劇效果。而在生活中，信息的傳輸時刻都在發(fā)生，模擬信號在傳輸過程中，由于各種影響因素的存在，會產(chǎn)生各種失真現(xiàn)象，且不容易糾正。數(shù)字信號是利用0、1兩個數(shù)字的編碼來表示信息，在數(shù)字設備之間，存儲、傳輸?shù)臄?shù)據(jù)都是數(shù)字信號，數(shù)據(jù)在存儲、傳輸過程中的錯誤會引起數(shù)據(jù)的變化。因此，在數(shù)字信號的傳輸過程中，以編碼理論為基礎的校驗糾錯技術就顯得尤為重要。

本文奇偶校驗原理

在諸多的校驗方法中，比較容易理解的是奇偶校驗，奇偶校驗是一種常用的檢驗代碼傳輸正確性的校驗方法，它根據(jù)傳輸?shù)囊唤M二進制數(shù)中的“1”的個數(shù)是奇數(shù)還是偶數(shù)來進行校驗。是奇數(shù)還是偶數(shù)是事先定好的，奇數(shù)的叫奇校驗，反之叫偶校驗。在數(shù)據(jù)傳輸之前，我們首先要設定一個校驗位，通過這個校驗位使傳輸?shù)臄?shù)據(jù)中“1”的個數(shù)為奇數(shù)或者偶數(shù)。若用奇校驗則在接收端收到代碼時校驗“1”的個數(shù)是否為奇數(shù)，同理，若用偶校驗則校驗“1”的個數(shù)是否為偶數(shù)，如圖1所示。

在接收方收到數(shù)據(jù)后，對數(shù)據(jù)中“1”的個數(shù)進行統(tǒng)計，如果為預定好的奇數(shù)或偶數(shù)則校驗通過，否則表示傳輸過程中有錯誤發(fā)生，此時接收方可以發(fā)送請求要求發(fā)送方重新發(fā)送數(shù)據(jù)。這種校驗方式只能校驗正誤，沒有糾錯能力，稱為一維奇偶校驗。

二維奇偶校驗，也被稱為矩陣校驗或水平垂直一致校驗。計算機在對數(shù)據(jù)信息進行傳送之前，除了對每行數(shù)據(jù)添加一個奇偶校驗位，還要對每列數(shù)據(jù)添加一個奇偶校驗位，所以，二維奇偶校驗就是結(jié)合行、列兩種一維校驗的校驗方法。通過這種橫向、縱向同時進行校驗的方式來對整個數(shù)據(jù)進行校驗，這種校驗方法擁有更好的校驗性能，因為它有可能檢測出偶數(shù)個錯誤。盡管每行的校驗位無法檢測出本行中的偶數(shù)個錯碼，但是按列的方向來進行檢測的話檢測出來的概率是非常大的。此外，二維奇偶校驗碼擁有一定的糾錯功能，可以糾正部分錯碼，如對數(shù)據(jù)中的1個隨機錯誤，就可以通過行列確定錯碼的位置，從而對其進行糾正。

本文用掌控板模擬數(shù)據(jù)傳遞中的奇偶校驗

本實驗使用掌控板模擬數(shù)字信號傳輸過程中出現(xiàn)誤碼，并通過二維奇偶校驗進行糾錯的過程。掌控板是一塊微控制器板，板載加速度計、按鍵、觸摸引腳、聲光傳感器、128*64的OLED屏幕等，通過mPython編程，借助掌控板的顯示屏就可以直觀地呈現(xiàn)數(shù)據(jù)。mPython0.5.4是在原版PythonEditor基礎上拓展開發(fā)的編程軟件，可以進行可視化代碼編程，有Blockly、Python、Jupyter三種代碼讀寫等功能。

啟動mPython0.5.4，使用“顯示”模塊中的繪制實心和繪制空心積木塊，繪制“十”字形二維矩陣。筆者用矩陣中的白色矩形代表數(shù)字“1”，用黑色矩形代表數(shù)字“0”。假設采用偶檢驗來進行校驗，那么需要在矩陣的最右側(cè)和最下面分別增加一列和一行校驗碼，使得每行每列的白色矩形均為偶數(shù)個，如圖2所示。

筆者通過掌控板S（send）上的“A”鍵來實現(xiàn)這一過程，并通過“B”鍵將這個二維矩陣發(fā)送到另一個掌控板R（receive）上。寫好掌控板S的代碼后，將掌控板S連接到計算機上，選擇好對應的端口號，將代碼上傳到掌控板，如圖3所示。

本文奇偶校驗模擬

接下來編寫信息接收方掌控板R的代碼，首先打開掌控板的無線廣播功能，當接收到掌控板S的廣播時開始繪制下頁圖4中含有校驗碼的二維矩陣。通過校驗可以發(fā)現(xiàn)第三行中的“1”變成了奇數(shù)個，同時第三列中的“1”也變成了奇數(shù)個，因此可以判斷是第三行和第三列交叉處的數(shù)據(jù)發(fā)生了錯誤。

這時通過按鈕“B”來進行糾錯，完成整個的傳輸糾錯過程，代碼如下頁圖5所示。

通過上面的實驗可以了解奇偶校驗是如何檢測并修正一個錯誤的，但計算機中會有不止一個數(shù)據(jù)發(fā)生錯誤的時候，當出現(xiàn)這樣的情況時，有一種特殊情況是能夠被糾正的。下頁圖6就顯示了這樣一個奇偶校驗陣列（每行每列的白色卡片數(shù)均為偶數(shù)），但是它的第四列數(shù)據(jù)全部丟失（灰色區(qū)域）。RAID（獨立冗余磁盤陣列）硬盤系統(tǒng)采用的就是這種糾錯方式，通過將數(shù)據(jù)分散存儲在多塊硬盤中，來保證運行的高速性和穩(wěn)定性。

上述實驗只是模擬了奇偶校驗中的基本原理，利用這種校驗方法還可以設計一個讀心術小游戲。首先準備好36張卡片，要保證每張卡片正反兩面的圖案和顏色不同（如實驗中的白色和黑色矩形）。找一個同伴，由他來把卡片放在桌子上，并決定每張卡片放置的正反。接下來，你可以增加幾張卡片（添加校驗數(shù)據(jù)），然后轉(zhuǎn)身，這時讓你的同伴隨意翻轉(zhuǎn)一張卡片，當他翻轉(zhuǎn)后你總能正確地說出哪一張卡片是他翻過的。

奇偶校驗系統(tǒng)的優(yōu)化方案稱為RAID5。假設需要使用8個硬盤來儲存大量的數(shù)據(jù)，這些數(shù)據(jù)包含大量字節(jié)，可能超過數(shù)億字節(jié)（吉字節(jié)）甚至千億字節(jié)（太字節(jié)）。這時，可以將每個字節(jié)打散成8比特分別儲存在多個硬盤上，而不是將數(shù)據(jù)陸續(xù)填滿每個磁盤。這樣的存儲方式會讓系統(tǒng)運行得更快，因為當計算機需要讀取文件時，它只要分別同時向每塊硬盤讀取片段即可。該方法也可用于提高糾錯性能：如果再增加存有奇偶校驗位的第9塊硬盤，我們可以用上面的思路讓每一列數(shù)據(jù)分別放在不同的硬盤上，這樣一來，如果其中一塊硬盤被損壞，即使損失全部數(shù)據(jù)，仍然能依靠奇偶校驗的思路來修復原始數(shù)據(jù)——只要算出遺失的比特使得9個硬盤上值為1的比特數(shù)總保持為偶數(shù)即可。正是因為RAID系統(tǒng)的存儲速度飛快，任何一塊硬盤被損壞也不會影響原始數(shù)據(jù)的讀取。所以，對于大型數(shù)據(jù)中心和主要的網(wǎng)站來說，RAID已經(jīng)成為提高運行速度和保障穩(wěn)定性的優(yōu)選方案。

信息的傳輸過程中很難避免干擾和錯誤的出現(xiàn)，糾錯是一種很好的解決方法，糾錯的方式有很多，奇偶校驗只是一種比較容易理解的方式，通過這種方式可以幫助學生非常直觀地理解糾錯的原理，這種類似的演示實驗設計，可能會成為今后信息科技的一個探索方向。