信息論基礎-線性分組碼

1、信源編碼（減少）冗余，提高編碼效率 ；信道編碼提高信息傳遞的可靠性 .1展望提高信息傳輸?shù)目煽啃院陀行?，始終是通信工作所追求的目標；近幾節(jié)課掌握的幾個編碼定理，已經(jīng)明確指出在一定條件下總存在簡單、有效編、譯的“好碼”. 但是，都沒有給出這類好碼的編、譯方法. 24.6 線性分組碼基礎知識抽象代數(shù)基礎線性代數(shù)基礎3引例線性分組碼的基本概念線性分組碼的譯碼漢明碼的編碼與譯碼4.6 線性分組碼4引例線性分組碼的基本概念線性分組碼的譯碼漢明碼的編碼與譯碼4.6 線性分組碼5設傳輸一比特字符x=0或1 若傳輸過程中出現(xiàn)差錯,不能被發(fā)現(xiàn)引例6引例0后附加字符0，1后附加1；即只有00和11被接受，且00

2、視為0，11視為1；故： 如果有一位錯誤發(fā)生，可以被檢出！7如果通信過程中發(fā)現(xiàn)差錯，可以通過要求對方重新發(fā)送來獲得正確的信息，即所謂的“數(shù)量換質(zhì)量”. 但是這在實時信息采集系統(tǒng)中可能是有困難的，因為信息源已經(jīng)發(fā)生變化；即使是在發(fā)方保留原信息樣本的情況下，也只有在差錯率很低的條件下是比較可行的. 因為如果通信條件比較惡劣，差錯出現(xiàn)頻繁，以至多次重發(fā)仍然得不到一份正確的信息. 這時，僅有“檢錯”手段，已無能為力！引例8引例0后附加字符00，1后附加11；即傳輸000相當于傳送單字符0，111相當于傳送單字符1；這時：發(fā)生不超過兩位的錯誤均可被檢出；發(fā)生一位錯誤可以被糾正.9引例0后附加字符00，1

3、后附加11；即傳輸000相當于傳送單字符0，111相當于傳送單字符1；這時：發(fā)生不超過兩位的錯誤均可被檢出；發(fā)生一位錯誤可以被糾正.糾錯碼信息位校驗位10引例線性分組碼的基本概念線性分組碼的編碼漢明碼的編碼與譯碼4.6 線性分組碼11線性分組碼的基本概念分組碼分組碼是把信源輸出的信息序列，以k個信息位分為一段，通過編碼器把這段信息位按一定規(guī)則f 產(chǎn)生r個校驗位，輸出長為n=k+r的一個碼字，所得碼字的全體. 稱之為（n， k ）分組碼 ！n表示碼長， k信息位個數(shù). 12引例0后附加字符00，1后附加11；即傳輸000相當于傳送單字符0，111相當于傳送單字符1；這時：發(fā)生不超過兩位的錯誤均可

4、被檢出；發(fā)生一位錯誤可以被糾正.(3,1)分組碼信息位校驗位13線性分組碼的基本概念（n， k ）分組碼若校驗位與信息位之間的關系是線性的，即上述編碼規(guī)則是線性的，稱之為（n， k ）線性分組碼！ 14線性編碼 從 到 的一個線性映射 稱為一個線性編碼；線性分組碼的基本概念即均有 ；若 是一一映射，則稱其為唯一可譯線性編碼；15線性分組碼的基本概念線性分組碼線性分組碼是把信源輸出的信息序列，以k個信息位分為一段，通過編碼器把這段信息位按線性編碼規(guī)則f 產(chǎn)生r個校驗位，輸出長為n=k+r的一個碼字，所得碼字的全體. 稱之為（n， k ）線性分組碼 ！n表示碼長， k信息位個數(shù). 碼字個數(shù)M=2k

