講義41信源編碼

1、信息論課程講義第四章 信源編碼4-1 離散信源的信源編碼通信的根本目的就是有效而可靠地傳輸信息。Shannon信息論中的一個(gè)重要內(nèi)容就是它給出了信息傳輸?shù)挠行院涂煽啃缘臉O限能力。具體表現(xiàn)為兩個(gè)編碼定理；一般稱為Shannon第一編碼定理（信源編碼定理，有效性編碼定理）和Shannon第二編碼定理（信道編碼定理，抗干擾編碼定理）。4-1-1 編碼器(Encoder)我們前面考慮的信源都是離散化的信源，實(shí)際上沒有考慮到編碼的問題。編碼的作用可以分為以下編兩點(diǎn)：§ 一些原始信源的符號不適應(yīng)信道的傳輸；§ 原始信源符號的傳輸效率很低；碼器可以看作這樣一個(gè)系統(tǒng)，它的輸入端為原始信源

2、S，其符號集為S:s1,s2,sn；si(i=1,2,n)；而信道所能傳輸?shù)姆柤癁锳:a1,a2,aq；編碼器的功能是用符號集A中的元素，將原始信源的符號si變換為相應(yīng)的碼字符號Wi，(i=1,2,n)，所以編碼器輸出端的符號集為W:W1,W2,Wn。S=原始信源符號集；A=碼元符號集；W=碼字符號集；（碼組）編碼器 S:s1,s2,sn W:W1,W2,Wn A:a1,a2,aqWi=w1,w2,wLi wia1,a2,aqLi為碼字Wi的碼元個(gè)數(shù)，稱為碼字Wi的碼字長度，簡稱碼長。q=2時(shí)，稱為二元編碼，否則稱為q元編碼。4-1-2 單義可譯碼(Uniquely decodable co

3、de)(1) 單義可譯碼定義：如果一個(gè)碼組的任一有限長的碼字序列（一串碼字），只能唯一地被譯成一個(gè)一個(gè)碼字，則稱為單義可譯碼，也稱為異前置碼。例如：S: s1,s2,s3; A:0,1; W: w1=0, w2=10, w3=11, 為單義可譯碼。當(dāng)接收碼字序列為：10011001111 時(shí)，可以唯一地譯為：w2,w1,w3,w1,w1,w3,w3;如果碼字集合為：W:0,01,11 則為非單義可譯碼。當(dāng)接收碼字序列為：10011001111 時(shí)，可以譯為：x,w1,w1(w2)(2) 瞬時(shí)可譯碼（非續(xù)長碼）定義：如果一個(gè)碼組中的任一個(gè)碼字都不是另一個(gè)碼字的續(xù)長，或者說，任何一個(gè)碼字后加上若干

4、碼元后都不是碼組中另一個(gè)碼字。則稱為瞬時(shí)可譯碼，也稱為非續(xù)長碼。例如：W：0，10，100，111不是瞬時(shí)可譯碼，100為10的續(xù)長。§ 瞬時(shí)可譯碼一定是單義的，單義可譯碼卻不一定是瞬時(shí)可譯碼。例如：W：0，01是單義的，但不是瞬時(shí)可譯碼。(3) 單義可譯碼定理：設(shè)原始信源符號集為S:s1,s2,sn，碼元符號集為A:a1,a2,aq，碼字集合為W:W1,W2,Wn，其碼長分別為L1,L2,Ln；則單義可譯碼存在的充要條件為碼長組合滿足Kraft不等式，即 § Kraft不等式不僅是單義可譯碼的充要條件，也是瞬時(shí)可譯碼的充要條件；§ 這里所說的充要條件是對于碼長組

5、合而言，而不是對于碼字本身而言，就是說：滿足Kraft不等式的碼長組合一定能構(gòu)成單義碼，單義碼的碼長組合一定滿足Kraft不等式。§ 有些碼字的碼長組合滿足Kraft不等式，但不是單義碼。（編碼方法不對）下面看一個(gè)例子：n=4, q=2 A:0,1信源符號W1W2W3W4W5W6s10000000s2011011101001s30111101001101110s40111111011011111011§ W1:滿足Kraft不等式，但只是單義的，不是瞬時(shí)可譯碼；碼長組合為1,2,3,4；§ W2:滿足Kraft不等式，是單義的，也是瞬時(shí)可譯碼；碼長組合為1,2,3

