奇偶校驗(yàn)碼在數(shù)據(jù)傳輸中的實(shí)現(xiàn)?

王 軍 劉 曦 羅清龍

1 引言

在信息的傳輸中，模擬信號(hào)的保真度一直受到各方面原因的限制，失真時(shí)有發(fā)生，而數(shù)字信號(hào)則用0、1兩個(gè)數(shù)字承載所傳輸?shù)男畔?，?zhǔn)確讀出數(shù)字即可保證信息的準(zhǔn)確性。與模擬信號(hào)相比，數(shù)字信號(hào)具有抗噪聲，抗干擾強(qiáng)的特點(diǎn)。但是過強(qiáng)的噪聲的干擾極有可能將傳輸?shù)?變?yōu)?，1變?yōu)?，此時(shí)以編碼理論為基礎(chǔ)的編碼糾錯(cuò)技術(shù)的存在在數(shù)字通信中就顯得尤為重要了。

對(duì)于通信系統(tǒng)而言，糾錯(cuò)碼的出現(xiàn)無疑提高了其通信的可靠性，大大增加了通信成功的概率。在多數(shù)實(shí)際差錯(cuò)控制系統(tǒng)中都使用線性碼作為數(shù)據(jù)傳輸過程中的校驗(yàn)糾錯(cuò)碼，因此對(duì)線性分組碼的研究是非常有必要的，不僅在學(xué)術(shù)方面意義重大，實(shí)際應(yīng)用價(jià)值也非常巨大。

本文主要研究一維及二維奇偶校驗(yàn)碼編碼和譯碼算法，并使用C語言來實(shí)現(xiàn)奇偶校驗(yàn)糾錯(cuò)碼的編碼譯碼算法，而這些研究展現(xiàn)了其良好的檢錯(cuò)糾錯(cuò)性能。一維奇偶校驗(yàn)碼根據(jù)其編碼位置的不同可分為垂直奇偶校驗(yàn)碼和水平奇偶校驗(yàn)碼，其中垂直奇偶校驗(yàn)碼對(duì)隨機(jī)錯(cuò)誤有很好的檢測(cè)效果，水平奇偶校驗(yàn)碼相對(duì)于垂直奇偶校驗(yàn)碼增加了檢測(cè)突發(fā)錯(cuò)碼的能力，二者都沒有糾錯(cuò)能力。本文將主要對(duì)水平奇偶校驗(yàn)碼的檢錯(cuò)功能進(jìn)行實(shí)現(xiàn)；二維奇偶檢驗(yàn)碼，也可以被稱為矩陣碼或水平垂直一致校驗(yàn)碼，檢錯(cuò)效果要優(yōu)于一維奇偶校驗(yàn)碼，具有一定的糾錯(cuò)能力，適用于檢測(cè)成串出現(xiàn)的突發(fā)錯(cuò)碼，在數(shù)據(jù)傳輸網(wǎng)絡(luò)中應(yīng)用較多，因此本文將對(duì)其檢錯(cuò)糾錯(cuò)功能進(jìn)行實(shí)現(xiàn)。

2 一維及二維奇偶校驗(yàn)碼概述

奇偶校驗(yàn)碼編碼的基本原理就是在信息位之前或之后額外增添1個(gè)冗余位，使得整個(gè)碼字中“1”的個(gè)數(shù)恒為奇數(shù)或偶數(shù)，而增加1個(gè)冗余位可以使碼距變?yōu)?，這樣就可以擁有檢測(cè)1位錯(cuò)誤的能力。奇偶校驗(yàn)應(yīng)用時(shí)一般將一個(gè)字節(jié)作為最小校驗(yàn)單位。而一個(gè)ASCII字符恰好占用一個(gè)字節(jié)也就是8位，因此也可以說奇偶校驗(yàn)碼以字符為最小單位來使用。而在現(xiàn)實(shí)的應(yīng)用中，又可以將其細(xì)分為垂直奇偶校驗(yàn)、水平奇偶校驗(yàn)和水平垂直奇偶校驗(yàn)這三種來使用，三種碼可分別應(yīng)用于不同的信道。此種校驗(yàn)方法的實(shí)質(zhì)其實(shí)就是確定一組被傳輸?shù)亩M(jìn)制代碼中“1”的個(gè)數(shù)的奇偶性。若最終確定信息碼組中“1”的個(gè)數(shù)為奇數(shù)的話就稱其為奇校驗(yàn)，反之，則稱為偶校驗(yàn)。

