信息論基礎(chǔ)：第五章 信道編碼

1、第五章 有噪信道編碼錯(cuò)誤概率及相關(guān)因素 如何使信號(hào)經(jīng)過傳輸后，錯(cuò)誤概率最小 信道編碼定理 在有噪信道中，無差錯(cuò)傳輸?shù)淖畲笮畔⒘坑卸啻?線性分組碼 實(shí)用編碼范例有噪信道編碼有噪信道編碼信源編碼：有效性信道編碼：可靠性 可以編碼成 有效性： 更好 可靠性： 更好，提供糾錯(cuò)功能有噪信道編碼 香農(nóng)第二定理，在理論上很好的統(tǒng)一了有效性和可靠性，使信息傳輸率達(dá)到信道容量的情況下，還能夠無失真的在有噪信道中傳輸。 有效性，可靠性很難兼顧。提高有效性，需要消除冗余；提高可靠性，需要適當(dāng)增加冗余。錯(cuò)誤概率及相關(guān)因素與以下三個(gè)因素有關(guān)：信道特性譯碼規(guī)則編碼方法信道統(tǒng)計(jì)特性無噪無損信道：錯(cuò)誤概率0P=0.5的二元對(duì)

2、稱信道：錯(cuò)誤概率50%譯碼規(guī)則譯碼規(guī)則“譯碼規(guī)則”：設(shè)計(jì)一個(gè)函數(shù) ，對(duì)于每一個(gè)輸出符號(hào) ，確定唯一的輸入符號(hào) 與之對(duì)應(yīng) 譯碼規(guī)則錯(cuò)誤概率為1錯(cuò)誤概率為0譯碼規(guī)則二元對(duì)稱信道錯(cuò)誤概率為0.99錯(cuò)誤概率下降為0.01譯碼規(guī)則對(duì)于一個(gè) 的傳遞矩陣，譯碼規(guī)則共有 種在這么多種譯碼規(guī)則中，我們選擇哪一種?當(dāng)然希望譯碼后的錯(cuò)誤概率越小越好.選擇的標(biāo)準(zhǔn)是什么？譯碼規(guī)則對(duì)于確定 ，制定譯碼函數(shù)譯碼錯(cuò)誤的概率是譯碼正確的概率是稱為條件錯(cuò)誤概率 因?yàn)檩敵鲂盘?hào)是個(gè)隨機(jī)變量， 只是其中一個(gè)符號(hào)定義平均錯(cuò)誤概率譯碼規(guī)則 正確概率譯碼規(guī)則技巧：一般都不直接求等輸入概率情況下稱為正確概率，而是先算然后用譯碼規(guī)則例 計(jì)算各種

3、譯碼規(guī)則對(duì)應(yīng)的平均差錯(cuò)概率 譯碼規(guī)則例 先計(jì)算譯碼正確的概率 對(duì)于規(guī)則一(F1)： 同理最小錯(cuò)誤概率準(zhǔn)則 平均錯(cuò)誤概率定義后，一個(gè)很自然的準(zhǔn)則就是使平均錯(cuò)誤概率最小，即最小錯(cuò)誤概率準(zhǔn)則 平均錯(cuò)誤概率是一個(gè)求和式，每一項(xiàng)都是非負(fù)的,如果每一項(xiàng)都為最小，則整個(gè)求和式最小. 求和式的每一項(xiàng) ,其中 與譯碼規(guī)則無關(guān)使 最小就是要使 最大最小錯(cuò)誤概率準(zhǔn)則 即選擇函數(shù)：并使之滿足條件： 即這種譯碼函數(shù)，它對(duì)于每一個(gè)輸出符號(hào)均譯成最大后驗(yàn)概率的那個(gè)輸入符號(hào)，則信道錯(cuò)誤概率就能最小，這種譯碼規(guī)則稱為“最大后驗(yàn)概率譯碼準(zhǔn)則”或“最小錯(cuò)誤概率譯碼準(zhǔn)則”最小錯(cuò)誤概率準(zhǔn)則貝葉斯定律最大后驗(yàn)概率準(zhǔn)則的條件式可以寫成最大

