第三章-無失真信源編碼(1)

1、第三章第三章 無失真信源編碼無失真信源編碼通信系統(tǒng)模型通信系統(tǒng)模型包括：信源、編碼器、信道、譯碼器、信宿五部分信道編碼信道編碼信源編碼信源編碼保密譯碼保密譯碼信道譯碼信道譯碼信源譯碼信源譯碼保密編碼保密編碼噪聲噪聲信道信道信源信源信宿信宿 編碼器、譯碼器是人為設(shè)計的，很大程度上編碼器、譯碼器是人為設(shè)計的，很大程度上決定了通信性能的好壞。決定了通信性能的好壞。n 無失真信源編碼冗余度壓縮編碼無失真信源編碼冗余度壓縮編碼u 只對信源的冗余度進(jìn)行壓縮，而只對信源的冗余度進(jìn)行壓縮，而不改變信源的熵。不改變信源的熵。u 保證碼元序列經(jīng)譯碼后能保證碼元序列經(jīng)譯碼后能無失真地?zé)o失真地恢復(fù)成信源符號序列。恢復(fù)

2、成信源符號序列。u 適用于適用于離散信源或數(shù)字信號離散信源或數(shù)字信號（文字、文件信源）。（文字、文件信源）。信源編碼的分類信源編碼的分類?n 限失真信源編碼熵壓縮編碼限失真信源編碼熵壓縮編碼u 改變信源的熵。改變信源的熵。u 只能保證碼元序列經(jīng)譯碼后能只能保證碼元序列經(jīng)譯碼后能按一定的失真容許度按一定的失真容許度恢復(fù)恢復(fù)信源符號序列。信源符號序列。u 適用于適用于連續(xù)信源或模擬信號連續(xù)信源或模擬信號（語音、圖像信源）。（語音、圖像信源）。為什么要對信源進(jìn)行編碼為什么要對信源進(jìn)行編碼? 由于信源符號之間存在分布由于信源符號之間存在分布不均勻不均勻和和相關(guān)性相關(guān)性，使得信源存，使得信源存在冗余度。

3、在冗余度。 （1）符號變化）符號變化 符號集中的符號不同，如英語信源的符號是英文字母或單詞，漢語信符號集中的符號不同，如英語信源的符號是英文字母或單詞，漢語信源的符號是漢字或漢語詞組等等。為了便于信道傳送，必須將信源符號源的符號是漢字或漢語詞組等等。為了便于信道傳送，必須將信源符號序列變換成信道能夠傳送的符號序列。序列變換成信道能夠傳送的符號序列。 （2）冗余度壓縮）冗余度壓縮 信源符號的概率分布不均勻，各個符號攜帶信息的多少相差很大即信源符號的概率分布不均勻，各個符號攜帶信息的多少相差很大即信息分布不均勻，信息冗余度大，因此有必要對信源符號序列加以變化，信息分布不均勻，信息冗余度大，因此有必

4、要對信源符號序列加以變化，使變化后的新序列的信息分布均勻化，信息冗余變小，提高信息傳輸效使變化后的新序列的信息分布均勻化，信息冗余變小，提高信息傳輸效率。率。 也就是說，實際發(fā)送的消息總是包含有無用的信息。信源包含有冗也就是說，實際發(fā)送的消息總是包含有無用的信息。信源包含有冗余。余。信源編碼的信源編碼的主要任務(wù)主要任務(wù)就是減少冗余，提高編碼效率。就是減少冗余，提高編碼效率。具體說，就是針對信源輸出符號序列的統(tǒng)計特性，具體說，就是針對信源輸出符號序列的統(tǒng)計特性，尋找一定的方法把信源輸出符號序列變換為最短的碼字序列。尋找一定的方法把信源輸出符號序列變換為最短的碼字序列。 信源編碼的基本途徑信源編碼

5、的基本途徑 是什么是什么? 信源編碼的信源編碼的基本途徑基本途徑有兩個：有兩個：u 使序列中的各個符號盡可能地互相獨(dú)立，即解除使序列中的各個符號盡可能地互相獨(dú)立，即解除相關(guān)性；相關(guān)性；u 解除相關(guān)性后，再使編碼中各個符號出現(xiàn)的概率解除相關(guān)性后，再使編碼中各個符號出現(xiàn)的概率盡可能地相等，即概率均勻化，就能進(jìn)一步改造有盡可能地相等，即概率均勻化，就能進(jìn)一步改造有冗余信源的輸出，去掉冗余度，增大傳輸效率。冗余信源的輸出，去掉冗余度，增大傳輸效率。 信源編碼的基礎(chǔ)是什么信源編碼的基礎(chǔ)是什么? 信源編碼的信源編碼的基礎(chǔ)基礎(chǔ)： 無失真編碼定理無失真編碼定理 限失真編碼定理限失真編碼定理1）無失真編碼是可逆

