講義41信源編碼講解

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

2、，其符號(hào)集為 S:s1,s2, ,sn；si(i=1,2, ；n)而信道所能傳輸?shù)姆?hào)集為 A:a 1,a2, ,aq；編碼器的功能是用符號(hào)集 A 中的 元素，將原始信源的符號(hào) si變換為相應(yīng)的碼字符號(hào) Wi，(i=1,2, ,n，) 所以編碼器輸出端的 符號(hào)集為 W:W 1,W2, ,Wn 。S=原始信源符號(hào)集；A= 碼元符號(hào)集；W=碼字符號(hào)集； (碼組)編碼器S:s1,s2, snW:W 1,W2, WnA:a 1,a2, aqWi=w 1,w2, wLi wi a1,a2, aqLi 為碼字 Wi 的碼元個(gè)數(shù)，稱(chēng)為碼字 Wi 的碼字長(zhǎng)度，簡(jiǎn)稱(chēng)碼長(zhǎng)。q=2 時(shí)，稱(chēng)為二元編碼，否則稱(chēng)為 q

3、元編碼。4-1-2 單義可譯碼 (Uniquely decodable code)(1) 單義可譯碼定義：如果一個(gè)碼組的任一有限長(zhǎng)的碼字序列 (一串碼字) ，只能唯一地被譯成一個(gè)一個(gè)碼字， 則稱(chēng)為單義可譯碼，也稱(chēng)為異前置碼。例如： 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í)可譯碼

4、(非續(xù)長(zhǎng)碼)定義： 如果一個(gè)碼組中的任一個(gè)碼字都不是另一個(gè)碼字的續(xù)長(zhǎng)，或者說(shuō)， 任何一個(gè)碼字后加上若干碼元后都不是碼組中另一個(gè)碼字。則稱(chēng)為瞬時(shí)可譯碼，也稱(chēng)為非續(xù)長(zhǎng)碼。例如： W：0，10，100，111不是瞬時(shí)可譯碼， 100 為 10的續(xù)長(zhǎng)。 瞬時(shí)可譯碼一定是單義的，單義可譯碼卻不一定是瞬時(shí)可譯碼。例如： W：0 ， 01是單義的，但不是瞬時(shí)可譯碼。4-1信息論課程講義(3) 單義可譯碼定理： 設(shè)原始信源符號(hào)集為 S:s1,s2, sn， 碼元符號(hào)集為 A:a1,a2, ,aq，碼字集合為 W:W1,W2, Wn ，其碼長(zhǎng)分別為 L1,L2, ,Ln；則單義可譯碼存在的充要條件為碼長(zhǎng)組合 滿(mǎn)

5、足 Kraft 不等式，即nq L i1i1Kraft 不等式不僅是單義可譯碼的充要條件，也是瞬時(shí)可譯碼的充要條件； 這里所說(shuō)的充要條件是對(duì)于碼長(zhǎng)組合而言，而不是對(duì)于碼字本身而言，就是說(shuō)：滿(mǎn) 足 Kraft 不等式的碼長(zhǎng)組合一定能構(gòu)成單義碼，單義碼的碼長(zhǎng)組合一定滿(mǎn)足 Kraft 不等式。有些碼字的碼長(zhǎng)組合滿(mǎn)足 Kraft 不等式，但不是單義碼。 (編碼方法不對(duì)) 下面看一個(gè)例子：n=4, q=2 A:0,1信源符號(hào)W1W2W3W4W5W6s10000000s2011011101001s30111101001101110s40111111011011111011W1: 滿(mǎn)足 Kraft 不等式，

6、但只是單義的，不是瞬時(shí)可譯碼；碼長(zhǎng)組合為1,2,3,4；W2: 滿(mǎn)足 Kraft 不等式，是單義的，也是瞬時(shí)可譯碼；碼長(zhǎng)組合為1,2,3,4；W3: 滿(mǎn)足 Kraft 不等式，不是單義的，也不是瞬時(shí)可譯碼；碼長(zhǎng)組合為1,2,3,3；W4: 滿(mǎn)足 Kraft 不等式，是單義的，也是瞬時(shí)可譯碼；碼長(zhǎng)組合為1,2,3,3；W5: 不滿(mǎn)足 Kraft 不等式，不可能為單義的；碼長(zhǎng)組合為1,2,2,3；W6: 滿(mǎn)足 Kraft 不等式，是單義的，也是瞬時(shí)可譯碼；為等長(zhǎng)碼；(4) 用碼樹(shù)圖構(gòu)成瞬時(shí)可譯碼從根開(kāi)始，畫(huà)出 q 條分支，任選一個(gè)分支作為 W1 ； 在另一個(gè)分支上再分出 q 條分支，任選一個(gè)分支作

