無(wú)失真信源編碼

1、第三章 無(wú)失真信源編碼,3.1 編碼的相關(guān)概念3.2 定長(zhǎng)編碼定理3.3 變長(zhǎng)編碼定理3.4 最佳編碼,無(wú)失真信源編碼,為什么要對(duì)進(jìn)行編碼？1.信源發(fā)出的消息符號(hào)可能不適合信道的傳輸，將信源發(fā)出的消息符號(hào)轉(zhuǎn)換為適合信道傳輸?shù)姆?hào)。2.信源消息確定后，提高通信的有效性--信源編碼。3.提高通信的可靠性 , 編碼具有發(fā)現(xiàn)錯(cuò)誤或糾正錯(cuò)誤的抗干擾能力---信道編碼 。4.提高通信的安全性---加密編碼。,3.1 編碼的相關(guān)概念,

2、3.1.1 信源編碼的定義3.1.2 信源編碼的研究方法3.1.3 編碼相關(guān)概念3.1.4 唯一可譯碼的存在條件,編碼的相關(guān)概念,信源編碼的定義信源編碼定義：指定能夠滿足信道特性/適合于信道傳輸?shù)姆?hào)序列/碼序列，來(lái)代表信源輸出的消息。完成編碼功能的器件稱為編碼器。離散信源輸出的碼序列離散信源輸出的消息是由一個(gè)個(gè)離散符號(hào)組成的隨機(jī)序列——信源符號(hào)序列；X=(X1X2…Xl…XL) Xl∈{x1,x2,…,xi,…x

3、n}信源編碼就是把信源輸出的隨機(jī)符號(hào)序列變成碼序列。Y=(Y1Y2…Yk…YK) Yk∈{y1,y2,…,yj,…ym},信源編碼的研究方法,研究方法研究信源編碼時(shí)，將信道編碼和譯碼看成是信道的一部分，而突出信源編碼；,信道,信源編碼的研究方法,研究信道編碼時(shí)，將信源編碼和譯碼看成是信源和信宿的一部分，而突出信道編碼。,信源,信宿,信源編碼的研究方法,討論無(wú)失真信源編碼可以先不考慮抗干擾問(wèn)題，所以它的數(shù)學(xué)模型比較簡(jiǎn)單，如圖所

4、示。,編碼相關(guān)概念,碼元和碼字碼元(符)集：信道可傳輸?shù)幕痉?hào)的集合, 記為Y; 設(shè) Y 有m個(gè)符號(hào)：Y={y1,y2,…,ym}，其中yi稱為碼元或碼符。m 元信道: 可傳輸m個(gè)基本符號(hào)的信道；二元信道: 可傳輸 2個(gè)基本符號(hào)的信道。這是一種最常用的信道, 基本符號(hào)常用 0 , 1 表示。碼字: 由碼元組成的序列稱為碼字，記為Yi 。碼字Yi的碼元個(gè)數(shù) Ki 稱為Yi的碼長(zhǎng)。所有碼字Yi的碼長(zhǎng) Ki 均相等稱為

5、定長(zhǎng)碼。碼字Yi的碼長(zhǎng) Ki不全相等稱為變長(zhǎng)碼。,編碼相關(guān)概念,編碼與譯碼信源編碼：將信源符號(hào)xi或符號(hào)序列X按一種規(guī)則映射成碼字Yj的過(guò)程。無(wú)失真編碼：信源符號(hào)到碼字的映射必須一一對(duì)應(yīng)。譯碼：從碼符號(hào)到信源符號(hào)的映射。碼表：所有映射規(guī)則的集合。,編碼相關(guān)概念,許用碼和禁用碼許用碼字：信源的符號(hào)xi或符號(hào)序列X與碼字Yj定義了對(duì)應(yīng)關(guān)系的碼字。禁用碼字：信源的符號(hào)xi或符號(hào)序列X與碼字Yj未定義對(duì)應(yīng)關(guān)系的碼字。許用碼字的全

