信源編碼精品課件

1、信源編碼第1頁，共43頁，2022年，5月20日，1點29分，星期一信源編碼：以提高通信有效性為目的的編碼。通過壓縮信源的冗余度來實現(xiàn)。采用的一般方法是壓縮每個信源符號的平均比特數(shù)或信源的碼率。即同樣多的信息用較少的碼率傳送，使單位時間內(nèi)傳送的平均信息量增加，從而提高通信的有效性。信道編碼：是以提高信息傳輸?shù)目煽啃詾槟康牡木幋a。通過增加信源的冗余度來實現(xiàn)。采用的一般方法是增大碼率/帶寬。與信源編碼正好相反。加密編碼：是以提高通信系統(tǒng)的安全性為目的的編碼。通過加密和解密來實現(xiàn)。從信息論的觀點出發(fā)，“加密”可視為增熵的過程，“解密”可視為減熵的過程。第2頁，共43頁，2022年，5月20日，1點2

2、9分，星期一一、信源的符號集和符號序列信源符號集：信源發(fā)出的符號消息的集合，記為X；設(shè)X 有n個符號：X = x1 , x2 , , xn .信源符號序列：由信源符號集合X中的符號組成長度為L的符號序列，記為 。 L為信源符號序列長 , 不同的符號序列共有 nL。 若L=1，則信源符號序列為信源符號集合中的符號。信源編碼器信道 碼表 5.1 信源編碼的基本概念第3頁，共43頁，2022年，5月20日，1點29分，星期一二、 碼元和碼字 1碼元(符)集 信道可傳輸?shù)幕痉柕募? 記為Y；設(shè) Y 有m個符號： Y= y1 , y2 , , ym ，其中 yi 稱為碼元或碼符。 m 元信道: 可

3、傳輸m個基本符號的信道。 二元信道: 可傳輸 2個基本符號的信道。這是一種最常用的信道, 其基本符號常用 0 , 1 表示。 2 碼字: 由碼元組成的序列稱為碼字，記為Y i 。 碼字Y i 的碼元個數(shù) Ki 稱為Y i的碼長。 所有碼字Y i 的碼長 Ki 均相等稱為碼長為 K 定長碼。 碼字Y i 的碼長 Ki 不全相等稱為變長碼。第4頁，共43頁，2022年，5月20日，1點29分，星期一三、 編碼與譯碼1信源編碼：將信源符號xi 或符號序列XLi 按一種規(guī)則映像成碼字Yi的過程。2無失真編碼：信源符號到碼字的映射必須一一對應(yīng)。3譯碼：從碼符號到信源符號的映射。4碼表：所有映射規(guī)則的集合

4、。四、許用碼和禁用碼1許用碼字：信源符號xi或符號序列XLi與碼字Y i定義對應(yīng)關(guān)系的碼字。2禁用碼字：信源符號xi或符號序列XLi與碼字Y i未定義對應(yīng)關(guān)系的碼字。3許用碼字的全體稱為碼集第5頁，共43頁，2022年，5月20日，1點29分，星期一五、分組碼（塊碼）分類1按碼字的碼長分類定長碼：碼集中所有碼字的碼長相等。變長碼：碼集中所有碼字的碼長不全相等。2按信源符號與碼字對應(yīng)關(guān)系分類非奇異碼：信源符號與碼字是一一對應(yīng)的，碼2。奇異碼：信源符號與碼字不是一一對應(yīng)的，碼1。3按譯碼唯一性分類唯一可譯碼：對于多個碼字組成的有限長碼流，只能唯一地分割成一個個的碼字。唯一可譯碼又稱為單義碼。非唯一

5、可譯碼：對有限長碼流，不能唯一地分割成一個個的碼字。信源符號ai碼1碼2a100a21110a30000a41101奇異碼與非奇異碼第6頁，共43頁，2022年，5月20日，1點29分，星期一 【例】 碼流 100111000 碼1 x10 x210 x311 可分割10, 0, 11, 10, 0, 0 x2 x1 x3 x2 x1 x1 碼2 x11 x210 x311 則無法唯一分割。4按譯碼的即時性分類 非即時碼：接收端收到一個完整的碼字后，不能立即譯碼，還需要等到下一個碼字開始接收后才能判斷是否可以譯碼。 即時碼：接收端收到一個完整的碼字后，就能立即譯碼，即時碼又稱為非延長碼或異前綴

