《信息論與編碼(第二版)》第5章

信源編碼

第5章15.1

編碼的定義5.2

無失真信源編碼5.3限失真信源編碼5.4常用信源編碼方法簡介內(nèi)容25.1編碼的定義3信源編碼：無失真信源編碼—第一極限定理離散信源限失真信源編碼—第三極限定理連續(xù)信源信道編碼

第二極限定理信源編碼在不失真或允許一定失真條件下,如何用盡可能少的符號(hào)來傳送信源信息,以便提高信息傳輸率信道編碼在信道受干擾的情況下如何增加信號(hào)的抗干擾能力,同時(shí)又使得信息傳輸率最大。編碼4編碼的定義信源編碼器碼表信源信道信源編碼:將信源輸出符號(hào),經(jīng)信源編碼器后變換成另外的壓縮符號(hào),然后將壓縮后信息經(jīng)信道傳送給信宿信源符號(hào)之間存在分布不均勻和相關(guān)性,使得信源存在冗余度,信源編碼的主要任務(wù)就是減少冗余,提高編碼效率。針對(duì)信源輸出符號(hào)序列的統(tǒng)計(jì)特性,尋找一定的方法把信源輸出符號(hào)序列變換為最短的碼字序列。XY5編碼的定義編碼定理證明:必存在一種編碼方法,使代碼的平均長度可任意接近但不能低于符號(hào)熵;達(dá)到這目標(biāo)的途徑就是使概率與碼長匹配。統(tǒng)計(jì)匹配編碼：根據(jù)信源的不同概率分布而選用與之匹配的編碼,以達(dá)到在系統(tǒng)中傳信速率最小。6編碼的定義信源符號(hào)

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

碼表碼0碼1碼2碼3碼4a1p(a1)=1/2000011a2p(a2)=1/40111101001a3p(a3)=1/8100000100001a4p(a4)=1/811110110000001等長碼：碼中所有碼字的長度都相同變長碼：碼中的碼字長短不一非奇異碼：信源符號(hào)與碼字是一一對(duì)應(yīng)的奇異碼：碼1若碼集為{0,1},所得碼字為二元序列,稱為二元碼例如,信源符號(hào)X＝{a1,a2,a3,a4},對(duì)應(yīng)不同碼字如表7編碼的定義唯一可譯碼：任意有限長的碼元序列,只能被唯一地分割成一個(gè)個(gè)的碼字。例：{0,10,11}是一種唯一可譯碼。任意一串有限長碼序列,如100111000,只能被分割成10,0,11,10,0,0。任何其他分割法都會(huì)產(chǎn)生一些非定義的碼字。奇異碼不是唯一可譯碼非奇異碼唯一可譯碼—碼3非唯一可譯碼—碼28編碼的定義唯一可譯碼

非即時(shí)碼：如果接收端收到一個(gè)完整的碼字后不能立即譯碼,還需等下一個(gè)碼字開始接收后才能判斷是否可以譯碼即時(shí)碼：(非延長碼)(異前綴碼)在譯碼時(shí)無需參考后續(xù)的碼符號(hào)就能立即作出判斷,譯成對(duì)應(yīng)的信源符號(hào)。任意一個(gè)碼字都不是其它碼字的前綴部分在延長碼中,有的碼是唯一可譯的,取決于碼的總體結(jié)構(gòu)9編碼的定義碼非分組碼分組碼奇異碼非奇異碼

非唯一可譯碼唯一可譯碼非即時(shí)碼即時(shí)碼

(非延長碼)10碼樹表示各碼字的構(gòu)成A0100000000000001111111011111二進(jìn)制碼樹2000001111122222三進(jìn)制碼樹樹根—碼字的起點(diǎn)分成r個(gè)樹枝—碼的進(jìn)制數(shù)終端節(jié)點(diǎn)—碼字1101中間節(jié)點(diǎn)—碼字的一部分節(jié)數(shù)—碼長11碼411110001010010001碼400001110101101110樹碼如果有n個(gè)信源符號(hào),那么在碼樹上就要選擇n個(gè)終端節(jié)點(diǎn),用相應(yīng)的r元基本符號(hào)表示這些碼字。碼001001111100100任一即時(shí)碼都可用樹圖法來表示。當(dāng)碼字長度給定,即時(shí)碼不是唯一的。