6、,4；§ W3:滿足Kraft不等式，不是單義的，也不是瞬時(shí)可譯碼；碼長組合為1,2,3,3；§ W4:滿足Kraft不等式，是單義的，也是瞬時(shí)可譯碼；碼長組合為1,2,3,3；§ W5:不滿足Kraft不等式，不可能為單義的；碼長組合為1,2,2,3；§ W6:滿足Kraft不等式，是單義的，也是瞬時(shí)可譯碼；為等長碼；(4) 用碼樹圖構(gòu)成瞬時(shí)可譯碼§ 從根開始，畫出q條分支，任選一個(gè)分支作為W1；§ 在另一個(gè)分支上再分出q條分支，任選一個(gè)分支作為W2；§ 繼續(xù)進(jìn)行，直至結(jié)束；§ 從根到各端點(diǎn)，所經(jīng)過的狀態(tài)即為碼字

7、；例如：A:0,1, q=2, W:W1,W2,W3,W4 根 根 0 1 1 0 W1 0 1 W1 1 0 W2 W2 0 1 1 0 W3 W4 W3 W4§ 這種方法構(gòu)成的瞬時(shí)可譯碼是不唯一的；§ 碼樹圖可以用于譯碼，有根，枝，節(jié)點(diǎn)等概念；§ 同樣可以用于q元編碼；例：S:s1,s2,s9,A=0,1,2, q=3 0 2 W1 1 2 2 W9 0 0 1 0 1 W2 1 2 W5 W6 W8 W3 W4 W7W1=0; W5=20; W9=222;W2=10; W6=21;W3=11; W7=220;W4=12; W8=221;4-1-3 平均碼子長

8、度如果一個(gè)碼組的參數(shù)滿足Kraft不等式，就一定可以構(gòu)成無噪聲信道下的無失真?zhèn)鬏?，然而，在一個(gè)通信系統(tǒng)中，信源編碼的主要目的是提高編碼效率，即每個(gè)碼元符號要攜帶更多的信息量。因此要定義平均碼長的概念。設(shè)原始信源的信源空間為S,P=s1s2snp(s1)p(s2)p(sn)其中：對此信源用碼元符號集A;a1,a2,aq進(jìn)行編碼，得單義可譯碼W：W1，W2，Wn。相應(yīng)得碼字長度分別為：Li,(i=1,2,n)。則這個(gè)信源編碼的平均碼長為：這時(shí)看一下信息傳輸效率：每個(gè)信道碼元所攜帶的平均信息量。當(dāng)信源S給定，信源的熵為H(S)，則每個(gè)信道碼元所攜帶的平均信息量可以表示為可見，當(dāng)原始信源一定時(shí)，編碼后

9、的平均碼長越小，信道傳信率越高，編碼效率越高。§ 編碼效率可以用平均碼長來描述；§ 每個(gè)碼字的長度應(yīng)當(dāng)與對應(yīng)的信源符號的先驗(yàn)概率有關(guān)。為了提高編碼效率，總希望平均碼長越小越好，但平均碼長能否無限小呢？定理: 平均碼長極限定理若一個(gè)離散無記憶信源S的熵為H(S)，對其進(jìn)行q元編碼，A:a1,a2,aq，則總可以找到一種無失真的編碼方法，構(gòu)成單義可譯碼，使其平均碼長滿足：對于常用的二元編碼來說： H(S)L<H(S)+1 下界證明根據(jù)平均碼長和熵的定義有 由單義可譯碼的存在定理可知，當(dāng)滿足q-Li1時(shí)，取對數(shù)后為小于等于0。則有： H(S)-Llogq0 LH(S)/lo

10、gq下界證畢。§ 平均碼長最小不能小于極限值，H(S)/logq，若小于，則不存在單義可譯碼；§ 當(dāng)下界等號成立時(shí)，效率最高時(shí)，為p(si)=q-Li可得：當(dāng)然這要求信源符號的先驗(yàn)概率滿足其是以q為底的對數(shù)為整數(shù)，這就要求信源符號的先驗(yàn)概率為p(si)=q-Li形式，如果滿足這一條件，編出的碼字稱為最佳碼。例如：S:s1,s2,s3,s4; P(S):1/2,1/4,1/8,1/8時(shí)，編碼后碼長為1,2,3,3，這時(shí)平均碼長將為L=H(S)=1.74 碼元/符號。上界證明我們考察在滿足Kraft不等式的條件下，平均碼長滿足下界。設(shè)每個(gè)碼字的平均碼長在以下區(qū)間取正整數(shù)?？紤]到