7、為 W2；繼續(xù)進(jìn)行，直至結(jié)束； 從根到各端點(diǎn)，所經(jīng)過(guò)的狀態(tài)即為碼字；例如： A:0,1, q=2, W:W1,W2,W3,W4根根這種方法構(gòu)成的瞬時(shí)可譯碼是不唯一的； 碼樹(shù)圖可以用于譯碼，有根，枝，節(jié)點(diǎn)等概念；同樣可以用于 q 元編碼； 例： S:s1,s2, s9,A=0,1,2, q=34-2信息論課程講義W1=0;W5=20; W9=222;W2=10;W6=21;W3=11;W7=220;W4=12;W8=221;4-1-3 平均碼子長(zhǎng)度如果一個(gè)碼組的參數(shù)滿(mǎn)足 Kraft 不等式，就一定可以構(gòu)成無(wú)噪聲信道下的無(wú)失真?zhèn)鬏敚?然而， 在一個(gè)通信系統(tǒng)中， 信源編碼的主要目的是提高編碼效率，

8、即每個(gè)碼元符號(hào)要攜帶更 多的信息量。因此要定義平均碼長(zhǎng)的概念。設(shè)原始信源的信源空間為S,P=s1s2snp(s1)p(s2)p(sn)n其中： p ( si )aq進(jìn)行編碼，得單義可譯碼 W ：W1 ，W2，Wn 。相 ,。n)則這個(gè)信源編碼的平均碼長(zhǎng)為：nLp(si )Lii1 這時(shí)看一下信息傳輸效率：每個(gè)信道碼元所攜帶的平均信息量。 當(dāng)信源 S給定，信源的熵為 H(S) ，則每個(gè)信道碼元所攜帶的平均信息量可以表示為H (S)R H (X)A;a1,a2,Li,(i=1,2,i1 對(duì)此信源用碼元符號(hào)集 應(yīng)得碼字長(zhǎng)度分別為：L可見(jiàn)，當(dāng)原始信源一定時(shí)，編碼后的平均碼長(zhǎng)越小，信道傳信率越高，編碼效

9、率越高。編碼效率可以用平均碼長(zhǎng)來(lái)描述； 每個(gè)碼字的長(zhǎng)度應(yīng)當(dāng)與對(duì)應(yīng)的信源符號(hào)的先驗(yàn)概率有關(guān)。為了提高編碼效率，總希望平均碼長(zhǎng)越小越好，但平均碼長(zhǎng)能否無(wú)限小呢？ 定理 : 平均碼長(zhǎng)極限定理 若一個(gè)離散無(wú)記憶信源 S的熵為 H(S)，對(duì)其進(jìn)行 q 元編碼， A:a1,a2, aq，則總可以 找到一種無(wú)失真的編碼方法，構(gòu)成單義可譯碼，使其平均碼長(zhǎng)滿(mǎn)足：H ( S ) H ( S ) L1 log q log q對(duì)于常用的二元編碼來(lái)說(shuō)：H(S) LH(S)+1下界證明 根據(jù)平均碼長(zhǎng)和熵的定義有4-3信息論課程講義H(S) Llog qp ( si )log p(si) p(si)Li log qi 1

10、i 1np(si)log i1np(si )log i1nlog q Lii1由單義可譯碼的存在定理可知，當(dāng)滿(mǎn)足np(si )p( si ) log( q Li )i1Liqlogp(si )Lini 1 p(si ) pq(si )q-Li1 時(shí)，取對(duì)數(shù)后為小于等于0。則有：H(S)-Llogq 0L H(S)/logq 下界證畢。平均碼長(zhǎng)最小不能小于極限值，H(S)/logq ，若小于，則不存在單義可譯碼；當(dāng)下界等號(hào)成立時(shí)，效率最高時(shí)，為-Lip(si)=q可得：Lilog p(si) log qlogq p(si) log q1p(si)當(dāng)然這要求信源符號(hào)的先驗(yàn)概率滿(mǎn)足其是以q 為底的對(duì)

11、數(shù)為整數(shù)， 這就要求信源符號(hào)的先驗(yàn)概率為 p(si)=q -Li 形式，如果滿(mǎn)足這一條件，編出的碼字稱(chēng)為最佳碼。例如： S:s1,s2,s3,s4; P(S):1/2,1/4,1/8,1/8 時(shí)，編碼后碼長(zhǎng)為 1,2,3,3 ，這時(shí)平均碼長(zhǎng)將 為 L=H(S)=1.74 碼元 / 符號(hào)。 上界證明 我們考察在滿(mǎn)足 Kraft 不等式的條件下，平均碼長(zhǎng)滿(mǎn)足下界。 設(shè)每個(gè)碼字的平均碼長(zhǎng)在以下區(qū)間取正整數(shù)。(i1, 2 ,. n)log q p(si) Li log q p(si ) 1考慮到對(duì)數(shù)為單調(diào)遞增函數(shù)，則有：1 Liqp ( si )qp ( si )( i1,2 ,.,n)進(jìn)而有：對(duì)上式

12、的p( si) q Lii 連續(xù)取和：np(si )i1p( si)qni1Li(ini11,2 ,., np(si )q即：這表明這樣選擇每個(gè)碼元的碼長(zhǎng)可以滿(mǎn)足n1i1Kraft 不等式，然后對(duì)所有的Liqi 相加，得 :4-4信息論課程講義n n np(si)Li p( si )log q p(si) p(si)i 1 i 1 i 1即H (S)L H q(S) 1 1q log q上界證畢。平均碼長(zhǎng)大于這個(gè)上界當(dāng)然也可以構(gòu)成單義可譯碼，但實(shí)際上總希望碼長(zhǎng)小； 當(dāng)一個(gè)離散無(wú)記憶信源得統(tǒng)計(jì)特性確定后，信源熵就確定了，平均編碼長(zhǎng)度下界也 就確定了，編碼效率也就確定了，如果進(jìn)一步提高效率，就要想

13、其它方法。下面得 編碼定理給出了方法。4-2 編碼定理以下是 Shannon 編碼定理的三種形式。它們是進(jìn)一步提高編碼效率的極限定理。 定理一 ：離散無(wú)記憶信源 S 的 N 次擴(kuò)展信源 SN ，其熵為 H(SN)，并且編碼器的碼元 符號(hào)集為 A:a 1,a2, aq ，對(duì)信源 SN 進(jìn)行編碼， 總可以找到一種編碼方法， 構(gòu)成單義可譯碼， 使信源 S中每個(gè)符號(hào) si 所需要的平均碼長(zhǎng)滿(mǎn)足：lim L Hq(S)Nq說(shuō)明：H(SN)=NH(S) ，根據(jù)平均碼長(zhǎng)的界限定理有：H(SN ) LH(SN ) 1L N 1log q log qLN為 N次擴(kuò)展信源每個(gè)符號(hào)的平均碼長(zhǎng)，原始信源的每符號(hào)的平均

14、碼長(zhǎng)則為L(zhǎng)NL則上式可以變?yōu)椋杭吹茫篘H(SN ) LNH(SN ) 1N log qNN log q NH (S)H (S) 1Llog qlog q N當(dāng)離散無(wú)記憶信源S 的擴(kuò)展次數(shù) N 足夠大時(shí)，有l(wèi)im LNH(S) log qHq(S)定理一表明當(dāng)將離散無(wú)記憶信源進(jìn)行 N 次擴(kuò)展后再進(jìn)行編碼，就可以使原始信源每 個(gè)符號(hào)的平均碼長(zhǎng)接近信源熵 H(S) ，即達(dá)到下限值。這時(shí)就不要求原始信源的先驗(yàn)概率滿(mǎn)足特殊條件了， 但卻要求擴(kuò)展次數(shù) N 趨于無(wú)窮。 因此，這也是一個(gè)極限定理， (給出一種不現(xiàn)實(shí)的方法) 。 定理二 ：離散平穩(wěn)各態(tài)歷經(jīng)有記憶信源 S 的 N 次擴(kuò)展信源 S=S 1,S2,

15、SN ，其熵為 H(S)= H(S1,S2, SN)，并且編碼器的碼元符號(hào)集為 A:a1,a2,aq，對(duì)信源 S進(jìn)行編碼，總 可以找到一種編碼方法，構(gòu)成單義可譯碼，使信源S 中每個(gè)符號(hào)所需要的平均碼長(zhǎng)滿(mǎn)足：4-5信息論課程講義lim LNlog qH ( S )1log q 1H ( S)N log q可以注意到：對(duì)于平穩(wěn)各態(tài)歷經(jīng)有記憶信源來(lái)說(shuō)， 每發(fā)一個(gè)符號(hào)攜帶的平均信息量等于其極限熵。1lim H(S1,S2,.SN) lim H(SN 1 / S1, S2,.SN ) HN N N又考慮到 lim(1/N)=0 ，可知：LNNH ( S) N log q 當(dāng)信源穩(wěn)定后，即當(dāng)N 趨于無(wú)窮時(shí)

16、，已知 N 次擴(kuò)展信源的熵為 H(S)=H(S 1,S2, ,SN)，根據(jù)平均的界限定理，H ( S )LNlog q將上式除以 N 得：Hlim L N log qH(S)H，所以，有記憶信源的平均碼長(zhǎng)的下界將小于H =Hm+1(S) ，則有：H m 1比較定理一和定理二，由于 無(wú)記憶信源的平均碼長(zhǎng)的下界； 對(duì)于 m 階馬爾柯夫信源來(lái)說(shuō)；lim N log q即，記憶長(zhǎng)度越長(zhǎng)，平均碼長(zhǎng)的下界就越小。定理一和定理二說(shuō)明：可以用信源擴(kuò)展的方法，達(dá)到數(shù)據(jù)壓縮的目的，擴(kuò)展程度越 高，編碼效率越高。定理三 ：設(shè)信源 S 的熵為 H(S)，無(wú)噪聲離散信道的信道容量為 C。則總可以找到一 種編碼方法，使信

17、道上的信源符號(hào)平均傳輸速率為C/H(S)- 。其中可以是任意小的正數(shù)。要使符號(hào)平均傳輸速率大于 C/H(S) 是不可能的。關(guān)于編碼定理的說(shuō)明 ：在編碼前， 離散無(wú)噪聲信道的信道容量為 C，C=r0Hmax(S)，Hmax(S)為信源的最大熵， r 為符號(hào)傳輸速率， C=H max(S) ，相當(dāng)于 r0=1。在編碼前， 離散無(wú)噪聲信道的實(shí)際熵速率為 R=r0H(S) ，這時(shí)的符號(hào)傳輸速率就等于 r0，單位是原始信源符號(hào)數(shù) /每秒。這時(shí)的傳輸效率(編碼效率) ：實(shí)際傳輸能力 /最大傳輸能力，為： =R/C=H(S)/H max (S)對(duì)于 n 個(gè)符號(hào)的原始信源，如果不進(jìn)行編碼就相當(dāng)于n 元編碼，其

18、最大熵為Hmax(S)=logn; 傳輸效率(編碼效率) =R/C=H(S)/H max(S)=H(S)/logn 。 編碼后，每個(gè)原始信源符號(hào) si 編成了 Li 個(gè)信道碼元組成的碼字 Wi 。編碼器的輸出 可以看成一個(gè)新的信源，它有 q 個(gè)信源符號(hào)(信道碼元) ，每個(gè)信道碼元所攜帶的 信息量為 H(S)/L 。如果將這個(gè)新信源記為 A ，則 H(A)=H(S)/L ，如果信道碼元的符 號(hào)速率為 n1，則信道的實(shí)際熵速率為 R=r 1H(A)=r 1H(S)/L 。 編碼器輸出的碼元符號(hào)集共有 q個(gè)元素，這個(gè)新信源的最大熵為當(dāng) q 個(gè)信道碼元符 號(hào)為等概率時(shí)，即 Hmax(A)=logq ，

19、信道容量為 C=r1Hmax(A) 。4-6信息論課程講義這時(shí)編碼器輸出端的傳輸效率(編碼效率)為： =R/C=H(A)/H max(A)=H(S)/LH max(A)=H(S)/Llogq當(dāng) q=2 時(shí)，為二元編碼， logq=1; 傳輸效率就為： =R/C=H(S)/L 。 這時(shí)從另一個(gè)角度，我們看一下編碼定理中定義的符號(hào)傳輸速率，它是指原始信源 符號(hào)的傳輸速率：即每秒傳輸?shù)脑夹旁捶?hào)的個(gè)數(shù)。實(shí)際符號(hào)傳輸速率為：為 r0=R/H(S) ( 比特/秒)/(比特/符號(hào))=(信源符號(hào) /秒) 有： r0=R/H(S) C/H(S);編碼定理指出：總可以有方法使 R 趨進(jìn)于 C，并構(gòu)成單義可譯碼