5、 . 16若設碼字 ，則即校驗位是由信息位線性組合得到.線性分組碼的基本概念17可見，碼字的三個校驗元都由其前兩位線性組合得到，即可由的線性方程組求得； 線性分組碼的基本概念信息位k=2碼字數(shù)M=418線性編碼線性分組碼的基本概念19例題1：下面是某個（n，k）線性二元碼的全部碼字x16=000000 x26=100011 x36=010101 x46=001111x56=110110 x66=101100 x76=011010 x86=111001求n、k的值；n=6;線性分組碼的基本概念M=2k k=3.解：20例2、（5，2）線性二元碼的全部碼字設碼字 ， 可得線性分組碼的基本概念21線

6、性分組碼的基本概念改寫為用矩陣可表示成： 校驗矩陣 與任一碼字的乘積為0 22線性分組碼的特性 2k個碼字完全可由其中一組k 個獨立的碼字組合而成； 線性分組碼的基本概念生成矩陣從線性分組碼（n，k）中任取 k 個線性無關的碼字，以行的形式寫成矩陣G，則稱為該線性分組碼的生成矩陣. 23例題3：下面是一個（6，3）線性二元碼的全部碼字構造它的一個生成矩陣.線性分組碼的基本概念解：由k=3 個線性獨立的碼字組成：24例題3：下面是一個（6，3）線性二元碼的全部碼字驗證：線性分組碼的基本概念25系統(tǒng)碼 若（n , k）線性分組碼的生成矩陣形如 G=(Ik A)其中Ik是k階單位陣， A為 階子陣，

7、則稱這類碼為系統(tǒng)碼.線性分組碼的基本概念特點：校驗矩陣為H=(-AT I(n-k) ) .26例題3：下面是一個（6，3）線性二元碼的全部碼字它的一個生成矩陣線性分組碼的基本概念請寫出它的校驗矩陣H.信息組原封不動地搬到碼字前位的碼 27線性分組碼的基本概念28線性分組碼的基本概念漢明距離： 指（n,k）分組碼中兩個碼字xn 、 yn對應位取值不同的個數(shù)；記為d（xn ，yn）. 例： 29線性分組碼的基本概念理查德衛(wèi)斯里漢明（Richard Wesley Hamming，1915.2.111998.1.7.），美國數(shù)學家，主要貢獻在計算機科學和電訊。1937年芝加哥大學學士學位畢業(yè)，1939

8、年內(nèi)布拉斯加大學碩士學位畢業(yè)，1942年伊利諾伊大學香檳分校博士學位畢業(yè)，博士論文為一些線性微分方程邊界值理論上的問題（Some Problems in the Boundary Value Theory of Linear Differential Equations）。二戰(zhàn)期間在路易斯維爾大學當教授，1945年參加曼哈頓計劃，負責編寫電腦程式，計算物理學家所提供方程的解。該程式是判斷引爆核彈會否燃燒大氣層，結果是不會，于是核彈便開始試驗。1946至76年在貝爾實驗室工作。他曾和約翰懷爾德杜奇、克勞德艾爾伍德香農(nóng)合作。1956年他參與了IBM 650的程式語言發(fā)展工作。30線性分組碼的基本概

9、念漢明距離： 指（n,k）分組碼中兩個碼字xn 、 yn對應位取值不同的個數(shù)；記為d（xn ， yn）. 例： 31線性分組碼的基本概念線性分組碼的最小距離： 稱（n,k）分組碼中任兩個碼字漢明距離的最小值，為該分組碼的最小距離d. （5,2）線性分組碼全部碼字：最小距離d=3. 漢明重量32引例線性分組碼的基本概念線性分組碼的譯碼漢明碼的編碼與譯碼4.6 線性分組碼生成矩陣校驗矩陣碼的最小距離33引例線性分組碼的基本概念線性分組碼的譯碼漢明碼的編碼與譯碼4.6 線性分組碼34線性分組碼的譯碼基本概念錯誤圖樣設發(fā)送的碼字xn =(x1， x2，xn)，通過有擾信道傳輸， 到達接收端譯碼器的序列