11、對數(shù)為單調(diào)遞增函數(shù)，則有：進(jìn)而有： 對上式的i連續(xù)取和：即：這表明這樣選擇每個(gè)碼元的碼長可以滿足Kraft不等式，然后對所有的i相加，得:即上界證畢。§ 平均碼長大于這個(gè)上界當(dāng)然也可以構(gòu)成單義可譯碼，但實(shí)際上總希望碼長??；§ 當(dāng)一個(gè)離散無記憶信源得統(tǒng)計(jì)特性確定后，信源熵就確定了，平均編碼長度下界也就確定了，編碼效率也就確定了，如果進(jìn)一步提高效率，就要想其它方法。下面得編碼定理給出了方法。4-2 編碼定理以下是Shannon編碼定理的三種形式。它們是進(jìn)一步提高編碼效率的極限定理。 定理一：離散無記憶信源S的N次擴(kuò)展信源SN，其熵為H(SN)，并且編碼器的碼元符號集為A:a1,

12、a2,aq，對信源SN進(jìn)行編碼，總可以找到一種編碼方法，構(gòu)成單義可譯碼，使信源S中每個(gè)符號si所需要的平均碼長滿足：說明： H(SN)=NH(S)，根據(jù)平均碼長的界限定理有：LN為N次擴(kuò)展信源每個(gè)符號的平均碼長，原始信源的每符號的平均碼長則為則上式可以變?yōu)椋杭吹茫?當(dāng)離散無記憶信源S的擴(kuò)展次數(shù)N足夠大時(shí)，有§ 定理一表明當(dāng)將離散無記憶信源進(jìn)行N次擴(kuò)展后再進(jìn)行編碼，就可以使原始信源每個(gè)符號的平均碼長接近信源熵H(S)，即達(dá)到下限值。§ 這時(shí)就不要求原始信源的先驗(yàn)概率滿足特殊條件了，但卻要求擴(kuò)展次數(shù)N趨于無窮。因此，這也是一個(gè)極限定理，（給出一種不現(xiàn)實(shí)的方法）。 定理二：離散平

13、穩(wěn)各態(tài)歷經(jīng)有記憶信源S的N次擴(kuò)展信源S=S1,S2,SN，其熵為H(S)= H(S1,S2,SN)，并且編碼器的碼元符號集為A:a1,a2,aq，對信源S進(jìn)行編碼，總可以找到一種編碼方法，構(gòu)成單義可譯碼，使信源S中每個(gè)符號所需要的平均碼長滿足：已知N次擴(kuò)展信源的熵為H(S)=H(S1,S2,SN)，根據(jù)平均的界限定理，將上式除以N得：可以注意到：對于平穩(wěn)各態(tài)歷經(jīng)有記憶信源來說，當(dāng)信源穩(wěn)定后，即當(dāng)N趨于無窮時(shí)，每發(fā)一個(gè)符號攜帶的平均信息量等于其極限熵。又考慮到lim(1/N)=0，可知：§ 比較定理一和定理二，由于H(S)H，所以，有記憶信源的平均碼長的下界將小于無記憶信源的平均碼長的

14、下界；§ 對于m階馬爾柯夫信源來說；H=Hm+1(S)，則有：即，記憶長度越長，平均碼長的下界就越小。§ 定理一和定理二說明：可以用信源擴(kuò)展的方法，達(dá)到數(shù)據(jù)壓縮的目的，擴(kuò)展程度越高，編碼效率越高。定理三：設(shè)信源S的熵為H(S)，無噪聲離散信道的信道容量為C。則總可以找到一種編碼方法，使信道上的信源符號平均傳輸速率為C/H(S)-。其中可以是任意小的正數(shù)。要使符號平均傳輸速率大于C/H(S)是不可能的。關(guān)于編碼定理的說明：§ 在編碼前，離散無噪聲信道的信道容量為C，C=r0Hmax(S)，Hmax(S)為信源的最大熵，r為符號傳輸速率，C=Hmax(S)，相當(dāng)于r0

