信息論-基礎(chǔ)理論與應(yīng)用第三版-第六章-講義(課堂PPT)課件

1、第6章 有噪信道編碼定理 6.1 錯(cuò)誤概率與譯碼規(guī)則6.2 錯(cuò)誤概率與編碼方法6.4 有噪信道編碼定理6.5 聯(lián)合信源信道編碼定理1 前面已經(jīng)從理論上討論了，對(duì)于無(wú)噪無(wú)損信道只要對(duì)信源進(jìn)行適當(dāng)?shù)木幋a，總能以信道容量無(wú)差錯(cuò)的傳遞信息。但是一般信道總會(huì)存在噪聲和干擾，信息傳輸會(huì)造成損失。 那么在有噪信道中怎樣能使消息傳輸發(fā)生的錯(cuò)誤最少？進(jìn)行無(wú)錯(cuò)傳輸?shù)目蛇_(dá)的最大信息傳輸率是多少呢？ 這就是本章所要討論的問(wèn)題。本章的核心是香農(nóng)第二定理。26.1 錯(cuò)誤概率與譯碼規(guī)則 為了減少傳輸錯(cuò)誤，提高通信的可靠性，就必須分析錯(cuò)誤概率與哪些因素有關(guān)，有沒(méi)有辦法控制？能控制到什么程度？ 一般地，錯(cuò)誤概率與如下因素相關(guān)：

2、信道的統(tǒng)計(jì)特性譯碼規(guī)則3例：有一個(gè)BSC信道，如圖所示 若收到“0”譯作“0”，收到“1”譯作“1”，則平均錯(cuò)誤概率為：反之，若收到“0”譯作“1”，收到“1”譯作“0”，則平均錯(cuò)誤概率為可見(jiàn)錯(cuò)誤概率與譯碼規(guī)則有關(guān)。01011/31/32/32/301譯碼信源P(0)P(1)4譯碼規(guī)則： 輸入符號(hào)集 輸出符號(hào)集 譯碼規(guī)則例：某信道轉(zhuǎn)移矩陣可以設(shè)計(jì)譯碼準(zhǔn)則： A： 和 B：5總的譯碼規(guī)則數(shù)目 信道的s個(gè)輸出符號(hào)的每一個(gè)譯碼輸出有 r 種選擇，因此，總的 譯碼規(guī)則總數(shù)為譯碼規(guī)則的選擇依據(jù) 一個(gè)自然的依據(jù)就是使平均錯(cuò)誤概率最小。 為了選擇譯碼規(guī)則，需要計(jì)算平均錯(cuò)誤概率。 平均錯(cuò)誤概率分析： 譯碼規(guī)則

3、確定后，設(shè)信道輸出端收到 時(shí)一定譯為 。如果發(fā)送端剛好發(fā)送的就是 ，則為正確譯碼，譯碼的條件正確概率為：6而錯(cuò)誤譯碼的概率為收到 后翻譯為 ，但發(fā)送端實(shí)際上發(fā)送的卻不是 ，則為錯(cuò)誤譯碼，其條件錯(cuò)誤概率為： e表示：除了 以外的所有輸入符號(hào)的集合。則可得平均錯(cuò)誤譯碼概率： 它表示經(jīng)過(guò)譯碼后平均每收到一個(gè)符號(hào)所產(chǎn)生錯(cuò)誤的大小，也稱(chēng)平均錯(cuò)誤概率。7條件正確概率 如何設(shè)計(jì)譯碼規(guī)則 ，使平均錯(cuò)誤概率最?。孔钚″e(cuò)誤概率準(zhǔn)則（最大后驗(yàn)概率準(zhǔn)則）條件錯(cuò)誤概率滿足關(guān)系：因此應(yīng)選擇譯碼規(guī)則 也即收到一個(gè)符號(hào)以后譯成具有最大后驗(yàn)概率的那個(gè)輸入符號(hào)。決定于譯碼規(guī)則i為待定8根據(jù)貝葉斯定理，上式可寫(xiě)成當(dāng)信源等概分布時(shí)，

