第五章無(wú)失真信源編碼定理

第五章無(wú)失真信源編碼定理5.1編碼器5.2等長(zhǎng)碼5.3*漸進(jìn)等分割性和典型序列5.5變長(zhǎng)碼5.4等長(zhǎng)信源編碼定理5.6變長(zhǎng)信源編碼定理1、信源編碼的目的

——在不失真或允許一定失真條件下，如何用盡可能少的符號(hào)來(lái)傳送信源信息，以便提高信息傳輸率。2、信道編碼的目的

——在信道受干擾的情況下，如何增加信號(hào)的抗干擾能力，同時(shí)又使得信息傳輸率最大。5.1編碼器5.1.1編碼器的構(gòu)成5.1.2有關(guān)常用碼的概念5.1.1編碼器的構(gòu)成編碼器S:信源符號(hào)碼符號(hào)，或碼元編碼實(shí)質(zhì)上是對(duì)信源的原始符號(hào)按一定的數(shù)學(xué)規(guī)則進(jìn)行的一種變換。碼字長(zhǎng)度或碼長(zhǎng)C碼字(信源符號(hào))(信源序列)碼字由碼元組成碼C由碼字組成編碼就是從信源符號(hào)到碼字的一種映射，一一對(duì)應(yīng)，可逆，則可實(shí)現(xiàn)無(wú)失真編碼。5.1.2有關(guān)常用碼的概念1、二元碼碼符號(hào)集為，所得碼字是二元序列。2、等長(zhǎng)碼一組碼中所有碼字的碼長(zhǎng)都相同。3、變長(zhǎng)碼一組碼中所有碼字的碼長(zhǎng)各不相同。4、非奇異碼C一組碼中所有碼字都不相同。即5、奇異碼C一組碼中有相同的碼字。即6、同價(jià)碼碼符號(hào)集中每個(gè)碼符號(hào)所占的傳輸時(shí)間都相同。一般二元碼是同價(jià)碼。對(duì)于同價(jià)碼，等長(zhǎng)碼中每個(gè)碼字的傳輸時(shí)間都相同，變長(zhǎng)碼每個(gè)碼字的傳輸時(shí)間就不一定相同。7、碼的N次擴(kuò)展碼N次擴(kuò)展信源對(duì)應(yīng)的N個(gè)碼字組成的碼字序列的集合。N次擴(kuò)展碼

B舉例信源符號(hào)的碼和二次擴(kuò)展碼的形式信源符號(hào)si符號(hào)概率P(si)碼1碼2s1P(s1)000s2P(s2)0101s3P(s3)10001s4P(s4)11111表5.1等長(zhǎng)碼變長(zhǎng)碼非奇異碼表5.2碼2的二次擴(kuò)展碼信源符號(hào)擴(kuò)展碼字信源符號(hào)擴(kuò)展碼字信源S的二次擴(kuò)展信源信源S的二次擴(kuò)展碼8、唯一可譯碼碼的任意一串有限長(zhǎng)的碼符號(hào)序列只能被唯一地譯成所對(duì)應(yīng)的信源符號(hào)序列，則此碼稱(chēng)唯一可譯碼或單譯可譯碼。(1)信源符號(hào)對(duì)應(yīng)的碼是非奇異碼。(2)任意有限長(zhǎng)的N次擴(kuò)展碼是非奇異的。例：碼符號(hào)序列“0010”“0010”5.2等長(zhǎng)碼5.2.1等長(zhǎng)碼的唯一可譯性5.2.2等長(zhǎng)碼的編碼長(zhǎng)度5.2.1等長(zhǎng)碼的唯一可譯性若等長(zhǎng)碼是非奇異碼，則它的任意有限長(zhǎng)N次擴(kuò)展碼一定也是非奇異碼，因此一定是唯一可譯碼。信源符號(hào)si符號(hào)概率P(si)碼1碼2s1P(s1)0000s2P(s2)0111s3P(s3)1010s4P(s4)1111表5.3唯一可譯碼非唯一可譯碼5.2.2等長(zhǎng)碼的編碼長(zhǎng)度1、q個(gè)信源符號(hào)：碼元數(shù)為r：則碼長(zhǎng)必須滿(mǎn)足下式例:(1)(2)（表4.2）必要條件