6、編碼，即信源符號轉(zhuǎn)換成代碼后，可）無失真編碼是可逆編碼，即信源符號轉(zhuǎn)換成代碼后，可從代碼無失真的恢復(fù)原信源符號。只適用于離散信源。從代碼無失真的恢復(fù)原信源符號。只適用于離散信源。2）對于連續(xù)信源，編成代碼后就無法無失真地恢復(fù)原來的連）對于連續(xù)信源，編成代碼后就無法無失真地恢復(fù)原來的連續(xù)值，因為后者的取值可有無限多個。此時只能根據(jù)限失真續(xù)值，因為后者的取值可有無限多個。此時只能根據(jù)限失真編碼定理在失真受限制的情況下進(jìn)行限失真編碼。編碼定理在失真受限制的情況下進(jìn)行限失真編碼。 說明說明：3.1 編碼定義編碼定義3.2 定長編碼定理定長編碼定理 3.3 變長編碼定理變長編碼定理3.4 最佳編碼最佳編

7、碼3.5 游程編碼游程編碼編碼器可看作這樣一個系統(tǒng)：編碼器可看作這樣一個系統(tǒng)： 輸入端輸入端：原始信源：原始信源U，其符號集為，其符號集為U:u1,u2,uq； 信道信道：所能傳輸?shù)拇a符號集（碼元集）為：所能傳輸?shù)拇a符號集（碼元集）為X:x1,x2,xr； 編碼器的功能編碼器的功能：用符號集：用符號集X中的元素，將原始信源的符號中的元素，將原始信源的符號ui變變 換為相應(yīng)的碼字符號換為相應(yīng)的碼字符號wi(i=1,2,q)，即相當(dāng)于，即相當(dāng)于 一個一一對應(yīng)的變化或映射一個一一對應(yīng)的變化或映射f (f: ui wi) 編碼器輸出端編碼器輸出端：符號集（碼字集）為：符號集（碼字集）為W:w1,w2,

8、wq。3.1 編碼定義編碼定義12(.) (1,2,., ),(1,2,., )lkiiiiiiiiwx xxiqxX kll其中 為碼字長度或者碼長?！咀ⅰ咀ⅰ啃旁淳幋a就是從信源符號到輸出碼字符信源編碼就是從信源符號到輸出碼字符號的一種映射。若要實現(xiàn)無失真編碼，則這種號的一種映射。若要實現(xiàn)無失真編碼，則這種映射必須是映射必須是一一對應(yīng)的、可逆一一對應(yīng)的、可逆的。的。1. 平均碼長平均碼長 碼字的碼長：碼字的碼長：碼字碼字wi所含碼元的個數(shù)，記為所含碼元的個數(shù)，記為li（碼元（碼元/符號，符號，r進(jìn)制單位進(jìn)制單位/符號）。符號）。 定長編碼（變長編碼）：定長編碼（變長編碼）： 所有碼字均有相同

9、的碼長所有碼字均有相同的碼長l，即，即l1=l2=lq=l 稱稱f為定長編碼，對應(yīng)的碼為定長編碼，對應(yīng)的碼W叫做定長碼。叫做定長碼。 否則，稱否則，稱f為變長編碼，對應(yīng)的碼為變長編碼，對應(yīng)的碼W叫做變長碼。叫做變長碼。 平均碼長：平均碼長：對碼對碼W中所有碼字的碼長求統(tǒng)計平均中所有碼字的碼長求統(tǒng)計平均 1111()()()()qqiiiiiiqqiiiilP w lP u llP w lP u ll碼元/符號碼元/符號 定長碼平均碼長是衡量碼的性能的重要參數(shù)，小說明平均一個碼元平均碼長是衡量碼的性能的重要參數(shù)，小說明平均一個碼元所攜帶的信息量大，信息的冗余度就小所攜帶的信息量大，信息的冗余度就

