1、第三章 無失真信源編碼,第一節(jié) 編碼的定義,第二節(jié) 定長編碼定理,第三節(jié) 變長編碼定理,第四節(jié) 最佳編碼,引言,引言,編碼分為信源編碼和信道編碼，其中信源編碼又分為無失真信源編碼和限失真信源編碼。 無失真信源編碼：適用于離散信源或數(shù)字 信號。 限失真信源編碼：主要用于連續(xù)信源或模擬信號，如語音、圖像等信號的數(shù)字處理。,香農(nóng)信息論三大定理 : 1. 第一極限定理:無失真信源編碼定理. 第二極限定理: 信道編碼定理（包括離 散和連續(xù)信道）. 3. 第三極限定理: 限失真信源編碼定理.,信源編碼的主要任務是什么? 由于信源符號之間存在分布不均勻和相關(guān)性，使得信源存在冗余度，信源編碼的主要任務就是減少

2、冗余，提高編碼效率。具體說，就是針對信源輸出符號序列的統(tǒng)計特性，尋找一定的方法把信源輸出符號序列變換為最短的碼字序列。,信源編碼的基本途徑 是什么?,信源編碼的基本途徑有兩個，一是使序列中的各個符號盡可能地互相獨立，即解除相關(guān)性；二是使編碼中各個符號出現(xiàn)的概率盡可能地相等，即概率均勻化。,信源編碼的基礎是什么?,信源編碼的基礎是：兩個編碼定理，即無失真編碼定理和限失真編碼定理。,編碼定理證明： （1）必存在一種編碼方法，使代碼的平均長度可任意接近但不能低于符號熵 （2）達到這目標的途徑，就是使概率與碼長匹配。,說明： （1）無失真編碼或可逆編碼只適用于離散信源。 （2）對于連續(xù)信源，編成代碼后

3、就無法無失真地恢復原來的連續(xù)值，因為后者的取值可有無限多個。此時只能根據(jù)限失真編碼定理進行限失真編碼 。,什么分組碼？ 設: 信源消息為符號序列Xi， ， 序列中的每個符號取自于符號集A， 。而每個符號序列Xi依照固 定的碼表映射成一個碼字Yi，這樣的碼稱為分組 碼，有時也叫塊碼。只有分組碼才有對應的碼表， 而非分組碼中則不存在碼表。,第一節(jié) 編碼的定義,信源編碼器,L長序列,K長碼字,圖3-1-1 信源編碼器,設: 信源輸出的序列長度為1，即信源符號集 信源概率空間為： 二元信道的信道基本符號集為0，1。若將信源 X通過一個二元信道傳輸，就必須把信源符號xi 變換成由0，1符號組成的碼符號序

4、列，即編碼。 可用不同的碼符號序列，如表311所示。 見書 (P35),分組碼的一些直觀屬性,分組碼的一些直觀屬性,碼,非分組碼,分組碼,奇異碼,非奇異碼,非唯一可譯碼,唯一可譯碼,非即時碼,即時碼（非延長碼）,碼樹圖,A,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,1,1,1,1,1,二進制碼樹,2,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2,三進制碼樹,唯一可譯碼存在的充分和必要條件,用樹的概念可導出唯一可譯碼存在的充分和必要條件，即各碼字的長度Ki應符合克勞夫特不等式： (3-1-1) 式中，m是進制數(shù)，n是信源符號數(shù)。,看

5、書P36(例3-1-1）,無失真信源編碼定理要研究的內(nèi)容,若信源輸出符號序列的長度 ，即 變換成由KL個符號組成的碼序列（碼字) 變換的要求: (1)能夠無失真或無差錯地從Y恢復X，也就是能正確地進行反變換或譯碼 (2)傳送Y時所需要的信息率最小,由于Yk可取m種可能值，即平均每個符號輸出的最大信息量為logm，KL長碼字的最大信息量為KLlogm。用該碼字表示L長的信源序列,則送出一個信源符號所需要的信息率平均為: 其中 是Y所能編成的碼字的個數(shù)。 信息率最小，就是找到一種編碼方式使 最小。 無失真信源編碼定理要研究的內(nèi)容: (1)最小信息率為多少時，才能得到無失真的譯碼？ (2)若小于這個

6、信息率是否還能無失真地譯碼？,定長編碼定理 由L個符號組成的、每個符號的熵為HL（X）的無記憶平穩(wěn)信源符號序列 ，可用KL個符號 （每個符號有m種可能值）進行定長編碼。對任意 ，只要 則當L足夠大時，必可使譯碼差錯小于 ；反之，當 時，譯碼差錯一定是有限值，而當L足夠大時，譯碼幾乎必定出錯。,第二節(jié) 定長編碼定理,說明,（1）當編碼器容許的輸出信息率，也就是當每個信源符號所必須輸出的碼長是 時，只要 ，這種編碼器一定可以做到幾 乎無失真，也就是收端的譯碼差錯概率接近于零， 條件是所取的符號數(shù)L足夠大。,（2）將定理的條件改寫成 其中：左邊：KL長碼字所能攜帶的最大信息量， 右邊：L長信源序列攜帶的信息量。 上述定理表明，只要碼字所能攜帶的信息量大于信源序列輸出的信息量，則可以使