1211010001001000碼3對(duì)應(yīng)的樹如下圖:編碼的定義該碼樹從根到終端節(jié)點(diǎn)所經(jīng)路徑上每一個(gè)中間節(jié)點(diǎn)皆為碼字,因此不滿足前綴條件。雖然碼3不是即時(shí)碼,但它是唯一可譯碼。13編碼的定義滿樹：每個(gè)節(jié)點(diǎn)上都有r個(gè)分枝的樹——等長碼非滿樹：變長碼用樹的概念可導(dǎo)出唯一可譯碼存在的充分和必要條件,即各碼字的長度Ki應(yīng)符合Kraft不等式式中:m是進(jìn)制數(shù)n是信源符號(hào)數(shù)14例：設(shè)二進(jìn)制碼樹中X=(a1,a2,a3,a4),K1=1,K2=2,K3=2,K4=3,應(yīng)用Kraft不等式,得：不存在滿足這種Ki的唯一可譯碼0001101011011中間節(jié)點(diǎn)如果將各碼字長度改成K1=1,K2=2,K3=3,K4=3,則這樣的碼字就存在唯一可譯碼11115編碼的定義必須注意：Kraft不等式只是用來說明唯一可譯碼是否存在,并不能作為唯一可譯碼的判據(jù)。如碼字{0，10，010，111}雖然滿足Kraft不等式,但它不是唯一可譯碼。165.2無失真信源編碼17無失真信源編碼信源編碼器碼表信源信道信源編碼器輸入的消息序列:X=(X1X2…Xl…XL),Xl∈{a1,…an},

輸入的消息總共有nL種可能的組合輸出的碼字為:Y=(Y1Y2…Yk…YK),Yk∈{b1,…bm}

輸出的碼字總共有mK種可能的組合。XYL長序列K長碼字18無失真信源編碼實(shí)現(xiàn)無失真的信源編碼,要求:信源符號(hào)X1X2…Xl…XL

是一一對(duì)應(yīng)的

碼字Y1Y2…Yk…YK能夠無失真或無差錯(cuò)地從Y恢復(fù)X,也就是能正確地進(jìn)行反變換或譯碼

;傳送Y時(shí)所需要的信息率最小

信息率最小就是找到一種編碼方式使最小195.2.1定長編碼定理信源編碼器碼表信源信道在定長編碼中,K是定值。我們的目的是尋找最小K值。編碼器輸入X=(X1X2…Xl…XL),

Xl∈{a1,…an},

輸入的消息總共有nL種可能的組合輸出的碼字Y=(Y1Y2…Yk…YK),Yk∈{b1,…bm}

輸出的碼字總共有mK種可能的組合。若對(duì)信源進(jìn)行定長編碼,必須滿足:nL≤mK

XYL長序列K長碼字20定長編碼若對(duì)信源進(jìn)行定長編碼,必須滿足:

