第7講-離散無記憶信源等長編碼

離散無記憶信源

等長編碼第七講信源編碼基本概念字母表信源輸出序列消息集碼字集集合碼字序列等長碼不等長碼D元碼唯一可譯碼信源符號

信源符號出現(xiàn)概率

碼表碼0碼1碼2碼3碼4a1p(a1)=1/2000011a2p(a2)=1/40111101001a3p(a3)=1/8100000100001a4p(a4)=1/811110110000001信源編碼基本概念信源編碼器碼表信源信道XYL長序列N長碼字無失真等長編碼英文電報(bào)27個(gè)符號,K=27,L=1,D=2(二元編碼)每個(gè)英文電報(bào)符號至少要用5位二元符號編碼

實(shí)際英文電報(bào)符號信源，在考慮了符號出現(xiàn)的概率以及符號之間的依賴性后，平均每個(gè)英文電報(bào)符號所提供的信息量約等于1.4比特，即編碼后5個(gè)二元符號只攜帶約1.4比特的信息量，遠(yuǎn)小于5比特(最大熵)，可見編碼后的信息傳輸效率極低。實(shí)例信源編碼器碼表信源信道XYL長序列N長碼字無失真等長編碼幾乎無失真編碼幾乎無失真等長編碼選擇L足夠長，使其中，為與L有關(guān)的正數(shù)，且當(dāng)時(shí)有,才能不損失信息。然而這樣的編碼不總能保證單義可譯，但非單義可譯所引起的錯(cuò)誤可漸近為任意小。反之，若，編碼誤差變得任意大。令信源的熵為，的方差為，則的均值為方差為由契比雪夫大數(shù)定理，對于可選，這可以通過適當(dāng)選擇L來實(shí)現(xiàn)，上式可以寫成即當(dāng)L足夠大時(shí)，將以概率1取值為H(U)。典型序列令H(U)是集的熵，定義為給定信源U輸出長為L的典型序列集，又可稱作弱ε典型序列集；的補(bǔ)集為非典型序列集。令H(U)是集的熵，定義為給定信源U輸出長為L的典型序列集，其中，是L序列中出現(xiàn)的次數(shù)，又稱之為強(qiáng)典型序列集。相應(yīng)信源劃分定理定理：給定信源和，當(dāng)時(shí)，由契比雪夫大數(shù)定理，對于可選，這可以通過適當(dāng)選擇L來實(shí)現(xiàn)，上式可以寫成即當(dāng)L足夠大時(shí)，將以概率1取值為H(U)。信源劃分定理定理：給定信源和，當(dāng)時(shí)，對于任意小，存在有正整數(shù)，使得當(dāng)時(shí)，有由契比雪夫大數(shù)定理，對于可選，這可以通過適當(dāng)選擇L來實(shí)現(xiàn)，上式可以寫成即當(dāng)L足夠大時(shí)，將以概率1取值為H(U)。，則證明：從典型序列定義式有即等式兩邊各項(xiàng)取指數(shù)，即得證。若推論1(特定序列出現(xiàn)的概率)即推論2(典型序列數(shù)目)當(dāng)L足夠大時(shí)，對于給定的信源的個(gè)數(shù)滿足證明：即由有即和,典型序列即理解典型序列一個(gè)離散無記憶信源輸出的消息序列可以分為兩組，各序列出現(xiàn)的概率近于相等；每個(gè)序列平均符號的信息量接近于信源熵H(U)；所有典型序列的概率和趨近于1。

個(gè)別非典型序列的概率不一定比個(gè)別典型序列的概率低。

雖然非典型序列集中序列的總概率很小，但是元素?cái)?shù)目不一定小。理解典型序列

個(gè)別非典型序列的概率不一定比個(gè)別典型序列的概率低。

雖然非典型序列集中序列的總概率很小，但是元素?cái)?shù)目不一定小。擲硬幣試驗(yàn)：正面出現(xiàn)概率p，反面出現(xiàn)概率1-p典型序列非典型序列（全反）離散無記憶信源編碼模型無錯(cuò)有錯(cuò)錯(cuò)誤概率編碼速率可達(dá)對于給定的信源和編碼速率R以及任意若存在有使當(dāng)碼長時(shí)就稱R是可達(dá)的，否則稱此R不可達(dá)。無擾編碼定理若R>H(U)，則R是可達(dá)的；若R<H(U)，則R是不可達(dá)的。對于給定的離散無記憶信源，若D元碼的速率R超過信源的熵，即，則存在有編碼方法，當(dāng)L足夠大時(shí)就能使譯碼錯(cuò)誤概率任意小。編碼效率證明充分性令，取。由信源劃分定理推論2，對于通過選擇足夠大的L，可使對于每個(gè)依次標(biāo)以碼號1,2,…,2LR-1,并令作為相應(yīng)消息的碼字；而對于，都用第2LR個(gè)標(biāo)號(000···000)表示。編碼：相應(yīng)號數(shù)的二元序列譯碼：若若因此，R為可達(dá)速率。則則證明必要性令，則正確譯碼概率為因?yàn)?，所以有個(gè)碼字，序列的個(gè)數(shù)至少為，所以在序列可以找到碼字的概率為而由此得隨著L的加大，上式趨于0，即從而R是不可達(dá)的。而典型中的本節(jié)小結(jié)

信源編碼基本概念DMS等長編碼無失真編碼充要條件幾乎無失真編碼充要條件（本節(jié)內(nèi)容見課本53-62頁）定義等長碼不等長碼唯一可譯碼

D元碼典型序列例題擲硬幣：正面出現(xiàn)p=0.25，這時(shí)信源熵H(U)=0.81。（1）若采用等長二元無錯(cuò)編碼時(shí)，（2）若采用只對典型序列編碼，要求譯碼錯(cuò)誤概率，求L由可得