6、碼。 【例】 非即時碼 碼流 01001100 x10 x201 x311 譯碼為 x2x1x1x3x1? 即時碼 碼流 01001100 x10 x210 x311 譯碼為 x1x2x1x3x1x1信源符號ai碼1碼2a110a21001a3100001a410000001即時碼與唯一可譯碼即時碼第7頁，共43頁，2022年，5月20日，1點29分，星期一 異前綴碼(即時碼)：碼集中任何一個碼不是其他碼的前綴。 即時碼必定是唯一可譯碼, 唯一可譯碼不一定是即時碼。 5有實用價值的分組碼 分組碼：將信源符號集中的每個信源符號固定地映射成一個碼字。 是非奇異碼、唯一可譯碼、即時碼 。 六、碼樹圖

7、 1碼樹圖: 用碼樹來描述給定碼集中各碼字的方法。 2碼樹圖的樹根、樹枝、節(jié)點 中間節(jié)點（一級節(jié)點、二級節(jié)點 ）用表示, 終端節(jié)點用表示。第8頁，共43頁，2022年，5月20日，1點29分，星期一 3二元（進制）碼樹 【例 1】 x11 x201 x300 A 0 1 x1 【例 2】 x11 x210 x311 0 1 x2 A 1 1 x3 x1 0 1 x2 x3第9頁，共43頁，2022年，5月20日，1點29分，星期一4用碼樹圖構(gòu)造碼 在樹的生長過程中，中間節(jié)點生出樹枝，各樹枝標出相應(yīng)的碼元，為了清晰起見，相同碼元的樹枝方向相同，終端節(jié)點表示信源符號，從樹根到終端節(jié)點所經(jīng)過的樹枝旁

8、的碼元按經(jīng)過的順序組成的序列構(gòu)成碼字。5用碼樹圖構(gòu)造即時碼的條件 如果表示信源符號的終端節(jié)點不再延伸，這樣構(gòu)造的碼滿足即時碼條件。七、唯一可譯碼存在的條件1前提條件：非奇異碼第10頁，共43頁，2022年，5月20日，1點29分，星期一2唯一可譯碼存在定理 設(shè)n為信源符號或信源符號序列個數(shù)，m為碼元個數(shù)，Ki 為信源各符號或信源符號序列對應(yīng)的碼長。則唯一可譯碼存在的充分和必要條件是滿足Kraft不等式 【注意】 Kraft不等式是一個存在定理，不是唯一可譯碼的判定定理; 如果n 、m、Ki 滿足Kraft不等式，則存在唯一可譯碼;如果是唯一可譯碼, 則n 、m、Ki 必定滿足Kraft不等式。

9、第11頁，共43頁，2022年，5月20日，1點29分，星期一一、平均碼長和編碼有效性 1 平均碼長 單符號信源空間，其中 信源符號 xi 對應(yīng)的碼字為Yi （i = 1, 2, , n），碼字Yi 對應(yīng)的碼長為 K i（i = 1, 2, , n ） 。 所有的 K i 相等為定長碼，記為K, 不相等時為變長碼。 單符號對應(yīng)變長碼的平均碼長為 碼符/信源符號5.2 離散信源編碼第12頁，共43頁，2022年，5月20日，1點29分，星期一符號序列信源空間XL 其中XL是X的L次擴展。 信源符號序列 對應(yīng)的碼字為Yi （i = 1, 2, , nL），碼字Yi 對應(yīng)的碼長為 K i（i = 1

