第五章 編碼定理

1、 第五章第五章 編碼定理編碼定理第五章第五章 編碼定理編碼定理 5.1 引言引言 5.2 無失真離散信源編碼定理無失真離散信源編碼定理 5.3 限限失真信源編碼定理失真信源編碼定理5.4 離離散信道編碼定理散信道編碼定理5.5 連續(xù)信道編碼定理連續(xù)信道編碼定理 第五章第五章 編碼定理編碼定理5.1 引言引言信源熵、信道容量、信息率失真函數(shù)信源熵、信道容量、信息率失真函數(shù)，解決了在無，解決了在無失真和限失真的條件下，傳送信源信息所必須具有失真和限失真的條件下，傳送信源信息所必須具有的最小信息率以及能通過信道的最大信息率問題。的最小信息率以及能通過信道的最大信息率問題。問題：以上最大和最小信息率的

2、極限是否能達(dá)到或問題：以上最大和最小信息率的極限是否能達(dá)到或接近？接近？編碼定理要解決的問題：盡量達(dá)到或接近上述最大編碼定理要解決的問題：盡量達(dá)到或接近上述最大和最小信息率的極限。故編碼定理也被稱為極限定和最小信息率的極限。故編碼定理也被稱為極限定理。理。 第五章第五章 編碼定理編碼定理 無失真編碼定理無失真編碼定理第一極限定理第一極限定理 信源信源 限失真編碼定理限失真編碼定理第三極限定理第三極限定理編碼定理編碼定理 離散信道編碼定理離散信道編碼定理 信道信道 第二極限定理第二極限定理 連續(xù)信道編碼定理連續(xù)信道編碼定理以上定理有其逆定理，即當(dāng)信息率小于信源熵（或以上定理有其逆定理，即當(dāng)信息率

3、小于信源熵（或R(D)）時(shí)，或信息率大于信道容量時(shí)，被傳送的信）時(shí)，或信息率大于信道容量時(shí)，被傳送的信息必然有失真息必然有失真 第五章第五章 編碼定理編碼定理5.2 無失真離散信源編碼定理無失真離散信源編碼定理信源編碼：將信源輸出的隨機(jī)序列變換成碼序列，信源編碼：將信源輸出的隨機(jī)序列變換成碼序列，且能進(jìn)行反變換或譯碼，同時(shí)使傳送碼序列所需的且能進(jìn)行反變換或譯碼，同時(shí)使傳送碼序列所需的信息率最小。信息率最小。一、等長(zhǎng)信源編碼定理一、等長(zhǎng)信源編碼定理信源符號(hào)信源符號(hào)Si（i=1,2, q）碼字碼字Wi（i=1,2, q）若若Wi中的碼元有中的碼元有r種可能的取值，碼長(zhǎng)為種可能的取值，碼長(zhǎng)為l則對(duì)則

4、對(duì)S S進(jìn)行等長(zhǎng)編碼，須滿足進(jìn)行等長(zhǎng)編碼，須滿足 q rl 第五章第五章 編碼定理編碼定理若若S送出一個(gè)信源符號(hào)所需的信息率為送出一個(gè)信源符號(hào)所需的信息率為R，則，則N長(zhǎng)符號(hào)長(zhǎng)符號(hào)所需的信息率為所需的信息率為NR而每個(gè)碼元的最大信息量為而每個(gè)碼元的最大信息量為log r，則，則 l 長(zhǎng)碼序列的信長(zhǎng)碼序列的信息量為息量為 l log r編碼前后信息量應(yīng)保持不變，即：編碼前后信息量應(yīng)保持不變，即： NR l log r送出一個(gè)信源符號(hào)所需信息率：送出一個(gè)信源符號(hào)所需信息率：R（l /N ）log r為使傳送信息率最小，需找到一種編碼方式，使為使傳送信息率最小，需找到一種編碼方式，使R最最小。編碼定

