丁偉 宋道星

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

本文奇偶校驗(yàn)原理

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

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

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

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

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

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

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

本文奇偶校驗(yàn)?zāi)M

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

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

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

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

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

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