個(gè)信源符號(hào)：可得到等長(zhǎng)非奇異碼取對(duì)數(shù)：當(dāng)N=1時(shí)是平均每個(gè)信源符號(hào)所需要的碼符號(hào)個(gè)數(shù)2、對(duì)N次擴(kuò)展信源編碼3、等長(zhǎng)碼的碼長(zhǎng)仍可壓縮考慮符號(hào)出現(xiàn)的概率和符號(hào)間的依賴(lài)關(guān)系，碼長(zhǎng)可壓縮。例：其余且二次擴(kuò)展信源

有個(gè)符號(hào),

壓縮至4個(gè)符號(hào),編碼即可.結(jié)論:考慮信源符號(hào)間的依賴(lài)關(guān)系后,

再考慮符號(hào)出現(xiàn)的概率時(shí),所需平均碼長(zhǎng)可能縮短.5.3*漸進(jìn)等分割性和典型序列對(duì)于離散無(wú)記憶信源

N次擴(kuò)展信源當(dāng)為有限值時(shí),弱大數(shù)定律對(duì)于獨(dú)立、等同分布的隨機(jī)變量，只要n

足夠大時(shí)，接近其數(shù)學(xué)期望E[X]。定理5.1

漸進(jìn)等分割性(AEP):

若隨機(jī)序列中相互統(tǒng)計(jì)獨(dú)立并且服從同一概率分布,又，則依概率收斂于。

可表示成,對(duì)于任意弱大數(shù)定律:此漸近等分割性說(shuō)明,離散無(wú)記憶信源的N次擴(kuò)展信源中,信源序列的自信息的均值，依概率收斂于信源熵。當(dāng)N為有限長(zhǎng)時(shí),在所有個(gè)長(zhǎng)為N的信源序列中必有一些,其自信息量的均值與信源熵之差小于,即:或稱(chēng)N長(zhǎng)序列為典型序列.中所有典型序列的集合表示為非典型序列集(2)若，則(3)設(shè)表示典型序列集中包含的典型序列的個(gè)數(shù)，定理5.2:對(duì)于任意小的正數(shù)當(dāng)N足夠大時(shí)，則(1)而顯然證明:(1)可由定理5.1直接推得當(dāng)時(shí)，契比雪夫不等式當(dāng)依概率收斂于(2)可由變形證得。推論：當(dāng)N足夠大時(shí)，可任意小，表明典型序列出現(xiàn)的概率近似相等，所以稱(chēng)為漸進(jìn)等概率序列。(3)由上述性質(zhì)(2)證得。性質(zhì)(1)表明，典型序列是經(jīng)常出現(xiàn)的信源序列。時(shí)，成為必然事件。性質(zhì)(2)表明接近等概分布性質(zhì)(3)表明當(dāng)時(shí),

典型序列的總數(shù)占信源序列的比值為：一般所以，當(dāng)

是高概率集，它含有序列數(shù)常常比非典型序列數(shù)要少很多。所有信源序列非典型序列集

典型序列集結(jié)論：只對(duì)少數(shù)的高概率典型序列進(jìn)行一一對(duì)應(yīng)的等長(zhǎng)編碼。碼字總數(shù)減少，所需碼長(zhǎng)就可以減小了。AEP結(jié)論：當(dāng)N足夠大時(shí)

所有典型序列出現(xiàn)的概率近似相等.2.可粗略認(rèn)為典型序列出現(xiàn)的概率為3.所有典型序列的概率和接近為1,5.4等長(zhǎng)信源編碼定理5.4.1等長(zhǎng)信源編碼定理5.4.2平穩(wěn)有記憶信源的碼長(zhǎng)5.4.3對(duì)于編碼好壞的評(píng)價(jià)5.4.1等長(zhǎng)信源編碼定理—

