【文章內(nèi)容簡介】 發(fā)送信息碼 T（ X） 為 N=k+n位 ， 其對應(yīng)多項式記為： T（ X） =X4 K（ X） +R（ X） （ 這里的 Xn中的 n是指有 n位冗余碼 ） 因為信息碼為 1011001， 冗余碼為 1010， 所以發(fā)送信息碼字為 : T（ X） =X4 K（ x） +R（ x） =X10+X8+X7+X4+X3+X =10110011010 由信息位產(chǎn)生冗余位的編碼過程 ， 就是己知 K（ x） 求 R（ x） 的過程 。 在 CRC碼中可以通過找到一個特定的 n次多項式 G（ X） ， 用 G（ X） 去除 Xn K（ x） 所得到的余式就是 R（ x） 。 設(shè) : K（ X） =X6+X4+X3+1 即： K（ X） =1011001 n=4 G（ X） = X4+X3+1 即 :11001 （ 實際上 ， G（ X） 是 K（ X） 的后 5位 ） 則 :X4 K（ X） =X10+X8+X7+X4 即 :10110010000 由上看出 , X4 K（ X）實際上是在 K（ X）后添加 4個 0得到的。 用 G（ X） 去連除 （ 即不斷進(jìn)行異或 ） X4 K（ X） 有 : 10110010000 11001 1111010000 11001 11110000 11001 111000 11001 1010 （ 余數(shù) ） 從 左邊的 演算過程中看出 ， 經(jīng)過若干次異或運(yùn)算后 ， 得到的最后余數(shù) 1010就是我們所需用的冗余碼 R（ X） ， 記為 R（ X） =X3+X。 設(shè)除法所得結(jié)果 （ 即商式 ） 為 Q（ X） ， 則有 : Xn K（ X） =G（ X） Q（ X） +R（ X） (1) 由于在信道上發(fā)送的碼字多項式為 T（ X） =Xn K（ X） +R（ X） ， 若傳輸無差錯 ， 則接收方收到的碼字也對應(yīng)此多項式 : T（ X） = Xn K（ X） +R（ X） (2) (1)代入 (2)有 : T（ X） =G（ X） Q（ X） +R（ X） +R（ X） (3) 由于加法采用的是半加和運(yùn)算 ， 即異或運(yùn)算 ， 所以 : R（ X） +R（ X） =0 所以 (3)式運(yùn)算結(jié)果為 : T（ X） =G（ X） Q（ X） 這一結(jié)果說明了 T（ X） 能被 G（ X） 整除 。 結(jié)論：在收端 ， 用信息碼與冗余碼進(jìn)行若干次異或運(yùn)算 ， 當(dāng)余式為零時則認(rèn)為傳輸無差錯 ， 否則認(rèn)為傳輸有差錯 。 驗算舉例： 設(shè) K（ X） =1011001， R（ X） =1010， G（ X） =11001 則： T（ X） = X4 K（ X） +R（ X） =10110011010 驗算方法：仍然采用不斷異或運(yùn)算的方法進(jìn)行驗算 ， 即用 T（ X） 與 G（ X）異或 ， 這里 G（ X） 取自 K（ X） 的后 5位 。 10110011010 11001 1111011010 11001 11111010 11001 110010 11001 0 驗算完畢 。 自動糾錯技術(shù) 自動糾錯就是在收端能自動檢測錯誤，并能進(jìn)行錯誤編碼的定位，從而能自動進(jìn)行糾錯。糾錯很簡單，將錯誤碼求反即可，關(guān)鍵是如何定位錯誤碼的位置。 1. 半加和運(yùn)算規(guī)則 在自動糾錯算法中，要用到半加和運(yùn)算，所以，在這里先介紹半加和的運(yùn)算規(guī)則。 半進(jìn)位加法（又叫做按位加法運(yùn)算）：按二進(jìn)制加法進(jìn)行加運(yùn)算，但不保留進(jìn)位位。 半借位減法（又叫做按位減法運(yùn)算）：按二進(jìn)制減法進(jìn)行減運(yùn)算，但不存在借位。 半進(jìn)位加減運(yùn)算又叫邏輯異或運(yùn)算，由以上運(yùn)算規(guī)則可看出，相同兩數(shù)碼異或得 “ 0”，不同兩數(shù)碼異或得 “ 1”。 2. 自動糾錯算法 (1)自動校驗公式及校驗碼 這里，我們以傳輸一個 4位數(shù)據(jù)為例，介紹一種自動糾錯的算法。 每個字符除了 4位數(shù)碼外，還要增加 4個校驗位，即一組信息共 8位。從左到右其二進(jìn)制編碼用 C1～ C8表示，其校驗碼計算公式如下： C1⊕ C2⊕ C3⊕ C4⊕ C5=0 (1) 即： C5＝ C1⊕ C2⊕ C3⊕ C4 (5) C1⊕ C2⊕ C3⊕ C6 ＝ 0 (2) C6＝ C4⊕ C5 (6) C1⊕ C3⊕ C4⊕ C7 ＝ 0 (3) C7＝ C2⊕ C5 (7) C1⊕ C2⊕ C4⊕ C8 ＝ 0 (4) C8＝ C3⊕ C5 (8) (2) 校驗方法 在發(fā)送端，用 (5)～ (8)式計算出校驗碼 C C C7和 C8，連同前４位數(shù)碼一起發(fā)給收端；在收端，用 (1)～ (4)式進(jìn)行校驗，若 4個式子計算結(jié)果都為 “ 0”，則傳正確，只要有一個式子的計算結(jié)果為 “ 1”，則說明傳輸有錯。 從上可看出，除了 (2)式正確（結(jié)果為 0）以外，其余 3式全錯（結(jié)果為 1）。 (3) 差錯判斷法則 若 (1)、 (2)、 (3)、 (4)式全錯，則 C1必錯；若 (1)、 (2)、(4)式錯而 (3)式不錯，則 C2必錯；若 (1)、 (2)、 (3)式錯而 (4)式不錯，則 C3必錯；若 (1)、 (3)、 (4)式錯而 (2)式不錯，則 C4必錯；若只有 (1)式錯則 C5必錯；若只有 (2)式錯則 C6必錯；若只有 (3)式錯則 C7必錯；若只有 (4)式錯則 C8必錯。 (4) 證明 在這里，我們采用反證法進(jìn)行證明。由于篇幅所限，這里只證明第一種情況。即當(dāng) (1)～ (4)式全錯時， C1必錯，而其他位正確。 設(shè) (1)～ (4)式全錯，而 C1不錯，則 C2～ C8必有一位錯。 ① 設(shè) C2錯，而 C1， C3～ C8正確。將 C1～ C8代入 (1)～ (4)有： C1⊕ C2⊕ C3⊕ C4⊕ C5=1 (1) C1⊕ C2⊕ C3⊕ C6 ＝ 1 (2) C1⊕ C3⊕ C4⊕ C7 ＝ 0 (3) C1⊕ C2⊕ C4⊕ C8 ＝ 1 (4) 由上看出， (1)、 (2)、 (4)式錯而 (3)式不錯，與 “ (1)～ (4)式全錯 ” 的條件相矛盾，所以 C2不可能錯。 其余情況的證明略。 值得注意的是 :上述介紹的幾種檢錯及糾錯方法中，只能檢測出一位編碼錯誤，對于兩位以上的錯誤是檢驗不出的。在實際通信過程中，誤碼本身是小概率事件，對于在一組數(shù)碼中同時出現(xiàn)兩位或兩位以上的錯誤的概率則更小，幾乎為 0，所以在實際應(yīng)用過程中，我們只考慮發(fā)生一位編碼錯誤的情況，即只對一位編碼錯誤進(jìn)行校驗和糾錯。 在實際應(yīng)用中，我們只須判斷前 4位數(shù)據(jù)編碼的正確性，即C1， C2， C3和 C4，后 4位是無須判斷的，也無須進(jìn)行糾錯。這樣能節(jié)省錯誤判斷和糾錯的時間，以提高數(shù)據(jù)傳輸?shù)乃俣群托省? 自動糾錯技術(shù)的應(yīng)用 在這里，我們?nèi)砸园l(fā)送字符串 “ Computer”為例，介紹。 將每個字符的 8位二進(jìn)制編碼（如 下 表所示）分成兩段，即高 4位和低 4位，分別求出其自動糾錯碼（校驗碼也是 4位）。 自動糾錯編碼用 （ 5）～（ 8）式計算，其校驗碼如表 78所示。表中的 “ 傳輸碼 ” 是由信息編碼的 4位再加上 4位校驗碼組成的。 表 78 “Computer”自動糾錯編碼表 序號 字符 ASCII碼（二進(jìn)制編碼） 校驗碼 傳輸碼 1 C 01000011 高 4位 0100 1101 01001101 低 4位 0011 0101 00110101 2 o 01101111 高 4位 0110 0011 01100011 低 4位 1111 0111 11110111 3 m 01101101 高 4位 0