第三章-無失真信源編碼課件

1、第三章 無失真信源編碼 引言 編碼的定義 定長編碼定理 變長編碼定理 變長編碼方法引言什么是編碼香農(nóng)信息論三大定理編碼的分類編碼的任務和途徑編碼器什么是編碼信源編碼和信道編碼 通信的實質是傳輸信息，要求傳輸具有高效率和質量： （1）在不失真和允許一定失真的條件下，用盡可能少的符號傳送信源信息，以便提高信息傳輸率。 （2）在信道受干擾的情況下，增加信號的抗干擾能力，以便提高信息傳輸?shù)目煽啃浴?解決以上兩個問題需要引入信源編碼和信道編碼。什么是編碼生活中編碼實例?學號、身份證號碼、一卡通、漢語等編碼。編碼實質：信息的表示。結論: 信息無處不在 ，編碼無處不在。香農(nóng)信息論三大定理第一極限定理: 無失

2、真信源編碼定理。第二極限定理: 信道編碼定理(包括離 散和連續(xù)信道)。第三極限定理: 限失真信源編碼定理。編碼的分類編碼：信源編碼、信道編碼。信源編碼：無失真信源編碼、限失真信源編碼。無失真信源編碼：適用于離散信源或數(shù)字 信號。限失真信源編碼：適用于連續(xù)信源或模擬信號，如語音、圖像等信號的數(shù)字處理。信源編碼目的與方法 信源編碼：將信源輸出的消息符號進行有效變換，使其成為適合信道傳輸?shù)姆栃蛄校沂乖撔蛄薪M成的新信源的冗余度盡可能地減少。 目的：提高通信的有效性。 方法：減少信源冗余度。信源編碼的基本途徑信源編碼的基本途徑 解除相關性：使序列中的各個符號盡可能地互相獨立。 概率均勻化：使編碼中各

3、個符號出現(xiàn)的概率盡可能地相等。 信源編碼的基礎 信源編碼的基礎：無失真信源編碼定理和限失真信源編碼定理。編碼定理表明：（1）必存在一種編碼方法，使代碼的平均長度可任意接近但不能低于符號熵。（2）達到這目標的途徑，就是使概率與碼長匹配。 編碼器不少原始信源的消息符號不適應信道的傳輸；原始信源消息符號的傳輸效率低；編碼器輸入端為原始信源u，其符號集為S:s1,s2,sq；si(i=1,2,q)；而信道所能傳輸?shù)姆柤癁閤:x1,x2,xr；編碼器的功能：用符號集x中的元素，將原始信源的符號si變換為相應的碼字符號Wi，(i=1,2,q)，所以編碼器輸出端的符號集為C=W1,W2,Wq。編碼器的數(shù)學

4、模型S=原始信源符號集；x=碼元符號集；C=碼字符號集；（碼組）基本源編碼消息集合碼字集合一些基本概念二元碼定長碼變長碼非奇異碼奇異碼同價碼分組碼唯一可譯碼即時碼碼的前綴碼樹1.二元碼 若碼符號集為X=0,1，所有碼字都是二元符號序列，則稱為二元碼。2.定長碼 若一組碼中所有碼字的碼長都相同，即li=l（i=1,2,n）,則稱為定長碼。3.變長碼若一組碼中所有碼字的碼長各不相同，即任意碼字由不同長度li的碼符號序列組成，則稱為變長碼。信源符號si信源符號出現(xiàn)概率p（si）碼1碼2S1p（s1）000S2p（s2）0101S3p（s3）10001S4p（s4）111114.非奇異碼 若一組碼中所

5、有碼字都不相同，即所有信源符號映射到不同的碼符號序列，則稱碼為非奇異碼。5.奇異碼若一組碼中有相同的碼字，則稱碼為奇異碼。信源符號si信源符號出現(xiàn)概率p（si）碼1碼2S1p（s1）00S2p（s2）1110S3p（s3）0000S4p（s4）11106.同價碼若碼符號集中每個碼符號所占的傳輸時間都相同，則所得的碼為同價碼。7.分組碼 將信源符號集中的每個信源符號映射成一個固定的碼字，這樣的碼稱為分組碼。8.唯一可譯碼 若碼的任意一串有限長的碼符號序列只能被唯一的譯成所對應的信源符號序列，則此碼稱為唯一可譯碼。也稱單義可譯碼。注意：定長碼是非奇異的就是唯一可譯碼，因為它能固定長度分組。 變長碼