20、， 實(shí)際上等效于： L 趨于 H(S)/logq 。或者說(shuō)：編碼后的編碼效率趨于 1。由平均碼長(zhǎng)界限定理可知，要構(gòu)成單義可以碼，平均碼長(zhǎng)有一個(gè)下界：H (S )Llog q結(jié)合這兩個(gè)關(guān)系，可以得到：?jiǎn)瘟x可譯碼的信道碼元符號(hào)在離散無(wú)噪聲信道上的熵速率(傳信率)就相應(yīng)有一個(gè)上界；H (S)H (S)LH (S)log qlog q我們知道 logq 是信道碼元符號(hào)集 A:a1,a2, a的q最大熵， 也就是將 A 看作信源時(shí)， 在離散無(wú)噪聲信道上的信道容量 C，所以有：RC這就是說(shuō)，要編成單義可譯碼，就不可能使信道傳信率(熵速率)大于信道容量。關(guān)于 Shannon 編碼第一定理：定理一、 定理二和

21、定理三實(shí)際上是同一個(gè)定理， 定理一和定理二是針對(duì)一個(gè)具體的信源 形式， 而定理三是一個(gè)概括性的。 這個(gè)定理稱(chēng)為無(wú)失真信源編碼定理， 也稱(chēng)為無(wú)噪聲信道編 碼定理。例 4-1：有一個(gè)離散無(wú)記憶信源， S:s1,s2, P(S):0.2, 0.8, 其原始信源熵為： H(S)=1/5log5+4/5log(5/4)=0.72193 bit/ 信源符號(hào) (si) 用二元信道碼元符號(hào) A:0,1 進(jìn)行編碼，得到碼字 W:W1=0, W2=1, 這時(shí)的平均碼 長(zhǎng)為： L=0.2 1+0.81=1 信道碼元符號(hào) /信源符號(hào)。這時(shí)的信道傳信率：R=H(S)/L=0.72193 比特 /信道碼元符號(hào)。對(duì)這個(gè)信源