定理5.31、定理內(nèi)容：一個(gè)離散無(wú)記憶信源，熵為，信源長(zhǎng)為N，碼符號(hào)r個(gè)，碼字長(zhǎng)，對(duì)于任意，只要滿(mǎn)足則當(dāng)N足夠大時(shí)，可實(shí)現(xiàn)幾乎無(wú)失真編碼。譯碼錯(cuò)誤概率為任意小。

若則不能實(shí)現(xiàn)無(wú)失真編碼，而當(dāng)N足夠大時(shí)，譯碼錯(cuò)誤概率近似等于1。

比較公式:

一般，當(dāng)信源符號(hào)有依賴(lài)時(shí)，，所以得到壓縮2、證明：(1)

整理

錯(cuò)誤概率設(shè)(3)當(dāng)二元編碼時(shí)，定理5.3為等長(zhǎng)編碼時(shí)平均每個(gè)信源符號(hào)所需要的二元碼符號(hào)的極限值是H(s)。(2)

選取的碼字總數(shù)小于集中可能有的信源序列數(shù)，譯碼時(shí)定會(huì)產(chǎn)生錯(cuò)誤。當(dāng)N很長(zhǎng)時(shí)，5.4.2平穩(wěn)有記憶信源的碼長(zhǎng)對(duì)平穩(wěn)有記憶信源：用替代定理5.3中的H(s)

無(wú)失真編碼不能實(shí)現(xiàn)無(wú)失真編碼5.4.3編碼的評(píng)價(jià)定理5.3

式(1)表示長(zhǎng)為的碼符號(hào)載荷的最大信息量大于信源序列攜帶的信息量時(shí),可實(shí)現(xiàn)幾乎無(wú)失真編碼.

式(2)令

稱(chēng)編碼信息率,表示編碼后平均每個(gè)信源符號(hào)能載荷的最大信息量.只有編碼信息率大于信源的熵,才能實(shí)現(xiàn)幾乎無(wú)失真編碼.編碼效率編碼效率用來(lái)衡量編碼效果等長(zhǎng)編碼的最佳效率得

表示編碼前后平均每個(gè)信源符號(hào)能載荷的最大信息率之比。即在已知方差和信源熵的條件下,容許錯(cuò)誤概率愈小,編碼效率愈高,則信源序列長(zhǎng)度N必須愈長(zhǎng).在實(shí)際情況下,要實(shí)現(xiàn)幾乎無(wú)失真的等長(zhǎng)編碼,N要大到難以實(shí)現(xiàn)的程度.已知當(dāng)允許錯(cuò)誤概率小于時(shí)代入采用二元編碼，要求編碼效率，允許錯(cuò)誤概率，求編碼長(zhǎng)度？解:例5.1

已知離散無(wú)記憶信源當(dāng)N取4120萬(wàn)以上時(shí)，才能按要求實(shí)現(xiàn)幾乎無(wú)失真編碼。因此N有限的等長(zhǎng)碼往往引入一定的失真和錯(cuò)誤。5.5變長(zhǎng)碼5.5.1唯一可譯變長(zhǎng)碼與即時(shí)碼5.5.2即時(shí)碼的樹(shù)圖構(gòu)造法5.5.3克拉夫特（kraft）不等式5.5.4唯一可譯變長(zhǎng)碼的判別法1、唯一可譯碼5.5.1唯一可譯變長(zhǎng)碼與即時(shí)碼信源si概率P(si)碼1碼2碼3碼4s11/20011s21/411101001s31/80000100001s41/8110110000001表5.4奇異碼非唯一可譯碼非即時(shí)碼即時(shí)碼（1）在唯一可譯變長(zhǎng)碼中，譯碼時(shí)無(wú)需參考后續(xù)的碼符號(hào)就能立即作出判斷，譯成對(duì)應(yīng)的信源符號(hào)，這類(lèi)碼稱(chēng)為即時(shí)碼

結(jié)構(gòu)特點(diǎn)：

