無失真信源編碼

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、的碼字為Yi （i = 1, 2, … , n）,碼字Yi 對應的碼長為 Ki（i = 1, 2, …, n ） 。所有的Ki相等為定長碼，記為K, 不相等時為變長碼。單符號對應變長碼的平均碼長,碼符/信源符號,平均碼長和編碼有效性/平均碼長,符號序列信源空間XL其中XL是X的L次擴展。信源符號序列 對應的碼字為Yi （i = 1, 2, … , nL）,碼字Yi 對應的碼長為 Ki（i = 1, 2, …, n

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

17、信源各符號對應的碼字長, 且滿足Kraft不等式。 定長碼: 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,平均碼長和編碼有效性/舉例,變長碼: 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 碼符/信源符號η= 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 碼符/信源符號η= 1.75 ÷ 2.625 = 0.667,平均碼長和編碼有效性,討論1：為什么定長碼的編碼效率小于1，而變長碼的編碼效率能達到1？原因：因為H(X)=1.75，是個小數(shù)，而定長碼的碼長不可能為小數(shù)，所以編碼效率小于1。除非H(X)為整數(shù)。但變長碼的平均碼長可以為小數(shù)，可能等于H(X)。,平均碼

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

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

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

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

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

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

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

27、大于1.6875×107。用變長編碼時，L不需要很大就可以達到相當高的編碼效率而且可實現(xiàn)無失真編碼。,變長編碼定理/舉例,例：設離散無記憶信源的概率空間為其信源熵為L=1定長碼：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個符號,變長編碼定理/舉例,定長碼 XL 00 01 10 11KL = 2碼符/2個信源符號編碼效率：η= H(XL)/KL =H(X)/K = 0.811變長碼 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個信源符號編碼效率：η=H(X)/K = 0.811×32/27=0.961 當 L=3 η=0.985 L=4 η=0.991

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

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

32、當m=2時, log2m =1，則,香農(nóng)編碼,編碼方法： (1)將信源符號消息按其出現(xiàn)概率的大小依次排序。 p(x1)≥ p(x2) … ≥ p(xn)(2)按如下不等式取所對應碼字的碼長為Ki。(3)計算第個 i 消息的累加概率, 以便獲得唯一可譯碼；(4)將累加概率變換為二進制數(shù)；(5)取二進制數(shù)的小數(shù)點后 Ki 位作為符號消息的二進制碼字。,香農(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編碼過程,香農(nóng)編碼/舉例,信源熵：H(X) = 2.61 bit/符號平均碼長編碼效率,費諾編碼,編碼方法： (1)將信源符號消息按其出現(xiàn)概率的大小依次排列。p(x1)≥ p(x2) …

34、 ≥ p(xn)(2)將依次排列的信源符號按其概率分為兩大組 , 使兩個組的概率之和近似相等 , 并對各組賦予一個碼元0和1。(3)按(2)方法將每一大組再分為兩組 , 各組再賦予一個碼元0和1。 (4)如此重復 , 直至每個組只剩一個信源符號為止。(5)信源符號所對應的碼字即為Fano 碼,費諾編碼/舉例,例：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編碼過程,費諾編碼/舉例,信源熵：H(X) = 2.61 bit/符號平均碼長編碼效率,哈夫曼編碼,編碼方法：(1)將信源符號消息按其出現(xiàn)概率的大小依次排序。p(x1)≥ p(x2) … ≥ p(xn)(2)取兩個概率最小的符號分別配以0和1 , 并將這兩個概率

36、相加作為新字母的概率，與未分配的字母重新排序。(3)對重新排序后的兩個概率最小的符號重復(2)的過程。(4)不斷重復上述過程 ,直至最后兩個符號配以 0 和 1為止。(5)從最后一級開始 , 向前返回到各個信源符號所對應的碼元序列 , 即為相應的碼字。,哈夫曼編碼/舉例,例：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編碼過程,,,,,,,,,,,,,,,,,,,,,,哈夫曼編碼/舉例,信源熵：H(X) = 2.61 bit/符號平均碼長編碼效率,哈夫曼編碼,哈夫曼編碼方法得到的碼并非唯一的。原因如下：每次對信源縮減時，賦予信源最后兩個概率最小的符號，用0和1是可以任意的，所以可以得到不同的哈夫曼碼，但不會影響碼字的長度

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

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