5、理所研究的就是最小的小。編碼定理所研究的就是最小的R為何值才能得到為何值才能得到無失真的譯碼，若小于此信息率是否還能無失真地譯無失真的譯碼，若小于此信息率是否還能無失真地譯碼？碼？ 第五章第五章 編碼定理編碼定理等長(zhǎng)信源編碼定理：等長(zhǎng)信源編碼定理：無記憶平穩(wěn)離散信源的熵為無記憶平穩(wěn)離散信源的熵為H(S)，若對(duì)信源長(zhǎng)為，若對(duì)信源長(zhǎng)為N的符號(hào)序列進(jìn)行等長(zhǎng)編碼，的符號(hào)序列進(jìn)行等長(zhǎng)編碼，碼字從碼字從 r 個(gè)碼符號(hào)集中選取個(gè)碼符號(hào)集中選取 l 個(gè)碼元組成，對(duì)于個(gè)碼元組成，對(duì)于任意任意0，只要滿足：，只要滿足： 或或則當(dāng)則當(dāng)N足夠大時(shí)，可實(shí)現(xiàn)幾乎無失真編碼即譯碼錯(cuò)足夠大時(shí)，可實(shí)現(xiàn)幾乎無失真編碼即譯碼錯(cuò)誤概

6、率能為任意小。反之，若：誤概率能為任意小。反之，若：則不能實(shí)現(xiàn)無失真編碼，而當(dāng)則不能實(shí)現(xiàn)無失真編碼，而當(dāng)N足夠大時(shí)，譯碼錯(cuò)誤足夠大時(shí)，譯碼錯(cuò)誤概率近似等于概率近似等于1，譯碼幾乎必定出錯(cuò)。，譯碼幾乎必定出錯(cuò)。 第五章第五章 編碼定理編碼定理定理證明：定理證明：設(shè)設(shè)N長(zhǎng)符號(hào)組成的序列為長(zhǎng)符號(hào)組成的序列為aN，則相應(yīng)的，則相應(yīng)的切比雪夫不等式為：切比雪夫不等式為：即：即：由于信源取值有由于信源取值有q種，則種，則N長(zhǎng)信源序列就有長(zhǎng)信源序列就有qN種，種，將將qN種序列分成兩個(gè)互補(bǔ)的集種序列分成兩個(gè)互補(bǔ)的集 和和22)()(|)()(|NSNNSNHaIPN22)(| )()(|NSSHNaIPNA

7、cA| )()(| )()(|SHNaIaASHNaIaANNCNN： 第五章第五章 編碼定理編碼定理根據(jù)隨機(jī)序列根據(jù)隨機(jī)序列a aN N的切比雪夫不等式，顯然：的切比雪夫不等式，顯然： 假設(shè)假設(shè) 中的序列有中的序列有 個(gè)，且：個(gè)，且：即：即：因此序列概率必然滿足條件：因此序列概率必然滿足條件：1)()(1)()(02222APNSNSAPcM)()(| )()(|SHNaISHNaINN)(exp)()(expNSHaPNSHNA 第五章第五章 編碼定理編碼定理序列處于序列處于 集中的概率必為集內(nèi)各序列集中的概率必為集內(nèi)各序列a aN N的概率的概率之和：之和：將將 式代入式代入式，得：式，

8、得： A)(exp)()()()(exp)()()(minmaxNSHMaPMaPAPNSHMaPMaPAPNAaAaNNAaAaNNNNN)(exp)(exp)(1 (22SHNMSHNNS)(AP 第五章第五章 編碼定理編碼定理由于由于N長(zhǎng)的全部可能的序列有長(zhǎng)的全部可能的序列有qN個(gè)，若只對(duì)屬于個(gè)，若只對(duì)屬于 集的集的 個(gè)序列進(jìn)行編碼，則：個(gè)序列進(jìn)行編碼，則： rl 考慮考慮式，可得：式，可得：最終可得：最終可得：其它其它 集內(nèi)的序列會(huì)在譯碼時(shí)將發(fā)生差錯(cuò)，考慮集內(nèi)的序列會(huì)在譯碼時(shí)將發(fā)生差錯(cuò)，考慮式可得差錯(cuò)概率：式可得差錯(cuò)概率：上式中，上式中， 和和 為定值，只要為定值，只要N足夠大，足夠大

9、，Pe 可可以小于任一正數(shù)以小于任一正數(shù) ，即：，即：為達(dá)到差錯(cuò)要求，為達(dá)到差錯(cuò)要求，信源序列長(zhǎng)信源序列長(zhǎng) N須滿足：須滿足：AMM)(expSHNr)(logSHrNcA22)()(NSPeAPc2222)(NS22)(SN 第五章第五章 編碼定理編碼定理以上為正定理部分的證明。以上為正定理部分的證明。利用表達(dá)式：利用表達(dá)式： 當(dāng)當(dāng) N N時(shí)，由時(shí)，由式得：式得： 0 絕大部分在絕大部分在 中的序列已中的序列已 無對(duì)應(yīng)的碼字，譯碼一定出錯(cuò)無對(duì)應(yīng)的碼字，譯碼一定出錯(cuò)在在N N時(shí)，由時(shí)，由式得式得 1 全部序列幾乎都落入全部序列幾乎都落入 集，且無對(duì)應(yīng)的碼字，故譯集，且無對(duì)應(yīng)的碼字，故譯碼錯(cuò)誤概

10、率趨于碼錯(cuò)誤概率趨于1 1。完成逆定理的證明。完成逆定理的證明。22)(1)exp(NSNMr22)(1)exp(NSNMrA)(AP0)(cAPA 第五章第五章 編碼定理編碼定理 小小 結(jié)結(jié):當(dāng)每個(gè)信源符號(hào)必須輸出的信息率為當(dāng)每個(gè)信源符號(hào)必須輸出的信息率為R（l /N ）log r 時(shí)，只要時(shí)，只要RH(S)，這種編，這種編碼一定可以做到幾乎無失真；碼一定可以做到幾乎無失真；反之，當(dāng)反之，當(dāng)RH(S)時(shí)，不可能構(gòu)成無失真的編時(shí)，不可能構(gòu)成無失真的編碼；碼；RH(S)時(shí)，為臨界狀態(tài)。時(shí)，為臨界狀態(tài)。 第五章第五章 編碼定理編碼定理注意：注意：等長(zhǎng)信源編碼定理是把信源限定為離散無等長(zhǎng)信源編碼定理

11、是把信源限定為離散無記憶和平穩(wěn)的，這些限制條件有的是能解除或減記憶和平穩(wěn)的，這些限制條件有的是能解除或減弱的，而對(duì)于非平穩(wěn)信源，或有記憶信源而言，弱的，而對(duì)于非平穩(wěn)信源，或有記憶信源而言，需再有一些限制，仍可成立。需再有一些限制，仍可成立。對(duì)于連續(xù)信源，由于信息量趨于無限，不能完成對(duì)于連續(xù)信源，由于信息量趨于無限，不能完成無失真編碼，只可進(jìn)行限失真編碼。無失真編碼，只可進(jìn)行限失真編碼。編碼定理使輸出符號(hào)的信息率與信源熵之比接近編碼定理使輸出符號(hào)的信息率與信源熵之比接近1，即：即： 或：或：但必須取無限長(zhǎng)的信源符號(hào)（但必須取無限長(zhǎng)的信源符號(hào)（N）進(jìn)行統(tǒng)一編）進(jìn)行統(tǒng)一編碼才能實(shí)現(xiàn)。碼才能實(shí)現(xiàn)。1l

12、og)(rNSH1)()(SHSH 第五章第五章 編碼定理編碼定理例：已知某信源可以求得H(S)=2.5524比特/符號(hào)及方差若要求編碼效率為90%，即 設(shè)譯碼差錯(cuò)為：信源符號(hào)序列長(zhǎng)度必須滿足：可見，差錯(cuò)率與編碼效率要求并不高時(shí)，必須把108個(gè)符號(hào)一起編碼才可滿足要求，這不便于工程實(shí)現(xiàn)。04. 005. 006. 007. 01 . 01 . 018. 04 . 087654321SSSSSSSSS862226-2101028. 082. 7)(1028. 09 . 0)()(82. 7SNSHSHS可解得）（862226-2101028. 082. 7)(1028. 09 . 0)()(82

13、. 7SNSHSHS可解得）（862226 -2101028. 082. 7)(1028. 09 . 0)()(82. 7SNSHSHS可解得）（862226-2101028. 082. 7)(1028. 09 . 0)()(82. 7SNSHSHS可解得）（ 第五章第五章 編碼定理編碼定理二、變長(zhǎng)碼二、變長(zhǎng)碼編碼原則：編碼原則：出現(xiàn)概率大的符號(hào)用短碼，概率小的符出現(xiàn)概率大的符號(hào)用短碼，概率小的符號(hào)用長(zhǎng)碼，可提高編碼效率。號(hào)用長(zhǎng)碼，可提高編碼效率。問題：?jiǎn)栴}：碼字如何分離。變長(zhǎng)碼必須是唯一可譯碼，碼字如何分離。變長(zhǎng)碼必須是唯一可譯碼，才能實(shí)現(xiàn)無失真編譯碼。才能實(shí)現(xiàn)無失真編譯碼。1、碼字可分離性