4、似然準(zhǔn)則 輸入符號(hào)等概率分布時(shí)，最大后驗(yàn)概率準(zhǔn)則變成了 最大似然準(zhǔn)則不再依賴于輸入符號(hào)的先驗(yàn)概率。在先驗(yàn)概率等概率分布時(shí)，最大似然準(zhǔn)則與最大后驗(yàn)概率準(zhǔn)則一致；在輸入非等概率分布時(shí)，最大似然準(zhǔn)則并不一定能使 最小 稱為最大似然準(zhǔn)則所以，最大似然準(zhǔn)則不是最佳譯碼規(guī)則譯碼規(guī)則的選取最大后驗(yàn)概率準(zhǔn)則依賴最大似然準(zhǔn)則僅依賴先驗(yàn)概率等概率分布，使用最大后驗(yàn)概率準(zhǔn)則和最大似然準(zhǔn)則是一致的如果知道先驗(yàn)概率，應(yīng)該使用最大后驗(yàn)概率準(zhǔn)則如果不知道先驗(yàn)概率，則只能用最大似然準(zhǔn)則譯碼規(guī)則例例：信道的傳遞概率矩陣求譯碼規(guī)則和平均錯(cuò)誤概率1.輸入等概率時(shí)2. 3. 用最大似然準(zhǔn)則譯碼規(guī)則例1.等概率分布時(shí)，用最大似然準(zhǔn)則，

5、等效于最大后驗(yàn)概率準(zhǔn)則。對(duì)于傳遞矩陣中的每一列，選一個(gè)最大的傳遞概率，對(duì)應(yīng)的輸入符號(hào)即為該輸出符號(hào)的譯碼函數(shù)譯碼規(guī)則例2.已知輸入概率分布，用最大后驗(yàn)概率準(zhǔn)則，求聯(lián)合概率譯碼規(guī)則例3.非等概率分布，但是規(guī)定要用最大似然準(zhǔn)則可見在輸入非等概率分布時(shí)，最大似然準(zhǔn)則并不一定是最佳譯碼規(guī)則課堂練習(xí)離散信道的傳遞概率矩陣為分別按照最小錯(cuò)誤概率準(zhǔn)則和最大似然準(zhǔn)則確定譯碼規(guī)則，并計(jì)算相應(yīng)的平均錯(cuò)誤概率課堂練習(xí)、作業(yè)用最大后驗(yàn)概率準(zhǔn)則，求聯(lián)合概率課堂練習(xí)、作業(yè)用最大似然準(zhǔn)則編碼方法 0.01的錯(cuò)誤率在很多情況下難以容忍。一般來說，信息傳輸系統(tǒng)的平均差錯(cuò)率要求控制在10-6 以下，因此必須要進(jìn)一步地降低錯(cuò)誤概率

6、：編碼方法編碼方法增加擴(kuò)展次數(shù)二元信源進(jìn)行編碼方法1：0；1方法2：000；111輸入符號(hào)等概率分布，譯碼規(guī)則采用最大似然準(zhǔn)則編碼方法增加擴(kuò)展次數(shù)方法1：0；1方法2：000；111編碼方法增加擴(kuò)展次數(shù)用方法二，增加擴(kuò)展次數(shù)可以降低錯(cuò)誤概率結(jié)論1：M不變時(shí)，n越大，PE 越小，R也越小。編碼方法減小輸入符號(hào)數(shù)令n=3，M變化，看看此時(shí) 和R的變化情況M=8時(shí)的情況：M=2時(shí)的情況：編碼方法減小輸入符號(hào)數(shù)M=8時(shí)的情況：編碼方法減小輸入符號(hào)數(shù)M=4時(shí)的情況，輸入符號(hào)是：000、011、101、110編碼方法減小輸入符號(hào)數(shù)M=4時(shí)的情況，輸入符號(hào)是：000、011、101、110編碼方法減小輸入符

