【正文】 ei =1時(shí)，表明碼字中第 i位 ci發(fā)生錯(cuò)誤； ? 當(dāng) ei =0時(shí)，表明碼字中第 i位 ci沒有錯(cuò)誤。 ? 每個(gè)碼字對(duì)應(yīng)于該重錯(cuò)誤圖樣的接收字集合中，不包含公共元素。 ()d a b， ab，信息論與編碼 例如： ( 01 10 0)( ) 2( 11 10 1 )a d a bb ? ? ?????，說明： ① 收到接收字 后，通過計(jì)算 與各碼字 之間的漢明距離，如 與某一碼字 的漢明距離最小，則 與碼字 最像，譯碼器將 譯成 。 (1 0 1 1 0 )r ?0( ) 1d c r ?， 1( ) 5d c r ?， 2( ) 2d c r ?， 3( ) 2d c r ?，0rc?2．漢明距離的性質(zhì) ① 自反性： n2( ) d ( ) 0a V F a a? ? ?， ，② 對(duì)稱性： n2( ) ( ) ( )a b V F d a b d b a? ? ?， ， ， ，③ 三角不等式： n2()a b c V F??， ，( ) ( ) ( )d a b d b c d a c??， ， ，信息論與編碼 二．分組碼的檢、糾錯(cuò)能力與最小漢明距離之間的關(guān)系 1．碼的最小距離 碼 C中不同碼字之間距離的最小值稱碼 C的最小距離。 線性分組碼及其矩陣描述 一．基本概念 1．線性空間 定義 ：如果域 F上的 n重元素集合 V滿足下述條件時(shí)， ① V關(guān)于加法構(gòu)成阿貝爾群； ② 對(duì) V中任何元素 和 F中的任何元素 a， ，稱 V中元素 為矢量（向量）， F中元素 a稱純量（標(biāo)量），稱乘 a運(yùn)算為數(shù)乘。 （ 2） 1 2 3(0 1 0 ) ( 1 0 0 ) ( 1 1 0 ) 0 0 0a a a? ? ?故 線性相關(guān)。 如果 是 n維矢量空間 Vn(F)中 k個(gè)線性無關(guān)的矢量，則這些矢量線性組合的集合可構(gòu)成 Vn(F)的一個(gè) k維子空間，這 k個(gè)矢量為子空間的基底。 【 例 】 （ 6， 3）分組碼 C 0 1 2 0 1 2 3 4 5()u u u c c c c c c?編碼規(guī)則： 0011223 0 14 0 25 1 2cucucuc u uc u uc u u?????? ??????? ???????用矩陣表示： ???????????110100101010011001)()( 210543210 uuucccccc組成矩陣的三個(gè) 6維的行矢量是線性無關(guān)的，它構(gòu)成了 V6(F2)上的一個(gè) 3維子空間，故 C是（ 6， 3）線性分組碼。 【 例 】 （ 6， 3）線性分組碼 0 1 2 3 4 5 0 1 21 0 0 1 1 0( ) ( ) 1 0 1 1 0 10 1 1 1 1 0c c c c c c u u u???????對(duì) G作初等行變換： ???????????? ?????????????? ?????????????? ????????????? ???011001101010110100110011101010110100110011011110110100110011101101110100231232 rrrrrrG信息論與編碼 （ 2）每個(gè)線性分組碼都有唯一的梯形生成矩陣 ? ?knkk PIG ??? ,（ 3）一個(gè)矢量空間的基底不止一個(gè)， G不唯一 . （ 4）等價(jià)的各個(gè) G編出的碼相同，但各消息對(duì)應(yīng)的碼字不同。 如：前例（ 7， 3）線性分組碼 ),(110100101110101110100)(211021020210210uuuuuuuuuuuuuuuGuc?????????????????????好 好 好好 好 好? ?433 , ?PI好 好 好 好一般性結(jié)論： （ 1）每一個(gè)線性分組碼都有一個(gè)與之等價(jià)的系統(tǒng)碼存在； （ 2）（ n， k）線性分組碼系統(tǒng)碼的生成矩陣是一個(gè) k k的單位陣 [ Ik ]和一個(gè) k (nk)矩陣 [Pk nk]組合而成的。 （ 2） 0( ) 0 0 0TT T T THc H u G H G u H Gc u G??? ? ? ? ? ? ? ? ? ? ??? ?＝H的行空間與 G的行空間是相互正交的（對(duì)偶的）。 3．線性分組碼的譯碼問題 由于生成矩陣和校驗(yàn)矩陣的行空間是對(duì)偶的，因此我們可以利用這種對(duì)偶特性來判斷接收到的任一矢量是否為碼矢量，這在原則上提供了一種解決線性分組碼的譯碼問題的途徑。 ()wc c2．最小重量：碼 C中非零碼字重量的最小值 ? ?m i n ( ) m i n ( ) 0w C w c c C c? ? ?，信息論與編碼 3．任一碼字的重量都可以看作是該碼字與 0碼字之間的漢明距離 10( 0 ) ( )niid c c w c?????，4．定理：任一線性分組碼的最小距離等于它的最小重量。 信息論與編碼 167。 交換群 （阿貝爾群）： a * b = b * a (滿足交換律 ) 加法群 ：運(yùn)算“ *”為加法運(yùn)算。 2．群按子群展開（陪集展開） 設(shè)加群 G的子群 ? ?1 2 3 rH h e h h h?? ， ， ， ，展開步驟： （ 1）把 H的元依次排在第一行； （ 2）取不屬于 H的 G中的任一元，記為 g1，將它與 H中的元依次相加，結(jié)果記為 ，并依次排在第二行； ? ?1 1 1 1 1 2 1 3 1 rg H g h g g h g h g h? ? ? ? ? ? ?， ， ， ，（ 3）再取不屬于 H又不屬于 g1+H的 G中的任一元 g2，將它與 H中的元依次相加，結(jié)果記為 ，并依次排在第三行； ? ?2 2 1 2 2 2 2 3 2 rg H g h g g h g h g h? ? ? ? ? ? ?， ， ， ，（ 4）按步驟繼續(xù)下去，直到排完 G中所有的元。 H 0000 0101 1110 1011 0110＋ H 0110 0011 1000 1101 1111＋ H 1111 1010 0001 0100 0010＋ H 0010 0111 1100 1001 結(jié)論：（ 1） G的每一個(gè)元素僅在且至少在子群 H的一個(gè)陪集中 （ 2）設(shè) G是個(gè)交換群， H是它的一個(gè)子群，那么 G可以唯一地表示為 H的一些兩兩沒有公共元的陪集的并。 二．伴隨式 1．伴隨式（校驗(yàn)子） 對(duì)任一錯(cuò)誤圖樣 ，接受字可表示為： e r c e??()T T T T TH r H c e H c H e? ? ? ?由于 c 是碼字， 0THc ? ，故 T T TH r H e s??稱 為接收字 的 伴隨式 或 校驗(yàn)子 ，它是一個(gè) nk維的行矢量。 信息論與編碼 【 例 】 （ 4， 2）系統(tǒng)線性碼 C = {0000， 0101， 1110， 1011}，其標(biāo)準(zhǔn)陣列為 碼字 伴隨式 0000 0101 1110 1011 10 0010 0111 1100 1001 01 0100 0001 1010 1111 11 1000 1101 0110 0011 其校驗(yàn)矩陣為 1 0 1 01 1 0 1H??? ????，計(jì)算其伴隨式，如表。 2．伴隨式譯碼 （ 1）原理： 對(duì)于碼 C的同一陪集，有相同的伴隨式和陪集首 (錯(cuò)誤圖樣 ），因此，只要知道伴隨式與陪集首的對(duì)應(yīng)關(guān)系，通過計(jì)算接收字的伴隨式，就可以知道錯(cuò)誤圖樣，從而進(jìn)行譯碼。 信息論與編碼 167。 m i n m i n ( ) 3d w C??定理： C是一個(gè)線性分組碼， H是校驗(yàn)矩陣， C是可以糾單個(gè)錯(cuò)誤的糾錯(cuò)碼的充要條件： （ 1） H中沒有元素全為 0的列矢量； （ 2） H中任意兩個(gè)列矢量都不相同。 信息論與編碼 結(jié)論：為了得到具有糾一個(gè)錯(cuò)誤的二元（ n， nm）線性碼，（其中 nm=k， m為校驗(yàn)位的個(gè)數(shù)），只需從定義在 F2上的 m維非零列矢量中選取彼此不同的 n個(gè)列矢量 H0、 H ...、 Hn1并依任意次序把它們排成一個(gè) m n的矩陣： ? ?0 1 1nH H H H ??那么以 H為校驗(yàn)矩陣的二元（ n， nm）線性碼 C就是一個(gè)可以糾正所有單個(gè)錯(cuò)誤的的碼。