14、、碼字可分離性異前置碼（前綴條件碼）：異前置碼（前綴條件碼）：任一碼字的前面任一起任一碼字的前面任一起始部分都不構(gòu)成其它碼字。這是碼字可分離的充分始部分都不構(gòu)成其它碼字。這是碼字可分離的充分條件。譯碼時(shí)無需參考后續(xù)的碼符號(hào)就能立即作出條件。譯碼時(shí)無需參考后續(xù)的碼符號(hào)就能立即作出判斷，譯成對(duì)應(yīng)的信源符號(hào)，則稱為即時(shí)碼。判斷，譯成對(duì)應(yīng)的信源符號(hào)，則稱為即時(shí)碼。 第五章第五章 編碼定理編碼定理2、碼樹、碼樹某節(jié)點(diǎn)被安排為碼字后，不再繼續(xù)某節(jié)點(diǎn)被安排為碼字后，不再繼續(xù)伸枝，稱伸枝，稱終端節(jié)點(diǎn)終端節(jié)點(diǎn)，其它為，其它為中間節(jié)點(diǎn)，中間節(jié)點(diǎn)，中間節(jié)點(diǎn)不安排碼字。中間節(jié)點(diǎn)不安排碼字。3、克拉夫特不等式：、克拉夫

15、特不等式：對(duì)于碼符號(hào)為對(duì)于碼符號(hào)為Xx1，x2，xr的任意即時(shí)碼，的任意即時(shí)碼，其碼字為其碼字為w1，w2， ， wq，所對(duì)應(yīng)的碼長(zhǎng)為，所對(duì)應(yīng)的碼長(zhǎng)為l1，l2， ， lq，則必定滿足克拉夫特不等式；反之，則必定滿足克拉夫特不等式；反之，若碼長(zhǎng)滿足克拉夫特不等式，則一定存在碼長(zhǎng)為若碼長(zhǎng)滿足克拉夫特不等式，則一定存在碼長(zhǎng)為li的即時(shí)碼。的即時(shí)碼。終端終端節(jié)點(diǎn)節(jié)點(diǎn)中間中間節(jié)點(diǎn)節(jié)點(diǎn) 第五章第五章 編碼定理編碼定理 三、離散信源變長(zhǎng)編碼定理三、離散信源變長(zhǎng)編碼定理 1、平均碼長(zhǎng)的概念平均碼長(zhǎng)的概念設(shè)信源：設(shè)信源：編碼后的碼字：編碼后的碼字：對(duì)應(yīng)的碼長(zhǎng)：對(duì)應(yīng)的碼長(zhǎng)：則平均碼長(zhǎng)：則平均碼長(zhǎng)： （碼符號(hào)（碼