15、=1。§ 在編碼前，離散無噪聲信道的實(shí)際熵速率為R=r0H(S)，這時(shí)的符號傳輸速率就等于r0，單位是原始信源符號數(shù)/每秒。§ 這時(shí)的傳輸效率（編碼效率）：實(shí)際傳輸能力/最大傳輸能力，為： =R/C=H(S)/Hmax(S)對于n個(gè)符號的原始信源，如果不進(jìn)行編碼就相當(dāng)于n元編碼，其最大熵為Hmax(S)=logn; 傳輸效率（編碼效率）=R/C=H(S)/Hmax(S)=H(S)/logn。§ 編碼后，每個(gè)原始信源符號si編成了Li個(gè)信道碼元組成的碼字Wi。編碼器的輸出可以看成一個(gè)新的信源，它有q個(gè)信源符號（信道碼元），每個(gè)信道碼元所攜帶的信息量為H(S)/L。如

16、果將這個(gè)新信源記為A，則H(A)=H(S)/L，如果信道碼元的符號速率為n1，則信道的實(shí)際熵速率為R=r1H(A)=r1H(S)/L。§ 編碼器輸出的碼元符號集共有q個(gè)元素，這個(gè)新信源的最大熵為當(dāng)q個(gè)信道碼元符號為等概率時(shí)，即Hmax(A)=logq，信道容量為C=r1Hmax(A)。§ 這時(shí)編碼器輸出端的傳輸效率（編碼效率）為： =R/C=H(A)/Hmax(A)=H(S)/LHmax(A)=H(S)/Llogq 當(dāng)q=2時(shí)，為二元編碼，logq=1; 傳輸效率就為：=R/C=H(S)/L。§ 這時(shí)從另一個(gè)角度，我們看一下編碼定理中定義的符號傳輸速率，它是指原始

17、信源符號的傳輸速率：即每秒傳輸?shù)脑夹旁捶柕膫€(gè)數(shù)。 實(shí)際符號傳輸速率為：為r0=R/H(S) (比特/秒)/(比特/符號)=(信源符號/秒) 有：r0=R/H(S)C/H(S);編碼定理指出：總可以有方法使R趨進(jìn)于C，并構(gòu)成單義可譯碼，實(shí)際上等效于：L趨于H(S)/logq ?；蛘哒f：編碼后的編碼效率趨于1。§ 由平均碼長界限定理可知，要構(gòu)成單義可以碼，平均碼長有一個(gè)下界： § 結(jié)合這兩個(gè)關(guān)系，可以得到：單義可譯碼的信道碼元符號在離散無噪聲信道上的熵速率（傳信率）就相應(yīng)有一個(gè)上界；§ 我們知道logq是信道碼元符號集A:a1,a2,aq的最大熵，也就是將A看作信

18、源時(shí)，在離散無噪聲信道上的信道容量C，所以有： RC§ 這就是說，要編成單義可譯碼，就不可能使信道傳信率（熵速率）大于信道容量。關(guān)于Shannon編碼第一定理：定理一、定理二和定理三實(shí)際上是同一個(gè)定理，定理一和定理二是針對一個(gè)具體的信源形式，而定理三是一個(gè)概括性的。這個(gè)定理稱為無失真信源編碼定理，也稱為無噪聲信道編碼定理。例4-1：有一個(gè)離散無記憶信源，S:s1,s2, P(S):0.2, 0.8,§ 其原始信源熵為：H(S)=1/5log5+4/5log(5/4)=0.72193 bit/信源符號(si)§ 用二元信道碼元符號A:0,1進(jìn)行編碼，得到碼字W:W1

19、=0, W2=1,這時(shí)的平均碼長為： L=0.2×1+0.8×1=1 信道碼元符號/信源符號。這時(shí)的信道傳信率： R=H(S)/L=0.72193 比特/信道碼元符號。§ 對這個(gè)信源進(jìn)行二次擴(kuò)展，得到S2，對其進(jìn)行二元編碼，得W:W1,W2,W3,W4。SiP(Si)WiS1=S1S11/25000S2=S1S24/25001S3=S2S14/2501S4=S2S216/251這時(shí)的平均碼長為：L2=(16/25)×1+(4/25)×2+(4/25)×3+(1/25)×3=37/27 信道碼元符號/2個(gè)信源符號則相應(yīng)的原始信