垂直奇偶校驗(yàn)碼和水平奇偶校驗(yàn)碼，只在一個(gè)方向上添加校驗(yàn)位，因此被稱為一維奇偶校驗(yàn)碼。

垂直奇偶校驗(yàn)，可以稱其為縱向奇偶校驗(yàn)，原則是對(duì)所要發(fā)送整個(gè)信息劃分成長(zhǎng)度一定的段信息，一般情況下以一個(gè)字節(jié)為一段，每個(gè)段信息后面按“1”的個(gè)數(shù)的奇偶性來添加一位奇偶位，也叫校驗(yàn)位。垂直奇偶校驗(yàn)碼，設(shè)每段信息的信息位為n位，那么編碼效率就是n/（n+1）。使用垂直奇偶校驗(yàn)碼可以檢測(cè)出每段信息中所有的奇數(shù)個(gè)錯(cuò)，但是任何偶數(shù)個(gè)的錯(cuò)都將無法檢測(cè)出。

水平奇偶校驗(yàn)，又可以稱其為橫向奇偶校驗(yàn)，原則是對(duì)劃分出來的所有信息段的相應(yīng)位來添加一個(gè)奇偶位，相當(dāng)于對(duì)所發(fā)送的各段信息橫向進(jìn)行奇偶編碼。水平奇偶校驗(yàn)碼，若所發(fā)送的信息塊被分為m段，每段n位，則其編碼效率為m/（m+1）。其可以檢測(cè)出各段同一位上所有的奇數(shù)個(gè)錯(cuò)，而且還能檢測(cè)出突發(fā)長(zhǎng)度不多于n（n為碼字的定長(zhǎng)位數(shù)）和突發(fā)長(zhǎng)度不為n的偶數(shù)倍以外的所有突發(fā)錯(cuò)誤。

二維奇偶校驗(yàn)碼，由于其編碼的方向，因此可以稱為水平垂直奇偶校驗(yàn)。通信系統(tǒng)在對(duì)整個(gè)以字節(jié)為分段單位的數(shù)據(jù)信息進(jìn)行傳送之前，除了對(duì)每個(gè)字節(jié)添加一個(gè)奇偶校驗(yàn)位，還要對(duì)所有字節(jié)所對(duì)應(yīng)的同一位也添加一個(gè)奇偶校驗(yàn)位，即結(jié)合兩種一維校驗(yàn)的方法。通過這種橫向、縱向同時(shí)進(jìn)行校驗(yàn)的方式來對(duì)整個(gè)信息塊進(jìn)行校驗(yàn)，稱這種校驗(yàn)方法稱為交叉校驗(yàn)。交叉檢驗(yàn)之所以擁有更好的檢錯(cuò)性能，就是因?yàn)槠溆锌赡軝z測(cè)出偶數(shù)個(gè)錯(cuò)誤。很容易理解，盡管每行的校驗(yàn)位無法檢測(cè)出本行中的偶數(shù)個(gè)錯(cuò)碼，但是按列的方向來進(jìn)行檢測(cè)的話檢測(cè)出來的概率是非常大的。但與此同時(shí)某些偶數(shù)錯(cuò)碼對(duì)其來說就是盲區(qū)了，比如可以構(gòu)成矩形的四個(gè)錯(cuò)碼。盡管如此，與前述的簡(jiǎn)單奇偶校驗(yàn)相比，其檢錯(cuò)性能要更優(yōu)越。此外，二維奇偶校驗(yàn)碼擁有一定的糾錯(cuò)功能，可以糾正部分錯(cuò)碼，比如對(duì)于碼組中的1個(gè)隨機(jī)錯(cuò)誤，完全就可以確定錯(cuò)碼的位置，從而對(duì)其進(jìn)行糾正。對(duì)于一個(gè)擁有m段，每段n位的信息塊，二維奇偶校驗(yàn)碼的編碼效率為（m×n）/［（m+1）×（n+1）］。其適用于檢測(cè)突發(fā)錯(cuò)碼。除檢錯(cuò)外，二維奇偶校驗(yàn)碼可以確定某些錯(cuò)誤的位置，進(jìn)而對(duì)其進(jìn)行糾正。

