信息論-基礎(chǔ)理論與應(yīng)用：第六章 有噪信道編碼定理

1、第六章 有噪信道編碼定理 第一節(jié) 錯誤概率與譯碼規(guī)則第二節(jié) 錯誤概率與編碼方法第三節(jié) 有噪信道編碼定理第四節(jié) 聯(lián)合信源信道編碼定理1第六章 有噪信道編碼定理 前一章已經(jīng)從理論上討論了，對于無噪無損信道只要對信源進行適當(dāng)?shù)木幋a，總能以信道容量無差錯的傳遞信息。但是一般信道總會存在噪聲和干擾，那么在有噪信道中進行無差錯傳輸可以達到的最大信息傳輸率是多少呢？這就是本章所要討論的問題。本章的核心是香農(nóng)第二定理。第一節(jié) 錯誤概率與譯碼規(guī)則 為了減少錯誤，提高通信的可靠性，就必須分析錯誤概率與哪些因素有關(guān)，有沒有辦法控制，能控制到什么程度。 前邊已經(jīng)討論過，錯誤概率與信道的統(tǒng)計特性有關(guān)，但并不是唯一相關(guān)的

2、因素，譯碼方法的選擇也會影響錯誤率。例：設(shè)一個二元對稱信道，其傳輸特性如圖所示。一般二元對稱信道輸出端的譯碼器是將接收到符號“0”譯成發(fā)送的符號為“0”，接收到符號“1”譯成發(fā)送的符號為“1”。 如果仍按照此譯碼器的譯碼規(guī)則，那么當(dāng)發(fā)送符號為“0”，接收到符號仍為“0”, 則譯碼器譯為符號“0”，為正確譯碼，因此對發(fā)送符號“0”來說，譯對的可能性只有1/3；而當(dāng)發(fā)送符號為“0”，接收到符號卻是“1”則譯成符號“1”，為錯誤譯碼，則譯錯的概率是2/3。因為信道對稱，對發(fā)送符號“1”來說，譯錯的概率也是2/3。在此譯碼規(guī)則下，平均錯誤概率 (假設(shè)輸入端符號是等概率分布) 反之，若根據(jù)這個特殊信道定

3、出另一種譯碼規(guī)則: 將輸出端接收符號“0”譯成符號“1”， 將輸出端接收符號“1”譯成符號“0” 則譯錯的可能性就減少了，為1/3；而譯對的可能性增大了，為2/3。可見，錯誤概率既與信道的統(tǒng)計特性有關(guān)，也與譯碼的規(guī)則有關(guān)?，F(xiàn)在我們來定義譯碼規(guī)則。設(shè)離散單符號信道的 輸入符號集為 A=ai ，i=1,2,r； 輸出符號集為 B=bj , j=1,2,s。 制定譯碼規(guī)則就是設(shè)計一個函數(shù)F(bj)，它對于每一個輸出符號 bj確定一個唯一的輸入符號ai與其對應(yīng)(單值函數(shù))。即 (i=1,2,r)(j=1,2,s) 有一離散單符號信道，信道矩陣為 根據(jù)這樣一個信道矩陣，設(shè)計一個譯碼規(guī)則A，也可以設(shè)計另外

4、一個譯碼規(guī)則B 由于s個輸出符號中的每一個都可以譯成r個輸入符號中的任何一個，所以共有rs 種譯碼規(guī)則可供選擇。譯碼規(guī)則的選擇應(yīng)該根據(jù)什么準則?一個很 自然的準則當(dāng)然就是要使平均錯誤概率為最小。為了選擇譯碼規(guī)則，首先必須計算平均錯誤概率。在確定譯碼規(guī)則F(bj)=ai 后，若信道輸出端接收到的符號為bj，則一定譯成 ai，如果發(fā)送端發(fā)送的就是ai，這就為正確譯碼；如果發(fā)送的不是ai，就認為是錯誤譯碼。那么，收到符號bj條件下譯碼的條件正確概率為令 為條件錯誤概率，其中e表示除了F(bj)=ai 以外的所有輸入符號的集合。條件錯誤概率與條件正確概率之間有關(guān)系。經(jīng)過譯碼后的平均錯誤概率PE應(yīng)是條件