6、體稱為碼集。,編碼相關(guān)概念,分組碼（塊碼）分類按碼字的碼長(zhǎng)分類定長(zhǎng)碼：碼集中所有碼字的碼長(zhǎng)相等。變長(zhǎng)碼：碼集中所有碼字的碼長(zhǎng)不全相等。按信源符號(hào)與碼字對(duì)應(yīng)關(guān)系分類非奇異碼：信源符號(hào)與碼字是一一對(duì)應(yīng)的。奇異碼：信源符號(hào)與碼字不是一一對(duì)應(yīng)的。,編碼相關(guān)概念/分類,按譯碼唯一性分類唯一可譯碼：對(duì)于多個(gè)碼字組成的有限長(zhǎng)碼流，只能唯一地分割一個(gè)個(gè)的碼字。唯一可譯碼又稱為單義碼。唯一可譯碼在傳輸過(guò)程中不需要同步碼。 非唯一可譯碼：

7、對(duì)有限長(zhǎng)碼流，不能唯一地分割一個(gè)個(gè)的碼字。例：碼流 100111000 …碼1：x1→0 x2→10 x3→11 可分割10, 0, 11, 10, 0, 0碼2：x1→1 x2→10 x3→11 則無(wú)法唯一分割,編碼相關(guān)概念/分類,按譯碼的即時(shí)性分類非即時(shí)碼：接收端收到一個(gè)完整的碼字后，不能立即譯碼；還需要等到下一個(gè)碼字開(kāi)始接收后才能判斷是否可以譯碼。即時(shí)碼：接收端收到一個(gè)完整的碼字后，就能立即譯碼；即時(shí)碼又稱為非

8、延長(zhǎng)碼或異前綴碼。例：非即時(shí)碼 ，碼流 01001100 … x1→0 x2→01 x3→11 譯碼為 x2, x1, x1, x3, x1, ?即時(shí)碼，碼流 01001100 …x1→0 x2→10 x3→11 譯碼為 x1, x2, x1, x3, x1, x1,結(jié)論：即時(shí)碼指的是碼集任何一個(gè)碼不能是其他碼的前綴，即時(shí)碼必定是唯一可譯碼, 唯一可譯碼不一定是即時(shí)碼。,編碼相關(guān)概念/分類/舉例,例：碼1

9、：顯然不是惟一可譯碼。x2和x4對(duì)應(yīng)于同一碼字“11”，碼1本身是一個(gè)奇異碼。碼2：是非奇異碼，不是惟一可譯碼。當(dāng)收到一串碼符號(hào)“01000”時(shí)，可將它譯成“x4 x3 x1”，也可譯為“x4x1x3”， “x1x2x3”或“x1x2x1x1”等，這種碼從單個(gè)碼字來(lái)看雖然不是奇異的，單從有限長(zhǎng)的碼序列來(lái)看，它仍然是一個(gè)奇異碼。碼3：雖然是惟一可譯碼，但它要等到下一個(gè)“1”收到后才能確定碼字的結(jié)束，譯碼有延時(shí)。碼4：既是惟一可譯碼，

10、又沒(méi)有譯碼延時(shí)。碼字中的符號(hào)“1”起了逗點(diǎn)的作用，故稱為逗點(diǎn)碼。,前綴條件碼/異前置碼/異字頭碼/逗點(diǎn)碼/即時(shí)碼/非延長(zhǎng)碼：如果一個(gè)碼的任何一個(gè)碼字都不是其它碼字的前綴。,唯一可譯碼的存在條件,碼樹(shù)圖碼樹(shù)圖: 用碼樹(shù)來(lái)描述給定碼集各碼字的方法。碼樹(shù)圖有樹(shù)根、樹(shù)枝、節(jié)點(diǎn)：一般中間節(jié)點(diǎn)（一級(jí)節(jié)點(diǎn)、二級(jí)節(jié)點(diǎn)… ）用○表示, 終端節(jié)點(diǎn)用●表示。傳輸m個(gè)基本符號(hào)信道的碼可用。例：二元（進(jìn)制）碼樹(shù),x1→1 x2→01 x3→001