6、則不一定，主要是不能固定長度分組。 唯一可譯碼還有判定準則，后面將介紹。唯一可譯碼(續(xù))信源符號si信源符號出現(xiàn)概率p（si）碼1碼2S1p（s1）000S2p（s2）0101S3p（s3）10001S4p（s4）111119.即時碼無需考慮后續(xù)的碼符號即可從碼符號序列中譯出碼字，這樣的唯一可譯碼稱為即時碼或瞬時碼或逗點碼或非延長碼或異前綴碼。信源符號si碼1碼2S111S21001S3100001S41000000110.碼的前綴 定理:唯一可譯碼成為即時碼的充要條件是其中任何一個碼字都不是其他碼字的前綴。11.碼樹 碼字的構造可用樹的形式來表示，稱為 碼的樹圖構造法。r元碼通常對應于r元樹

7、（r叉樹，r進制樹）。當然二元碼對應的是二叉樹或二元樹。 樹根、葉子節(jié)點、中間節(jié)點、深度、碼長。 整樹、非整樹、全樹。碼樹圖唯一可譯碼定理設原始信源符號集為S:S1,S2,Sq，碼元符號集為x:x1,x2,xr，碼字集合為W:W1,W2,Wq，其碼長分別為L1,L2,Lq；則唯一可譯碼存在的充要條件為碼長組合滿足Kraft不等式，即 式中，r是進制數(shù)，q是信源符號數(shù)，l為碼字長度。 唯一可譯碼Kraft不等式：是唯一可譯碼的充要條件，也是即時碼的充要條件；Kraft不等式指明了即時碼的碼長必須滿足的條件；充要條件是對于碼長組合而言，而不是對于碼字本身而言，即滿足Kraft不等式的碼長組合一定能

8、構成至少一種唯一碼，唯一碼的碼長組合一定滿足Kraft不等式。否則無法構成唯一可譯碼。唯一可譯碼有些碼字的碼長組合雖滿足Kraft不等式，但不是唯一碼。Kraft 不等式不能用來判斷W是否是唯一可譯碼，但不滿足該不等式的W一定不是唯一可譯碼。唯一可譯碼判別準則：用來判斷W是否是唯一可譯碼。無失真信源編碼定理研究內容若信源輸出符號序列的長度 ，即 變換成由KL個符號組成的碼序列（碼字)變換要求:(1)能夠無失真或無差錯地從Y恢復X，也就是能正確地進行反變換或譯碼 。(2)傳送Y時所需要的信息率最小 。 由于Yk可取m種可能值，即平均每個符號輸出的最大信息量為logm，KL長碼字的最大信息量為KL

9、logm。用該碼字表示L長的信源序列,則送出一個信源符號所需要的信息率平均為:其中 是Y所能編成的碼字的個數(shù)。信息率最小，就是找到一種編碼方式使 最小。無失真信源編碼定理研究內容: (1)最小信息率為多少時，才能得到無失真的譯碼？(2)若小于這個信息率是否還能無失真地譯碼？第二節(jié) 定長編碼定理定長信源編碼定理 由L個符號組成的、平均符號熵為HL（X）的無記憶平穩(wěn)信源符號序列 ，可用KL個符號 （每個符號有m種可能值）進行定長編碼。對任意 ，只要(注:把L移過去觀察) 則當L足夠大時，必可使譯碼差錯小于 ；反之，當 時，譯碼差錯一定是有限值，而當L足夠大時，譯碼幾乎必定出錯。 說明（1）當編碼器

10、容許的輸出信息率，也就是當每個信源符號所必須輸出的碼長是時，只要 ，這種編碼器一定可以做到幾乎無失真，也就是收端的譯碼差錯概率接近于零，條件是所取的符號數(shù)L足夠大。(2)將定理的條件改寫成 其中：左邊：KL長碼字所能攜帶的最大信息量， 右邊：L長信源序列攜帶的信息量。 上述定理表明，只要碼字所能攜帶的信息量大于信源序列輸出的信息量，則可以使傳輸幾乎無失真，當然條件是L足夠大。 反之，當 時，不可能構成無失真的編碼，也就是不可能做一種編碼器，能使收端譯碼時差錯概率趨于零。 時，則為臨界狀態(tài)，可能無失真，也可能有失真。 第三節(jié) 變長編碼定理單個符號變長編碼定理: 若一離散無記憶信源的符號熵為H（X

11、），每個信源符號用m進制碼元進行變長編碼，一定存在一種無失真編碼方法，其碼字平均長度滿足下列不等式 離散平穩(wěn)無記憶序列變長編碼定理 對于平均符號熵為HL（X）的離散平穩(wěn)無記憶信源，必存在一種無失真編碼方法，使平均信息率 滿足不等式 其中 為任意小正數(shù)。證明:設用m進制碼元作變長編碼，序列長度為L個信源符號，則由（331）式可以得到平均碼字長度 滿足下列不等式 當L足夠大時，可使 ，這就得到了 所需結論說明: (1) 用變長編碼來達到相當高的編碼效率，一般所要求的符號長度L可以比定長編碼小得多?？傻镁幋a效率的下界： (2) 例 用二進制，m2，log2m=l，H（X）2.55比特符號，若要求 ，