3 一維及二維奇偶校驗(yàn)碼的編譯碼

3.1 編碼過程

對(duì)于同一個(gè)信息塊，垂直奇偶校驗(yàn)是將其分為定長(zhǎng)n位的m段，設(shè)為Iij（i=1，…，n；j=1，…，m），每段后面按“1”的個(gè)數(shù)為奇數(shù)或偶數(shù)的規(guī)律加上一位校驗(yàn)位ri（i=1，2，3，…，m）。水平奇偶校驗(yàn)碼則是對(duì)n位m段信息的相應(yīng)位橫向進(jìn)行編碼，每段后面按“1”的個(gè)數(shù)為奇數(shù)或偶數(shù)的規(guī)律加上一位校驗(yàn)位ri（i=1，2，3，…，n）。

對(duì)于一個(gè)信息塊，將其分為定長(zhǎng)為n位的m段后，二維奇偶校驗(yàn)碼不僅對(duì)每段信息進(jìn)行奇偶校驗(yàn)編碼，而且同時(shí)對(duì)m段信息的相應(yīng)位進(jìn)行奇偶校驗(yàn)編碼。

三者的編碼規(guī)則是一致的，以垂直奇偶校驗(yàn)碼為例，具體的編碼規(guī)則為

奇校驗(yàn)的校驗(yàn)位可由式（1）求得。

偶校驗(yàn)的校驗(yàn)位可由式（2）求得。

在各種實(shí)際應(yīng)用情況中，一般都是采用奇校驗(yàn)，原因是使用奇校驗(yàn)可以使碼字中不存在全“0”代碼，在一些場(chǎng)合中就會(huì)更加便于判別。

3.2 譯碼過程

奇偶校驗(yàn)碼的譯碼也非常簡(jiǎn)單，對(duì)于垂直奇偶校驗(yàn)碼而言，若經(jīng)檢驗(yàn)該段無差錯(cuò)，我們只需要在接收端將該段的最后一位校驗(yàn)位去掉即可。而對(duì)于水平奇偶校驗(yàn)碼而言，譯碼則需等到整個(gè)信息塊到達(dá)且確認(rèn)無誤后進(jìn)行。若發(fā)現(xiàn)信息出錯(cuò)，對(duì)一維奇偶校驗(yàn)碼而言則需要重傳。

二維奇偶校驗(yàn)碼譯碼時(shí)也需等到整個(gè)信息塊到達(dá)，然后分別檢查各行、各列的校驗(yàn)關(guān)系，判斷是否有錯(cuò)，若無錯(cuò)則可提取整個(gè)信息。若判斷有錯(cuò)，在某些情況下可以進(jìn)行糾錯(cuò)，若無法糾錯(cuò)，則信息塊就要重傳。

4 奇偶校驗(yàn)碼的實(shí)現(xiàn)及結(jié)果

4.1 一維奇偶校驗(yàn)碼的算法

由于水平奇偶校驗(yàn)碼的檢錯(cuò)能力相對(duì)垂直奇偶校驗(yàn)碼更優(yōu)，而且二者編譯碼方法一致，所以在此我們僅對(duì)水平奇偶校驗(yàn)碼的實(shí)現(xiàn)算法進(jìn)行設(shè)計(jì)。

具體的實(shí)現(xiàn)過程如下：

1）信息矩陣中暫存所傳信息；

2）對(duì)m段信息的對(duì)應(yīng)位增加奇校驗(yàn)位；