11、,唯一可譯碼的存在條件/碼樹(shù)圖,如果節(jié)點(diǎn)過(guò)多，也可以用如下方法表示碼樹(shù)圖。,唯一可譯碼的存在條件/碼樹(shù)圖,用碼樹(shù)圖構(gòu)造碼的方法在樹(shù)的生長(zhǎng)過(guò)程中，中間節(jié)點(diǎn)生出樹(shù)枝，各樹(shù)枝標(biāo)出相應(yīng)的碼元；為了清晰起見(jiàn)相同碼元的樹(shù)枝方向相同，終端節(jié)點(diǎn)表示信源符號(hào)； 從樹(shù)根到終端節(jié)點(diǎn)所經(jīng)過(guò)的樹(shù)枝旁的碼元按經(jīng)過(guò)的順序組成的序列構(gòu)成碼字。用碼樹(shù)圖構(gòu)造即時(shí)碼的條件如果表示信源符號(hào)的終端節(jié)點(diǎn)不再延伸，即信源符號(hào)都在終端節(jié)點(diǎn)上，這樣構(gòu)造的碼滿足即時(shí)碼條件。,唯

12、一可譯碼的存在條件,前提條件：非奇異碼唯一可譯碼存在定理：設(shè)n為信源符號(hào)或信源符號(hào)序列個(gè)數(shù)，m 為碼元個(gè)數(shù)或進(jìn)制數(shù)，Ki 為信源各符號(hào)或信源符號(hào)序列對(duì)應(yīng)的碼長(zhǎng); 則唯一可譯碼存在的充分和必要條件是滿足Kraft不等式：注意：Kraft不等式是一個(gè)存在定理，不是唯一可譯碼的判定定理。如果n 、m、Ki 滿足該不等式, 則存在唯一可譯碼如果是唯一可譯碼, 則n 、m、Ki 必定滿足該不等式。,唯一可譯碼的存在條件,例：設(shè)二進(jìn)

13、制碼樹(shù)中X∈{x1,x2,x3,x4}，K1=1，K2=2，K3=2，K4=3，應(yīng)用上述判斷定理，可得,因此，不存在滿足這種Ki的唯一可譯碼,用樹(shù)碼進(jìn)行檢查如圖所示。,唯一可譯碼的存在條件,信息率若信源輸出符號(hào)序列長(zhǎng)度L≥1變換成由KL個(gè)符號(hào)組成的碼序列/碼字變換要求：能夠無(wú)失真或無(wú)差錯(cuò)地從Y恢復(fù)X，同時(shí)傳送Y時(shí)所需要的信息率最小。,唯一可譯碼的存在條件/信息率,Yk有m種可能值，能編成的碼字個(gè)數(shù)所以平均每個(gè)符號(hào)輸出的最

14、大信息量為logm，KL長(zhǎng)碼字最大信息量為KLlogm。用該碼字表示長(zhǎng)度為L(zhǎng)的信源序列，則送出一個(gè)信源符號(hào)所需要的信息率平均為,所謂信息率最小，就是找到一種編碼方式使KLlogm/L最小。,幾個(gè)問(wèn)題：信息率最小為多少時(shí)，才能無(wú)失真譯碼？若小于這個(gè)信息率是否還能無(wú)失真譯碼？,3.2 定長(zhǎng)編碼定理,3.2.1 平均碼長(zhǎng)和編碼有效性3.2.2 定長(zhǎng)編碼定理,平均碼長(zhǎng)和編碼有效性,平均碼長(zhǎng)單符號(hào)信源空間，其中信源符號(hào) xi 對(duì)應(yīng)

15、的碼字為Yi （i = 1, 2, … , n）,碼字Yi 對(duì)應(yīng)的碼長(zhǎng)為 Ki（i = 1, 2, …, n ） 。所有的Ki相等為定長(zhǎng)碼，記為K, 不相等時(shí)為變長(zhǎng)碼。單符號(hào)對(duì)應(yīng)變長(zhǎng)碼的平均碼長(zhǎng),碼符/信源符號(hào),平均碼長(zhǎng)和編碼有效性/平均碼長(zhǎng),符號(hào)序列信源空間XL其中XL是X的L次擴(kuò)展。信源符號(hào)序列 對(duì)應(yīng)的碼字為Yi （i = 1, 2, … , nL）,碼字Yi 對(duì)應(yīng)的碼長(zhǎng)為 Ki（i = 1, 2, …, n