16、符號(hào)/每信源符號(hào)）每信源符號(hào)）平均碼長(zhǎng)是每個(gè)信源符號(hào)平均需用的碼元數(shù)平均碼長(zhǎng)是每個(gè)信源符號(hào)平均需用的碼元數(shù)。 第五章第五章 編碼定理編碼定理 平均每個(gè)碼元攜帶的信息量（編碼后所需信道的平均每個(gè)碼元攜帶的信息量（編碼后所需信道的信息傳輸率）：信息傳輸率）： R 若傳輸一個(gè)碼符號(hào)平均需要若傳輸一個(gè)碼符號(hào)平均需要t秒鐘，則編碼后信秒鐘，則編碼后信道每秒鐘傳輸?shù)男畔⒘繛椋旱烂棵腌妭鬏數(shù)男畔⒘繛椋?顯然，平均碼長(zhǎng)越短，則顯然，平均碼長(zhǎng)越短，則Rt越大，信息傳輸效率越大，信息傳輸效率就越高，編碼中使平均碼長(zhǎng)為最短的碼是人們感就越高，編碼中使平均碼長(zhǎng)為最短的碼是人們感興趣的。興趣的。 第五章第五章 編碼定理

17、編碼定理 最佳碼：最佳碼： 凡是能載荷一定的信息量，且碼字的平均凡是能載荷一定的信息量，且碼字的平均長(zhǎng)度最短，可分離的變長(zhǎng)碼的碼字集合稱長(zhǎng)度最短，可分離的變長(zhǎng)碼的碼字集合稱為為最佳碼最佳碼或或緊致碼緊致碼。無失真信源編碼的基本問題就是要找最佳無失真信源編碼的基本問題就是要找最佳碼，變長(zhǎng)碼的編碼定理確定了最佳碼的平碼，變長(zhǎng)碼的編碼定理確定了最佳碼的平均碼長(zhǎng)可能達(dá)到的理論極限。均碼長(zhǎng)可能達(dá)到的理論極限。 第五章第五章 編碼定理編碼定理2 2、按符號(hào)變長(zhǎng)編碼定理、按符號(hào)變長(zhǎng)編碼定理 若一離散無記憶信源的符號(hào)熵為若一離散無記憶信源的符號(hào)熵為H(S)H(S)，每個(gè)信，每個(gè)信源符號(hào)用源符號(hào)用r r元碼元進(jìn)

