前向糾錯算法的研究

肖利平

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

0 引言

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

自動請求重發技術就是當接收端所接收的信息碼有錯時，請求發送端重新發送該組信息碼。

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

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

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

2 前向糾錯算法

2.1 邏輯異或運算

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

2.2 算法描述

2.2.1 校驗碼及校驗公式

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

B9～B16的計算式:

2.2.2 校驗方法

在發送端，用(1)～(8)式計算出校驗碼B9～B16，連同前8位信息碼一道發出；在接收端，用(9)～(16)式進行校驗，若這8個式子的計算結果都為0，則說明傳輸正確，只要有一個式子的計算結果為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 算法的證明

在這里，我們采用反證法進行證明。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

證畢。

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

3 結語

本算法顯著的優點是:每組發送的信息碼為8個二進制位，而標準的ASCII碼每個字符的長度也正好是8位，因此，每次可發送一個完整的字符，這正符合現代計算機網絡通信規范。算法存在的主要不足是:信息的傳輸量要增加一倍。如何壓縮校驗位的長度，值得繼續研究。

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