16、L） 。符號(hào)序列對(duì)應(yīng)變長(zhǎng)碼的平均碼長(zhǎng),碼符/信源符號(hào)序列,碼符/信源符號(hào),平均碼長(zhǎng)和編碼有效性/編碼效率,編碼效率（碼率）定義：平均一個(gè)碼符所攜帶的平均信息量稱為編碼效率，記作η；,平均碼長(zhǎng)和編碼有效性,例：信源空間 H(X) = - ( 1/2 log1/2+1/4 log1/4+1/8 log1/8+1/8 log1/8 ) =1.75 bit/消息信源符號(hào)個(gè)數(shù)為n=4，二元碼符{0 , 1}, 碼符個(gè)數(shù)為m=2，Ki為

17、信源各符號(hào)對(duì)應(yīng)的碼字長(zhǎng), 且滿足Kraft不等式。 定長(zhǎng)碼: K1= K2= K3= K4=2 2-2+2-2+2-2+2-2=1 碼字: Y1=00 , Y2=01 , Y3=10 , Y4=11編碼效率η= H(X)/K=1.75 ÷ 2 = 0.825,平均碼長(zhǎng)和編碼有效性/舉例,變長(zhǎng)碼: K1=1, K2=2, K3=3, K4=3 滿足不等式：2-1+2-2+2-3+

18、2-3=1 碼字: Y1=0 , Y2=10 , Y3=110 , Y4=111方案1 : x1→0，x2→10，x3→110，x4→111 =1×1/2+2×1/4+3×1/8+3×1/8=1.75 碼符/信源符號(hào)η= 1.75 ÷ 1.75 = 1方案2 : x1→111，x2→110，x3→10，x4→0 =

19、3×1/2+3×1/4+2×1/8+1×1/8 =2.625 碼符/信源符號(hào)η= 1.75 ÷ 2.625 = 0.667,平均碼長(zhǎng)和編碼有效性,討論1：為什么定長(zhǎng)碼的編碼效率小于1，而變長(zhǎng)碼的編碼效率能達(dá)到1？原因：因?yàn)镠(X)=1.75，是個(gè)小數(shù)，而定長(zhǎng)碼的碼長(zhǎng)不可能為小數(shù)，所以編碼效率小于1。除非H(X)為整數(shù)。但變長(zhǎng)碼的平均碼長(zhǎng)可以為小數(shù)，可能等于H(X)。,平均碼

20、長(zhǎng)和編碼有效性,討論2：編碼后碼字集合確定，符號(hào)對(duì)應(yīng)的碼字長(zhǎng)度不同，為什么編碼效率不同？原因：不同符號(hào)的先驗(yàn)概率不同，對(duì)應(yīng)的碼字長(zhǎng)度不同，計(jì)算出的平均碼長(zhǎng)也不同，編碼效率也就不同?？偨Y(jié)：一般情況下，變長(zhǎng)編碼的編碼效率可能達(dá)到1；對(duì)于變長(zhǎng)編碼，若概率大的符號(hào)對(duì)應(yīng)短碼,概率小的符號(hào)對(duì)應(yīng)長(zhǎng)碼，編碼效率越高；反之越低。這也是后面最佳編碼的思路。,定長(zhǎng)編碼定理,定理：由L個(gè)符號(hào)組成的、每個(gè)符號(hào)的熵為HL(X)的無(wú)記憶平穩(wěn)信源符號(hào)序列X1

21、X2…Xl…XL，可用KL個(gè)符號(hào)（每個(gè)符號(hào)有m種可能值）進(jìn)行定長(zhǎng)編碼。對(duì)任意ε＞0，δ＞0，只要 則當(dāng)L足夠大時(shí)，必可使譯碼差錯(cuò)小于δ；反之，當(dāng) 時(shí)，譯碼差錯(cuò)一定是有限值，而當(dāng)L足夠大時(shí)，譯碼幾乎必定出錯(cuò)。,定長(zhǎng)編碼定理,定理中的公式改寫(xiě)成表明：不等式左邊表示長(zhǎng)為KL的碼字能載荷的最大信息量，右邊代表長(zhǎng)為L(zhǎng)的信源序列平均攜帶的信息量。所以定長(zhǎng)編碼定理告訴我們：只要碼字傳輸?shù)男畔⒘看笥谛旁磾y帶的信息量，總