22、進(jìn)行二次擴(kuò)展，得到 S2，對(duì)其進(jìn)行二元編碼，得 W:W 1,W2,W3,W4 。SiP(Si)WiS1=S1S11/25000S2=S1S24/25001S3=S2S14/2501S4=S2S216/251這時(shí)的平均碼長(zhǎng)為：L2=(16/25)1+(4/25)2+(4/25)3+(1/25)3=37/27 信道碼元符號(hào) /2 個(gè)信源符號(hào) 則相應(yīng)的原始信源每個(gè)信源符號(hào)的平均碼長(zhǎng)L=L 2/2=37/50 信道碼元符號(hào) /信源符號(hào)4-7信息論課程講義這時(shí)的信道傳信率為R=H(S)/L=0.72193/(37/50)=0.97 比特 /信道碼元符號(hào)。 可以看到：經(jīng)過(guò)信源的二次擴(kuò)展，編碼復(fù)雜一點(diǎn)，但使

23、傳信率(編碼效率)明顯提高， 可知二元編碼的信道容量為 1比特 /碼元，當(dāng)擴(kuò)展次數(shù)增加時(shí)，傳信率將無(wú)限接近信道容量。4-3 Huffman 編碼上面我們看到， 通過(guò)無(wú)失真信源編碼可以使信道傳信率無(wú)限接近于信道容量， 為了評(píng)價(jià) 信源編碼的好壞，定義一個(gè)參數(shù)稱(chēng)為編碼效率：RC編碼效率是一個(gè)小于等于 1 的參數(shù)，當(dāng)然編碼效率越高越好，只要保證是單義可譯碼。 當(dāng)編碼效率等于 1 時(shí)稱(chēng)為最佳碼。4-3-1 Shannon-Fano 算法(1) Shannon 編碼思想： 由于概率的不均勻， 使編碼效率下降， 因此， 可以根據(jù)消息狀態(tài)的概率來(lái)確定各碼字的 編碼長(zhǎng)度，概率大的編成短碼，概率小的編成長(zhǎng)碼。最初

