【正文】 0 ????? 2/1222 )1(njjnjnju ppCP82443242204442242212424210666126)1(6)1()1()1(????????????????????? ?ppppppppppCppCppCPjjjju18 二維奇偶監(jiān)督碼 ?碼率等于 ?有可能檢測偶數(shù)個錯碼 ?適合檢測突發(fā)錯碼 ?能夠糾正部分錯碼 nmnmnk)1()1(???19 線性分組碼 ? 基本概念 ?代數(shù)碼 － 利用代數(shù)關(guān)系式產(chǎn)生監(jiān)督位的編碼 ?線性分組碼 － 代數(shù)碼的一種，其 監(jiān)督位和信息位的關(guān)系由線性代數(shù)方程決定 ?漢明碼 － 一種能夠糾正一個錯碼的線性分組碼 ?校正子： 在偶數(shù)監(jiān)督碼中，計算 實際上就是計算 并檢驗 S是否等于 0。 S稱為校正子。 ?監(jiān)督關(guān)系式： 0021 ???? ?? aaa nn ?021 aaaS nn ???? ?? ?021 aaaS nn ???? ?? ?20 ? 糾錯基本原理 ? 中， S只有兩種取值，故只能表示有錯和無錯，而不能進一步指明錯碼的位置。 ?若此碼組長度增加一位，則能增加一個監(jiān)督關(guān)系式。這樣，就能得到兩個校正子。兩個校正子的可能取值有 4種組合，即 00， 01， 10， 11，故能表示 4種不同的信息。若用其中一種組合表示無錯碼，則還有其他 3種組合可以用于指明一個錯碼的 3種不同位置， 從而可以有糾錯能力。 ?一般而言，若有 r 個監(jiān)督關(guān)系式，則 r 個校正子可以指明一個錯碼的 (2^r – 1) 個不同位置。 ?當(dāng)校正子可以指明的錯碼位置數(shù)目等于或大于碼組長度 n時，才能夠糾正碼組中任何一個位置上的錯碼，即要求 021 aaaS nn ???? ?? ?1212 ????? rkn rr 或21 ? 漢明碼 ?例：要求設(shè)計一個能夠糾正 1個錯碼的分組碼 (n, k)，給定的碼組中有 4個信息位，即 k = 4。 ?由 這時要求監(jiān)督位數(shù) r ? 3。若取 r = 3，則 n = k + r = 7?，F(xiàn)在用 a6 a5 a4 a3 a2 a1 a0表示這 7個碼元，用 S1 S2 S3表示校正子，則這 3個校正子恰好能夠指明 23 – 1 = 7個錯碼的位置。 ?若規(guī)定校正子和錯碼位置的關(guān)系如下表，則僅當(dāng)在 a6, a5, a4 , a2位置上有錯碼時，校正子 S1的值才等于 1；否則 S1的值為零。這就意味著 a6 a5 a4 a2四個碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系： ?同理，有 S1 S2 S3 錯碼位置 S1 S2 S3 錯碼位置 001 a0 101 a4 010 a1 110 a5 100 a2 111 a6 011 a3 000 無錯碼 1212 ????? rkn rr 或24561 aaaaS ????13562 aaaaS ????03463 aaaaS ????22 ?在編碼時，信息位 a6 a5 a4 a3的值決定于輸入信號，它們是隨機的。監(jiān)督位 a2 a1 a0是按監(jiān)督關(guān)系確定的，應(yīng)該保證上列 3式中的校正子等于 0，即有 給定信息位后，為了 計算監(jiān)督位，上式可 以改寫為 按照上式計算結(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 ?在接收端解碼時，對于每個接收碼組，先按式 計算出校正子 S1， S2和 S3，然后按照表 判斷錯碼的位置。 例：若接收碼組為 0000011，則按上三式計算得到： S1 = 0， S2 = 1， S3 = 1。這樣，由上表可知，錯碼位置在a3。 24561 aaaaS ????13562 aaaaS ????03463 aaaaS ????S1 S2 S3 錯碼位置 S1 S2 S3 錯碼位置 001 a0 101 a4 010 a1 110 a5 100 a2 111 a6 011 a3 000 無錯碼 24 ?上例中的漢明碼是 (7, 4)碼，其最小碼距 d0 = 3。 ?由式 ?可知，此碼能夠檢測 2個錯碼，或糾正 1個錯碼。 ?漢明碼的碼率： 當(dāng) r (或 n)很大時，上式趨近于 1。所以漢明碼是一種高效編碼。 10 ?? ed120 ?? td1212????rr rnk25 ? 分組碼的一般原理 ?線性分組碼的監(jiān)督位和信息位的關(guān)系 可以改寫為 上式中，已經(jīng)將“ ?”簡寫成“ +”。 ?????????????????000034613562456aaaaaaaaaaaa???????????????????????????????????????????????010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa26 ?監(jiān)督矩陣 上式可以寫成矩陣形式： （模 2） 將上式簡寫為 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 的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目，即監(jiān)督位數(shù) r 。 ?H 的每行中“ 1”的位置表示相應(yīng)的碼元參與監(jiān)督關(guān)系。 ? H 可以分成兩部分，例如 －典型監(jiān)督矩陣 式中， P 為 r ? k階矩陣， Ir為 r ? r 階單位方陣。 ???????????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)該是線性無關(guān)的，否則將得不到 r 個線性無關(guān)的監(jiān)督關(guān)系式。 ?若一個矩陣能寫成典型陣形式 [P Ir]，則其各行一定是線性無關(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的左邊加上一個 k階單位方陣，稱為生成矩陣： － 生成矩陣 G稱為生成矩陣，因為可以用它產(chǎn)生整個碼組 A，即有 ?生成矩陣的性質(zhì) ?具有 [Ik Q]形式的生成矩陣稱為 典型生成矩陣 。 ?由典型生成矩陣得出的碼組 A中，信息位的位置不變，監(jiān)督位附加于其后。這種形式的碼組稱為 系統(tǒng)碼 。 ?矩陣 G的各行也必須是線性無關(guān)的。 ?如果已有 k個線性無關(guān)的碼組，則可以將其用來作為生成矩陣 G，并由它生成其余碼組。 ? ???????????????0 1 10 0 0 11 0 10 0 1 01 1 00 1 0 01 1 11 0 0 0????QG kI? ? ? ?G34560123456 aaaaaaaaaaaA ??30 ?錯誤圖樣 設(shè)：發(fā)送碼組 A是一個 n列的行矩陣： 接收碼組是一個 n列的行矩陣 B： 令接收碼組和發(fā)送碼組之差為 E就是錯碼的行矩陣