10、小。例題：例題：123411111122213331444412DMS1/ 21/ 41/81/8()00,2()01,2()10,2()11,21111()22222 (/)2488iiiuuuuUPXff uwlf uwlf uwlf uwllP u lf設(shè)的概率空間，對其單個符號進(jìn)行二進(jìn)制編碼，即碼元集為 =0，1。定義編碼 為：碼元 符號定義編碼 為：211122221333244441()0,1()10,2()110,3()111,31111()12331.75 (/)2488iiif uwlf uwlf uwlf uwllP u l 碼元 符號【說明】 f1是定長編碼； f2是變長

11、編碼，根據(jù)信源符號的概率不同，采用不同碼長的碼字，經(jīng)常出現(xiàn)（概率大）的符號采用較短的碼字，不經(jīng)常出現(xiàn)（概率?。┑姆柌捎幂^長的碼字，因此平均碼長就會縮短，是一種較好的編碼策略。2.信源編碼前后的熵信源編碼前后的熵將信源編碼器輸出可視為一個新信源：信源W：以碼字集碼字集為符號集； 無失真編碼一一對應(yīng)映射，故 P(wi)=P(ui) (i=1,2,q)， 編碼前后熵保持不變： H(W)=H(U) (bit/碼字或bit/符號)信源X：以碼元集碼元集為符號集；()( )()(/)H WH UH Xbitll碼元編碼后的信息率： 平均一個碼元攜帶的信息量，記為R（就是X的熵）： 可見：平均碼長越小，每

12、個碼元攜帶的信息量就越 多；傳輸一個碼元就傳輸了較多的信息。編碼效率： 編碼后的實際信息率與編碼后的最大信息率之比：( )()(/)H URH Xbitl碼元maxmax()( )/( )()loglogcRH XH UlH URHXrlr 編碼效率是新信源X的熵的相對率，冗余度為：1ccr r為碼元集X的維數(shù)3. 碼的類型碼的類型 碼碼奇異碼奇異碼非奇異碼非奇異碼非唯一可譯碼非唯一可譯碼唯一可譯碼唯一可譯碼非即時碼非即時碼即時碼（非延長碼）即時碼（非延長碼）3.1 碼元集中符號數(shù)碼元集中符號數(shù)r2稱為二元碼，稱為二元碼，r3稱為三元碼稱為三元碼3.2 若分組碼中的碼長都相同則稱為等長碼，否則

13、稱為變長碼若分組碼中的碼長都相同則稱為等長碼，否則稱為變長碼信源符號信源符號信源符號出信源符號出現(xiàn)概率現(xiàn)概率碼表碼表a1a2a3a4p(a1)p(a2)p(a3)p(a4) 00 01 10 11 0 01 001 111碼碼1碼碼2碼碼1是等長碼，碼是等長碼，碼2是變長碼是變長碼3.3 奇異碼和非奇異碼奇異碼和非奇異碼若信源符號和碼字是一一對應(yīng)的，即所有碼字都不相同，若信源符號和碼字是一一對應(yīng)的，即所有碼字都不相同，則該碼為非奇異碼；反之為奇異碼。則該碼為非奇異碼；反之為奇異碼。信源符號信源符號符號出現(xiàn)概率符號出現(xiàn)概率 碼碼1碼碼2碼碼3碼碼4a1a2a3a41/21/41/81/8 011

14、0011010000111010010001010010001碼碼1是奇異碼，碼是奇異碼，碼2，碼，碼3和碼和碼4是非奇異碼是非奇異碼3.4 唯一可譯碼唯一可譯碼非奇異碼中，任意有限長的碼元序列，只能被唯一的譯成所對非奇異碼中，任意有限長的碼元序列，只能被唯一的譯成所對應(yīng)的信源符號序列，稱為唯一可譯碼。應(yīng)的信源符號序列，稱為唯一可譯碼。例如：例如：U: u1,u2,u3; X:0,1; W: w1=0, w2=10, w3=11, 為唯一可譯碼。為唯一可譯碼。當(dāng)接收碼字序列為：當(dāng)接收碼字序列為：10011001111 時，可以唯一地譯為：時，可以唯一地譯為：w2,w1,w3,w1,w1,w3,

