【正文】 重復(fù)碼： R = 1/n，編碼效率最低，檢糾錯(cuò)能力最高。 ② 奇偶校驗(yàn)碼： R = (n1)/n，編碼效率最高，檢糾錯(cuò)能力最低。（兩個(gè)極端） 3．糾錯(cuò)編碼理論的中心任務(wù) ：在重復(fù)碼和奇偶校驗(yàn)碼之間尋找一些性能良好的碼，使編碼效率和檢、糾錯(cuò)能力得到統(tǒng)一。 信息論與編碼 二．分組碼檢、糾錯(cuò)能力的獲得 【 例 】 （ 2， 1）重復(fù)碼 0 0 00 00 11 01 11 1 10 00 11 01 1好 好 好 好???好 好 好好 好 好好 好 好 好 好 好 好 好 好好 好 好 好 好 “ 0 0 ” 好好 “ 1 1 ” 好 好 好 好 好（ 2， 1）重復(fù)碼可以檢出一個(gè)錯(cuò)誤，但錯(cuò)誤不能糾正。 信息論與編碼 （ 3， 1）重復(fù)碼 0 0 0 00 0 10 1 01 0 00 1 11 1 1 10 1 00 1 11 0 10 1 1好 好 好 好 好 好?好 好......0 0 01 1 10 0 0?1 1 1好 好 好 好 好 好 好 好好 好 好 好 好 好 好 好好 好 好 好 好 好1 1 10 0 0?1 1 10 0 0??好 好 好 好（ 3， 1）重復(fù)碼可以檢出最多不超過(guò)兩個(gè)錯(cuò)誤（作為檢錯(cuò)碼使用），能糾正一個(gè)錯(cuò)誤（作為糾錯(cuò)碼使用），但不能檢出 3個(gè)錯(cuò)誤。 信息論與編碼 三．錯(cuò)誤圖樣 對(duì)應(yīng)著 n為碼字，長(zhǎng)為 n的二元序列 0 1 1 2( , )nie e e e e F???， ， ，? 當(dāng) ei =1時(shí)，表明碼字中第 i位 ci發(fā)生錯(cuò)誤； ? 當(dāng) ei =0時(shí)，表明碼字中第 i位 ci沒(méi)有錯(cuò)誤。 稱 為 錯(cuò)誤圖樣 。 0 1 1( , )ne e e e ?? ， ，中“ 1”的個(gè)數(shù)表示產(chǎn)生錯(cuò)誤的個(gè)數(shù)，稱錯(cuò)誤圖樣的 錯(cuò)誤重?cái)?shù) （ t）。 e設(shè) 為碼字在傳輸過(guò)程中發(fā)生錯(cuò)誤而得到的接收字，則 rr c e??信息論與編碼 【 例 】 （ 2， 1）重復(fù)碼 c?r?e?（ 0 0 ） （ 1 1 ）（ 1 0 ）（ 0 1 ）（ 1 1 ）（ 1 0 ）（ 0 1 ）（ 1 1 ）（ 0 1 ）（ 1 0 ）（ 0 0 ）1 好 好 好 好 好 好 好 好 好 好 好 好 好 好 好2 好 好 好 好 好 好 好 好 好 好 好 好 好 好 好（ 3， 1）重復(fù)碼 c?r?e?（ 0 0 0 ） （ 1 1 1 ）1 好 好 好2 好 好 好（ 1 0 0 ）（ 0 1 0 ）（ 0 0 1 ）（ 1 1 0 ）（ 1 0 1 ）（ 0 1 1 ）（ 1 1 1 ）（ 1 0 0 ）（ 0 1 0 ）（ 0 0 1 ）（ 1 1 0 ）（ 1 0 1 ）（ 0 1 1 ）（ 1 1 1 ）（ 0 1 1 ）（ 1 0 1 ）（ 1 1 0 ）（ 0 0 1 ）（ 0 1 0 ）（ 1 0 0 ）（ 0 0 0 ）好 好 好 好 好 好 好 好 好 好?好 好 好 好 好 好 好 好 好 好3 好 好 好好 好好 好 好信息論與編碼 作為按照極大似然準(zhǔn)則譯碼的糾錯(cuò)碼，可以糾正該重錯(cuò)誤圖樣的條件為： ? 每個(gè)碼字對(duì)應(yīng)于該重錯(cuò)誤圖樣的接收字集合中，不可包含發(fā)送的碼字。 ? 每個(gè)碼字對(duì)應(yīng)于該重錯(cuò)誤圖樣的接收字集合中，不包含公共元素。 ? 每個(gè)碼字對(duì)應(yīng)于該重錯(cuò)誤圖樣的接收字集合，與其它碼字的錯(cuò)誤重?cái)?shù)低的接收字集合中，不包含公共元素。 信息論與編碼 167。 漢明距離和分組碼的檢、糾錯(cuò)能力 一．漢明距離 1．定義： 設(shè) 是集合 Vn（ F2）（ n維向量空間 ）中的任意兩個(gè)字，令 ab，? ?0 1 1na a a a ?＝ ， ， ，? ?0 1 1nb b b b ?＝ ， ， ，ai， bi取自 G(F2) (0， 1) 規(guī)定 表示字 的各對(duì)應(yīng)碼元之間不相同的個(gè)數(shù)，則 ()d a b， ab，1100( ) ( )nni i i iiid a b a b a b????? ? ? ???， 稱 為 之間的 漢明距離 ，簡(jiǎn)稱 距離 。 ()d a b， ab，信息論與編碼 例如： ( 01 10 0)( ) 2( 11 10 1 )a d a bb ? ? ?????，說(shuō)明： ① 收到接收字 后，通過(guò)計(jì)算 與各碼字 之間的漢明距離，如 與某一碼字 的漢明距離最小，則 與碼字 最像，譯碼器將 譯成 。 r r ic rjc jcr r?jcr② 極大似然譯碼基礎(chǔ)：收到的字是從一個(gè)碼字經(jīng)錯(cuò)傳盡可能少的位而來(lái)的可能性較從一個(gè)碼字經(jīng)錯(cuò)傳較多的位而來(lái)的可能性要大。故通過(guò)判斷漢明距離來(lái)譯碼，符合極大似然譯碼規(guī)則。 如： pe＝ 105，則錯(cuò)一位的概率： pe＝ 105，錯(cuò)兩位的概率： pe＝ 1010 信息論與編碼 【 例 】 有碼字 0 1 2 3( 1 0 0 1 0 ) (0 1 0 0 1 ) ( 1 0 1 0 1 ) (0 1 1 1 0 )c c c c? ? ? ?， ， ，如接收字： 判斷該接收字最有可能的碼字。 (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的最小距離。 ? ?m i n i j i jm in ( ) , ,d d c c c c C i j? ? ?，dmin是衡量碼的檢、糾錯(cuò)能力的一個(gè)重要的參數(shù)。 2．碼的檢、糾錯(cuò)能力與 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ò)誤。 dm i nt好 好 t 好 好 好 l 好l信息論與編碼 167。 線性分組碼及其矩陣描述 一．基本概念 1．線性空間 定義 ：如果域 F上的 n重元素集合 V滿足下述條件時(shí)， ① V關(guān)于加法構(gòu)成阿貝爾群； ② 對(duì) V中任何元素 和 F中的任何元素 a， ，稱 V中元素 為矢量（向量）， F中元素 a稱純量（標(biāo)量），稱乘 a運(yùn)算為數(shù)乘。 c ac V? c③ 分配律成立： ,u v V a b F? ? ? ?， ，( ) ( )a u v a u a v a b u a u b u? ? ? ? ? ?( ) ( ) 1 1a b v a b v v v F? ? ? ?，④ 若 ,a b F v V??， 有 則稱 V是域 F上的一個(gè) n維線性空間 （矢量空間），表示為： Vn（ F） 信息論與編碼 2．子空間 線性空間 Vn(F)中矢量 的所有線性組合所構(gòu)成的集合 S是 Vn(F)的子空間。 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ú)立）。 即：若 12 kv v v， ， ，線性無(wú)關(guān)，若等式成立，必有 12 0ka a a? ? ? ?信息論與編碼 如： （ 1） 1 2 3(0 1 0 ) ( 1 0 0 ) (0 0 1 ) 0 0 0a a a? ? ?則 1 2 3 0a a a? ? ? (0 1 0 ) (1 0 0 ) (0 0 1 )故