18、行變長(zhǎng)編碼，則一定存在一元碼元進(jìn)行變長(zhǎng)編碼，則一定存在一種無失真編碼方法，構(gòu)成唯一可譯碼，其平均碼種無失真編碼方法，構(gòu)成唯一可譯碼，其平均碼長(zhǎng)滿足：長(zhǎng)滿足： 以上定理給出了平均碼長(zhǎng)的上、下界，平均碼長(zhǎng)以上定理給出了平均碼長(zhǎng)的上、下界，平均碼長(zhǎng)不能小于下界不能小于下界 否則唯一可譯碼不存在。否則唯一可譯碼不存在。 第五章第五章 編碼定理編碼定理3、無失真變長(zhǎng)信源編碼定理（香農(nóng)第一定理）、無失真變長(zhǎng)信源編碼定理（香農(nóng)第一定理） 對(duì)于平均符號(hào)熵為對(duì)于平均符號(hào)熵為H(S)的離散平穩(wěn)無記憶信源，的離散平穩(wěn)無記憶信源， 必存在一種無失真編碼方法，使平均信息率滿足必存在一種無失真編碼方法，使平均信息率滿足

19、不等式：不等式：H(S) RH(S)，為任意正數(shù)為任意正數(shù) 或平均碼長(zhǎng)滿足：或平均碼長(zhǎng)滿足：對(duì)香農(nóng)第一定理的理解：對(duì)香農(nóng)第一定理的理解：若若RH(S)，就存在唯一可譯變長(zhǎng)編碼；，就存在唯一可譯變長(zhǎng)編碼；若若RH(S)，唯一可譯變長(zhǎng)編碼不存在，不能實(shí)現(xiàn)，唯一可譯變長(zhǎng)編碼不存在，不能實(shí)現(xiàn)無失真的信源編碼。無失真的信源編碼。 第五章第五章 編碼定理編碼定理香農(nóng)第一定理的物理意義：香農(nóng)第一定理的物理意義：無失真信源編碼的實(shí)質(zhì)就是對(duì)離散信源進(jìn)行適當(dāng)無失真信源編碼的實(shí)質(zhì)就是對(duì)離散信源進(jìn)行適當(dāng)?shù)淖儞Q，使變換后新的碼符號(hào)信源（信道的輸入的變換，使變換后新的碼符號(hào)信源（信道的輸入信源）盡可能為等概率分布，以使新

20、信源的每個(gè)信源）盡可能為等概率分布，以使新信源的每個(gè)碼符號(hào)平均所含的信息量達(dá)到最大，從而使信道碼符號(hào)平均所含的信息量達(dá)到最大，從而使信道的信息傳輸率的信息傳輸率R R達(dá)到信道容量達(dá)到信道容量C C，實(shí)現(xiàn)信源與信道，實(shí)現(xiàn)信源與信道理想的統(tǒng)計(jì)匹配。理想的統(tǒng)計(jì)匹配。定義變長(zhǎng)碼的編碼效率為：定義變長(zhǎng)碼的編碼效率為： 第五章第五章 編碼定理編碼定理5.3 幾種信源編碼方法幾種信源編碼方法一、信源編碼種類歸納一、信源編碼種類歸納1、熵保持編碼（匹配編碼，平均信息量法）、熵保持編碼（匹配編碼，平均信息量法）特點(diǎn)：特點(diǎn)：在編碼過程中，不允許丟失任何信息。根據(jù)符在編碼過程中，不允許丟失任何信息。根據(jù)符號(hào)的概率分

21、布，分別對(duì)應(yīng)長(zhǎng)短不同的代碼。號(hào)的概率分布，分別對(duì)應(yīng)長(zhǎng)短不同的代碼。如香農(nóng)編碼法、費(fèi)諾編碼法、霍夫曼編碼法等如香農(nóng)編碼法、費(fèi)諾編碼法、霍夫曼編碼法等2、預(yù)測(cè)編碼、預(yù)測(cè)編碼特點(diǎn)：特點(diǎn)：編碼和傳輸?shù)牟皇遣蓸又当旧?，而是采樣值的編碼和傳輸?shù)牟皇遣蓸又当旧?，而是采樣值的預(yù)測(cè)值與實(shí)際值之間的差值。預(yù)測(cè)值與實(shí)際值之間的差值。如差值脈沖編碼調(diào)制法（如差值脈沖編碼調(diào)制法（DPCM） 第五章第五章 編碼定理編碼定理 3 3、變換編碼、變換編碼特點(diǎn)：將原來的信號(hào)空間變換為另外一個(gè)空間。特點(diǎn)：將原來的信號(hào)空間變換為另外一個(gè)空間。如如FourierFourier（傅里葉）變換、（傅里葉）變換、HaarHaar（哈爾）變