10、為 rn =(r1， r2，rn)信道中的干擾表示為二進序列：錯誤圖樣en =(e1， e2，en). 相應有錯的ei取值為1.rn = xn + en ， 其中ri=xi+ei， xi， ri， eiGF(2)稱en為信道中的錯誤圖樣. 譯碼器任務從rn中得到xn或en .35線性分組碼的譯碼例4 設發(fā)送序列xn = (1111100000)， 收到的序列rn = (1001010000). 第二、三、五、六位產(chǎn)生了錯誤， 因此信道的錯誤圖樣en的二、 三、 五、 六位取值為1，其它各位取值為0， 即 en =(0110110000). 用式子可表示成： rn = xn + en36線性分組

11、碼的譯碼基本概念伴隨式由于分組碼中的任一碼字滿足： xnHT=0， 所以，可對收到的序列rn進行檢驗： rnHT=(xn+en )HT=xnHT+enHT=enHT若en=0，則rnHT=0；若en0，則rnHT 0. 記S= enHT ，稱之為接收序列rn的伴隨式.rnHT僅與錯誤圖樣有關，與發(fā)送什么碼字無關！37（n，k）線性分組碼的校驗矩陣，用列向量表出：線性分組碼的譯碼其中，hn-i為H矩陣的第i列.38設en=(e1， e2，en)=(0，ei1，0，ei2，0，ei3，0，eit，0，0) 其中eij=1,即第i1，i2，it位有錯， 則線性分組碼的譯碼S是H中相應于eij那幾列的

12、線性組合！39線性分組碼的譯碼例5 已知（7，3）碼的校驗矩陣為若發(fā)送碼字xn =（），收到rn =（）. 則錯誤圖樣為en =（）.40線性分組碼的譯碼由定義可以求得， rn的伴隨式：是H矩陣第一列與第二列之和！41線性分組碼的譯碼若錯誤圖樣en =（），則是H矩陣第三列！若錯誤圖樣中只有一個分量非零，則ST是H矩陣相應的列，因而能夠糾正單個錯誤！42線性分組碼的譯碼若錯誤圖樣en =（），則是H矩陣第三列與第五列之和！43線性分組碼的譯碼由定義可以求得， rn的伴隨式：是H矩陣第一列與第二列之和！若發(fā)生兩個錯誤，譯碼器只能判決傳輸有錯（ en 0 ）,不能判定由哪幾位錯誤引起！44線性分組

13、碼的譯碼線性分組碼能自動糾正t個錯誤的充要條件是d=2t+1 .最大似然譯碼準則是糾錯的策略依據(jù).若收到的字符串是碼字本身，則直接按碼字譯碼；否則，按與接收到的字的Hamming距離最接近的碼字譯碼.45線性分組碼的譯碼例5 已知（7，3）碼的校驗矩陣為最小距離 d=3 d=2t+146線性分組碼的譯碼（n,k）碼的譯碼步驟 （1）由接收到的rn，計算伴隨式S= rnHT ； （2）若S=0，則認為接收無誤； 若S0，則由S找出錯誤圖樣en ； （3）由en和rn找出xn= rn-en.47引例線性分組碼的基本概念線性分組碼的譯碼漢明碼的編碼與譯碼4.6 線性分組碼48線性分組碼漢明碼(Ham

14、ming Code)漢明碼是1950年由漢明首先構造， 用以糾正單個錯誤的線性分組碼.由于它的編譯碼非常簡單， 很容易實現(xiàn)， 因此用得很普遍， 特別是在計算機的存貯和運算系統(tǒng)中更常用到，是一類特別引人注意的碼.49線性分組碼漢明碼(Hamming Code)漢明碼不是指一個碼，而是代表一類碼；漢明碼碼長n和信息位k服從以下規(guī)律： (n,k)=(2m-1, 2m-1-m)，其中m= n-k；漢明碼的最小距離d=3；所以，糾錯能力t = 1；50漢明碼(Hamming Code) 的譯碼例6 已知GF(2)上的（6，3）漢明碼的一致校驗矩陣H為： 線性分組碼51線性分組碼若發(fā)送碼字xn=(1010

15、11), 接收序列為rn=(101011).若發(fā)送碼字xn=(101011), 接收序列為rn=(100011). 判定傳輸中沒有發(fā)生錯誤！判定接收序列rn的第3位是有錯的！ 52線性分組碼：生成矩陣，校驗矩陣；伴隨式：線性分組碼的譯碼；漢明碼的編碼與譯碼.結語53作業(yè)設一分組碼具有一致校驗矩陣：求這個分組碼n=？k=？，共有多少個碼字？此分組碼的生成矩陣；向量101010是否是碼字？設發(fā)送碼字C=(001111)，但接收序列為R=(000010),其伴隨式S是什么？這個伴隨式指出已發(fā)生的錯誤在什么地方，為什么與實際錯誤不符？54習題課1-b)解：信道的信道矩陣為其滿足對稱性，所以信道為對稱離