24、的 Shaanon 編碼算法是一種簡(jiǎn)單的按概率編碼的方法，對(duì)于一個(gè)離散無(wú)記憶信源， 如果其某一狀態(tài) si 的先驗(yàn)概率為 p(si)，則就取其碼長(zhǎng)為：1Li logp(si)其X符號(hào)表示為取不小于 X 的整數(shù)，即11log Li log 1p(si) p(si )W2=10W3=110其實(shí)這種方法是滿(mǎn)足 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; 利用碼樹(shù)圖的方法可以得到其編碼：W4=111這個(gè)例子可以驗(yàn)證其編碼效率為下是不能實(shí)現(xiàn)最

25、佳碼的，而且編碼效率比較低。1，即為最佳碼。但可以發(fā)現(xiàn)，這種方法對(duì)于多數(shù)情況這種算法稱(chēng)為 Shannon算法；后來(lái)提出了一種改進(jìn)方法為 Shannon-Fano 算法。(2) Fano 算法的步驟： 把原始信源的符號(hào)按概率從大到小重新排列； 把信源符號(hào)按盡可能概率相等分為q 組，分別分配給 a1,a2, aq碼元； 將每個(gè)分組再次分組，直至分完； 從左至右將分得的碼元排列即得碼字Wi 。4-8信息論課程講義 算法舉例 ：設(shè)有一個(gè)離散無(wú)記憶信源 S；其信源空間為：S: s1 s2 s3 s4 s5 s6 s7 s8p(S): 0.1 0.18 0.4 0.05 0.06 0.1 0.07 0.0