4、則最小錯(cuò)誤概率準(zhǔn)則變?yōu)?這稱(chēng)為最大似然譯碼準(zhǔn)則，方法是收到一個(gè) 后，在信道矩陣的第j列元素中選擇最大的值所對(duì)應(yīng)的輸入符號(hào)作為譯碼輸出。最大似然譯碼準(zhǔn)則即9當(dāng)譯碼規(guī)則確定后，可進(jìn)一步計(jì)算平均錯(cuò)誤概率：平均錯(cuò)誤概率的計(jì)算信道傳遞概率平均正確概率上式中，平均錯(cuò)誤概率計(jì)算是在聯(lián)合概率矩陣P(ai)P(bj|ai)中： 1）先求每一列除去F(bj)=a*所對(duì)應(yīng)的P(a*bj)以外的元素之和； 2）然后，對(duì)所有列求和。10（選講）當(dāng)然，也可以對(duì)聯(lián)合概率矩陣P(ai)P(bj/ai)中：1）先求每一行中除去F(bj)=ai*所對(duì)應(yīng)的P(aibj)以外的元素之和; 2）然后，對(duì)各行的和求和。 如果先驗(yàn)概率相等

5、，則：某個(gè)輸入符號(hào)ai傳輸引起的錯(cuò)誤概率即：具體計(jì)算如下：11例：某信道1）若根據(jù)最大似然準(zhǔn)則選擇譯碼函數(shù)為B：若輸入等概率，則平均錯(cuò)誤概率為若輸入不等概分布 ，則錯(cuò)誤概率為：122）采用最小錯(cuò)誤概率譯碼準(zhǔn)則，則聯(lián)合矩陣為：所得譯碼函數(shù)為：C：平均錯(cuò)誤概率：136.2 錯(cuò)誤概率與編碼方法 一般信道傳輸時(shí)都會(huì)產(chǎn)生錯(cuò)誤，而選擇譯碼準(zhǔn)則并不會(huì)消除錯(cuò)誤，那么如何減少錯(cuò)誤概率呢？下邊討論通過(guò)編碼方法來(lái)降低錯(cuò)誤概率。例：對(duì)于如下二元對(duì)稱(chēng)信道01010.990.990.010.01按照最大似然準(zhǔn)則譯碼，14 如何提高信道傳輸?shù)恼_率呢？可用重復(fù)消息的方法，即嘗試擴(kuò)展信道的方法。未用的碼字（禁用碼字）0010

6、10011100101110用作消息的碼字（許用碼字）000 （表示0）111 （表示1）輸出端接收序列000001010011100101110111二元對(duì)稱(chēng)信道的三次擴(kuò)展信道15則信道矩陣為：根據(jù)最大似然譯碼準(zhǔn)則，當(dāng)p=0.01，可得譯碼函數(shù)為：F(000)=000 F(001)=000 F(010)=000 F(011)=111F(100)=000 F(101)=111 F(110)=111 F(111)=111一位錯(cuò)誤當(dāng)000、111等概時(shí)，平均錯(cuò)誤概率變小了：16 現(xiàn)在碼元個(gè)數(shù)n=3，已經(jīng)將錯(cuò)誤概率降低了兩個(gè)數(shù)量級(jí)；若重復(fù)更多次，n=5，7，還可以進(jìn)一步降低錯(cuò)誤概率，上例中：當(dāng)n=5

7、時(shí) 當(dāng)n=7時(shí) 當(dāng)n=9時(shí) 當(dāng)n=11時(shí) 但是n很大時(shí)，信道的信息傳輸率會(huì)降低很多：（M為許用碼字的個(gè)數(shù)，即輸入消息個(gè)數(shù)，n為編碼后碼字的長(zhǎng)度） 在上例中：M=2當(dāng)n=1時(shí) R=1當(dāng)n=3時(shí) R=1/3當(dāng)n=5時(shí) R=1/5（比特/碼符號(hào)）（比特/碼符號(hào)）（比特/碼符號(hào)）17 分析前邊的例子，只用了擴(kuò)展信源的兩個(gè)字符，因此信息率降低了，如果把8個(gè)字符全用上，信息傳輸率就會(huì)回到1，但是此時(shí)錯(cuò)誤率更大了：一般地，有如下規(guī)律： 在二元信道的n次擴(kuò)展信道中，選取其中的M個(gè)作為消息，則M大一些， 跟著大，R也大；M小一些， 跟著小，R也小。 如果上例中，取M4，如：取000 011 101 110為消息