10、, 2, , n L） 。 符號序列對應(yīng)變長碼的平均碼長為 碼符/信源符號序列 碼符/信源符號第13頁，共43頁，2022年，5月20日，1點29分，星期一2 編碼效率（碼率） 定義：平均一個碼符所攜帶的平均信息量稱為編碼效率， 記作。概率匹配原則：概率大的編短碼，概率小的編長碼。按照概率匹配原則編碼可以提高編碼效率。第14頁，共43頁，2022年，5月20日，1點29分，星期一【例 5.2.1】信源空間 H(X) = ( 1/2 log1/21/4 log1/41/8 log1/81/8 log1/8 ) =1.75bit/消息 信源符號個數(shù)為n=4，二元碼符0 , 1，碼符個數(shù)為m=2，K

11、i為信源各符號對應(yīng)的碼字長, 且滿足Kraft不等式。 定長碼: K1= K2= K3= K4=2 2-2+2-2+2-2+2-2=1 碼字: Y1=00 , Y2=01 , Y3=10 , Y4=11 變長碼: K1=1, K2=2, K3=3, K4=3 2-1+2-2+2-3+2-3=1 碼字: Y1=0 , Y2=10 , Y3=110 , Y4=111第15頁，共43頁，2022年，5月20日，1點29分，星期一定長碼 x100 x201 x310 x411 K=2 = 1.75 2 = 0.825變長碼 方案1 : x10 x210 x3110 x4111 =11/2+21/4+3

12、1/8+31/8=1.75 碼符/信源符號 = 1.75 1.75 = 1 方案2 : x1111 x2110 x310 x40 = 31/2+31/4+21/8+11/8 =2.625 碼符/信源符號 = 1.75 2.625 = 0.667比較方案1、2.第16頁，共43頁，2022年，5月20日，1點29分，星期一 二、定長編碼定理 1 定長編碼定理 信源 X有n個信源符號 , 其 L 次擴展信源為XL , 信源熵 為 H(XL) , 信源 XL 中的信源符號序列均用碼長為 KL的碼字對其進行編碼，H(X) = H(XL)/L , 對任意0, 0 , 只要當L足夠大時, 必定可使譯碼碼小

13、于。若譯碼差錯一定是有限值 , 當L足夠大時,譯碼必定出錯。 第17頁，共43頁，2022年，5月20日，1點29分，星期一2 切比雪夫不等式 設(shè)隨機變量有數(shù)學期望M及方差D, 則對任何正數(shù)，不等式 成立。3 定長編碼 L 的計算計算隨機變量I(xi)的數(shù)學期望MI(xi)，即H(X) ；計算I(xi)的方差2(X) 。 第18頁，共43頁，2022年，5月20日，1點29分，星期一 計算符號序列長度L 若已知編碼效率和譯碼錯誤概率第19頁，共43頁，2022年，5月20日，1點29分，星期一三、變長編碼定理 1 平均碼長的界限變長編碼定理 符號信源空間 Y1 Y2 Yn 對應(yīng) K1 K2 K

14、n。 m為碼符個數(shù)，則存在唯一可譯碼，使其平均碼長滿足如下 不等式第20頁，共43頁，2022年，5月20日，1點29分，星期一證明：若 xi 按如下不等式取所對應(yīng)碼字的碼長為Ki若 為整數(shù), 則上述不等式左邊取等號。 故可得 第21頁，共43頁，2022年，5月20日，1點29分，星期一 因為 所以 所有碼字長度滿足Kraft不等式。 如何降低平均碼長： （1） 減少信源熵H(X) ； （2） 增加信道碼元數(shù) m。第22頁，共43頁，2022年，5月20日，1點29分，星期一2 離散平穩(wěn)無記憶序列變長編碼定理 信源 X 的 L 次擴展信源 XL XL 的信源熵為： H(XL) bit/L個信

15、源符號 XL 所對應(yīng)碼字的碼長為 碼符/L個信源符號 因為 ， 所以 ，當L時 第23頁，共43頁，2022年，5月20日，1點29分，星期一【例5.2.2】 H(X)=0.811 bit/符號 定長碼 x10， x21 K=1 編碼效率 =H(X)/K = 0.811序列：L=2， XL x1x1 x1x2 x2x1 x2x2 p(XL) 9/16 3/16 3/16 1/16 H(XL)=1.622 bit/2個符號 序列的定長碼 Y 00 01 10 11 K 2 2 2 2 編碼效率 = H(XL)/KL =H(X)/K = 0.811第24頁，共43頁，2022年，5月20日，1點2