22、可實(shí)現(xiàn)幾乎無(wú)失真編碼。,定長(zhǎng)編碼定理,信源熵HL(X)就是一個(gè)界限/臨界值。當(dāng)編碼器輸出的信息率超過(guò)這個(gè)臨界值時(shí)，就能無(wú)失真譯碼，否則就不行。信源編碼定理從理論上說(shuō)明了編碼效率接近于1，即 的理想編碼器的存在性，代價(jià)是在實(shí)際編碼時(shí)取無(wú)限長(zhǎng)的信源符號(hào)(L→∞)進(jìn)行統(tǒng)一編碼。只要δ足夠小，就可實(shí)現(xiàn)幾乎無(wú)失真譯碼；若ε足夠小，編碼效率就接近于1。說(shuō)明：定長(zhǎng)編碼定理是在平穩(wěn)無(wú)記憶離散信源的條件下論證的，但它同樣

23、適用于平穩(wěn)有記憶信源，只是要求有記憶信源的極限熵和極限方差存在即可。對(duì)于平穩(wěn)有記憶信源，定理中的熵應(yīng)改為極限熵。,定長(zhǎng)編碼定理,定長(zhǎng)編碼 L 計(jì)算隨機(jī)變量I(xi)；I(xi)的數(shù)學(xué)期望M[ I(xi) ]，即H(X) ；I(xi)的方差 σ2(X)；符號(hào)序列長(zhǎng)度L；已知編碼效率η和譯碼錯(cuò)誤概率δ。,定長(zhǎng)編碼定理,例：設(shè)單符號(hào)信源模型為信源熵為：H(X)=2.55(比特/符號(hào))自信息方差為：σ2(x)=1.323

24、若要求編碼效率為90%，即譯碼差錯(cuò)率為δ=10-6，則由此可見(jiàn)：在差錯(cuò)率和效率要求都不苛刻的情況下，就必須有1600多萬(wàn)個(gè)信源符號(hào)一起編碼，技術(shù)實(shí)現(xiàn)非常困難。,3.3 變長(zhǎng)編碼定理,,變長(zhǎng)編碼定理,單個(gè)符號(hào)變長(zhǎng)編碼定理：若一離散無(wú)記憶信源的符號(hào)熵為H(X)，每個(gè)信源符號(hào)用m進(jìn)制碼元進(jìn)行變長(zhǎng)編碼，一定存在一種無(wú)失真編碼方法，其碼字平均長(zhǎng)度K滿足下列不等式,變長(zhǎng)編碼定理/單符號(hào),證明：若 xi 按如下不等式取所對(duì)應(yīng)碼字的碼長(zhǎng)為Ki

25、 ,若 為整數(shù) , 則上述不等式左邊取等號(hào)。 故可得：,變長(zhǎng)編碼定理/單符號(hào),,∴所有碼字長(zhǎng)度滿足Kraft不等式。,如何降低平均碼長(zhǎng)：1、減少信源熵H(X)2、增加信道碼元數(shù)m,變長(zhǎng)編碼定理,離散平穩(wěn)無(wú)記憶序列變長(zhǎng)編碼定理：對(duì)于平均符號(hào)熵為HL(X)的離散平穩(wěn)無(wú)記憶信源，必存在一種無(wú)失真編碼方法，使平均信息率K滿足不等式：證明：信源 X 的 L 次

26、擴(kuò)展信源XLXL 的信源熵為H(XL) bit/L個(gè)信源符號(hào)XL 所對(duì)應(yīng)碼字的碼長(zhǎng) 碼符/L個(gè)信源符號(hào),,變長(zhǎng)編碼定理/證明,,編碼效率的下界：,碼的剩余度：,變長(zhǎng)編碼定理/舉例,例：設(shè)單符號(hào)信源模型為其信息熵為：H(X)=2.55(比特/符號(hào))這里m=2，log2m=1要求η>90%，則,結(jié)論：與定長(zhǎng)編碼相比，對(duì)同一信源，要求編碼效率都達(dá)到90%時(shí)，變長(zhǎng)編碼只需L=4進(jìn)行編碼，而等長(zhǎng)碼則要求L