只有當(dāng)K長的碼符號(hào)序列數(shù)mK大于或等于信源的符號(hào)數(shù)nL時(shí),才可能存在定長非奇異碼。例如英文電報(bào)有27個(gè)符號(hào),n=27,L=1,m=2(二元編碼)每個(gè)英文電報(bào)符號(hào)至少要用5位二元符號(hào)編碼21定長編碼實(shí)際英文電報(bào)符號(hào)信源,在考慮了符號(hào)出現(xiàn)的概率以及符號(hào)之間的依賴性后,平均每個(gè)英文電報(bào)符號(hào)所提供的信息量約等于1.4比特,大大小于5比特。編碼后5個(gè)二元符號(hào)只攜帶約1.4比特信息量。定長編碼的信息傳輸效率極低。22定長編碼定理定長編碼定理：由L個(gè)符號(hào)組成的、每個(gè)符號(hào)的熵為HL(X)的無記憶平穩(wěn)信源符號(hào)序列X1…Xl…XL,可用K個(gè)符號(hào)Y1…Yk…YK(每個(gè)符號(hào)有m種可能值)進(jìn)行定長編碼。對(duì)任意ε＞0,δ＞0,只要?jiǎng)t當(dāng)L足夠大時(shí),必可使譯碼差錯(cuò)小于δ;反之,當(dāng)時(shí),譯碼差錯(cuò)一定是有限值,而當(dāng)L足夠大時(shí),譯碼幾乎必定出錯(cuò)23定長編碼定理⑴當(dāng)編碼器容許的輸出信息率,也就是當(dāng)每個(gè)信源符號(hào)所必須輸出的碼長是時(shí),只要,這種編碼器一定可以做到幾乎無失真,也就是收端的譯碼差錯(cuò)概率接近于零,條件是所取的符號(hào)數(shù)L足夠大。24⑵將定理的條件改寫成其中：左邊：KL長碼字所能攜帶的最大信息，右邊：L長信源序列攜帶的信息量。上述定理表明:只要碼字所能攜帶的信息量大于信源序列輸出的信息量,則可以使傳輸幾乎無失真,當(dāng)然條件是L足夠大。反之,當(dāng)時(shí),不可能構(gòu)成無失真的編碼,也就是不可能做一種編碼器,能使收端譯碼時(shí)差錯(cuò)概率趨于零。

時(shí),則為臨界狀態(tài),可能無失真,也可能有失真。

25定長編碼定理為了衡量編碼效果,定義編碼效率：對(duì)定長編碼,若要實(shí)現(xiàn)幾乎無失真編碼,則信源長度必須滿足:信源序列的自信息方差26例5-2設(shè)離散無記憶信源概率空間信源熵：方差：若取差錯(cuò)率δ≤10－6,編碼效率為90%,則L應(yīng)滿足在差錯(cuò)率和編碼效率要求并不十分苛刻的條件下,就需要L=108個(gè)信源符號(hào)進(jìn)行聯(lián)合編碼,這顯然是很難實(shí)現(xiàn)的。275.2.2變長編碼定理在變長編碼中碼長K是變化的。我們可根據(jù)信源各個(gè)符號(hào)的統(tǒng)計(jì)特性,如概率大的符號(hào)用短碼,概率小的用較長的碼,這樣在大量信源符號(hào)編成碼后平均每個(gè)信源符號(hào)所需的輸出符號(hào)數(shù)就可以降低,從而提高編碼效率28變長編碼定理單個(gè)符號(hào)變長編碼定理：若一離散無記憶信源的符號(hào)熵為H(X),每個(gè)信源符號(hào)用m進(jìn)制碼元進(jìn)行變長編碼,一定存在一種無失真編碼方法,其碼字平均長度滿足下列不等式:29變長編碼定理離散平穩(wěn)無記憶序列變長編碼定理對(duì)于平均符號(hào)熵為HL(X)的離散平穩(wěn)無記憶信源,必存在一種無失真編碼方法,使平均信息率滿足不等式其中ε為任意小正數(shù)30ABCDEFGHIJ·––···–·–·–·····–·––········–––KLMNOPQRST–·–·–··–––·–––·––·––·–·–····–UVWXYZ，.··–···–·–––··––·––––··––··––·–·–·–1234567890·––––··–––···––····–·····–····––···–––··––––·–––––Morse電報(bào)字符31變長編碼定理用變長編碼來達(dá)到相當(dāng)高的編碼效率,一般所要求的符號(hào)長度L可以比定長編碼小得多。編碼效率的下界：32由若對(duì)例5-2用變長碼實(shí)現(xiàn),要求η＞90%,用二進(jìn)制,m＝2,log2m=l。得L=433例5-3設(shè)離散無記憶信源概率空間信源熵：若用二元定長編碼(0,1)來構(gòu)造一個(gè)即時(shí)碼:a1→0,a2→1平均碼長為編碼效率為輸出的信息效率為34再對(duì)長度為L=2的信源序列進(jìn)行變長編碼,其即時(shí)