7、號(hào)數(shù)總結(jié)：當(dāng)n=3不變，M變化時(shí)結(jié)論2：n不變時(shí)，M越大，PE 越大，R也越大編碼方法調(diào)整輸入符號(hào)n一定，M也一定，選擇不同的輸入符號(hào)輸入符號(hào)是000、001、010、100輸入是000、011、101、110時(shí)編碼方法調(diào)整輸入符號(hào)第二種方式和第一種方式相比，信息傳輸率一樣，平均錯(cuò)誤概率更大結(jié)論3：n、M一定，選擇不同的輸入符號(hào)， PE不同，R相等編碼方法增大最小距離 第一種：兩兩之間都有2個(gè)二元符號(hào)不同。一個(gè)二元符號(hào)出錯(cuò)，不會(huì)串?dāng)_到其它輸入符號(hào)，因此可以判斷出現(xiàn)了錯(cuò)誤 。 第二種：000與其它輸入符號(hào)之間只差一個(gè)二元符號(hào)，當(dāng)000任何一個(gè)二元符號(hào)出現(xiàn)錯(cuò)誤時(shí)，就會(huì)串?dāng)_到其它輸入符號(hào)上，也就判斷

8、不出錯(cuò)誤。編碼方法增大最小距離 為了描述符號(hào)序列之間的這種相差性，定義了漢明距離。長(zhǎng)度為n的兩個(gè)符號(hào)序列 間的漢明距離是指兩符號(hào)序列對(duì)應(yīng)位置上不同碼元的個(gè)數(shù)。用符號(hào) 表示，簡(jiǎn)寫為例如對(duì)應(yīng)位置上有3個(gè)碼元不同編碼方法增大最小距離相應(yīng)位置上的碼元是否相同，在C語言中就是異或運(yùn)算（相異為1，相同為0），所以漢明距離可以表示為：在碼字集合中，共有M個(gè)碼字，兩兩之間的漢明距離共有編碼方法增大最小距離最小距離：任意兩個(gè)碼字的漢明距離的最小值，稱為該碼的最小距離M、n相同的情況下， 越大， 就越小對(duì)于不同的M和n，也有這樣的準(zhǔn)則編碼方法增大最小距離 前面我們講到的減小錯(cuò)誤概率的方法，如M一定，增大n；n一定

9、，減小M。本質(zhì)上都是為了增大最小距離結(jié)論4（本質(zhì)結(jié)論）：增大 ，就可以減小 所以我們選擇編碼方法時(shí)，要使碼字間的距離盡可能大最小距離譯碼規(guī)則定義了漢明距離之后，又引入了一種譯碼規(guī)則：最小距離譯碼規(guī)則即選擇譯碼函數(shù)：最小距離譯碼規(guī)則選擇譯碼函數(shù)時(shí)不用計(jì)算傳遞概率，只用計(jì)算漢明距離F(000)=000F(001)=000F(010)=000F(011)=111F(100)=000F(101)=111F(110)=111F(111)=111最小距離譯碼規(guī)則最小距離譯碼規(guī)則、最大似然準(zhǔn)則都僅僅考慮了信道的統(tǒng)計(jì)特性，沒有考慮輸入序列的概率分布。兩種譯碼規(guī)則有什么樣的區(qū)別與聯(lián)系呢？我們可以證明，在正常的二

