【正文】 ： 0021 ???? ?? aaa nn ?021 aaaS nn ???? ?? ?021 aaaS nn ???? ?? ?20 ? 糾錯(cuò)基本原理 ? 中， S只有兩種取值，故只能表示有錯(cuò)和無(wú)錯(cuò)，而不能進(jìn)一步指明錯(cuò)碼的位置。這樣，就能得到兩個(gè)校正子。若用其中一種組合表示無(wú)錯(cuò)碼，則還有其他 3種組合可以用于指明一個(gè)錯(cuò)碼的 3種不同位置， 從而可以有糾錯(cuò)能力。 ?當(dāng)校正子可以指明的錯(cuò)碼位置數(shù)目等于或大于碼組長(zhǎng)度 n時(shí)，才能夠糾正碼組中任何一個(gè)位置上的錯(cuò)碼，即要求 021 aaaS nn ???? ?? ?1212 ????? rkn rr 或21 ? 漢明碼 ?例：要求設(shè)計(jì)一個(gè)能夠糾正 1個(gè)錯(cuò)碼的分組碼 (n, k)，給定的碼組中有 4個(gè)信息位，即 k = 4。若取 r = 3，則 n = k + r = 7。 ?若規(guī)定校正子和錯(cuò)碼位置的關(guān)系如下表，則僅當(dāng)在 a6, a5, a4 , a2位置上有錯(cuò)碼時(shí)，校正子 S1的值才等于 1；否則 S1的值為零。監(jiān)督位 a2 a1 a0是按監(jiān)督關(guān)系確定的，應(yīng)該保證上列 3式中的校正子等于 0，即有 給定信息位后，為了 計(jì)算監(jiān)督位，上式可 以改寫為 按照上式計(jì)算結(jié)果為 ?????????????????000034613562456aaaaaaaaaaaa??????????????346035614562aaaaaaaaaaaa信息位 a6 a5 a4 a3 監(jiān)督位 a2 a1 a0 信息位 a6 a5 a4 a3 監(jiān)督位 a2 a1 a0 0000 000 1000 111 0001 011 1001 100 0010 101 1010 010 0011 110 1011 001 0100 110 1100 001 0101 101 1101 010 0110 011 1110 100 0111 000 1111 111 23 ?在接收端解碼時(shí)，對(duì)于每個(gè)接收碼組，先按式 計(jì)算出校正子 S1， S2和 S3，然后按照表 判斷錯(cuò)碼的位置。這樣，由上表可知，錯(cuò)碼位置在a3。 ?由式 ?可知，此碼能夠檢測(cè) 2個(gè)錯(cuò)碼，或糾正 1個(gè)錯(cuò)碼。所以漢明碼是一種高效編碼。 ?????????????????000034613562456aaaaaaaaaaaa???????????????????????????????????????????????010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa26 ?監(jiān)督矩陣 上式可以寫成矩陣形式： （模 2） 將上式簡(jiǎn)寫為 HAT = 0T 或 AHT = 0 ???????????????????????????????????????????????010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa???????????????????????????????????????????0001 0 1 1 0 0 11 1 0 1 0 1 01 1 1 0 1 0 00123456aaaaaaa27 HAT = 0T 式中， － 稱為監(jiān)督矩陣 ?監(jiān)督矩陣的性質(zhì) ?監(jiān)督矩陣 H確定碼組中的信息位和監(jiān)督位的關(guān)系。 ?H 的每行中“ 1”的位置表示相應(yīng)的碼元參與監(jiān)督關(guān)系。 ???????????1 0 1 1 0 0 11 1 0 1 0 1 01 1 1 0 1 0 0H? ?rPIH ????????????0 0 11 0 1 10 1 01 1 0 11 0 01 1 1 0??? A = [a6 a5 a4 a3 a2 a1 a0] 0 = [000] 28 ?H 矩陣的各行應(yīng)該是線性無(wú)關(guān)的，否則將得不到 r 個(gè)線性無(wú)關(guān)的監(jiān)督關(guān)系式。 ?生成矩陣 ?例： 可以寫為 上式兩端分別轉(zhuǎn)置后，可以變成 式中， Q為 k ? r 階矩陣，是 P的轉(zhuǎn)置，即 Q = PT ?????????????????????????????????34560121 0 1 11 1 0 11 1 1 0aaaaaaa??????????????346035614562aaaaaaaaaaaa? ? ? ? ? ?Q345634560120 1 11 0 11 1 01 1 1aaaaaaaaaaa ??????????????29 將 Q的左邊加上一個(gè) k階單位方陣，稱為生成矩陣： － 生成矩陣 G稱為生成矩陣，因?yàn)榭梢杂盟a(chǎn)生整個(gè)碼組 A，即有 ?生成矩陣的性質(zhì) ?具有 [Ik Q]形式的生成矩陣稱為 典型生成矩陣 。這種形式的碼組稱為 系統(tǒng)碼 。 ?如果已有 k個(gè)線性無(wú)關(guān)的碼組，則可以將其用來(lái)作為生成矩陣 G，并由它生成其余碼組。 ? ?0121 aaaaA nn ????? ?0121 bbbbB nn ????B – A = E (模 2) ? ?0121 eeeeE nn ??????????iiiii ababe當(dāng)當(dāng),1,031 ?校正子矩陣 B – A = E 可以改寫成 B = A + E 上式表示發(fā)送碼組 A與錯(cuò)碼矩陣 E之和等于接收碼組 B。 在接收端解碼時(shí)，將接收碼組 B代入式 AHT = 0 中 A的位置進(jìn)行計(jì)算。代入后，該式仍成立，即有 BH T = 0 只有當(dāng)錯(cuò)碼未超出檢測(cè)能力時(shí)，上式才成立。 這意味著， S 和錯(cuò)碼 E 之間有確定的線性變換關(guān)系。 ?線性碼的封閉性：若 A1和 A2是一種線性碼中的兩個(gè)碼組，則 (A1+A2)仍是其中一個(gè)碼組。 由于線性碼具有封閉性，所以兩個(gè)碼組 (A1和 A2)之間的距離（即對(duì)應(yīng)位不同的數(shù)目）必定是另一個(gè)碼組 (A1 + A2)的重量（即“ 1”的數(shù)目）。 33 循環(huán)碼 循環(huán)碼的概念： 循環(huán)性是指任一碼組循環(huán)一位后仍然是該編碼中的一個(gè)碼組。 碼組編號(hào) 信息位 監(jiān)督位 碼組編號(hào) 信息位 監(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)碼的一個(gè)碼組，則循環(huán)移位后的碼組： (an2 an3 … a0 an1) (an3 an4 … an1 an2) … … (a0 an1 … a2 a1) 仍然是該編碼中的碼組。 例：碼組 1 1 0 0 1 0 1可以表示為 012211)( axaxaxaxT nnnn ????? ???? ?11010011)(25623456?????????????????xxxxxxxxxxT35 循環(huán)碼的運(yùn)算 ? 整數(shù)的按模運(yùn)算 在整數(shù)運(yùn)算中，有模 n運(yùn)算。 一般說(shuō)來(lái)，若一個(gè)整數(shù) m可以表示為 式中， Q為整數(shù)，則在模 n運(yùn)算下，有 m ? p (模 n) 所以，在模 n運(yùn)算下，一個(gè)整數(shù) m等于它被 n除得的余數(shù)。 例 1： x3被 (x3 + 1)除，得到余項(xiàng) 1，即 例 2： 因?yàn)? x x3 + 1 x4 +x2 + 1 x4 + x x2 +x +1 在模 2運(yùn)算中 , 加法和減法一樣。 [證 ] 設(shè)一循環(huán)碼為 則有 上式中的 T? (x) 正是碼組 T (x)向左循環(huán)移位 i 次的結(jié)果。 結(jié)論：一個(gè)長(zhǎng)為 n的循環(huán)碼必定為按模 (xn + 1)運(yùn)算的一個(gè)余式。 ?因此，若能找到 k 個(gè)已知的碼組，就能構(gòu)成矩陣 G。 ?在循環(huán)碼中，一個(gè) (n, k)碼有 2k個(gè)不同的碼組。因此它們可以用來(lái)構(gòu)成此循環(huán)碼的生成矩陣 G。否則，在經(jīng)過(guò)若干次循環(huán)移位后將得到 k位信息位全為“ 0”，但監(jiān)督位不全為“ 0”的一個(gè)碼組。 ?因此， g(x)必須是一個(gè)常數(shù)項(xiàng)不為“ 0”的 (n k)次多項(xiàng)式，而且這個(gè) g(x)還是這種 (n, k)碼中次數(shù)為 (n – k)的唯一一個(gè)多項(xiàng)式。顯然，這是與前面的結(jié)論矛盾的。一旦確定了 g(x)，則整個(gè) (n, k)循環(huán)碼就被確定了。 ?????????????????????)()()()()(21xgxxgxgxxgxxkk?G碼組編號(hào) 信息位 監(jiān)督位 碼組編號(hào) 信