【正文】 ， ， 是（ n， k）線性分組碼中 k個線性無關的非零碼字， 0 1 1 ( 2 )ku u u G F? ?， ， ，則（ n， k）線性分組碼 2k個碼字中的任一碼字 可表示為 c0 0 1 1 1 1kkc u g u g u g??? ? ? ?用矩陣表示： 010 1 11() kkggc u G u u ug????????? ? ???????：長為 k的序列，構成 2k個不同的消息。 信息論與編碼 二．線性分組碼的矩陣描述 1．定義：（線性分組碼的模型） 設 Vn(F2)是定義在 F2上的一個 n維的矢量空間，而 C是它的一個 k維的子空間，則稱 C是碼長為 n，消息位為 k的 線性分組碼 或 （ n， k）線性分組碼 。 12 kv v v， ， ，結論：（ n， k）線性分組碼可由 k個線性獨立的碼字組成的基底張成。 12 nv v v， ， ，n維矢量空間包含 n個基底，也可以說， n個基底“張成” n維矢量空間。 則 1 2 3 1a a a? ? ? (0 1 0 ) (1 0 0 ) (1 1 0 )線性相關的充要條件 ：在線性空間中，對于矢量 存在著一個矢量 ，它可以表示為其余矢量的線性組合。 即：若 12 kv v v， ， ，線性無關，若等式成立，必有 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 )故 線性無關。 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上的一個 n維線性空間 （矢量空間），表示為： Vn（ F） 信息論與編碼 2．子空間 線性空間 Vn(F)中矢量 的所有線性組合所構成的集合 S是 Vn(F)的子空間。 dm i nt好 好 t 好 好 好 l 好l信息論與編碼 167。 ? ?m i n i j i jm in ( ) , ,d d c c c c C i j? ? ?，dmin是衡量碼的檢、糾錯能力的一個重要的參數(shù)。 如： pe＝ 105，則錯一位的概率： pe＝ 105，錯兩位的概率： 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? ? ? ?， ， ，如接收字： 判斷該接收字最有可能的碼字。 r r ic rjc jcr r?jcr② 極大似然譯碼基礎：收到的字是從一個碼字經(jīng)錯傳盡可能少的位而來的可能性較從一個碼字經(jīng)錯傳較多的位而來的可能性要大。 漢明距離和分組碼的檢、糾錯能力 一．漢明距離 1．定義： 設 是集合 Vn（ F2）（ n維向量空間 ）中的任意兩個字，令 ab，? ?0 1 1na a a a ?＝ ， ， ，? ?0 1 1nb b b b ?＝ ， ， ，ai， bi取自 G(F2) (0， 1) 規(guī)定 表示字 的各對應碼元之間不相同的個數(shù)，則 ()d a b， ab，1100( ) ( )nni i i iiid a b a b a b????? ? ? ???， 稱 為 之間的 漢明距離 ，簡稱 距離 。 ? 每個碼字對應于該重錯誤圖樣的接收字集合，與其它碼字的錯誤重數(shù)低的接收字集合中，不包含公共元素。 e設 為碼字在傳輸過程中發(fā)生錯誤而得到的接收字，則 rr c e??信息論與編碼 【 例 】 （ 2， 1）重復碼 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）重復碼 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 好 好 好好 好好 好 好信息論與編碼 作為按照極大似然準則譯碼的糾錯碼，可以糾正該重錯誤圖樣的條件為： ? 每個碼字對應于該重錯誤圖樣的接收字集合中，不可包含發(fā)送的碼字。 稱 為 錯誤圖樣 。 信息論與編碼 （ 3， 1）重復碼 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）重復碼可以檢出最多不超過兩個錯誤（作為檢錯碼使用），能糾正一個錯誤（作為糾錯碼使用），但不能檢出 3個錯誤。（兩個極端） 3．糾錯編碼理論的中心任務 ：在重復碼和奇偶校驗碼之間尋找一些性能良好的碼，使編碼效率和檢、糾錯能力得到統(tǒng)一。 比較上面兩例編碼方案： ① 重復碼： R = 1/n，編碼效率最低，檢糾錯能力最高。 在接收到一個字中 1的個數(shù)不是偶數(shù)時，就可以確定接收的不是碼字。 信息論與編碼 【 例 】 一個原始數(shù)字消息 u0 編碼規(guī)則： 001010ncucucu???? ????? ??000 , 0 0 01 , 1 1 1nucuc????k = 1，故為（ n， 1）碼，稱（ n， 1）重復碼。 消息 ：長為 k的二元碼元序列，用 表示。 碼 ：所有碼字的集合，用 C表示。 ? ?? ?0 1 n 1c c c， ， ，幾個概念： 碼字 ：對應于消息的長 n的 2k個碼元序列，用 表示。 分組碼及檢、糾錯能力的獲得 一．分組碼定義 設消息或數(shù)據(jù)以二進制形式表示，并以 F2 = { 0 , 1 }表示這個二元集。隨機錯誤與突發(fā)錯誤并存的信道，稱為 組合信道 或 復合信道 。下圖就是這種信道的一個模型。在無記憶信道中，錯誤是隨機產生的，因此被稱作 隨機錯誤 ，無記憶信道也被稱為 隨機信道（ random channel） 。 信息論與編碼 四．差錯類型 討論碼字序列通過離散信道時發(fā)生的情況，信道分為 無記憶信道 和 有記憶信道 。 卷積碼 ：把信息序列以每 k個分組，通過編碼器輸出長為 n（ n ? k）的一個子碼。 對于 k個碼元分組，共有 2k個不同的信息組，編碼器輸出長 n的 2k個碼字，這 2k個長為 n的碼字構成的集合稱為一個（ n， k）分組碼。 三．糾錯碼的分類 常用的糾錯碼按其碼字結構形式和對信息序列處理方式的不同可分成兩大類： 分組碼 和 卷積碼 。 信息論與編碼 在設計差錯控制系統(tǒng)時，選擇何種實現(xiàn)方式，應綜合考慮各方面的因素。收端譯碼時若發(fā)現(xiàn)錯誤個數(shù)在碼的糾錯能力以內，則自動進行糾錯；若錯誤個數(shù)超過了碼的糾錯能力，但能檢測出來，則通過反饋信道告知發(fā)方重發(fā)。 ⑶ 混合糾錯 (HEC)方式： HEC (Hybrid Error Control) 方式是上述兩種方式的結合。 缺點 ：應用 ARQ方式必須有一條從收端至發(fā)端的反饋信道。發(fā)端把收端認為有錯的消息再次傳送，直到收端認為正確接收為止。 缺點 ：是譯碼設備較復雜；編碼效率較低。 ⑴ 前向糾錯 (FEC)方式 ：