20、源每個(gè)信源符號的平均碼長L=L2/2=37/50 信道碼元符號/信源符號§ 這時(shí)的信道傳信率為 R=H(S)/L=0.72193/(37/50)=0.97 比特/信道碼元符號。可以看到：經(jīng)過信源的二次擴(kuò)展，編碼復(fù)雜一點(diǎn)，但使傳信率（編碼效率）明顯提高，可知二元編碼的信道容量為1比特/碼元，當(dāng)擴(kuò)展次數(shù)增加時(shí)，傳信率將無限接近信道容量。4-3 Huffman編碼上面我們看到，通過無失真信源編碼可以使信道傳信率無限接近于信道容量，為了評價(jià)信源編碼的好壞，定義一個(gè)參數(shù)稱為編碼效率：編碼效率是一個(gè)小于等于1的參數(shù)，當(dāng)然編碼效率越高越好，只要保證是單義可譯碼。當(dāng)編碼效率等于1時(shí)稱為最佳碼。4-3

21、-1 Shannon-Fano算法(1) Shannon編碼思想：由于概率的不均勻，使編碼效率下降，因此，可以根據(jù)消息狀態(tài)的概率來確定各碼字的編碼長度，概率大的編成短碼，概率小的編成長碼。最初的Shaanon編碼算法是一種簡單的按概率編碼的方法，對于一個(gè)離散無記憶信源，如果其某一狀態(tài)si的先驗(yàn)概率為p(si)，則就取其碼長為： 其X符號表示為取不小于X的整數(shù)，即 其實(shí)這種方法是滿足Kraft不等式的一種直接的應(yīng)用；例如：一個(gè)離散信源S:s1,s2,s3,s4 p(S):1/2,1/4,1/8,1/8這時(shí)有：L1=log2=1; L2=log4=2; L3=L4=log8=3;利用碼樹圖的方法可

22、以得到其編碼： 0 W1=0 1 0 W2=10 1 0 W3=110 1 W4=111這個(gè)例子可以驗(yàn)證其編碼效率為1，即為最佳碼。但可以發(fā)現(xiàn)，這種方法對于多數(shù)情況下是不能實(shí)現(xiàn)最佳碼的，而且編碼效率比較低。這種算法稱為Shannon算法；后來提出了一種改進(jìn)方法為Shannon-Fano算法。(2) Fano算法的步驟：把原始信源的符號按概率從大到小重新排列；把信源符號按盡可能概率相等分為q組，分別分配給a1,a2,aq碼元；將每個(gè)分組再次分組，直至分完；從左至右將分得的碼元排列即得碼字Wi。算法舉例：設(shè)有一個(gè)離散無記憶信源S；其信源空間為：S:s1s2s3s4s5s6s7s8p(S):0.10

23、.180.40.050.060.10.070.04可知這個(gè)原始信源的熵為：H(S)=-p(si)logp(si)=2.55 bit/原始信源符號。而這時(shí)的最大熵為：Hmax(S)=log8=3 bit/原始信源符號。編碼效率為=R/C=H(S)/Hmax(S)=2.55/3=85%。利用Shannon-Fano算法編碼：sip(si)第一次第二次第三次第四次WiLis30.4000002s20.1801012s10.101001003s60.101011013s70.07110011004s50.06110111014s40.05111011104s80.04111111114這時(shí)可以用碼樹圖

24、描述： 0 0 s3 1 1 s2 0 0 s1 1 1 s6 1 0 s7 0 1 s5 1 s8 s4§ 注意：1，0碼元分配是任意的，因此編碼的結(jié)果是不唯一的；§ 0/1分配的上下順序也是不唯一的，能構(gòu)成不同的單義可譯碼；(3) 關(guān)于編碼效率 編碼前信源熵為H(S)，最大熵為Hmax(S)，熵速率為R=rH(S)，信道容量為C=rHmax(S)；這時(shí)的編碼效率為： 編碼后一個(gè)信源狀態(tài)si對應(yīng)于一個(gè)碼子Wi，Wi的碼長為Li，W的平均碼長為L，一個(gè)碼元的熵為H(A)=H(S)/L，其最大熵為Hmax(A)=logq，熵速率和信道容量分別為R=rH(S)/L, C=rHm

25、ax(A)。這時(shí)的編碼效率為： 對于二元編碼q=2，Hmax(A)=log2=1，同時(shí)考慮到H(S)與H(A)的關(guān)系，有由于L總是大于等于H(S)，因此編碼效率總是小于1。當(dāng)L趨于H(S)時(shí)，編碼效率也趨于1。編碼效率趨于1的過程，就是L趨于H(S)，和R趨于C的過程?？催@個(gè)例題的編碼效率：其平均碼長為L=2.64 信道碼元/信源符號。H(S)=2.55 bit/信源符號。所以可見編碼效率得到提高。§ 如果將信源做n次擴(kuò)展后再進(jìn)行編碼，可以進(jìn)一步提高編碼效率。4-3-2 Shannon-Fano算法的最佳條件同樣是上面的例子，如果我們將原始信源改變一下，信源空間為：S:s1s2s3s