即時(shí)碼：碼字不是其它碼的前綴或延長(zhǎng)

非即時(shí)碼：某些碼字是其它碼的前綴或延長(zhǎng)。2、即時(shí)碼（2）在譯碼過(guò)程中，當(dāng)收到一個(gè)完整的碼符號(hào)序列時(shí)，無(wú)需等待下一個(gè)符號(hào)到達(dá)后作判斷，而能直接譯成對(duì)應(yīng)的信源符號(hào)。3、碼的分類(lèi)及關(guān)系奇異碼非奇異碼唯一可譯碼即時(shí)碼所有碼5.5.2即時(shí)碼的樹(shù)圖構(gòu)造法1、碼樹(shù)的構(gòu)造過(guò)程（1）根：從根出發(fā)伸出樹(shù)枝，樹(shù)枝的數(shù)目等于碼符號(hào)的總數(shù)r（2）節(jié)點(diǎn)：樹(shù)枝的盡頭為節(jié)點(diǎn)。從節(jié)點(diǎn)出發(fā)再伸出樹(shù)枝，每次每個(gè)節(jié)點(diǎn)伸出r枝，依次下去構(gòu)成一棵樹(shù)。（3）終端節(jié)點(diǎn)：被安排為碼字的節(jié)點(diǎn),它不再繼續(xù)伸枝，用粗黑點(diǎn)表示。（4）中間節(jié)點(diǎn)：沒(méi)被安排為碼字繼續(xù)伸出枝的節(jié)點(diǎn)，用空心圓表示。（5）碼字：由從根出發(fā)到終端節(jié)點(diǎn)走過(guò)的路徑所對(duì)應(yīng)的碼符號(hào)組成。按樹(shù)圖法構(gòu)成的碼一定滿(mǎn)足即時(shí)碼的要求。（2）當(dāng)碼字長(zhǎng)度給定，即時(shí)碼不是唯一的（4）碼樹(shù)圖可用來(lái)譯碼從根—中間節(jié)點(diǎn)—終端節(jié)點(diǎn)2、碼字與樹(shù)圖的聯(lián)系（1）當(dāng)?shù)陔A的節(jié)點(diǎn)作為終端節(jié)點(diǎn)，相應(yīng)碼字的碼長(zhǎng)為。（3）當(dāng)元節(jié)的碼樹(shù)的所有樹(shù)枝都被用上時(shí)，第階節(jié)點(diǎn)共有個(gè)終端節(jié)點(diǎn)—對(duì)應(yīng)于長(zhǎng)的等長(zhǎng)編碼—等長(zhǎng)碼也是即時(shí)碼的一種。碼3的碼樹(shù)

r=2,r=3

的三階節(jié)點(diǎn)樹(shù)圖畫(huà)出碼4的樹(shù)圖碼4的另一種樹(shù)圖小結(jié)：將變長(zhǎng)碼與碼樹(shù)建立“一一對(duì)應(yīng)”關(guān)系：樹(shù)根碼字起點(diǎn)樹(shù)枝數(shù)碼的進(jìn)制數(shù)節(jié)點(diǎn)碼字或碼字的一部分終止節(jié)點(diǎn)碼字節(jié)數(shù)碼長(zhǎng)非滿(mǎn)樹(shù)變長(zhǎng)碼滿(mǎn)樹(shù)等長(zhǎng)碼

5.5.3克拉夫特（kraft）不等式1、定理5.4對(duì)于碼符號(hào)為任意即時(shí)碼(非延長(zhǎng)碼)，其碼字為，所對(duì)應(yīng)的碼長(zhǎng)為，則必定滿(mǎn)足反之，若碼長(zhǎng)滿(mǎn)足上面不等式，則一定存在具有這樣碼長(zhǎng)的即時(shí)碼。證明：充分性(1)r元樹(shù)，第N階的總枝數(shù)枝(2)第階節(jié)點(diǎn)作為碼字，使第N