3）發(fā)送信息位；

4）接收端接收整個(gè)信息塊后，判斷信息是否出現(xiàn)誤碼，如果有誤碼，轉(zhuǎn)到3），否則繼續(xù)；

5）刪去校驗(yàn)位得到的信息。

4.2 二維奇偶校驗(yàn)碼的算法

二維奇偶校驗(yàn)碼的檢錯(cuò)效果很好，尤其是對(duì)突發(fā)錯(cuò)誤的檢查，在一定情況下還可以對(duì)這些錯(cuò)誤實(shí)現(xiàn)糾正，比如在整個(gè)信息塊中僅發(fā)生1個(gè)隨機(jī)錯(cuò)誤時(shí)是肯定可以糾正的，因此對(duì)二維奇偶校驗(yàn)碼的實(shí)現(xiàn)過程如下：

1）信息矩陣中暫存所傳信息；

2）對(duì)m段信息的對(duì)應(yīng)位增加奇校驗(yàn)位；

3）發(fā)送信息位；

4）接收端接收整個(gè)信息塊后，判斷信息是否出現(xiàn)誤碼，如果沒有誤碼，則繼續(xù)執(zhí)行，如果有誤碼，再判斷誤碼是否為極少個(gè)，如果為否，則轉(zhuǎn)到3），否則對(duì)誤碼進(jìn)行糾正；

5）刪去校驗(yàn)位得到的信息。

4.3 水平奇偶校驗(yàn)碼的實(shí)現(xiàn)及實(shí)現(xiàn)結(jié)果

1）水平奇偶校驗(yàn)碼的編碼實(shí)現(xiàn)及實(shí)現(xiàn)結(jié)果

水平奇偶校驗(yàn)碼的編碼就是對(duì)m段信息的對(duì)應(yīng)位添加校驗(yàn)位，此處選擇奇校驗(yàn)，假設(shè)有8個(gè)字節(jié)，具體實(shí)現(xiàn)代碼如下：

int i=0，j=0；//i代表列，j代表行

while（i＜8）

｛

c=0；

while（j＜8）

｛

if（I［j］［i］==1）

c++；

j++；

｝

if（c%2==0）

R［i］=1；

else

R［i］=0；

i++；

｝

編碼實(shí)現(xiàn)結(jié)果如圖1所示，發(fā)送時(shí)只需將信息塊按段發(fā)出，校驗(yàn)位一般位于最高位，應(yīng)當(dāng)首先發(fā)送。

2）水平奇偶校驗(yàn)碼的檢錯(cuò)功能實(shí)現(xiàn)及實(shí)現(xiàn)結(jié)果

水平奇偶校驗(yàn)碼的檢錯(cuò)功能優(yōu)于垂直奇偶校驗(yàn)碼的原因就是其可以對(duì)突發(fā)錯(cuò)誤的進(jìn)行檢測(cè)。接收端可完成水平奇偶檢驗(yàn)碼的檢測(cè)功能，具體實(shí)現(xiàn)如下：

int i=0，j=0；//i代表列，j代表行

while（i＜=7）

｛

c=0；

while（j＜=7）

｛

if（I［j］［i］==1）

c++；

j++；

｝

if（c%2==0）

temp=1；

else

temp=0；

if（R［i］==temp）

printf（“段信息對(duì)應(yīng)第%d位無差錯(cuò) ”，n）；

else

printf（“段信息對(duì)應(yīng)第%d位出錯(cuò) ”，n）；

i++；

｝

圖1 水平奇偶校驗(yàn)碼編碼實(shí)現(xiàn)結(jié)果

在不出現(xiàn)錯(cuò)誤的情況下，也就是不添加模擬信道出錯(cuò)的代碼，則可得到如圖2的結(jié)果。

圖2 水平奇偶校驗(yàn)碼的檢錯(cuò)結(jié)果1

若添加模擬信道隨機(jī)出現(xiàn)突發(fā)錯(cuò)誤的代碼，即如下代碼：

srand（（unsigned）time（NULL））；

rand_row=rand（）%8；