16、9分，星期一序列的變長碼 Y 0 10 110 111 Ki 1 2 3 3 = 1 9/16+2 3/16 + 3 3/16 +3 1/16 = 27/16 = 1.6875 碼符/ 2個信源符號編碼效率 =H(X)/K = 0.81132/27=0.961 當 L=3 =0.985 L=4 =0.991采用擴展信源提高編碼效率帶來的問題： (1) 碼表迅速擴大 (2) 需求內(nèi)存大 (3) 譯碼延時第25頁，共43頁，2022年，5月20日，1點29分，星期一三、信息傳輸效率 1 平均信息率R 平均每個碼元所含有的信息量。單位: bit/碼元 2 碼元傳輸率 碼元速率(RB) ：每秒鐘傳輸碼

17、元的數(shù)目.單位: 波特(B) 碼元時間長度(TB) : TB= 1/RB ，單位: 秒(s) 3 平均信息傳輸率Rt 平均每秒鐘傳輸?shù)男畔⒘縍t = R / TB 單位: bit/s第26頁，共43頁，2022年，5月20日，1點29分，星期一四、最佳編碼 最佳碼：能載荷一定信息量，碼字的平均碼長最短, 可分離的碼字集合。 編碼思路：對概率大的信息符號編以短碼，對概率小 的信息符號編以長碼 。 這種編碼方法稱為統(tǒng)計編碼，熵編碼，概率匹配編碼。1 Shannon 編碼方法 若 xi 按如下不等式取所對應(yīng)碼字的碼長為Ki 當m等于 2 時 , log m =1，則 第27頁，共43頁，2022年，

18、5月20日，1點29分，星期一Shannon 編碼過程: 將信源符號消息按其出現(xiàn)概率的大小依次排序 p(x1) p(x2) p(xn) 按如下不等式取所對應(yīng)碼字的碼長為Ki 計算第 i個消息的累加概率, 以便獲得唯一可譯碼 將累加概率變換為二進制數(shù)； 取二進制數(shù)的小數(shù)點后 Ki 位作為符號消息的二進制碼。第28頁，共43頁，2022年，5月20日，1點29分，星期一【例5.2.3】 xi x1 x2 x3 x4 x5 x6 x7 p(xi) 0.20 0.19 0.18 0.17 0.15 0.10 0.01解：信源熵 H(X) = 2.61 bit/符號 平均碼長 編碼效率第29頁，共43頁

19、，2022年，5月20日，1點29分，星期一xip(xi)I(xi)KiPiPi二進制碼字x10.202.32300.0000000 x20.192.4030.200.0011001x30.182.4730.390.0110011x40.172.5630.570.1001100 x50.152.7430.740.1011101x60.103.3240.890.111001110 x70.016.6470.990.111111011111110Shannon 編碼過程【例5.2.3】 xi x1 x2 x3 x4 x5 x6 x7 p(xi) 0.20 0.19 0.18 0.17 0.15 0

20、.10 0.01第30頁，共43頁，2022年，5月20日，1點29分，星期一 2 費諾（Fano ）編碼方法將信源符號消息按其出現(xiàn)概率的大小依次排列 p(x1) p(x2) p(xn) 將依次排列的信源符號按其概率分為兩大組 , 使兩個組的概率之和近似相等 , 并對各組賦予一個碼元0和1 。按前一步將每一大組再分為兩組, 各組再賦予一個碼元0和1 。如此重復(fù) , 直至每個組只剩一個信源符號為止。信源符號所對應(yīng)的碼字即為Fano 碼。第31頁，共43頁，2022年，5月20日，1點29分，星期一【例5.2.4】 Fano 編碼過程xip(xi)第1次第2次第3次第4次碼字碼長x0.200000