27、大于1.6875×107。用變長(zhǎng)編碼時(shí)，L不需要很大就可以達(dá)到相當(dāng)高的編碼效率而且可實(shí)現(xiàn)無(wú)失真編碼。,變長(zhǎng)編碼定理/舉例,例：設(shè)離散無(wú)記憶信源的概率空間為其信源熵為L(zhǎng)=1定長(zhǎng)碼：x1→0，x2→1，則K=1 編碼效率：η=H(X)/K = 0.811L=2XL x1x1 x1x2 x2x1 x2x2 p(XL) 9/16 3/16

28、 3/16 1/16H(XL)=1.622 bit/2個(gè)符號(hào),變長(zhǎng)編碼定理/舉例,定長(zhǎng)碼 XL 00 01 10 11KL = 2碼符/2個(gè)信源符號(hào)編碼效率：η= H(XL)/KL =H(X)/K = 0.811變長(zhǎng)碼 Y 0 10 110 111 Ki 1

29、 2 3 3 = 1× 9/16+2× 3/16 + 3× 3/16 +3× 1/16 = 27/16 = 1.6875 碼符/ 2個(gè)信源符號(hào)編碼效率：η=H(X)/K = 0.811×32/27=0.961 當(dāng) L=3 η=0.985 L=4 η=0.991

30、,采用擴(kuò)展信源提高編碼效率帶來(lái)的問(wèn)題： 1.碼表迅速擴(kuò)大；2.需求內(nèi)存大；3.譯碼延時(shí)。,變長(zhǎng)編碼定理,信息傳輸效率平均信息率R：平均每個(gè)碼元所含有的信息量。單位: bit/碼元碼元傳輸率/碼元速率(RB) : 每秒鐘傳輸碼元的數(shù)目。單位: 波特(B) 碼元時(shí)間長(zhǎng)度(TB) : TB= 1/RB單位: 秒(s) 平均信息傳輸率(Rt):平均每秒鐘傳輸?shù)男畔⒘俊?單

31、位: bit/sRt = R / TB,3.4 最佳編碼,3.4.1 香農(nóng)編碼3.4.2 費(fèi)諾編碼3.4.3 哈夫曼編碼,最佳編碼,最佳碼：能載荷一定信息量, 且碼字的平均碼長(zhǎng)最短, 可分離的碼字集合。編碼思路：對(duì)概率大的信息符號(hào)編以短碼；對(duì)概率小的信息符號(hào)編以長(zhǎng)碼。目的：使平均碼字長(zhǎng)度最短。這種編碼方法稱為統(tǒng)計(jì)編碼/熵編碼/概率匹配編碼。,最佳編碼,香農(nóng)編碼若單個(gè)字符xi按如下不等式取所對(duì)應(yīng)碼字的碼長(zhǎng)為Ki

32、當(dāng)m=2時(shí), log2m =1，則,香農(nóng)編碼,編碼方法： (1)將信源符號(hào)消息按其出現(xiàn)概率的大小依次排序。 p(x1)≥ p(x2) … ≥ p(xn)(2)按如下不等式取所對(duì)應(yīng)碼字的碼長(zhǎng)為Ki。(3)計(jì)算第個(gè) i 消息的累加概率, 以便獲得唯一可譯碼；(4)將累加概率變換為二進(jìn)制數(shù)；(5)取二進(jìn)制數(shù)的小數(shù)點(diǎn)后 Ki 位作為符號(hào)消息的二進(jìn)制碼字。,香農(nóng)編碼/舉例,例：xi x1 x

33、2 x3 x4 x5 x6 x7 p(xi) 0.20 0.19 0.18 0.17 0.15 0.10 0.01編碼過(guò)程,香農(nóng)編碼/舉例,信源熵：H(X) = 2.61 bit/符號(hào)平均碼長(zhǎng)編碼效率,費(fèi)諾編碼,編碼方法： (1)將信源符號(hào)消息按其出現(xiàn)概率的大小依次排列。p(x1)≥ p(x2) …