10、元對(duì)稱信道上，兩者是一致的，而在其他信道上則不一定。所謂正常的二元對(duì)稱信道，指正確概率大于錯(cuò)誤概率的二元對(duì)稱信道最小距離譯碼規(guī)則最小距離準(zhǔn)則為：因?yàn)槎獙?duì)稱信道是離散無記憶信道，輸出分量只與當(dāng)前時(shí)刻的輸入分量相關(guān)最大似然準(zhǔn)則為：最小距離譯碼規(guī)則因此有：最小距離譯碼規(guī)則對(duì)于正常的信道，有 ，正確概率大于錯(cuò)誤概率 的冪數(shù)越高， 則越大，也就是漢明距離D 越小， 越大最大似然準(zhǔn)則和最小距離準(zhǔn)則實(shí)現(xiàn)了統(tǒng)一 最小距離和糾錯(cuò)能力 要糾正1位錯(cuò)誤，要求碼的最小距離 一個(gè)碼能夠檢測(cè) 位錯(cuò)誤的充要條件為： 一個(gè)碼能夠糾正 位錯(cuò)誤的充要條件為： 一個(gè)碼能夠糾正 個(gè)錯(cuò)誤，同時(shí)又能檢測(cè)出 位錯(cuò)誤的充要條件為：要檢測(cè)1

11、位錯(cuò)誤，要求碼的最小距離課堂練習(xí)設(shè)某二元碼為C=11100, 01001, 10010, 001111、計(jì)算此碼的最小距離2、計(jì)算此碼的碼率R，假設(shè)碼字等概率分布3、采用最小距離譯碼準(zhǔn)則，試問接收序列10000，01100和00100應(yīng)譯為什么碼字4、此碼能夠糾正幾位碼元的錯(cuò)誤？練習(xí)、作業(yè)解：設(shè)練習(xí)、作業(yè)有噪信道編碼定理 信息傳輸?shù)目煽啃院陀行灾g，仿佛總是存在著沖突，提高了可靠性的同時(shí)，往往都會(huì)犧牲了有效性 有沒有一種解決方法，存在不存在一種編碼方法，能夠協(xié)調(diào)有效性和可靠性之間的沖突，在信息傳輸率R不降低的情況下，減小錯(cuò)誤概率呢？ 香農(nóng)第二定理，有噪信道編碼定理很好的回答了這個(gè)問題有噪信道

12、編碼定理香農(nóng)第二定理：設(shè)離散無記憶信道X、Y分別代表輸入、輸出信號(hào)， 是傳遞概率分布。當(dāng)信息傳輸率 時(shí)，只要碼長(zhǎng)n足夠大，就存在著一種碼和對(duì)應(yīng)的譯碼規(guī)則，使譯碼后的錯(cuò)誤概率任意小 香農(nóng)第二定理指出信道容量是保證無差錯(cuò)傳輸時(shí)，信息傳輸率的極限值有噪信道編碼逆定理設(shè)離散無記憶信道 ，信道容量為C。當(dāng)信息傳輸率 時(shí)，無論碼長(zhǎng)n有多長(zhǎng)，總也找不到一種編碼，使平均錯(cuò)誤概率任意小信道糾錯(cuò)編碼的基本概念 盡管早在1948年，香農(nóng)就提出了關(guān)于在有噪信道中傳輸信息的重要理論，但是卻沒有明確的給出具體的編解碼算法。 之后無數(shù)的科學(xué)技術(shù)工作者在香農(nóng)第二定理的指導(dǎo)下進(jìn)行了很多積極的實(shí)踐和探索，總結(jié)出許多行之有效的編解碼算法，從而逐步形成了一門技術(shù)學(xué)科糾錯(cuò)編碼 在差錯(cuò)控制系統(tǒng)中按照糾錯(cuò)能力的不同，分為檢錯(cuò)碼和糾錯(cuò)碼兩種線性分組碼線性分組碼的基本概念線性分組碼的基本概念分組碼：每k個(gè)信息碼元為一組，以一定的規(guī)律再生成r個(gè)校驗(yàn)碼元，共同組成一個(gè)n=k+r個(gè)碼元的碼字線性碼：信息碼元和校驗(yàn)碼元之間的是線性的關(guān)系。即校驗(yàn)碼元的產(chǎn)生，是由各信息碼元以線性的關(guān)系產(chǎn)生的(7,4)漢明碼漢明碼是重要的線性分組碼，以（7，