22、換、（哈爾）變換、 Walsh-HadamardWalsh-Hadamard（阿達(dá)瑪）變換（簡(jiǎn)稱（阿達(dá)瑪）變換（簡(jiǎn)稱DWHTDWHT）、）、SlantSlant變換、變換、CosineCosine變換、變換、SineSine變換、變換、 HotellingHotelling變換等變換等4 4、識(shí)別編碼、識(shí)別編碼特點(diǎn)：關(guān)聯(lián)識(shí)別（與樣本比較識(shí)別），邏輯識(shí)別特點(diǎn)：關(guān)聯(lián)識(shí)別（與樣本比較識(shí)別），邏輯識(shí)別（利用邏輯表達(dá)式判斷識(shí)別）。（利用邏輯表達(dá)式判斷識(shí)別）。 第五章第五章 編碼定理編碼定理二、霍夫曼編碼方法二、霍夫曼編碼方法1 1、二元霍夫曼編碼步驟：、二元霍夫曼編碼步驟：把一個(gè)信源符號(hào)的幾種字母按概率

23、大小的次序排把一個(gè)信源符號(hào)的幾種字母按概率大小的次序排列好；列好；取二個(gè)概率最小的字母分配以取二個(gè)概率最小的字母分配以“0”0”和和“1”1”，并，并把這二個(gè)概率相加作為一個(gè)新字母的概率重新與把這二個(gè)概率相加作為一個(gè)新字母的概率重新與未分配的二進(jìn)符號(hào)的字母排隊(duì)；未分配的二進(jìn)符號(hào)的字母排隊(duì)；重新排隊(duì)后，再取二個(gè)概率最小的字母分別配以重新排隊(duì)后，再取二個(gè)概率最小的字母分別配以“0”0”和和“1”1”，再把這二個(gè)概率相加作為一個(gè)新，再把這二個(gè)概率相加作為一個(gè)新的字母的概率；的字母的概率； 第五章第五章 編碼定理編碼定理重復(fù)重復(fù)，直到概率之和為，直到概率之和為1；倒回寫出相應(yīng)碼字。（舉例）倒回寫出相應(yīng)

24、碼字。（舉例）2、r元霍夫曼編碼元霍夫曼編碼規(guī)則：規(guī)則：由二元霍夫曼編碼推廣而來，每次把由二元霍夫曼編碼推廣而來，每次把r個(gè)概個(gè)概率最小的符號(hào)合并成一個(gè)新的信源符號(hào)，并分別率最小的符號(hào)合并成一個(gè)新的信源符號(hào)，并分別用碼元用碼元0，1，（，（r 1）表示。為使平均碼長(zhǎng)）表示。為使平均碼長(zhǎng)最短，必須使最后一步的縮減信源有最短，必須使最后一步的縮減信源有r個(gè)信源符個(gè)信源符號(hào)。即信源符號(hào)個(gè)數(shù)號(hào)。即信源符號(hào)個(gè)數(shù)q必須滿足：必須滿足： 第五章第五章 編碼定理編碼定理注意：若注意：若q不滿足上式，可虛設(shè)不滿足上式，可虛設(shè)t個(gè)出現(xiàn)概率為個(gè)出現(xiàn)概率為0的信源符號(hào)，使的信源符號(hào)，使qt滿足表達(dá)式，得到滿足表達(dá)式，

25、得到r元霍元霍夫曼碼一定也是最佳碼（緊致碼）。夫曼碼一定也是最佳碼（緊致碼）。例：信源符號(hào)概率分布如下，實(shí)現(xiàn)四元霍夫曼例：信源符號(hào)概率分布如下，實(shí)現(xiàn)四元霍夫曼編碼：編碼：S1 S2 S3 S4 S5 S6 S7 S80.22 0.2 0.18 0.15 0.1 0.08 0.05 0.02 第五章第五章 編碼定理編碼定理二、費(fèi)諾（二、費(fèi)諾（Fano）編碼步驟）編碼步驟先把消息按概率大小順序排列；先把消息按概率大小順序排列；將概率序列分成兩組，使兩組的概率盡可能接近將概率序列分成兩組，使兩組的概率盡可能接近或相等，兩組消息分別以或相等，兩組消息分別以“0”和和“1”表示；表示；再對(duì)每組符號(hào)又分成

