前向糾錯算法的研究

肖利平

(貴州理工學(xué)院，貴州 貴陽 550003)

0 引言

在現(xiàn)代通信過程中，差錯控制方法主要有3種:自動請求重發(fā)技術(shù)、反饋校驗技術(shù)和前向糾錯技術(shù)。

自動請求重發(fā)技術(shù)就是當(dāng)接收端所接收的信息碼有錯時，請求發(fā)送端重新發(fā)送該組信息碼。

反饋校驗法就是接收端接收到的信息后，無論其正確與否，都無條件地將接收到的信息碼原原本本地送回到發(fā)送端，由發(fā)送端進(jìn)行判斷，若不正確，則自動重發(fā)該組信息碼。

前向糾錯技術(shù)的基本思想是，接收端不僅能對數(shù)據(jù)進(jìn)行錯誤判斷，而且還能對錯誤進(jìn)行定位，從而能自動進(jìn)行糾錯。糾錯時，將錯誤位求反即可。

本文研究的就是第三種差錯控制方法，即前向糾錯算法。

2 前向糾錯算法

2.1 邏輯異或運算

邏輯異或運算符通常用“⊕”表示。其運算規(guī)則是，相同兩數(shù)碼異或結(jié)果得0，不同兩數(shù)碼異或結(jié)果得1。

2.2 算法描述

2.2.1 校驗碼及校驗公式

算法的設(shè)計思路是，每組傳輸信息由8個數(shù)碼位＋8個校驗位組成，即一個傳輸信息組共16位，依次用B1～B16表示。

B9～B16的計算式:

2.2.2 校驗方法

在發(fā)送端，用(1)～(8)式計算出校驗碼B9～B16，連同前8位信息碼一道發(fā)出；在接收端，用(9)～(16)式進(jìn)行校驗，若這8個式子的計算結(jié)果都為0，則說明傳輸正確，只要有一個式子的計算結(jié)果為1，則說明傳輸有錯。

2.2.3 判斷法則

法則1:若(9)～(16)式子全錯，則B1必錯；

法則2:若只有(10)式正確而其余7個式子全錯，則B2必錯；

法則3:若只有(11)式正確而其余7個式子全錯，則B3必錯；

法則4:若只有(12)式正確而其余7個式子全錯，則B4必錯；

法則5:若只有(13)式正確而其余7個式子全錯，則B5必錯；

法則6:若只有(14)式正確而其余7個式子全錯，則B6必錯；

法則7:若只有(15)式正確而其余7個式子全錯，則B7必錯；

法則8:若只有(16)式正確而其余7個式子全錯，則B8必錯；

法則9:若只有(9)式錯而其余7個式子正確，則B9必錯；

法則10:若只有(10)式錯而其余7個式子正確，則B10必錯；

法則11:若只有(11)式錯而其余7個式子正確，則B11必錯；

法則12:若只有(12)式錯而其余7個式子正確，則B12必錯。

法則13:若只有(13)式錯而其余7個式子正確，則B13必錯；

法則14:若只有(14)式錯而其余7個式子正確，則B14必錯；

法則15:若只有(15)式錯而其余7個式子正確，則B15必錯；

法則16:若只有(16)式錯而其余7個式子正確，則B16必錯。

2.2.4 算法的證明

在這里，我們采用反證法進(jìn)行證明。

由于篇幅所限，本文只證明第一種情況:即當(dāng)(9)～(16)式全錯時，B1必錯，而其他位正確。

假設(shè)(9)～(16)式全錯，而B1正確，則B2～B16必有一位錯。

假設(shè)B2錯，而B1，B3～B16正確，將其代入(9)～(16)式:

從上述計算結(jié)果可看出，只有(10)式正確而其余式全錯，與“(9)～(16)式全錯”相矛盾，因此，B2不可能有錯。

假設(shè)B3錯，而其余位正確，將其代入(9)～(16)式:

從上述計算結(jié)果可看出，只有(11)式正確而其余式全錯，與“(9)～(16)式全錯”相矛盾，因此，B3不可能有錯。

