第三章-無(wú)失真信源編碼課件

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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