26、4 可知這個(gè)原始信源的熵為：H(S)=- p(si)logp(si)=2.55 bit/ 原始信源符號(hào)。 而這時(shí)的最大熵為： Hmax(S)=log8=3 bit/ 原始信源符號(hào)。 編碼效率為 =R/C=H(S)/H max(S)=2.55/3=85% 。利用 Shannon-Fano 算法編碼：sip(si)第一次第二次s30.4000s20.1801s10.1010s60.1010s70.0711s50.0611s40.0511s80.0411第三次第四次WiLi00201201003110130011004011101410111041111114這時(shí)可以用碼樹(shù)圖描述：注意： 1，0 碼

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

28、A)0 C Hmax(A) log q對(duì)于二元編碼 q=2， Hmax(A)=log2=1 ，同時(shí)考慮到 H(S)與 H(A) 的關(guān)系，有4-9信息論課程講義L由于 L 總是大于等于 H(S) ，因此編碼效率總是小于 1。當(dāng) L 趨于 H(S) 時(shí)，編碼效率也 趨于 1。編碼效率趨于 1的過(guò)程，就是 L 趨于 H(S) ，和 R 趨于 C 的過(guò)程。 看這個(gè)例題的編碼效率： 其平均碼長(zhǎng)為 L=2.64 信道碼元 /信源符號(hào)。 H(S)=2.55 bit/ 信源符號(hào)。所以H(S)9.66%R H 2( A) H ( S) C H 2 max ( A ) L可見(jiàn)編碼效率得到提高。如果將信源做 n 次

