【文章內容簡介】 收碼組是一個 n列的行矩陣 B： 令接收碼組和發(fā)送碼組之差為 E就是錯碼的行矩陣 －稱為錯誤圖樣 式中， (i = 0, 1, …, n1) 若 ei = 0，表示該碼元未錯；若 ei = 1，表示該碼元為錯碼。 ? ?0121 aaaaA nn ????? ?0121 bbbbB nn ????B – A = E (模 2) ? ?0121 eeeeE nn ??????????iiiii ababe當當,1,031 ?校正子矩陣 B – A = E 可以改寫成 B = A + E 上式表示發(fā)送碼組 A與錯碼矩陣 E之和等于接收碼組 B。 例如， 若發(fā)送碼組 A = [1 0 0 0 1 1 1]， 錯碼矩陣 E = [0 0 0 0 1 0 0]， 則 接收碼組 B = [1 0 0 0 0 1 1]。 在接收端解碼時，將接收碼組 B代入式 AHT = 0 中 A的位置進行計算。若接收碼組中無錯碼，則 B = A。代入后，該式仍成立，即有 BH T = 0 只有當錯碼未超出檢測能力時，上式才不成立。 假設，這時該式的右端等于 S，即有 BH T = S 將 B = A + E 代入上式，得到 :S = (A + E) H T = AH T + EH T 32 S = (A + E) H T = AH T + EH T 上式右端第一項等于 0，所以 S = EH T － 校正子矩陣 當 H 確定后，上式中 S只與 E 有關，而與 A 無關。 這意味著， S 和錯碼 E 之間有確定的線性變換關系。 若 S 和 E 有一一對應關系，則 S 將能代表錯碼位置。 ?線性碼的封閉性：若 A1和 A2是一種線性碼中的兩個碼組，則 (A1+A2)仍是其中一個碼組。 『 證 』 若 A1和 A2是兩個碼組，則有： A1HT = 0, A2HT = 0 將上兩式相加，得出 A1HT + A2HT = (A1 + A2 ) HT = 0 所以 (A1 + A2)也是一個碼組。 由于線性碼具有封閉性，所以兩個碼組 (A1和 A2)之間的距離（即對應位不同的數(shù)目）必定是另一個碼組 (A1 + A2)的重量（即“ 1”的數(shù)目）。因此，碼的最小距離就是碼的最小重量（除全“ 0”碼組外）。 33 循環(huán)碼 循環(huán)碼的概念： 循環(huán)性是指任一碼組循環(huán)一位后仍然是該編碼中的一個碼組。 ? 例：一種 (7, 3)循環(huán)碼的全部碼組如下 表中第 2碼組向右移一位即得到第 5碼組；第 5碼組向右移一位即得到第 7碼組。 碼組編號 信息位 監(jiān)督位 碼組編號 信息位 監(jiān)督位 A6a5a4 a3a2a1a0 a6a5a4 A3a2a1a0 1 000 0000 5 100 1011 2 001 0111 6 101 1100 3 010 1110 7 110 0101 4 011 1001 8 111 0010 34 ? 一般情況 若 (an1 an2 … a0)是循環(huán)碼的一個碼組，則循環(huán)移位后的碼組： (an2 an3 … a0 an1) (an3 an4 … an1 an2) … … (a0 an1 … a2 a1) 仍然是該編碼中的碼組。 ? 多項式表示法 一個長度為 n的碼組 (an1 an2 … a0)可以表示成 上式中 x 的值沒有任何意義，僅用它的冪代表碼元的位置。 例：碼組 1 1 0 0 1 0 1可以表示為 012211)( axaxaxaxT nnnn ????? ???? ?11010011)(25623456?????????????????xxxxxxxxxxT35 循環(huán)碼的運算 ? 整數(shù)的按模運算 在整數(shù)運算中，有模 n運算。例如，在模 2運算中，有 1 + 1 = 2 ? 0 (模 2)， 1 + 2 = 3 ? 1 (模 2)， 2 ? 3 = 6 ? 0 (模 2) 等等。 一般說來，若一個整數(shù) m可以表示為 式中， Q為整數(shù)，則在模 n運算下，有 m ? p (模 n) 所以，在模 n運算下，一個整數(shù) m等于它被 n除得的余數(shù)。 npnpQnm ??? ,36 ? 碼多項式的按模運算 若任意一個多項式 F(x)被一個 n次多項式 N(x)除，得到商式 Q(x)和一個次數(shù)小于 n的余式 R(x)，即 則在按模 N(x)運算下，有 這時，碼多項式系數(shù)仍按模 2運算。 例 1： x3被 (x3 + 1)除，得到余項 1，即 例 2： 因為 x x3 + 1 x4 +x2 + 1 x4 + x x2 +x +1 在模 2運算中加法和減法一樣。 )()()()( xRxQxNxF ??）（模 )()()( xNxRxF ?）（模 )1(1 33 ?? xx）（模 )1(11 3224 ?????? xxxxx37 ? 循環(huán)碼的數(shù)學表示法 在循環(huán)碼中，設 T(x)是一個長度為 n的碼組，若 則 T? (x)也是該編碼中的一個碼組。 [證 ] 設一循環(huán)碼為 則有 上式中的 T? (x) 正是碼組 T (x)向左循環(huán)移位 i 次的結果。 例： 一循環(huán)碼為 1100101，即 若給定 i = 3，則有 上式對應的碼組為 0101110，它正是 T(x)向左移 3位的結果。 結論：一個長為 n的循環(huán)碼必定為按模 (xn + 1)運算的一個余式。 ）（模 )1()()( ???? ni xxTxTx012211)( axaxaxaxT nnnn ????? ???? ?)()(1102211011112211xTaxaxaxaxaxaxaxaxaxaxTxininininniniinininninni????????????????????????????????????????1)( 256 ???? xxxxT）（模 )1()( 723535893 ?????????? xxxxxxxxxxTx38 ? 循環(huán)碼的生成 ?有了生成矩陣 G，就可以由 k個信息位得出整個碼組： 例： 式中， 生成矩陣 G的每一行都是一個碼組。 ?因此，若能找到 k 個已知的碼組，就能構成矩陣 G。如前所述，這 k個已知碼組必須是線性不相關的。 ?在循環(huán)碼中，一個 (n, k)碼有 2k個不同的碼組。若用 g(x)表示其中前 (k1)位皆為“ 0”的碼組，則 g(x)， x g(x)， x2 g(x)，?， xk1 g(x)都是碼組，而且這 k個碼組是線性無關的。因此它們可以用來構成此循環(huán)碼的生成矩陣 G。 ? ? ? ?G34560123456 aaaaaaaaaaaA ??? ???????????????0 1 10 0 0 11 0 10 0 1 01 1 00 1 0 01 1 11 0 0 0????QG kI39 ?在循環(huán)碼中除全“ 0”碼組外，再沒有連續(xù) k位均為“ 0”的碼組。否則，在經(jīng)過若干次循環(huán)移位后將得到 k位信息位全為“ 0”，但監(jiān)督位不全為“ 0”的一個碼組。這在線性碼中顯然是不可能的。 ?因此， g(x)必須是一個常數(shù)項不為“ 0”的 (n k)次多項式，而且這個 g(x)還是這種 (n, k)碼中次數(shù)為 (n – k)的唯一一個多項式。因為如果有兩個，則由碼的封閉性，把這兩個相加也應該是一個碼組，且此碼組多項式的次數(shù)將小于 (n – k)，即連續(xù)“ 0”的個數(shù)多于 (k – 1)。顯然，這是與前面的結論矛盾的。 ?我們稱這唯一的 (n – k)次多項式 g(x)為碼的生成多項式。一旦確定了 g(x)，則整個 (n, k)循環(huán)碼就被確定了。 40 ?因此，循環(huán)碼的生成矩陣 G可以寫成 ?例： 上表中的編碼為 (7, 3)循環(huán)碼， n = 7, k = 3, n – k = 4，其中唯一的一個 (n – k) = 4次碼多項式代表的碼組是第二碼組 0010111，與它對應的碼多項式，即生成多項式，為 g(x) = x4 + x2 + x + 1。 ?????????????????????)()()()()(21xgxxgxgxxgxxkk?G碼組編號 信息位 監(jiān)督位 碼組編號 信息位 監(jiān)督位 A6a5a4 a3a2a1a0 a6a5a4 A3a2a1a0 1 000 0000 5 100 1011 2 001 0111 6 101 1100 3 010 1110 7 110 0101 4 011 1001 8 111 0010 41 g(x) = x4 + x2 + x + 1 即 “ 1 0 1 1 1” 將此 g(x)代入上矩陣，得到 或 上式不符合 G = [IkQ]形式，所以它不是典型生成矩陣。但它經(jīng)過線性變換后，不難化成典型陣。 此循環(huán)碼組的多項式表示式 T(x)： 上式表明，所有碼多項式 T(x)都能夠被 g(x)整除，而且任意一個次數(shù)不大于 (k – 1)的多項式乘 g(x)都是碼多項式。 ???????????)()()()(2xgxxgxgxxG???????????0 0 1 0 1 1 10 1 0 1 1 1 01 0 1 1 1 0 0)( xG)()(