16、散信道.由對稱離散信道的信道容量公式得55最佳輸入分布是輸入為等概分布.習題課56習題課1-c)解：信道的信道矩陣為可設P(0)=P(1)=1/2，此時輸出端的概率分布為P(0)=P(1)=(1-q)/2，P()=q由定理可以求得572 達到信道容量輸入分布的充要條件信道容量的計算令定理4.2.2 一般離散信道的互信息I(X；Y)達到極大值（即等于信道容量）的充要條件是輸入概率分布p(x)滿足58習題課1-f)解：信道的信道矩陣為可設P(0)=p，此時輸出端的概率分布為P(Y=0)=p/2.平均互信息I(X;Y)=H(p/2)-pH(1/2)對互信息求駐點，它的極值即為信道容量.59dI/dp

17、=1/2*log(2-p)/p-H(1/2)=0；整理得p=2/5，所以C=H(Y)-H(Y|X)=H(1/5)-2/5=0.3219bit/symbol習題課60習題課1-h)解：信道的信道矩陣為設j=C+logP(yj)，則61習題課即解得所以j=C+logP(yj)62從而，習題課由于可以解得635) 由信道的信道矩陣可知：是非對稱信道，不能利用公式；可以利用方程組求解習題課j=C+logP(yj)64習題課65由于輸入為1、2時信道的轉(zhuǎn)移概率對稱分布，所以可設信源的概率分布為習題課66設一分組碼具有一致校驗矩陣：求這個分組碼n=？k=？，共有多少個碼字？此分組碼的生成矩陣；向量1010

18、10是否是碼字？設發(fā)送碼字C=(001111)，但接收序列為R=(000010),其伴隨式S是什么？這個伴隨式指出已發(fā)生的錯誤在什么地方，為什么與實際錯誤不符？習題課（補充）67解：設碼字C=(c5c4c3c2c1c0)，有習題課故得所以n=6，k=3，為(6,3)分組碼共有碼字2k=8個68設一分組碼具有一致校驗矩陣：求這個分組碼n=？k=？，共有多少個碼字？此分組碼的生成矩陣；向量101010是否是碼字？設發(fā)送碼字C=(001111)，但接收序列為R=(000010),其伴隨式S是什么？這個伴隨式指出已發(fā)生的錯誤在什么地方，為什么與實際錯誤不符？習題課（補充）69習題課由上式可得取一組線性無關的基礎解系，得到生成矩陣70設一分組碼具有一致校驗矩陣：求這個分組碼n=？k=？，共有多少個碼字？此分組碼的生成矩陣；向量101010是否是碼字？設發(fā)送碼字C=(001111)，但接收序列為R=(000010),其伴隨式S是什么？這個伴隨式指出已發(fā)生的錯誤在什么地方，為什么與實際錯誤不符？習題課（補充）71習題課由可知，向量101010不是碼字72設一分組碼具有一致校驗矩陣：求這個分組碼n=？k=