26、兩組，也使兩組的概率盡可再對(duì)每組符號(hào)又分成兩組，也使兩組的概率盡可能接近或相等，兩組消息分別以能接近或相等，兩組消息分別以“0”和和“1”表示；表示；重復(fù)重復(fù)，直至每個(gè)消息被分隔出來為止；，直至每個(gè)消息被分隔出來為止；將二進(jìn)數(shù)字順序?qū)懗龅玫较鄳?yīng)消息的碼字。將二進(jìn)數(shù)字順序?qū)懗龅玫较鄳?yīng)消息的碼字。 第五章第五章 編碼定理編碼定理例：信源消息如下，實(shí)現(xiàn)費(fèi)諾編碼：例：信源消息如下，實(shí)現(xiàn)費(fèi)諾編碼：S1 S2 S3 S4 S5 S60.25 0.25 0.2 0.15 0.1 0.05 第五章第五章 編碼定理編碼定理5.4 5.4 限失真信源編碼定理（香農(nóng)第三定理）限失真信源編碼定理（香農(nóng)第三定理）定理具

27、體描述（定理具體描述（P311定理定理7.1）限失真編碼定理說明：當(dāng)傳輸速率限失真編碼定理說明：當(dāng)傳輸速率RR(D)時(shí)，只要時(shí)，只要碼長(zhǎng)足夠長(zhǎng)，就一定存在一種編碼方法，使平均失真碼長(zhǎng)足夠長(zhǎng)，就一定存在一種編碼方法，使平均失真任意接近于任意接近于D，否則這種編碼不存在。，否則這種編碼不存在。注意：不同的編碼，將有不同的平均失真，希望找到注意：不同的編碼，將有不同的平均失真，希望找到平均失真最小的編碼，即最佳編碼。平均失真最小的編碼，即最佳編碼。 第五章第五章 編碼定理編碼定理小結(jié)：小結(jié)：比較香農(nóng)第一和第三定理可知，當(dāng)信源給定后，無比較香農(nóng)第一和第三定理可知，當(dāng)信源給定后，無失真信源壓縮的極限值是

28、信源熵失真信源壓縮的極限值是信源熵H(S)，而有失真信，而有失真信源壓縮的極限值是信息率失真函數(shù)源壓縮的極限值是信息率失真函數(shù)R(D) ，在給定，在給定失真值失真值D后，一般后，一般R(D) H(S)。存在的問題：存在的問題：1）符合實(shí)際信源的）符合實(shí)際信源的R(D)函數(shù)的計(jì)算相當(dāng)困難；函數(shù)的計(jì)算相當(dāng)困難；2）采用何種實(shí)用的最佳編碼方法才能達(dá)到）采用何種實(shí)用的最佳編碼方法才能達(dá)到R(D)？ 第五章第五章 編碼定理編碼定理5.5 5.5 有噪信道編碼有噪信道編碼一、信道編碼概念一、信道編碼概念信道編碼是為了保證信息傳輸?shù)目煽啃?，使信源與信道編碼是為了保證信息傳輸?shù)目煽啃裕剐旁磁c信道特性相匹配，

29、且傳輸中的差錯(cuò)為任意小，提高信道特性相匹配，且傳輸中的差錯(cuò)為任意小，提高傳輸質(zhì)量而設(shè)計(jì)的一種編碼。傳輸質(zhì)量而設(shè)計(jì)的一種編碼。信道編碼是在信息碼中增加一定數(shù)量的多余碼元，信道編碼是在信息碼中增加一定數(shù)量的多余碼元，在編碼效率一定的條件下，提高檢糾錯(cuò)能力，使碼在編碼效率一定的條件下，提高檢糾錯(cuò)能力，使碼字具有一定的抗干擾能力，故又稱為抗干擾編碼。字具有一定的抗干擾能力，故又稱為抗干擾編碼。 第五章第五章 編碼定理編碼定理定義編碼效率為：定義編碼效率為：R RK/nK/n其中其中K K位信息，經(jīng)編碼得到長(zhǎng)為位信息，經(jīng)編碼得到長(zhǎng)為n n（n nK K）的碼字，）的碼字，增加了增加了n nK Kr r位