5、錯誤概率 對Y空間取平均值。即 它表示經(jīng)過譯碼后平均接收到一個符號所產(chǎn)生的錯誤大小，也稱平均錯誤概率。 “最大后驗概率準則”或“最小錯誤概率準則”設(shè)計這樣一種譯碼函數(shù) 可使平均錯誤概率最小。因為我們一般是已知信道的傳遞概率 與輸入符號的先驗概率 ，所以根據(jù)貝葉斯定律，上式可寫成 一般P(bi)0,這樣，最大后驗概率準則就可表示為： 選擇譯碼函數(shù) 使?jié)M足 若輸入符號的先驗概率 均相等，則上式可寫成選擇譯碼函數(shù)并滿足 這樣定義的譯碼規(guī)則稱為最大似然譯碼準則。在輸入符號等概率時，這兩個譯碼準則是等價的。根據(jù)最大似然譯碼準則我們可以直接從信道矩陣的傳遞概率中去選定譯碼函數(shù)。就是說，收到bi后，譯成信道

6、矩陣P的第j列中最大那個元素所對應(yīng)的信源符號。 最大似然譯碼準則本身不再依賴于先驗概率。 但是當(dāng)先驗概率為等概率分布時，它使錯誤 概率PE最小。(注意：如果先驗概率不相等或不知道時，仍可以采用這個準則，但不一定能使PE最小)。根據(jù)譯碼準則，進一步可寫出平均錯誤概率，即式中求和號 表示對輸入符號集A中除a* 以外的所有元素求和。上式也可以寫成 上式的平均錯誤概率是在聯(lián)合概率矩陣 中先求每列除去F(bj)=a* 所對應(yīng)的P(a*bj)以外所有元素之和，然后再對各列求和。當(dāng)然，我們也可以在矩陣中先對行求和，除去譯碼規(guī)則中F(bj)= a* 所對應(yīng)的 P(a* bj);然后再對各行求和。因此上式還可以

7、寫成其中令 。 就是某個輸入符號ai傳輸所引起的錯誤概率。接前例 有一離散單符號信道，信道矩陣為 根據(jù)最大似然譯碼準則可選擇譯碼函數(shù)為B在輸入等概率分布時采用譯碼函數(shù)B可使信道平均錯誤概率最小。若選用前述譯碼函數(shù)A則得平均錯誤概率可見若輸入不是等概分布，其概率分布為根據(jù)最大似然譯碼準則仍可選擇譯碼函數(shù)為B，計算其平均錯誤概率。但采用最小錯誤概率譯碼準則，它的聯(lián)合概率矩陣為所以得譯碼函數(shù)為計算平均錯誤概率可見，此時 。所以，輸入不是等概分布時最大似然譯碼準則的平均錯誤概率不是最小。例題：有一離散信道，信道矩陣為， 假如信道輸入消息符號的概率分別為： 請分別用最大后驗概率譯碼準則和最大似然譯碼準則

8、確定譯碼函數(shù)，并計算其相應(yīng)的平均錯誤概率。解：（1）最大后驗概率譯碼準則（2）最大似然譯碼準則費諾不等式PE和信道疑義度H(X/Y)的關(guān)系 雖然平均錯誤概率與譯碼規(guī)則有關(guān)，但是不管采用什么譯碼規(guī)則該不等式都是成立的。第二節(jié) 錯誤概率與編碼方法 一般信道傳輸時都會產(chǎn)生錯誤，而選擇譯碼準則并不會消除錯誤，那么如何減少錯誤概率呢？下邊討論通過編碼方法來降低錯誤概率。01010.990.990.010.01例：對于如下二元對稱信道 如何提高信道傳輸?shù)恼_率呢？ 可以嘗試用下面的方法沒有使用的碼字001010011100101110用作消息的碼字000111輸出端接收序列0000010100111001

9、01110111二元對稱信道的三次擴展信道則：根據(jù)最大似然譯碼準則，可得譯碼函數(shù)為：F(000)=000 F(001)=000 F(010)=000 F(011)=111F(100)=000 F(101)=111 F(110)=111 F(111)=111 此時，譯碼可以采用“擇多譯碼”，即根據(jù)接收序列中0多還是1多，0多就判作0，1多就判作1。錯誤概率降低了兩個數(shù)量級，這種編碼可以糾正碼字中的一位碼元出錯。若重復(fù)多次可進一步降低錯誤率。 但是又出現(xiàn)了一個新的問題，n很大時，信息傳輸率會降低很多，我們把編碼后的信息傳輸率表示為： 在上例中：M=2當(dāng)n=1時 R=1 比特碼符號當(dāng)n=3時 R=1

