【正文】 dmin的關(guān)系 ① 若 dmin ≥ t + 1，則碼 C可以檢出所有不多于 t重的錯(cuò)誤； dm i nl好 好 好 l 好信息論與編碼 ② 若 dmin ≥ 2t + 1，則碼 C可以糾正所有不多于 t重的錯(cuò)誤； dm i nt好 好 t 好t③ 若 dmin ≥ 2t1 + t2 + 1，則碼 C可以糾正所有不多于 t1重的錯(cuò)誤，并能檢出所有的從 t1+1到 （ t1+t2）重的錯(cuò)誤。 線性分組碼及其矩陣描述 一．基本概念 1．線性空間 定義 ：如果域 F上的 n重元素集合 V滿足下述條件時(shí)， ① V關(guān)于加法構(gòu)成阿貝爾群； ② 對(duì) V中任何元素 和 F中的任何元素 a， ，稱 V中元素 為矢量（向量）， F中元素 a稱純量（標(biāo)量），稱乘 a運(yùn)算為數(shù)乘。 12 kv v v， ， ，1 1 2 2 k k iu b v b v b v b F? ? ? ? ?3．線性相關(guān)和線性無(wú)關(guān) 設(shè) 是線性空間 Vn(F)中的一組非全零矢量，當(dāng)且僅當(dāng)存在有一組不全為零的純量 12 kv v v， ， ，1 2 i()ka a a a F?， ， ，使 1 1 2 2 0kka v a v a v? ? ? ?成立時(shí)，稱這組矢量線性相關(guān)，否則，稱這組矢量 線性無(wú)關(guān) （線性獨(dú)立）。 （ 2） 1 2 3(0 1 0 ) ( 1 0 0 ) ( 1 1 0 ) 0 0 0a a a? ? ?故 線性相關(guān)。 12 kv v v， ， ，iv信息論與編碼 4．矢量空間（線性空間）的基底 如果存在一組線性無(wú)關(guān)的矢量 ，這些矢量的線性組合的集合可以構(gòu)成一個(gè)矢量空間，則稱這組矢量為這個(gè)矢量空間的 基底 。 如果 是 n維矢量空間 Vn(F)中 k個(gè)線性無(wú)關(guān)的矢量，則這些矢量線性組合的集合可構(gòu)成 Vn(F)的一個(gè) k維子空間，這 k個(gè)矢量為子空間的基底。 碼矢量 ：由（ n， k）線性分組碼的每個(gè)碼字構(gòu)成的矢量（碼字） 字矢量 ： n維線性空間任一個(gè)字構(gòu)成的矢量。 【 例 】 （ 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維的行矢量是線性無(wú)關(guān)的，它構(gòu)成了 V6(F2)上的一個(gè) 3維子空間，故 C是（ 6， 3）線性分組碼。 0 1 1()ku u u u ??????????????????????????????????? 1,11,10,11,11,10,11,01,00,0110nkkknnk ggggggggggggG??????????生成矩陣 信息論與編碼 【 例 】 （ 7， 3）線性分組碼， k = 3， 2k = 8（消息） u0 u1 u20 0 00 0 10 1 01 0 01 1 01 0 10 1 11 1 10 0 0 0 0 0 00 0 1 1 1 0 10 1 0 0 1 1 11 0 0 1 1 1 01 1 0 1 0 0 11 0 1 0 0 1 10 1 1 1 0 1 01 1 1 0 1 0 0c0 c1 c2 c3 c4 c5 c6 u? c?012100111001001110011101ggg???00 1 2 1 0 1 221001110( ) ( ) 0 1 0 0 1 1 10011101gc u G u u u g u u ug? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?則： 如： 41001110( 110 ) 010 011 1 ( 110 100 1 )0011101c????????????信息論與編碼 3．生成矩陣的性質(zhì) （ 1）如果 G是一個(gè)生成矩陣，那么與 G行等價(jià)的任一矩陣也是生成矩陣。 【 例 】 （ 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)的碼字不同。 （ 6）各個(gè) G編出的碼相同，因此碼集合的最小漢明距離 dmin 不變， 因此碼的檢糾錯(cuò)能力不變，因此可以尋找最容易實(shí)現(xiàn)的編碼 方案。 如：前例（ 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]組合而成的。 信息論與編碼 三．線性分組碼的校驗(yàn)矩陣 1．校驗(yàn)矩陣 【 例 】 （ 6， 3）線性分組碼 ),(110100101010011001)()(212021210210543210uuuuuuuuuuuucccccc???????????????在碼字中 c0、 c c2是信息位， c c c5是冗余位（校驗(yàn)位） 信息論與編碼 ),()( 212021210543210 uuuuuuuuucccccc ????由校驗(yàn)位方程得： ?????????????????212152020410103ccuucccuucccuuc???????????????000521420310ccccccccc用矩陣表示 0100110010101001011543210???????????????????????????????cccccc0THc??即 （ H為 n－ k行 n列的矩陣） 信息論與編碼 【 例 】 （ 1）（ n， 1）重復(fù)碼， k＝ 1 ????????????????校驗(yàn)位010100ucucucn???????????????? 000102010ncccccc?01001010100111101???????????????????????????? nnn ccc?????（ 2）（ n， n1）奇偶校驗(yàn)碼 ????????????????????)(2101221100校驗(yàn)位nnnnuuucucucuc??0110 ????? ?nccc ?