15、w3;如果碼字集合為：如果碼字集合為：W:w1=0,w2=01,w3=11 則為非唯一可譯碼。則為非唯一可譯碼。當(dāng)接收碼字序列為：當(dāng)接收碼字序列為：0011111101 時，可以譯為：時，可以譯為：w1,w1(w2)3.5 非即時碼和即時碼非即時碼和即時碼唯一可譯碼中，如果接收端收到一個完整的碼字后，不能立唯一可譯碼中，如果接收端收到一個完整的碼字后，不能立即譯碼，還需等下一個碼字開始接收后才能判斷是否可以譯即譯碼，還需等下一個碼字開始接收后才能判斷是否可以譯碼，這樣的碼叫做非即時碼。碼，這樣的碼叫做非即時碼。沒有任何完整的碼字是其他碼字的前綴，可立即譯碼的叫做沒有任何完整的碼字是其他碼字的前

16、綴，可立即譯碼的叫做即時碼（非延長碼）。即時碼（非延長碼）。例如：例如：W：1，10，100，111不是即時碼，不是即時碼， 1是是 10的前綴，的前綴， 10 為為100的前綴。的前綴。即時碼一定是唯一的，唯一可譯碼卻不一定是即時碼。即時碼一定是唯一的，唯一可譯碼卻不一定是即時碼。例如：例如：W：0，01是唯一的，但不是即時碼。是唯一的，但不是即時碼。接收到的碼字序列接收到的碼字序列0010，唯一的被可譯為，唯一的被可譯為w1w2 .4. 即時碼及其樹圖構(gòu)造法即時碼及其樹圖構(gòu)造法 碼樹碼樹碼樹碼樹：用碼樹表示碼字的組成，由：用碼樹表示碼字的組成，由樹根、樹枝、節(jié)點樹根、樹枝、節(jié)點組成。組成。

17、碼樹構(gòu)造要點：碼樹構(gòu)造要點：1）最上（下）端為樹根，從樹根向下（上）延伸出樹枝，）最上（下）端為樹根，從樹根向下（上）延伸出樹枝，樹枝總數(shù)等于樹枝總數(shù)等于r，樹枝的盡頭為節(jié)點。，樹枝的盡頭為節(jié)點。2）從每個節(jié)點再伸出）從每個節(jié)點再伸出r個樹枝，當(dāng)某節(jié)點被安排為碼字個樹枝，當(dāng)某節(jié)點被安排為碼字 后，就不再伸枝，此節(jié)點稱為后，就不再伸枝，此節(jié)點稱為終端節(jié)點終端節(jié)點（用粗黑點表用粗黑點表 示示），其它節(jié)點稱為中間節(jié)點（用空心圈表示）。），其它節(jié)點稱為中間節(jié)點（用空心圈表示）。3）每個節(jié)點伸出的樹枝標(biāo)上碼符號，從根出發(fā)到終端節(jié)）每個節(jié)點伸出的樹枝標(biāo)上碼符號，從根出發(fā)到終端節(jié) 點所走路徑對應(yīng)的碼符號序列

18、則為點所走路徑對應(yīng)的碼符號序列則為終端節(jié)點的碼字終端節(jié)點的碼字。r進(jìn)制碼樹：有進(jìn)制碼樹：有r個分支個分支一級節(jié)點：經(jīng)過一個分支到達(dá)的節(jié)點，有一級節(jié)點：經(jīng)過一個分支到達(dá)的節(jié)點，有r個個N階節(jié)點：階節(jié)點：rn個個碼字：從樹根到節(jié)點的分枝標(biāo)號序列碼字：從樹根到節(jié)點的分枝標(biāo)號序列碼樹圖碼樹圖 4 唯一可譯碼存在的充要條件唯一可譯碼存在的充要條件：iNli1r1其中其中N表示信源符號數(shù)，表示信源符號數(shù)，r表示進(jìn)制數(shù)，表示進(jìn)制數(shù)，li表示各碼字長度。表示各碼字長度。對含有對含有N個信源符號的信源用含有個信源符號的信源用含有r個碼元的碼符號集進(jìn)行個碼元的碼符號集進(jìn)行編碼，各碼字的長為編碼，各碼字的長為l1，l2.，其唯一可譯碼存在的充要條其唯一可譯碼存在的充要條件是，滿足件是，滿足克勞夫特（克勞夫特（Kraft）不等式）不等式例：設(shè)二進(jìn)制碼樹中例：設(shè)二進(jìn)制碼樹中Uu1,u2,u3,u4,l1=1,l2=2,l3=2,l4=3,請判斷這是否存在唯一可譯碼？請判斷這是否存在唯一可譯碼？41il-2-2-3i92= 2 +2 +2 +2