10、/3 比特碼符號當(dāng)n=5時 R=1/5 比特碼符號.n越大，PE越低,信息傳輸率R越低. 這顯然是一個矛盾，有沒有解決的辦法呢？香農(nóng)第二定理可以解決這一問題。 我們分析前邊的例子，我們只用了擴展信源的兩個字符，因此信息率降低了，如果我們把8個字符全用上，信息傳輸率就會回到1，但是此時錯誤概率為3*10-2 ， 比單符號時還大三倍。我們可以總結(jié)如下：在二元信道的n次擴展信道中，選取其中的M個作為消息，則M大一些，PE 跟著大，R也大; M小一些,PE 跟著小，R也小。 如果在上例中，取M4，如：取000 011 101 110為消息，其他的不用，則 則與M=8比較，錯誤率降低了，而信息率也降低了

11、。 還存在另外一個問題，M=4時，有70種選取方法，而選取方法不同，錯誤率也不同。我們比較下面兩種選取方法：第一種： 000 011 101 110 第二種： 000 001 010 100 可以計算得第一種方法的錯誤率為2*10-2 第二種方法的錯誤率為2.28*10-2 比較可知，第一種方法好，仔細觀察發(fā)現(xiàn)，在第一種方法中，如果000有一位出錯，我們就可以判定出錯了；而在第二種方法中，如果000中任何一位出錯，就變成了其他的合法的碼字，我們無法判斷是否出錯。再仔細觀察，發(fā)現(xiàn)第二種方法中，碼字之間太“象”了，或者說太“近”了。 我們再討論一個例子，取M4，n5，這時信道的信息傳輸率為：這4個

12、碼字按如下規(guī)則選?。?設(shè)輸入序列為:滿足方程：若譯碼采取最大似然準則： 此碼能糾正所有碼字中一位碼元錯誤，也能糾正其中兩個兩位碼元的錯誤。 我們引進這樣一個概念：漢明距離。在二元碼中：如：則 在某一碼書中，任意兩個碼字的漢明距離的最小值稱為該碼C的最小距離。 碼A碼B碼C碼D碼字000111000011101110000001010100000 001010 011100 101100 111消息數(shù)M2448最小距離dmin3211信息傳輸率R1/32/32/31錯誤概率我們來討論前邊的5種碼的距離：很明顯， 越大，PE 越小，在M相同的情況下也是一樣最小距離譯碼準則設(shè)信道輸入端作為消息的碼字

13、為i，長度為n；輸出端可能有的所有接收序列為j，長度為n。 最大似然譯碼準則可表述為： 若i和j之間的距離為D(i, j)，簡記為Dij，它表示傳輸過程中i傳輸?shù)絡(luò)有Dij個位置發(fā)生了錯誤，(n- Dij)個位置沒有錯誤。設(shè)二元對稱信道的單個符號傳輸錯誤概率為p，當(dāng)信道是無記憶時，則編碼后信道的傳遞概率為如果p1/2(這是正常情況，例如 p=10-2 )， 可以看出dij越大，P(j/i)越小, dij越小，P(j/i) 越大。根據(jù)前式，最大似然譯碼準則可用漢明距離表示為選擇譯碼函數(shù)使?jié)M足即滿足 上式又稱為最小距離譯碼準則。 在二元對稱信道中最小距離譯碼準則等于最大似然譯碼準則。在任意信道中也

14、可采用最小距離譯碼準則，但它不一定等于最大似然譯碼準則。 因此，在二元信道中最大似然譯碼準則可表述為：當(dāng)收到j(luò)后，譯成與之距離(漢明距離)為最近的輸入碼字*，可使平均錯誤概率PE達到最小。同時在M和n不變的情況下，即保持一定信息傳輸率R的前提下，選擇不同的編碼方法，可取得不同的Dij=D(i,j)和D*j=D(*,j)，而使PE不同。 因此，我們可以選擇這樣的編碼方法：對選擇的每一個碼字*都與某一特定接收序列j的距離盡可能近，D（*,j）盡量小；又使其他碼字i*與這接收序列j 的距離盡可能地遠，D(i,j)盡量大。換句話說，應(yīng)盡量設(shè)法使選取的M個碼字中任意兩兩不同碼字的距離D(i,j)盡量大。