8、，則 與M=8比較，錯(cuò)誤率降低了，而信息率也降低了。18另外一個(gè)問(wèn)題，消息數(shù)固定而編碼選取方法不同，錯(cuò)誤率也不同。比較兩種選取方法： 第一種： 000 011 101 110 第二種： 000 001 010 100 可以計(jì)算得第一種方法的錯(cuò)誤率為 第二種方法的錯(cuò)誤率為 比較可知，第一種方法好。仔細(xì)觀察發(fā)現(xiàn)： 在第一種方法中，如果 000 有一位出錯(cuò)，就可以判定出錯(cuò)了； 而在第二種方法中，如果000中任何一位出錯(cuò)，就變成了其他的合法的碼字，我們無(wú)法判斷是否出錯(cuò)。 再仔細(xì)觀察，發(fā)現(xiàn)第二種方法中，碼字之間太相似。19碼字距離： 長(zhǎng)度為n的兩個(gè)碼字對(duì)應(yīng)位置上不同碼元的個(gè)數(shù)。通常稱(chēng)為漢明距離： 在二元

9、碼中，碼字的漢明距離：如：則 在某一碼中，任意兩個(gè)碼字Ci、Cj的漢明距離的最小值稱(chēng)為該碼C的最小距離。20 碼A碼B碼C碼D消息數(shù)M2448碼字000111000011101110000001010100000 001010 011100 101100 111最小距離dmin3211信息傳輸率R1/32/32/31錯(cuò)誤概率 很明顯， 越大， 越小，在M相同時(shí)也如此。碼C中最小距離越大，受到干擾后，越不容易成為另一碼字，因而錯(cuò)誤概率??；相反，則容易干擾后變成另一碼字。所以：應(yīng)盡量設(shè)法使選取的M個(gè)碼字中任意兩兩不同碼字的距離盡量大。討論4種碼的距離和錯(cuò)誤概率（碼長(zhǎng)=3）：21 二元信道的譯碼規(guī)則

10、可以如下規(guī)定：選擇 使之滿足條件： 它稱(chēng)為最小距離譯碼準(zhǔn)則，也就是收到一個(gè)碼字后，把它譯成與它距離（漢明距離）最近的輸入碼字。 這樣可以使平均錯(cuò)誤率較小。最小距離譯碼準(zhǔn)則即：最近碼字接收序列22最小距離譯碼準(zhǔn)則與最大似然準(zhǔn)則的關(guān)系 在二元無(wú)記憶對(duì)稱(chēng)信道中，最小距離譯碼準(zhǔn)則等于最大似然譯碼準(zhǔn)則。 （略）證明：n次擴(kuò)展信道傳遞概率為：錯(cuò)誤位數(shù)正確位數(shù)N長(zhǎng)接收序列N長(zhǎng)發(fā)送序列信道轉(zhuǎn)移概率23 在任意信道中，也可以采用最小距離譯碼準(zhǔn)則，但它不一定等于最大似然準(zhǔn)則。由此，按照最大似然準(zhǔn)則，應(yīng)選擇傳遞概率最大者對(duì)應(yīng)的輸入序列作為譯碼輸出。選擇譯碼函數(shù)：使?jié)M足：即滿足：24小 結(jié) 在消息數(shù) M和碼長(zhǎng) n不變