12、則 (3) 碼的冗余度為 碼的冗余度用來衡量各種編碼方法與最佳碼的差距。例331設離散無記憶信源的概率空間為 求:編碼效率?解:根據(jù)信源熵計算公式有： 比特/符號 (1)定長編碼 若用二元定長編碼（0,1）來構造一個 即時碼：這時平均碼長為 =1 二元碼符號/信源符號編碼效率為(對于無記憶信源而言,有HL(X)=H(X) ) 輸出的信息率為 R0.811比特二元碼符號 (2)變長編碼 假定信源序列的長度為L=2,其即時碼如表3-3所示。 序列序列概率即時碼 x1x1 9/16 0 x1x2 x2x1 x2x2 1/16 3/16 3/16 111 110 10這個碼的碼字平均長度 單個符號的平

13、均碼長 編碼效率 輸出的信息率為 R20961 比特二元碼符號 將信源序列的長度增加，L3或L=4，對這些信源序列X進行編碼，并求出其編碼效率為 信息傳輸率分別為： R30985比特二元碼符號 R40991比特二元碼符號如果對這一信源采用定長二元碼編碼，要求編碼效率達到96時，允許譯碼錯誤概率 。則根據(jù)（326）式，自信息的方差 所需要的信源序列長度 變長碼相關結論應用變長碼往往在N不很大時，就可編出效率很高且無失真的碼；變長碼必須是唯一可譯碼，才能實現(xiàn)無失真編碼；變長碼要滿足唯一可譯碼必須是非奇異碼,而且任意有限長N次擴展碼也必須是非奇異的；為了能夠即時進行譯碼，變長碼還必須是即時碼。第四節(jié)

14、 變長碼的編碼方法(1)最佳碼定義 凡是能載荷一定的信息量，且碼字的平均長度最短，可分離的變長碼的碼字集合都可稱為最佳碼。 (2)最佳編碼思想 將概率大的信息符號編以短的碼字，概率小的符號編以長的碼字，使得平均碼字長度最短。 (3)最佳碼的編碼主要方法 香農(nóng)（Shannon）、費諾（Fano）、哈夫曼（Huffman）編碼等。 3.4.1 香農(nóng)編碼方法香農(nóng)第一定理編碼方法如下： (1)將信源消息符號按其出現(xiàn)的概率大小依次排列 (2) 確定滿足下列不等式的整數(shù)碼長Ki： (3)為了編成唯一可譯碼，計算第i個消息 的累加概率 (4)將累加概率Pi 變換成二進制數(shù)。 (5)取Pi二進數(shù)的小數(shù)點后Ki

15、位即為該消 息符號的二進制碼字。 例3-4-1 設信源共7個符號消息，其概率和累加概率如表3-4-1所示。以i=4為例， 累加概率P4=0.57，變換成二進制為0.1001，由于3，所以第4個消息的編碼碼字為100。其他消息的碼字可用同樣方法求得，7個消息符號對應的碼字依次為： 000,001,011,100,101,1110,1111110說明: (1)該信源共有5個三位的碼字，各碼字之間至少有一位數(shù)字不相同，故是唯一可譯碼。同時可以看出，這7個碼字都不是延長碼，它們都屬于即時碼。這里L=1，m=2. (2)信源符號的平均碼長 碼元/符號 (3) 平均信息傳輸率 3.4.2 費諾編碼方法編碼

16、步驟：（1）將信源消息符號按其出現(xiàn)的概率大小依次排列：p(x1) p(x2) p(xn)。（2）將依次排列的信源符號按概率值分為兩大組，使兩個組的概率之和近于相同，并對各組賦予一個二進制碼元“0”和“1”。（3）將每一大組的信源符號進一步再分成兩組，使劃分后的兩個組的概率之和近于相同，并又賦予兩個組一個二進制符號“0和“1”。（4）如此重復，直至每個組只剩下一個信源符號為止。（5）信源符號所對應的碼字即為費諾碼。 如何求出費諾碼 編碼過程參見P44 ，表3-4-2。 費諾碼的平均碼長 信息傳輸速率 3.4.3 哈夫曼編碼方法哈夫曼編碼步驟：（1）將n個信源消息符號按其出現(xiàn)的概率大小依 次排列， p（x1）p（x2）p（xn）（2）取兩個概率最小的字母分別配以0和1兩碼元，并將這兩個概率相加作為一個新字母的概率，與未分配的二進符號的字母重新排隊。 （3）對重排后的兩個概率最小符號重復步驟（2）的過程。（4）不斷繼續(xù)上述過程，直到最后兩個符號配以0和1為止。（5）從最后一級開始，向前返回得到各個信源符號所對應的碼元序列，即相應的碼字。 哈夫曼編碼過程，見P44表3-4-3