30、多余碼元。位多余碼元。因此，信道編碼以降低信息傳輸效率為代價(jià)，來增因此，信道編碼以降低信息傳輸效率為代價(jià)，來增加碼字的抗干擾能力。加碼字的抗干擾能力。檢錯(cuò)碼：檢錯(cuò)碼：收端收到碼字后，通過檢驗(yàn)收到碼字是否收端收到碼字后，通過檢驗(yàn)收到碼字是否滿足預(yù)先約定的約束關(guān)系而發(fā)現(xiàn)錯(cuò)誤。滿足預(yù)先約定的約束關(guān)系而發(fā)現(xiàn)錯(cuò)誤。糾錯(cuò)碼：糾錯(cuò)碼：收到碼字后，不僅能判斷是否有錯(cuò)，而且收到碼字后，不僅能判斷是否有錯(cuò)，而且可通過譯碼器直接糾錯(cuò)，得到正確碼字。可通過譯碼器直接糾錯(cuò)，得到正確碼字。 第五章第五章 編碼定理編碼定理例：例： 反復(fù)傳送可以提高通信的可靠性。反復(fù)傳送可以提高通信的可靠性。二、有噪信道編碼定理（香農(nóng)第二定

31、理）二、有噪信道編碼定理（香農(nóng)第二定理）已知某離散無記憶平穩(wěn)信道的信道容量為已知某離散無記憶平穩(wěn)信道的信道容量為C，只要，只要待傳送的信息率待傳送的信息率RC，總可以在輸入，總可以在輸入Xn符號(hào)集中找符號(hào)集中找到到M（2nR）個(gè)碼字組成的一組碼（一種碼長(zhǎng)為）個(gè)碼字組成的一組碼（一種碼長(zhǎng)為n的的編碼）和相應(yīng)的譯碼規(guī)則，當(dāng)碼長(zhǎng)編碼）和相應(yīng)的譯碼規(guī)則，當(dāng)碼長(zhǎng)n足夠長(zhǎng)時(shí)，譯碼足夠長(zhǎng)時(shí)，譯碼錯(cuò)誤概率錯(cuò)誤概率PE ， 為任意正數(shù)；為任意正數(shù)；反之，當(dāng)反之，當(dāng)RC時(shí)，譯碼錯(cuò)誤概率任意小的碼不存在，時(shí)，譯碼錯(cuò)誤概率任意小的碼不存在，而當(dāng)而當(dāng)n時(shí)，時(shí)，PE1。 第五章第五章 編碼定理編碼定理三、譯碼錯(cuò)誤概率和譯

32、碼規(guī)則三、譯碼錯(cuò)誤概率和譯碼規(guī)則問題：當(dāng)碼長(zhǎng)問題：當(dāng)碼長(zhǎng)n為有限值時(shí)，譯碼錯(cuò)誤概率情況怎樣？為有限值時(shí)，譯碼錯(cuò)誤概率情況怎樣？可靠性函數(shù)：可靠性函數(shù)：表示在表示在n為有限值時(shí)，差錯(cuò)概率的上界；為有限值時(shí)，差錯(cuò)概率的上界；同時(shí)也表示同時(shí)也表示 n時(shí)，時(shí)， PE0的速率?？煽啃院瘮?shù)可幫的速率?？煽啃院瘮?shù)可幫助我們選擇信息率助我們選擇信息率R和編碼長(zhǎng)度和編碼長(zhǎng)度n。注意：注意：錯(cuò)誤概率不僅與信道的統(tǒng)計(jì)特性有關(guān)，也與譯錯(cuò)誤概率不僅與信道的統(tǒng)計(jì)特性有關(guān)，也與譯碼規(guī)則有關(guān)。碼規(guī)則有關(guān)。最佳判斷法則是最大似然譯碼法則最佳判斷法則是最大似然譯碼法則 第五章第五章 編碼定理編碼定理設(shè)：信道輸入符號(hào)集為設(shè)：信道輸入符號(hào)集為A a1,a2, ,ai, ar 信道輸出符號(hào)集為信道輸出符號(hào)集為B b1,b2, ,bj, bs譯碼就是收到譯碼就是收到bj后，判斷發(fā)送的是哪一個(gè)后，判斷發(fā)送的是哪一個(gè)ai制定譯碼規(guī)則就是設(shè)計(jì)一個(gè)函數(shù)制定譯碼規(guī)則就是設(shè)計(jì)一個(gè)函數(shù)F(bj)，即：，