11、的時(shí)，信息傳輸率R=logM/n。采用不同的編碼可獲得的不同的碼字距離和最小碼字距離，并導(dǎo)致不同的平均錯(cuò)誤概率。且最小碼字距離越大，平均錯(cuò)誤概率越小。 因此：應(yīng)盡量設(shè)法使選取的M個(gè)碼字中任意兩兩不同碼字的距離dmin盡量大。 總之，在有噪信道中，除了信道本身的統(tǒng)計(jì)特性外，傳輸?shù)钠骄e(cuò)誤概率與各種編譯碼方法相關(guān)。編碼：可選擇M個(gè)消息所對(duì)應(yīng)得碼字之間最小距離dmin盡可能大的編碼方法。譯碼：則將接收序列譯成與之最近的那個(gè)碼字。 只要碼長(zhǎng)n足夠大，合適地選擇M個(gè)消息的對(duì)應(yīng)碼字，就可以使錯(cuò)誤概率很小，而信息傳輸率保持一定。256.3 有噪信道編碼定理1、有噪信道編碼定理（香農(nóng)第二定理） 設(shè)一個(gè)離散無(wú)記

12、憶信道 ， 為信道傳遞概率，信道容量為C。當(dāng)信息傳輸率 RC時(shí)，則無(wú)論碼長(zhǎng)n多長(zhǎng)，總找不到一種編碼 使信道輸出端的平均錯(cuò)誤譯碼概率達(dá)到任意小。26 這個(gè)定理是信道編碼的理論依據(jù)，可以看出：信道容量是一個(gè)明確的分界點(diǎn)，當(dāng)取分界點(diǎn)以下的信息傳輸率時(shí)， 以指數(shù)趨進(jìn)于0；當(dāng)取分界點(diǎn)以下的信息傳輸率時(shí)， 以指數(shù)趨進(jìn)于1。 因此在任何信道中，信道容量都是可達(dá)的、最大的可靠信息傳輸率。 這個(gè)定理是一個(gè)存在定理，它說(shuō)明錯(cuò)誤概率趨于0的好碼是存在的。但它沒(méi)有給出一個(gè)具體可構(gòu)造的編碼方法，在它的證明過(guò)程中，碼是隨機(jī)的選取的。然而，它有助于指導(dǎo)各種通信系統(tǒng)的設(shè)計(jì)，有助于評(píng)價(jià)各種系統(tǒng)及編碼的效率。意 義27 從香農(nóng)第

13、一、第二定理可以看出，要做到有效和可靠的傳輸信息，可以將通信系統(tǒng)設(shè)計(jì)成兩部分的組合，即信源編碼和信道編碼兩部分： 1）首先通過(guò)信源編碼，用盡可能少的信道符號(hào)來(lái)表達(dá)信源，盡可能減少編碼后信源的數(shù)據(jù)的剩余率； 2）然后針對(duì)信道，對(duì)信源編碼后的數(shù)據(jù)獨(dú)立的進(jìn)行信道編碼，適當(dāng)增加一些剩余度，使能糾正和克服信道中引起的錯(cuò)誤和干擾。 理論分析表明，只要滿足香農(nóng)第一定理和第二定理，用兩步編碼的方法傳輸信息和一步編碼的方法傳輸信息其效果是一樣的。（選講）6.5 聯(lián)合信源信道編碼定理28兩步編碼分析：其信源壓縮編碼只與信源有關(guān)，不依賴(lài)于信道；信道編碼只與信道有關(guān)，不依賴(lài)于信源。如果信源編碼是一一對(duì)應(yīng)的無(wú)失真編碼 (RH)，則編碼、譯碼都是一一對(duì)應(yīng)的映射，不會(huì)帶來(lái)信息的損失；信道會(huì)導(dǎo)致信息有一些損失。但通過(guò)適當(dāng)?shù)男诺谰幋a（RC），可使信道引起的損失或錯(cuò)誤盡可能小。 因此，兩步處理不會(huì)帶來(lái)信息的損失。29若 是有限符號(hào)集的隨機(jī)序列，并滿足AEP(漸進(jìn)等分性)，信源S的極限熵 ，則存在信源與信道編碼，其 。反之，對(duì)于任意平穩(wěn)隨機(jī)序列，若極限熵 ，則錯(cuò)誤概率遠(yuǎn)離0，即不可能以任意小的錯(cuò)誤概率發(fā)送隨機(jī)序列。信源-信道編碼定理 因此，信源通過(guò)信道傳輸，有效和可靠地傳輸?shù)某湟獥l件是 HC。30 可見(jiàn)，當(dāng)且僅當(dāng)信源極限熵H信道容量C，在信道上無(wú)錯(cuò)誤地傳