26、4s5s6s7s8p(S):1/41/41/81/81/161/161/161/16可知這個(gè)原始信源的熵為：H(S)=-p(si)logp(si)=2.75 bit/原始信源符號。而這時(shí)的最大熵為：Hmax(S)=log8=3 bit/原始信源符號。編碼效率為=R/C=H(S)/Hmax(S)=2.75/3=91.7%。利用Shannon-Fano算法編碼：sip(si)第一次第二次第三次第四次WiLis11/400002s21/401012s31/81001003s41/81011013s51/16110011004s61/16110111014s71/16111011104s81/1611

27、1111114這時(shí)的平均碼長為L=p(si)Li=2.75 信道碼元/信源符號。編碼效率為： =H(S)/L=2.75/2.75=1， 表明R=C。4-3-3 Huffman算法這種算法比Shannon-Fano算法的效率還要高，稱為最佳編碼算法。(1) 二元Huffman算法的步驟將信源S的n個(gè)符號狀態(tài)s1,s2,sn按概率從大到小排列，作為碼樹圖的葉；將概率最小的兩個(gè)符號分別分配給“0”和“1”碼元，然后其概率相加，合成一個(gè)節(jié)點(diǎn)，作為一個(gè)新的符號，重新與其它符號按概率大小排列；重復(fù)這樣的步驟，一直到處理完全部狀態(tài)；從右到左將分配的碼元排列后即得相應(yīng)得編碼。算法舉例：將上一題的信源編為Huf

28、fman編碼。設(shè)有一個(gè)離散無記憶信源S；其信源空間為：S:s1s2s3s4s5s6s7s8p(S):0.10.180.40.050.060.10.070.04可知這個(gè)原始信源的熵為：H(S)=-p(si)logp(si)=2.55 bit/原始信源符號。而這時(shí)的最大熵為：Hmax(S)=log8=3 bit/原始信源符號。編碼效率為=R/C=H(S)/Hmax(S)=2.55/3=85%。利用Huffman算法編碼：s3 0.4 1s2 0.18 1s1 0.1 (0.37) 0 1.0s6 0.1 0 (0.6) 0s7 0.07 0 (0.23) 1s5 0.06 1 (0.13) (0.

29、19) 0s4 0.05 0 (0.09) 1s8 0.04 1編碼結(jié)果：W3=1 W7=0100W2=001 W5=0101W1=011 W4=00010W6=0000 W8=00011平均碼長L=2.61 碼元/狀態(tài)。編碼效率為可見Huffman編碼比Shannon-Fano編碼可以得到更高的編碼效率。同樣：§ 1/0碼元分配是任意的，因此編碼的結(jié)果是不唯一的；§ 但0/1分配的上下順序在整個(gè)編碼過程中應(yīng)保持一致，否則不能構(gòu)成單義可譯碼；(2) q元Huffman算法首先我們看一個(gè)例子；設(shè)離散信源的信源空間為：對其進(jìn)行 q=3,A:0,1,2編碼。S:s1s2s3s4s

30、5s6p(S):0.240.200.180.160.140.08如果按二元Huffman編碼的方法 Li Wi si p(si) S(1) S(2) S(3) 0 0.62 1 1.0 0.38 0.38 2 2 10 s1 0.24 0.24 0 2 11 s2 0.20 0.20 1 2 12 s3 0.18 0.18 2 2 20 s4 0.16 0 2 21 s5 0.14 1 2 22 s6 0.08 2 可知：平均碼長為L=2 碼元/信源符號。下面我們看一下一種改進(jìn)方法：還是這一個(gè)信源，我們在6個(gè)信源符號的后面再加一個(gè)概率為0的符號，記為s7,同時(shí)有p(s7)=0，這個(gè)符號稱為虛假符號。將信源按7個(gè)符號進(jìn)行三元編碼。 Li Wi si p(si) S(1) S(2) S(3) 0.54 0 2 1 s1 0.24 0.24 0.24 1 1.0 0.22 0.22 2 2 00 s2 0.20 0.20 0 2 01 s3 0.18 0.18 1 2 02 s4 0.16 0.16 2 2 20 s5 0.14 0