階減少的枝數(shù)(3)第階的碼長(zhǎng)(4)個(gè)碼字使第N階減少的樹(shù)枝數(shù)證得Kraft不等式的物理意義：給定信源符號(hào)數(shù)q和碼符號(hào)數(shù)r，只要允許碼字長(zhǎng)度可以足夠長(zhǎng)，就總可以滿(mǎn)足Kraft不等式，從而得到即時(shí)碼。2、定理5.5

將定理5.4中的即時(shí)碼改為唯一可譯碼，其余不變。推論:(1)當(dāng)碼長(zhǎng)滿(mǎn)足kraft不等式時(shí)，不一定是唯一可譯碼。(2)但一定存在至少一種碼長(zhǎng)相同的唯一可譯碼。不一定是即時(shí)碼。(3)也一定能找到至少一種相同碼長(zhǎng)的即時(shí)碼。5.5.4唯一可譯變長(zhǎng)碼的判別法1、樹(shù)圖判別即時(shí)碼2、尾隨后綴法由A.A.Sardinas和G.W.Patterson1957年提出A1A2A3Am…B1B2B3Bn…5.5.4唯一可譯變長(zhǎng)碼的判別法2、尾隨后綴法步驟：(1)F1是C中所有碼字尾隨后綴的集合;(2)考察C和Fi兩個(gè)集合,如果C中任一碼字是Fi中元素的前綴,或者Fi中任一元素是C中碼字的前綴,則將其相應(yīng)的尾隨后綴放入集合Fi+1;(3)(4)一旦F中出現(xiàn)了C中的元素,則算法終止,C不是唯一可譯碼;若出現(xiàn)Fi+1為空集或Fi+1中的元素在F中已經(jīng)全部存在,算法終止,C是唯一可譯碼.5.5.4唯一可譯變長(zhǎng)碼的判別法解:

例設(shè)消息集合共有7個(gè)元素,判斷其編碼的唯一可譯性.siCF1F2F3F4F5s1as2cs3adds4abbbbs5badads6debebbs7bbcdecdedebcde非唯一可譯碼!5.6變長(zhǎng)信源編碼定理5.6.2離散無(wú)記憶信源的唯一可譯碼長(zhǎng)的理論極限5.6.1平均碼長(zhǎng)5.6.3離散無(wú)記憶N次擴(kuò)展信源編碼的平均碼長(zhǎng)理論極限5.6.1平均碼長(zhǎng)對(duì)應(yīng)碼長(zhǎng)為，而1、平均碼長(zhǎng)單位是：碼符號(hào)/信源符號(hào)2、每個(gè)碼元攜帶的信息量H(X)每個(gè)信源符號(hào)攜帶的信息量H(S)3、編碼后信道的信息傳輸率顯然，越短，越大，信息傳輸效率越高4、最佳碼—或緊致碼平均長(zhǎng)度最小的唯一可譯碼。5.6.2離散無(wú)記憶信源的唯一可譯碼長(zhǎng)的理論極限定理5.7

信源S熵為H(S),r個(gè)碼元可以找到一種唯一可譯碼，使碼長(zhǎng)滿(mǎn)足且的理論下限是，獲得條件向上取整得香農(nóng)碼長(zhǎng)！

定理5.7表達(dá)式定理5.7可表示成5.6.3離散無(wú)記憶N次擴(kuò)展信源編碼的平均碼長(zhǎng)理論極限定理5.8—香農(nóng)第一定理

—無(wú)失真變長(zhǎng)信源編碼定理信源的熵為，r個(gè)碼元，可構(gòu)成唯一可譯碼，使信源S中每個(gè)信源符號(hào)所需的平均碼長(zhǎng)滿(mǎn)足或

且式中

是對(duì)應(yīng)的碼字長(zhǎng)度證明：定理指出，要做到無(wú)失真信源編碼，編碼每個(gè)信源符號(hào)所需要的碼元數(shù)就是信源的熵(以r為底)。當(dāng)擴(kuò)展次數(shù)時(shí)，平均碼長(zhǎng)