34、 ≥ p(xn)(2)將依次排列的信源符號(hào)按其概率分為兩大組 , 使兩個(gè)組的概率之和近似相等 , 并對(duì)各組賦予一個(gè)碼元0和1。(3)按(2)方法將每一大組再分為兩組 , 各組再賦予一個(gè)碼元0和1。 (4)如此重復(fù) , 直至每個(gè)組只剩一個(gè)信源符號(hào)為止。(5)信源符號(hào)所對(duì)應(yīng)的碼字即為Fano 碼,費(fèi)諾編碼/舉例,例：xi x1 x2 x3 x4 x5 x6

35、 x7 p(xi) 0.20 0.19 0.18 0.17 0.15 0.10 0.01編碼過(guò)程,費(fèi)諾編碼/舉例,信源熵：H(X) = 2.61 bit/符號(hào)平均碼長(zhǎng)編碼效率,哈夫曼編碼,編碼方法：(1)將信源符號(hào)消息按其出現(xiàn)概率的大小依次排序。p(x1)≥ p(x2) … ≥ p(xn)(2)取兩個(gè)概率最小的符號(hào)分別配以0和1 , 并將這兩個(gè)概率

36、相加作為新字母的概率，與未分配的字母重新排序。(3)對(duì)重新排序后的兩個(gè)概率最小的符號(hào)重復(fù)(2)的過(guò)程。(4)不斷重復(fù)上述過(guò)程 ,直至最后兩個(gè)符號(hào)配以 0 和 1為止。(5)從最后一級(jí)開(kāi)始 , 向前返回到各個(gè)信源符號(hào)所對(duì)應(yīng)的碼元序列 , 即為相應(yīng)的碼字。,哈夫曼編碼/舉例,例：xi x1 x2 x3 x4 x5 x6 x7 p(

37、xi) 0.20 0.19 0.18 0.17 0.15 0.10 0.01編碼過(guò)程,,,,,,,,,,,,,,,,,,,,,,哈夫曼編碼/舉例,信源熵：H(X) = 2.61 bit/符號(hào)平均碼長(zhǎng)編碼效率,哈夫曼編碼,哈夫曼編碼方法得到的碼并非唯一的。原因如下：每次對(duì)信源縮減時(shí)，賦予信源最后兩個(gè)概率最小的符號(hào)，用0和1是可以任意的，所以可以得到不同的哈夫曼碼，但不會(huì)影響碼字的長(zhǎng)度

38、。對(duì)信源進(jìn)行縮減時(shí)，兩個(gè)概率最小的符號(hào)合并后的概率與其它信源符號(hào)的概率相同時(shí)，這兩者在縮減信源中進(jìn)行概率排序，其放置次序是可以任意的，故會(huì)得到不同的哈夫曼碼。此時(shí)將影響碼字的長(zhǎng)度，一般將合并的概率放在上面，這樣可獲得較小的碼方差。,哈夫曼編碼/舉例,例：設(shè)有離散無(wú)記憶信源方法一：將合并的概率放在下面。,哈夫曼編碼/舉例,方法二：將合并的概率放在上面。,結(jié)論：哈夫曼碼的平均碼長(zhǎng)相等，編碼效率也相等。但是兩種碼的質(zhì)量不完全相同，可

39、用碼方差來(lái)表示。碼方差越小，越接近平均碼長(zhǎng)，質(zhì)量越好。,哈夫曼編碼/舉例,碼方差：,哈夫曼編碼,特點(diǎn)：最佳變長(zhǎng)碼；編碼不是唯一的；碼方差小的編碼質(zhì)量好。局限性：只能用近似的整數(shù)位來(lái)表示單個(gè)符號(hào)，而不是理想的小數(shù)位。需要知道輸入符號(hào)集的概率分布。,本章小結(jié),1、非奇異碼、唯一可譯碼、即時(shí)碼等相關(guān)概念；2、定長(zhǎng)編碼定理和變長(zhǎng)編碼定理；3、最佳編碼：香農(nóng)編碼、費(fèi)諾編碼和哈夫曼編碼的編碼方法。（重點(diǎn)）,作業(yè),3-13-73-