15、這樣就可做到保持一定信息傳輸率R，而使PE盡可能的小。綜上所述，在有噪信道中，傳輸?shù)钠骄e誤概率PE與各種編、譯碼方法有關(guān)。編碼可采用選擇M個消息所對應(yīng)的碼字間最小距離dmin盡可能增大的編碼方法，而譯碼采用將接收序列j譯成與之距離最近的那個碼字*的譯碼規(guī)則，則只要碼長n足夠長時，合適地選擇M個消息所對應(yīng)的碼字，就可以使錯誤概率很小，而信息傳輸率保持一定。第三節(jié) 有噪信道編碼定理（香農(nóng)第二定理）1、有噪信道編碼定理 如一個離散無記憶信道，信道容量為C。當(dāng)信息傳輸率RC時，只要碼長足夠長，總可以在輸入Xn符號集中找到 M=2nR 個碼字組成的一組碼(2nR,n)和相應(yīng)的譯碼準則，使譯碼的平均錯誤

16、概率達到任意小(PE 0)有噪信道編碼定理證明方法中的基本思路 (1)連續(xù)使用信道多次，即在n次無記憶信道中討論，以便使大數(shù)定律有效; (2)隨機選取碼字，也就是在Xn符號序列集中隨機的選取經(jīng)常出現(xiàn)的高概率序列作為碼字；（3）采用最大似然譯碼準則，也就是將接收序列譯成與其最近的那個碼字；（4）在隨機編碼的基礎(chǔ)上，對所有的碼字計算其平均錯誤概率，當(dāng)n足夠大時，此平均錯誤概率趨近于零，由此證明至少有一種好碼存在；我們也可采用與上述相同的基本思路，但主要的區(qū)別在于譯碼規(guī)則： 我們在編碼時，隨機地選擇輸入端典型序列x作為碼字，因為它們是在輸入端Xn集中經(jīng)常、高概率出現(xiàn)的序列。而在接收端Yn集中，對接收

17、序列y尋找與它構(gòu)成聯(lián)合典型序列的那個碼字。若只有惟一一個碼字滿足此性質(zhì)，則判定這碼字為所發(fā)送的碼字。根據(jù)上節(jié)所述的聯(lián)合典型序列的性質(zhì)，所發(fā)送的碼字與接收序列y構(gòu)成聯(lián)合典型序列的概率很高，它們之間是高概率密切相關(guān)的。2、有噪信道編碼逆定理 如一個離散無記憶信道，信道容量為C。當(dāng)信息傳輸率RC時，則無論碼長n多長，總也找不到一種編碼(M=2nR,n)，使信道輸出端的譯碼錯誤概率任意小。 這個定理是信道編碼的理論依據(jù)，可以看出：信道容量是一個明確的分界點，當(dāng)取分界點以下的信息傳輸率時，PE以指數(shù)趨近于0；當(dāng)取分界點以上的信息傳輸率時，PE 以指數(shù)趨近于1；因此在任何信道中，信道容量都是可達的、最大的

18、可靠信息傳輸率。 這個定理是一個存在定理，它沒有給出一個具體可構(gòu)造的編碼方法，在它的證明過程中，碼書是隨機地選取的，當(dāng)n很大時，這碼書構(gòu)成的碼表就非常龐大，也就無法實用和實現(xiàn)。盡管如此，信道編碼定理仍然具有根本性的重要意義。它有助于指導(dǎo)各種通信系統(tǒng)的設(shè)計，有助于評價各種系統(tǒng)及編碼的效率。第四節(jié) 聯(lián)合信源信道編碼定理 從香農(nóng)第一、第二定理可以看出，要做到有效和可靠的傳輸信息，我們可以將通信系統(tǒng)設(shè)計成兩部分的組合，即信源編碼和信道編碼兩部分，首先通過信源編碼，用盡可能少的信道符號來表達信源，盡可能減少編碼后信源的數(shù)據(jù)的剩余度。然后針對信道，對信源編碼后所得的數(shù)據(jù)獨立的設(shè)計信道編碼，也就是適當(dāng)增加一些剩余度，使能糾正和克服信道中引起的錯誤和干擾。 我們可以證明，只要滿足香農(nóng)第一定理和第二定理，用兩步編碼的方法傳輸信息和一步編碼的方法傳輸信息其效果是一樣的。定理6.7 信源-信道編碼定理 若Xn是有限符號集的隨機序列，并滿足AEP（漸進等分割性），有信源