丁偉 宋道星
很多娛樂節(jié)目中都有一個(gè)名叫“傳聲筒”的游戲,在游戲中,由于受到各種因素的影響,參與人員在傳遞信息的過程中會(huì)使信息發(fā)生錯(cuò)誤而產(chǎn)生喜劇效果。而在生活中,信息的傳輸時(shí)刻都在發(fā)生,模擬信號(hào)在傳輸過程中,由于各種影響因素的存在,會(huì)產(chǎn)生各種失真現(xiàn)象,且不容易糾正。數(shù)字信號(hào)是利用0、1兩個(gè)數(shù)字的編碼來表示信息,在數(shù)字設(shè)備之間,存儲(chǔ)、傳輸?shù)臄?shù)據(jù)都是數(shù)字信號(hào),數(shù)據(jù)在存儲(chǔ)、傳輸過程中的錯(cuò)誤會(huì)引起數(shù)據(jù)的變化。因此,在數(shù)字信號(hào)的傳輸過程中,以編碼理論為基礎(chǔ)的校驗(yàn)糾錯(cuò)技術(shù)就顯得尤為重要。
本文奇偶校驗(yàn)原理
在諸多的校驗(yàn)方法中,比較容易理解的是奇偶校驗(yàn),奇偶校驗(yàn)是一種常用的檢驗(yàn)代碼傳輸正確性的校驗(yàn)方法,它根據(jù)傳輸?shù)囊唤M二進(jìn)制數(shù)中的“1”的個(gè)數(shù)是奇數(shù)還是偶數(shù)來進(jìn)行校驗(yàn)。是奇數(shù)還是偶數(shù)是事先定好的,奇數(shù)的叫奇校驗(yàn),反之叫偶校驗(yàn)。在數(shù)據(jù)傳輸之前,我們首先要設(shè)定一個(gè)校驗(yàn)位,通過這個(gè)校驗(yàn)位使傳輸?shù)臄?shù)據(jù)中“1”的個(gè)數(shù)為奇數(shù)或者偶數(shù)。若用奇校驗(yàn)則在接收端收到代碼時(shí)校驗(yàn)“1”的個(gè)數(shù)是否為奇數(shù),同理,若用偶校驗(yàn)則校驗(yàn)“1”的個(gè)數(shù)是否為偶數(shù),如圖1所示。
在接收方收到數(shù)據(jù)后,對(duì)數(shù)據(jù)中“1”的個(gè)數(shù)進(jìn)行統(tǒng)計(jì),如果為預(yù)定好的奇數(shù)或偶數(shù)則校驗(yàn)通過,否則表示傳輸過程中有錯(cuò)誤發(fā)生,此時(shí)接收方可以發(fā)送請(qǐng)求要求發(fā)送方重新發(fā)送數(shù)據(jù)。這種校驗(yàn)方式只能校驗(yàn)正誤,沒有糾錯(cuò)能力,稱為一維奇偶校驗(yàn)。
二維奇偶校驗(yàn),也被稱為矩陣校驗(yàn)或水平垂直一致校驗(yàn)。計(jì)算機(jī)在對(duì)數(shù)據(jù)信息進(jìn)行傳送之前,除了對(duì)每行數(shù)據(jù)添加一個(gè)奇偶校驗(yàn)位,還要對(duì)每列數(shù)據(jù)添加一個(gè)奇偶校驗(yàn)位,所以,二維奇偶校驗(yàn)就是結(jié)合行、列兩種一維校驗(yàn)的校驗(yàn)方法。通過這種橫向、縱向同時(shí)進(jìn)行校驗(yàn)的方式來對(duì)整個(gè)數(shù)據(jù)進(jìn)行校驗(yàn),這種校驗(yàn)方法擁有更好的校驗(yàn)性能,因?yàn)樗锌赡軝z測(cè)出偶數(shù)個(gè)錯(cuò)誤。盡管每行的校驗(yàn)位無法檢測(cè)出本行中的偶數(shù)個(gè)錯(cuò)碼,但是按列的方向來進(jìn)行檢測(cè)的話檢測(cè)出來的概率是非常大的。此外,二維奇偶校驗(yàn)碼擁有一定的糾錯(cuò)功能,可以糾正部分錯(cuò)碼,如對(duì)數(shù)據(jù)中的1個(gè)隨機(jī)錯(cuò)誤,就可以通過行列確定錯(cuò)碼的位置,從而對(duì)其進(jìn)行糾正。
本文用掌控板模擬數(shù)據(jù)傳遞中的奇偶校驗(yàn)
本實(shí)驗(yàn)使用掌控板模擬數(shù)字信號(hào)傳輸過程中出現(xiàn)誤碼,并通過二維奇偶校驗(yàn)進(jìn)行糾錯(cuò)的過程。掌控板是一塊微控制器板,板載加速度計(jì)、按鍵、觸摸引腳、聲光傳感器、128*64的OLED屏幕等,通過mPython編程,借助掌控板的顯示屏就可以直觀地呈現(xiàn)數(shù)據(jù)。mPython0.5.4是在原版PythonEditor基礎(chǔ)上拓展開發(fā)的編程軟件,可以進(jìn)行可視化代碼編程,有Blockly、Python、Jupyter三種代碼讀寫等功能。
啟動(dòng)mPython0.5.4,使用“顯示”模塊中的繪制實(shí)心和繪制空心積木塊,繪制“十”字形二維矩陣。筆者用矩陣中的白色矩形代表數(shù)字“1”,用黑色矩形代表數(shù)字“0”。假設(shè)采用偶檢驗(yàn)來進(jìn)行校驗(yàn),那么需要在矩陣的最右側(cè)和最下面分別增加一列和一行校驗(yàn)碼,使得每行每列的白色矩形均為偶數(shù)個(gè),如圖2所示。
筆者通過掌控板S(send)上的“A”鍵來實(shí)現(xiàn)這一過程,并通過“B”鍵將這個(gè)二維矩陣發(fā)送到另一個(gè)掌控板R(receive)上。寫好掌控板S的代碼后,將掌控板S連接到計(jì)算機(jī)上,選擇好對(duì)應(yīng)的端口號(hào),將代碼上傳到掌控板,如圖3所示。
本文奇偶校驗(yàn)?zāi)M
接下來編寫信息接收方掌控板R的代碼,首先打開掌控板的無線廣播功能,當(dāng)接收到掌控板S的廣播時(shí)開始繪制下頁(yè)圖4中含有校驗(yàn)碼的二維矩陣。通過校驗(yàn)可以發(fā)現(xiàn)第三行中的“1”變成了奇數(shù)個(gè),同時(shí)第三列中的“1”也變成了奇數(shù)個(gè),因此可以判斷是第三行和第三列交叉處的數(shù)據(jù)發(fā)生了錯(cuò)誤。
這時(shí)通過按鈕“B”來進(jìn)行糾錯(cuò),完成整個(gè)的傳輸糾錯(cuò)過程,代碼如下頁(yè)圖5所示。
通過上面的實(shí)驗(yàn)可以了解奇偶校驗(yàn)是如何檢測(cè)并修正一個(gè)錯(cuò)誤的,但計(jì)算機(jī)中會(huì)有不止一個(gè)數(shù)據(jù)發(fā)生錯(cuò)誤的時(shí)候,當(dāng)出現(xiàn)這樣的情況時(shí),有一種特殊情況是能夠被糾正的。下頁(yè)圖6就顯示了這樣一個(gè)奇偶校驗(yàn)陣列(每行每列的白色卡片數(shù)均為偶數(shù)),但是它的第四列數(shù)據(jù)全部丟失(灰色區(qū)域)。RAID(獨(dú)立冗余磁盤陣列)硬盤系統(tǒng)采用的就是這種糾錯(cuò)方式,通過將數(shù)據(jù)分散存儲(chǔ)在多塊硬盤中,來保證運(yùn)行的高速性和穩(wěn)定性。
上述實(shí)驗(yàn)只是模擬了奇偶校驗(yàn)中的基本原理,利用這種校驗(yàn)方法還可以設(shè)計(jì)一個(gè)讀心術(shù)小游戲。首先準(zhǔn)備好36張卡片,要保證每張卡片正反兩面的圖案和顏色不同(如實(shí)驗(yàn)中的白色和黑色矩形)。找一個(gè)同伴,由他來把卡片放在桌子上,并決定每張卡片放置的正反。接下來,你可以增加幾張卡片(添加校驗(yàn)數(shù)據(jù)),然后轉(zhuǎn)身,這時(shí)讓你的同伴隨意翻轉(zhuǎn)一張卡片,當(dāng)他翻轉(zhuǎn)后你總能正確地說出哪一張卡片是他翻過的。
奇偶校驗(yàn)系統(tǒng)的優(yōu)化方案稱為RAID5。假設(shè)需要使用8個(gè)硬盤來儲(chǔ)存大量的數(shù)據(jù),這些數(shù)據(jù)包含大量字節(jié),可能超過數(shù)億字節(jié)(吉字節(jié))甚至千億字節(jié)(太字節(jié))。這時(shí),可以將每個(gè)字節(jié)打散成8比特分別儲(chǔ)存在多個(gè)硬盤上,而不是將數(shù)據(jù)陸續(xù)填滿每個(gè)磁盤。這樣的存儲(chǔ)方式會(huì)讓系統(tǒng)運(yùn)行得更快,因?yàn)楫?dāng)計(jì)算機(jī)需要讀取文件時(shí),它只要分別同時(shí)向每塊硬盤讀取片段即可。該方法也可用于提高糾錯(cuò)性能:如果再增加存有奇偶校驗(yàn)位的第9塊硬盤,我們可以用上面的思路讓每一列數(shù)據(jù)分別放在不同的硬盤上,這樣一來,如果其中一塊硬盤被損壞,即使損失全部數(shù)據(jù),仍然能依靠奇偶校驗(yàn)的思路來修復(fù)原始數(shù)據(jù)——只要算出遺失的比特使得9個(gè)硬盤上值為1的比特?cái)?shù)總保持為偶數(shù)即可。正是因?yàn)镽AID系統(tǒng)的存儲(chǔ)速度飛快,任何一塊硬盤被損壞也不會(huì)影響原始數(shù)據(jù)的讀取。所以,對(duì)于大型數(shù)據(jù)中心和主要的網(wǎng)站來說,RAID已經(jīng)成為提高運(yùn)行速度和保障穩(wěn)定性的優(yōu)選方案。
信息的傳輸過程中很難避免干擾和錯(cuò)誤的出現(xiàn),糾錯(cuò)是一種很好的解決方法,糾錯(cuò)的方式有很多,奇偶校驗(yàn)只是一種比較容易理解的方式,通過這種方式可以幫助學(xué)生非常直觀地理解糾錯(cuò)的原理,這種類似的演示實(shí)驗(yàn)設(shè)計(jì),可能會(huì)成為今后信息科技的一個(gè)探索方向。