rand_col=rand（）%8；

error_c=8-rand_col；

printf（“從%d行%d列開始將連續(xù)出現(xiàn)%d個(gè)錯(cuò)誤 ”，rand_row，rand_col，error_c）；

while（error_c＞0）

｛

if（I［rand_row］［rand_col］==‘1’）

I［rand_row］［rand_col］=‘0’；

else

I［rand_row］［rand_col］=‘1’；

rand_col++；

error_c--；

｝

運(yùn)行便可以得到如圖3的檢錯(cuò)結(jié)果。

圖3 水平奇偶校驗(yàn)碼的檢錯(cuò)結(jié)果2

令信息矩陣隨機(jī)出現(xiàn)突發(fā)錯(cuò)誤，最終的檢驗(yàn)結(jié)果與其出現(xiàn)誤碼的位置是相同的。

4.4 二維奇偶校驗(yàn)碼的實(shí)現(xiàn)及實(shí)現(xiàn)結(jié)果

1）二維奇偶奇偶校驗(yàn)碼的編碼實(shí)現(xiàn)及實(shí)現(xiàn)結(jié)果

二維奇偶校驗(yàn)碼的編碼原理與一維奇偶校驗(yàn)碼相同，同樣假設(shè)有8個(gè)字節(jié)的信息，具體的實(shí)現(xiàn)過程如下：

int i=0，j=0；//i代表列，j代表行

while（i＜=7）

｛

c_col=0；

while（j＜=7）

｛

if（I［j］［i］==1）

c_col++；

j++；

｝

if（c_col%2==0）

R_col［i］=1；

else

R_col［i］=0；

i++；

｝

printf（“列校驗(yàn)位為： ”）；

while（i＜=7）

｛

printf（“%2d”，R_col［i］）；

i++；

｝

printf（“ ”）；

while（j＜=7）

｛

c_row=0；

while（i＜=7）

｛

if（I［j］［i］==1）

c_row++；

i++；

｝

if（c_row%2==0）

R_row［j］=1；

else

R_row［j］=0；

j++；

｝

printf（“行校驗(yàn)位為： ”）；

while（j＜=7）

｛

printf（“%2d ”，R_row［j］）；

j++；

｝

編碼的實(shí)現(xiàn)結(jié)果如圖4所示。

圖4 二維奇偶校驗(yàn)碼的編碼結(jié)果

2）二維奇偶校驗(yàn)碼的檢錯(cuò)糾錯(cuò)實(shí)現(xiàn)及實(shí)現(xiàn)結(jié)果

二維奇偶校驗(yàn)碼擁有一定的糾錯(cuò)能力，若發(fā)送8個(gè)字節(jié)的信息，當(dāng)發(fā)生極少數(shù)的隨機(jī)錯(cuò)誤，比如1個(gè)隨機(jī)錯(cuò)誤，我們就可以確定錯(cuò)誤發(fā)生的位置，從而進(jìn)行糾錯(cuò)。檢錯(cuò)糾錯(cuò)代碼如下：

int i=0，j=0；

while（i＜=7）

｛

c_col=0；

while（j＜=7）

｛

if（I［j］［i］==1）

c_col++；

j++；

｝

if（c_col%2==0）

temp=1；

else

temp=0；

if（R_col［i］！=temp）

printf（“%d列出錯(cuò) ”，i）；

i++；

｝

printf（“ ”）；

while（j＜=7）

｛

c_row=0；

while（j＜=7）

｛

if（I［j］［i］==1）

c_row++；

j++；

｝

if（c_row%2==0）

temp=1；

else

temp=0；

if（R_row［j］！=temp）

printf（“%d行出錯(cuò) ”，j）；

j++；

｝

若發(fā)生1個(gè)隨機(jī)錯(cuò)誤，可得到如圖5的結(jié)果。可以看出隨機(jī)產(chǎn)生1個(gè)錯(cuò)誤的話，二維奇偶校驗(yàn)碼可以得到誤碼在哪行哪列，從而進(jìn)行糾正。