21、2x20.190100103x30.180110113x40.1710102x50.151101103x60.10111011104x70.01111111114平均碼長編碼效率第32頁，共43頁，2022年，5月20日，1點29分，星期一3 Huffman編碼方法將信源符號消息按其出現(xiàn)概率的大小依次排序 p(x1) p(x2) p(xn)取兩個概率最小的符號分別配以0和1, 并將這兩個概率相加作為新符號的概率,與未分配的符號重新排序。對重新排序后的兩個概率最小的符號重復(fù)(2)的過程 。不斷重復(fù)上述過程，至最后兩個符號配以 0 和 1為止。從最后一級開始 , 向前返回到各個信源符號所對應(yīng)的碼元

22、序列，即為相應(yīng)的Huffman碼。 第33頁，共43頁，2022年，5月20日，1點29分，星期一【例5.2.5】 x p(xi) 編 碼 過 程 碼字 x1 0.20 0.20 0.26 0.35 0.39 0.61 0 10 x2 0.19 0.19 0.20 0.26 0.35 0 0.39 1 11x3 0.18 0.18 0.19 0.20 0 0.26 1 000 x4 0.17 0.17 0.18 0 0.19 1 001x5 0.15 0.15 0 0.17 1 010 x6 0.10 0 0.11 1 0110 x7 0.01 1 0111平均碼長編碼效率第34頁，共43頁，

23、2022年，5月20日，1點29分，星期一Huffman編碼方法并不唯一，因為：每次對縮減信源兩個概率最小的符號分配“0”和“1”碼元是任意的，所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性，即能得到可分離碼字。不同的碼元分配，得到的具體碼字不同，但碼長ki不變，平均碼長也不變，所以沒有本質(zhì)區(qū)別?？s減信源時，若合并后的新符號概率與其他符號概率相等，從編碼方法上來說，這幾個符號的次序可任意排列，編出的碼都是正確的，但得到的碼字不相同。不同的編碼方法得到的 碼字長度ki也不盡相同。第35頁，共43頁，2022年，5月20日，1點29分，星期一x p(xi) 編 碼 過 程 碼字 x

24、1 0.4 0.4 0.4 0.6 0 1 0 1x2 0.2 0.2 0.4 0 0.4 1 01 x1x3 0.2 0.2 0 0.2 1 000 0 1 x4 0.1 0 0.2 1 0010 x2X5 0.1 1 0011 0 1 x3 x1 0.4 0.4 0.4 0.6 0 00 0 1x2 0.2 0.2 0.4 0 0.4 1 10 x4 x5x3 0.2 0.2 0 0.2 1 11x4 0.1 0 0.2 1 100 x5 0.1 1 101 【例5.2.6】下面一組：概率相同時總是放在前面。上面一組：概率相同時總是放在后面。第36頁，共43頁，2022年，5月20日，1點

25、29分，星期一平均碼長編碼效率Huffman編碼的特點： 1)最佳變長碼； 2) Huffman編碼不是唯一的； 3)碼方差小的Huffman編碼質(zhì)量好。碼方差對于例5.2.6 第37頁，共43頁，2022年，5月20日，1點29分，星期一m元Huffman編碼方法：信源符號個數(shù)n必須滿足n=(m-1)k+m （1） （k表示縮減次數(shù)）不滿足（1）式時，設(shè)一些概率為0的虛假符號，使其滿足。將信源符號以概率遞減的次序排列。給m個概率最小的信源符號各分配一位碼元，并將它們合并成一個新符號，m個最小概率之和作為新符號的概率，并與未分配的符號重新排序，并把所得新符號盡可能排列在靠前位置上，這樣所得碼的方差最小。對重新排序后的m個概率最小的符號重復(fù)上步過程 。不斷重復(fù)上述過程，直至縮減信源只剩m個符號為止。從最后一級開始 , 向前返回到各個信源符號所對應(yīng)的碼元序列 , 即為相應(yīng)的m元Huffman碼。 第38頁，共43頁，2022年，5月20日，1點29分，星期一香農(nóng)碼、費諾碼、哈夫曼碼都考慮了信源的統(tǒng)計