29、擴(kuò)展后再進(jìn)行編碼，可以進(jìn)步提高編碼效率。4-3-2 Shannon-Fano 算法的最佳條件同樣是上面的例子，如果我們將原始信源改變一下，信源空間為：S: s1s2s3s4s5s6s7s8p(S): 1/4 1/4 1/8 1/8 1/16 1/16 1/16 1/16 可知這個(gè)原始信源的熵為： H(S)=- p(si)logp(si)=2.75 bit/ 原始信源符號(hào)。 而這時(shí)的最大熵為： Hmax(S)=log8=3 bit/ 原始信源符號(hào)。編碼效率為 =R/C=H(S)/H max(S)=2.75/3=91.7% 。利用 Shannon-Fano 算法編碼：sip(si)第一次第二次第三

30、次第四次WiLis11/400002s21/401012s31/81001003s41/81011013s51/16110011004s61/16110111014s71/16111011104s81/16111111114這時(shí)的平均碼長(zhǎng)為 L= p(si)Li=2.75 信道碼元 /信源符號(hào)。編碼效率為： =H(S)/L=2.75/2.75=1 ， 表明 R=C。4-3-3 Huffman 算法這種算法比 Shannon-Fano 算法的效率還要高，稱(chēng)為最佳編碼算法。(1) 二元 Huffman 算法的步驟 將信源 S 的 n 個(gè)符號(hào)狀態(tài) s1,s2, sn按 概率從大到小排列，作為碼樹(shù)圖的

31、葉； 將概率最小的兩個(gè)符號(hào)分別分配給“ 0”和“ 1”碼元，然后其概率相加，合成一個(gè)節(jié) 點(diǎn)，作為一個(gè)新的符號(hào)，重新與其它符號(hào)按概率大小排列； 重復(fù)這樣的步驟，一直到處理完全部狀態(tài)； 從右到左將分配的碼元排列后即得相應(yīng)得編碼。 算法舉例 ：將上一題的信源編為 Huffman 編碼。設(shè)有一個(gè)離散無(wú)記憶信源 S；其信源空間為：4-10信息論課程講義S: s1 s2s3s4s5s6p(S): 0.1 0.180.4 0.050.060.1可知這個(gè)原始信源的熵為：H(S)=- p(si)logp(si)=2.55 bit/原始信源符號(hào)。而這時(shí)的最大熵為： Hmax(S)=log8=3 bit/ 原始信源

32、符號(hào)。 編碼效率為 =R/C=H(S)/H max(S)=2.55/3=85% 。利用 Huffman 算法編碼：s7s80.070.041.0編碼結(jié)果：W3=1W2=001W1=011W6=0000 平均碼長(zhǎng) L=2.61W7=0100W5=0101W4=00010W8=00011碼元 /狀態(tài)。編碼效率為R H 2( A) H (S) 2.55C H 2 max ( A ) L 2.6197 .8%可見(jiàn) Huffman 編碼比 Shannon-Fano 編碼可以得到更高的編碼效率。同樣：S:s1s2s3s4s5s6p(S):0.240.200.180.160.140.081/0 碼元分配是任

33、意的，因此編碼的結(jié)果是不唯一的；但 0/1 分配的上下順序在整個(gè)編碼過(guò)程中應(yīng)保持一致，否則不能構(gòu)成單義可譯碼； (2) q 元 Huffman 算法 首先我們看一個(gè)例子；設(shè)離散信源的信源空間為：對(duì)其進(jìn)行 q=3,A:0,1,2 編碼。如果按二元 Huffman 編碼的方法LiWisi222222101112202122s1s2s3s4s5s60.62 10.38 24-11S(3)01.0信息論課程講義可知：平均碼長(zhǎng)為 L=2 碼元 /信源符號(hào)。 下面我們看一下一種改進(jìn)方法： 還是這一個(gè)信源，我們?cè)?6 個(gè)信源符號(hào)的后面再加一個(gè)概率為0 的符號(hào)，記為 s7同,時(shí)有 p(s7 )=，0這個(gè)符號(hào)稱(chēng)為虛假符號(hào)。將信源按7個(gè)符號(hào)進(jìn)行三元編碼。LiWisip(s