圖5 二維奇偶校驗(yàn)碼的檢錯(cuò)糾錯(cuò)結(jié)果

5 結(jié)語

文章對(duì)一維、二維奇偶校驗(yàn)碼原理及編譯碼方法進(jìn)行了研究，提供了一維及二維奇偶校驗(yàn)碼檢錯(cuò)能力的算法設(shè)計(jì)。利用了C語言實(shí)現(xiàn)了一維、二維奇偶校驗(yàn)碼的檢錯(cuò)、糾錯(cuò)功能，得到了比較理想的結(jié)果，設(shè)計(jì)的程序簡(jiǎn)單有效，易于理解應(yīng)用，給以后更深入的研究奠定了基礎(chǔ)。

［1］韓天榮.奇偶校驗(yàn)碼的產(chǎn)生和檢驗(yàn)方法［J］.集寧師專學(xué)報(bào)，2004，26（3）：30-31.

HAN Tianrong.The method of produce and check parity code［J］.Journal of Jining Normal College，2004，26（3）：30-31.

［2］Luděk Dud ácˇek，Ivo Veˇrtát.Multidimensional Parity Check codes with short block lengths［J］.24th Telecommunications forum TELFOR，2016：1-3.

［3］楊鴻文.通信原理［M］.北京：北京郵電大學(xué)出版社，2008：467-475.

YANG Hongwen.Communication Fundamentals［M］.Beijing：Beijing University of Posts and Telecommunication Press，2008：467-475.

［4］葛林富.多維奇偶校驗(yàn)碼的糾錯(cuò)效果分析［J］.西南交通大學(xué)學(xué)報(bào)，1998（1）：80-83.

GEFulin.Analysis of error correction effect of multidimensional parity codes［J］.Journal of Southwest Jiaotong University，1998（1）：80-83.

［5］唐朔飛.計(jì)算機(jī)組成原理［M］.北京：高等教育出版社，2006：53-57.

TANG Shuofei.Principles of Computer Composition［M］.Beijing：Higher Education Press，2006：53-57.

［6］嚴(yán)蔚敏，等.數(shù)據(jù)結(jié)構(gòu)教程（C語言版）［M］.北京：清華大學(xué)出版社，2009：103-108.

YAN Weimin.Data structure course（C language version）［M］.Beijing：Tsinghua University Press，2009：103-108.

［7］錢建發(fā).糾錯(cuò)碼理論及應(yīng)用研究［D］.西安：西安電子科技大學(xué)，2010：7-9.

QIAN Jianfa.Research on Error-correcting Code and Its Application［D］.Xi'an：Xidian University，2010：7-9.

［8］譚浩強(qiáng).C程序設(shè)計(jì)［M］.北京：清華大學(xué)出版社，2010，148-152.

TAN Haoqiang.C Program Design［M］.Beijing：Tsinghua University Press，2010，148-152.

［9］邵朝，于凱云.聯(lián)合迭代均衡譯碼算法［J］.西安郵電大學(xué)學(xué)報(bào)，2016，21（4）：23-25.

SHAO Chao，YU Kaiyun.Joint Iterative Equalization Decoding Algorithm［J］.Journal of Xi'an Institute of Posts and Telecommunications，2016，21（4）：23-25.

［10］李高和，殷娟娟，程建國(guó).一種新型的隨機(jī)奇偶校驗(yàn)碼［J］.經(jīng)營(yíng)者管理，2015（15）：420-420.

LI Gaohe，YIN Juanjuan，CHENG Jianguo.A new Random Parity Code［J］.Manager'Journal，2015（15）：420-420.

［11］曹德勝.糾錯(cuò)碼在計(jì)算機(jī)科學(xué)中的應(yīng)用：離散數(shù)學(xué)與糾錯(cuò)碼［J］.華北礦業(yè)高等?？茖W(xué)校學(xué)報(bào)，2000，2（1）：25-28.

CAO Desheng.The application of error correcting codes in Computer Science：Discrete Mathematics and error correcting codes［J］.Journal of North China Mining College，2000，2（1）：25-28.