信息論基礎(chǔ)-線性分組碼

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

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

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

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

5、 . 16若設(shè)碼字 ，則即校驗(yàn)位是由信息位線性組合得到.線性分組碼的基本概念17可見(jiàn)，碼字的三個(gè)校驗(yàn)元都由其前兩位線性組合得到，即可由的線性方程組求得； 線性分組碼的基本概念信息位k=2碼字?jǐn)?shù)M=418線性編碼線性分組碼的基本概念19例題1：下面是某個(gè)（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）線性二元碼的全部碼字設(shè)碼字 ， 可得線性分組碼的基本概念21線

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

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

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

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

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

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

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

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

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

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

16、散信道.由對(duì)稱離散信道的信道容量公式得55最佳輸入分布是輸入為等概分布.習(xí)題課56習(xí)題課1-c)解：信道的信道矩陣為可設(shè)P(0)=P(1)=1/2，此時(shí)輸出端的概率分布為P(0)=P(1)=(1-q)/2，P()=q由定理可以求得572 達(dá)到信道容量輸入分布的充要條件信道容量的計(jì)算令定理4.2.2 一般離散信道的互信息I(X；Y)達(dá)到極大值（即等于信道容量）的充要條件是輸入概率分布p(x)滿足58習(xí)題課1-f)解：信道的信道矩陣為可設(shè)P(0)=p，此時(shí)輸出端的概率分布為P(Y=0)=p/2.平均互信息I(X;Y)=H(p/2)-pH(1/2)對(duì)互信息求駐點(diǎn)，它的極值即為信道容量.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習(xí)題課60習(xí)題課1-h)解：信道的信道矩陣為設(shè)j=C+logP(yj)，則61習(xí)題課即解得所以j=C+logP(yj)62從而，習(xí)題課由于可以解得635) 由信道的信道矩陣可知：是非對(duì)稱信道，不能利用公式；可以利用方程組求解習(xí)題課j=C+logP(yj)64習(xí)題課65由于輸入為1、2時(shí)信道的轉(zhuǎn)移概率對(duì)稱分布，所以可設(shè)信源的概率分布為習(xí)題課66設(shè)一分組碼具有一致校驗(yàn)矩陣：求這個(gè)分組碼n=？k=？，共有多少個(gè)碼字？此分組碼的生成矩陣；向量1010

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