假設(shè)B4錯，而其余位正確，將其代入(9)～(16)式:

從上述計算結(jié)果可看出，只有(12)式正確而其余式全錯，與“(9)～(16)式全錯”相矛盾，因此，B4不可能有錯。

假設(shè)B5錯，而其余位正確，將其代入(9)～(16)式:

從上述計算結(jié)果可看出，只有(13)式正確而其余式全錯，與“(9)～(16)式全錯”相矛盾，因此，B5不可能有錯。

假設(shè)B6錯，而其余位正確，將其代入(9)～(16)式:

從上述計算結(jié)果可看出，只有(14)式正確而其余式全錯，與“(9)～(16)式全錯”相矛盾，因此，B6不可能有錯。

假設(shè)B7錯，而其余位正確，將其代入(9)～(16)式:

從上述計算結(jié)果可看出，只有(15)式正確而其余式全錯，與“(9)～(16)式全錯”相矛盾，因此，B7不可能有錯。

假設(shè)B8錯，而其余位正確，將其代入(9)～(16)式:

從上述計算結(jié)果可看出，只有(16)式正確而其余式全錯，與“(9)～(16)式全錯”相矛盾，因此，B8不可能有錯。

假設(shè)B9錯，而其余位正確，將其代入(9)～(16)式:

從上述計算結(jié)果可看出，只有(9)式錯而其余式正確，與“(9)～(16)式全錯”相矛盾，因此，B9不可能有錯。

假設(shè)B10錯，而其余位正確，將其代入(9)～(16)式:

從上述計算結(jié)果可看出，只有(10)式錯而其余式正確，與“(9)～(16)式全錯”相矛盾，因此，B10不可能有錯。

假設(shè)B11錯，而其余位正確，將其代入(9)～(16)式:

從上述計算結(jié)果可看出，只有(11)式錯而其余式正確，與“(9)～(16)式全錯”相矛盾，因此，B11不可能有錯。

假設(shè)B12錯，而其余位正確，將其代入(9)～(16)式:

從上述計算結(jié)果可看出，只有(12)式錯而其余式正確，與“(9)～(16)式全錯”相矛盾，因此，B12不可能有錯。

假設(shè)B13錯，而其余位正確，將其代入(9)～(16)式:

從上述計算結(jié)果可看出，只有(13)式錯而其余式正確，與“(9)～(16)式全錯”相矛盾，因此，B13不可能有錯。

假設(shè)B14錯，而其余位正確，將其代入(9)～(16)式:

從上述計算結(jié)果可看出，只有(14)式錯而其余式正確，與“(9)～(16)式全錯”相矛盾，因此，B14不可能有錯。

假設(shè)B15錯，而其余位正確，將其代入(9)～(16)式:

從上述計算結(jié)果可看出，只有(15)式錯而其余式正確，與“(9)～(16)式全錯”相矛盾，因此，B15不可能有錯。

假設(shè)B16錯，而其余位正確，將其代入(9)～(16)式:

從上述計算結(jié)果可看出，只有(16)式錯而其余式正確，與“(9)～(16)式全錯”相矛盾，因此，B16不可能有錯。

由上證明過程可看出，在(9)～(16)式全錯的情況下，B2～B16都不可能有錯，因此，必有B1錯。

證畢。

同理，可證明其他15種情況。

3 結(jié)語

本算法顯著的優(yōu)點是:每組發(fā)送的信息碼為8個二進(jìn)制位，而標(biāo)準(zhǔn)的ASCII碼每個字符的長度也正好是8位，因此，每次可發(fā)送一個完整的字符，這正符合現(xiàn)代計算機網(wǎng)絡(luò)通信規(guī)范。算法存在的主要不足是:信息的傳輸量要增加一倍。如何壓縮校驗位的長度，值得繼續(xù)研究。

在實際網(wǎng)絡(luò)通信過程，糾錯時只需要判斷前8位B1～B8的正確性，而后8位B9～B16是不必判斷的，這樣可節(jié)省差錯判斷的時間，以提高通信數(shù)據(jù)處理能力。