中南大學信息論與編碼課件Inf_T_C_64N

1、信息論與編碼張祖平/Zhang Zuping電子信息工程系School of Information Science and Engineering,Central South University ,InformationTheory & Coding2013 秋季 信息11Inf Theory & Coding-張祖平2本章主要內(nèi)容 (Main Content )6.1 單義可譯碼6.2 非延長碼6.3 單義可譯定理6.4 平均碼長與有效性6.5 平均碼長的界限定理6.8 霍夫曼（Huffman）編碼6.0 編碼概述6.6 香農(nóng)碼6.7 費諾碼2013 秋季 信息11Inf Theory

2、& Coding-張祖平3 信源信源編碼信道編碼信道譯碼信源譯碼信宿信道6.0 編碼概述編碼概述2013 秋季 信息11Inf Theory & Coding-張祖平44生活中編碼實例? 學號、身份證號碼、一卡通、漢語等編碼。編碼實質：信息的組織方式。對信源的原始符號按一定的數(shù)學規(guī)則進行變換。結論: 信息無處不在 ，編碼無處不在。6.0 編碼概述編碼概述2013 秋季 信息11Inf Theory & Coding-張祖平5通信的基本問題：通信的基本問題： 通信的基本問題：如何高速、高質地傳送信息。 高速和高質有效性和可靠性。通信的還需要解決的問題：通信的還需要解決的問題： 1：解決信源發(fā)出的

3、消息不適合信道的傳輸，信源編碼 2：希望信道可以盡快的傳輸信息，信源編碼的編碼效率 3：信道中有噪聲，進入信道以前需要加入抗干擾能力，信道編碼總結得到：總結得到： 信息質量一定時，如何提高信息傳輸速度（提高編碼效率或壓縮比）-信源編碼信源編碼（本章討論問題），提高信息傳輸?shù)挠行浴?信道傳輸速度一定時，如何提高信息傳輸質量（抗干擾能力） ， -信道編碼信道編碼（下一章討論），提高信息傳輸?shù)目煽啃浴?6.0 編碼概述編碼概述2013 秋季 信息11Inf Theory & Coding-張祖平6信源編碼定義信源編碼定義 將信源輸出的消息符號進行有效變換，使其成為適合信道傳輸?shù)姆栃蛄校沂乖撔蛄?/p>

4、組成的新信源的冗余度盡可能地減少。信源編碼目的信源編碼目的 符號變換：使信源輸出符號與信道的輸入符號相匹配。 減少冗余：提高通信的有效性，就是針對信源輸出符號序列的統(tǒng)計特性，尋找一定的把信源輸出符號序列變換為最短碼字序列的方法。信源編碼基本方法信源編碼基本方法 （1） 解除相關性：使序列中的各個符號盡可能地互相獨立。比如：一個英文單詞視為系列符號從而消除單詞內(nèi)部字母之間的相關性 。 （2） 概率均勻化：使編碼中各個符號出現(xiàn)的概率盡可能地相等，盡可能縮短出現(xiàn)概率大的信源符號的碼字，壓縮每個信源符號的平均比特數(shù)。即同樣多的信息用較少的碼率傳送，使單位時間內(nèi)傳送的平均信息量增加，從而提高通信的有效性

5、。 66.0 編碼概述編碼概述2013 秋季 信息11Inf Theory & Coding-張祖平7信源編碼的兩大定理信源編碼的兩大定理 信源編碼理論是信息論的一個重要分支，其理論基礎是兩個定理。 無失真信源編碼定理無失真信源編碼定理：是離散信源/數(shù)字信號編碼的基礎；無失真編碼是可逆的，即當信源符號變換成代碼以后，可以從代碼無失真地恢復出原信源符號。 限失真信源編碼定理限失真信源編碼定理：是連續(xù)信源/模擬信號編碼的基礎，如語音、圖像等信號。在連續(xù)信源的情況下，由于信源的信息量趨于無限，顯然不能用離散符號序列來完成無失真編碼，而只能進行限失真編碼。香農(nóng)信息論三大定理香農(nóng)信息論三大定理 無失真信

6、源編碼定理為第一極限定理； 信道編碼定理（離散和連續(xù)信道）稱為第二極限定理； 限失真信源編碼定理稱為第三極限定理。76.0 編碼概述編碼概述2013 秋季 信息11Inf Theory & Coding-張祖平8編碼器的數(shù)學模型編碼器的數(shù)學模型8 編碼器可以看作這樣一個系統(tǒng)，它的輸入端為原始信源編碼器可以看作這樣一個系統(tǒng)，它的輸入端為原始信源S S，其符號集為，其符號集為 ；而；而信道所能傳輸?shù)姆柤诺浪軅鬏數(shù)姆柤癁闉?。編碼器的功能是用符號集。編碼器的功能是用符號集X X中的元素，中的元素，將原始信源的符號將原始信源的符號 變換為相應的碼字符號變換為相應的碼字符號 ，所以編碼，所以編碼

7、器輸出端的符號集為器輸出端的符號集為 稱為稱為碼字碼字， 為碼字為碼字 的碼元個數(shù)，稱為碼字的碼元個數(shù)，稱為碼字 的碼的碼字長度，簡稱字長度，簡稱碼長碼長。碼字的集合。碼字的集合C C 稱為稱為碼書碼書。 稱為稱為碼元。碼元。12,.,qSS SS12 ,.,rXx xx12 ,.,qSs ss12 ,.,rXx xx編碼器編碼器12:,.,qCW WW12:,.,qCwwwiSiwiwiLiwiwix6.0 編碼概述編碼概述2013 秋季 信息11Inf Theory & Coding-張祖平9單義可譯碼單義可譯碼 若碼的任意一串有限長的碼符號序列只能被惟一地譯成所對應的信源符號序列，則此碼

8、稱為惟一可譯碼（單義可譯碼） 否則就稱為非惟一可譯碼或非單義可譯碼。比如：比如： 信源S的符號集是英文字母和標點 而信道只能傳輸0,1序列，即信道要求的信源其符號集只能包含0和1我們需要用我們需要用0和和1組成的組成的碼字碼字來表示來表示S中的英文字母和標點中的英文字母和標點 要求1：碼字要與S中的每種字符一一對應 要求2：碼字序列要與S的N個符號組成的序列一一對應6.1 單義可譯碼單義可譯碼2013 秋季 信息11Inf Theory & Coding-張祖平1010碼碼1：W(1)碼碼2：W(2)碼碼3：W(3)碼碼4：W(4)碼碼5：W(5)00011100110010010100001

9、011110000001二元碼二元碼：若碼符號集X0，1，即：碼元只有2種取值可能、所有碼字都是二元序列，則稱為二元碼。二元碼是數(shù)字通信和計算機中最常用的一種碼。二元信道二元信道：一種最簡單的邏輯信道（信源編碼器），信道的基本符號集為0，1，輸入、輸出符號都只有這兩種取值。二元信源二元信源：信源輸出符號只有這兩種取值。6.1 單義可譯碼單義可譯碼2013 秋季 信息11Inf Theory & Coding-張祖平1111碼碼1：W(1)碼碼2：W(2)碼碼3：W(3)碼碼4：W(4)碼碼5：W(5)00011100110010010100001011110000001奇異碼非奇異碼：非奇異碼

10、：若一組碼中所有碼字都不相同(即所有信源符號映射到不同的碼符號序列，不同信源符號可分辨)，則稱為非奇異碼。奇異碼：奇異碼：反之，若碼組中含有相同的碼字則為奇異碼。6.1 單義可譯碼單義可譯碼2013 秋季 信息11Inf Theory & Coding-張祖平1212碼碼1：W(1)碼碼2：W(2)碼碼3：W(3)碼碼4：W(4)碼碼5：W(5)000111001100100101000010111100000016.1 單義可譯碼單義可譯碼2013 秋季 信息11Inf Theory & Coding-張祖平1313碼碼1：W(1)碼碼2：W(2)碼碼3：W(3)碼碼4：W(4)碼碼5：W(

11、5)00011100110010010100001011110000001定長碼（等長碼）：若一組碼中所有碼字的碼長都相同，則稱為定長碼。因為長度相同，相當于每個碼字后有一個無形的逗號(點),又叫逗號(點)碼。變長碼：若一組碼中所有碼字的碼長各不相同，則稱為變長碼。非奇異的等長碼一定是單義可譯碼6.1 單義可譯碼單義可譯碼2013 秋季 信息11Inf Theory & Coding-張祖平1414碼碼1：W(1)碼碼2：W(2)碼碼3：W(3)碼碼4：W(4)碼碼5：W(5)00011100110010010100001011110000001奇異碼非奇異的等長碼一定是單義可譯碼都是非奇異的

12、且都是單義可譯碼6.1 單義可譯碼單義可譯碼2013 秋季 信息11Inf Theory & Coding-張祖平1515碼碼4：W(4)碼碼5：W(5)11100110000110000001W4，W5 都是非奇異的且都是單義可譯碼非即時碼：如果接收端收到一個完整的碼字后不能立即譯碼，必須結合后續(xù)的碼元序列才能進行譯碼，稱為非即時碼。如碼4，收到10無法判斷結束。即時碼：在譯碼時，如果當前已經(jīng)接收到一個完整的碼元序列之后，無需參考后續(xù)的碼元符號、立即能夠確定對應的碼字，這種碼制稱為即時碼。如碼5，每個碼字最后符號都是1，收到1好像逗(點)號，又叫逗號(點)碼。6.2 非延長碼非延長碼2013

13、 秋季 信息11Inf Theory & Coding-張祖平1616碼碼4：W(4)碼碼5：W(5)11100110000110000001異前綴碼異前綴碼/ /非延長碼非延長碼：即時碼要求任何一個碼字都不是其他碼字的前綴部分，所以也叫做異前綴碼/非延長碼，反之就叫延長碼。即時碼（異前綴碼）一定可以單義可譯碼即時碼（異前綴碼）一定可以單義可譯碼。因為，如果沒有一個碼字是其他碼字的前綴，則在譯碼過程中，當收到一個完整碼字的碼符號序列時，無需考慮下一個符號，就能直接把它譯成對應的碼字或信源符號。所有碼所有碼非奇異碼非奇異碼單義可譯碼單義可譯碼即時碼即時碼6.2 非延長碼非延長碼2013 秋季 信

14、息11Inf Theory & Coding-張祖平1717怎樣構建非延長碼？ 可用“樹圖法/碼樹”來構建非延長碼6.2 非延長碼非延長碼2013 秋季 信息11Inf Theory & Coding-張祖平18 q=4, r=2, n1=1, n2=2, n3=3, n4=401得到一階節(jié)點標記每條樹枝樹枝數(shù)為rW1可以二選一186.2 非延長碼非延長碼2013 秋季 信息11Inf Theory & Coding-張祖平19 q=4, r=2, n1=1, n2=2, n3=3, n4=4010011該選哪個節(jié)點？196.2 非延長碼非延長碼2013 秋季 信息11Inf Theory &

15、 Coding-張祖平20 q=4, r=2, n1=1, n2=2, n3=3, n4=4010011該選哪個節(jié)點？206.2 非延長碼非延長碼2013 秋季 信息11Inf Theory & Coding-張祖平21 q=4, r=2, n1=1, n2=2, n3=3, n4=4010011011216.2 非延長碼非延長碼2013 秋季 信息11Inf Theory & Coding-張祖平22 q=4, r=2, n1=1, n2=2, n3=3, n4=4010011011w1=1w2=01w3=001w4=0001未用盡226.2 非延長碼非延長碼2013 秋季 信息11Inf

16、Theory & Coding-張祖平23 q=4, r=2, n1=1, n2=2, n3=3, n4=40101011w1=1w2=01w3=001w4=0001未用盡236.2 非延長碼非延長碼2013 秋季 信息11Inf Theory & Coding-張祖平2424根：樹的最上端樹枝的個數(shù)為r，r=2為二元碼樹01001111010010001碼5的樹圖ABCD中間節(jié)點（空心）節(jié)點：樹枝的終端，從節(jié)點生出樹枝，每個節(jié)點伸出r個枝終端節(jié)點（實心）碼字：從根到終端節(jié)點對應的碼符號，又稱樹葉 q=4, r=2, n1=1, n2=2, n3=3, n4=4w1=1w2=01w3=001w

17、4=00016.2 非延長碼非延長碼2013 秋季 信息11Inf Theory & Coding-張祖平2525該樹的5個終端節(jié)點W1,W2,W3,W4,W5分別表示5個二進制碼字0，100，111，1010，1011碼樹的性質：任一即時碼都可用樹圖表示。即時碼不是惟一的。單義可譯碼成為即時碼的充要條件是其中任何一個碼字都不是其他碼字的前綴，按樹圖法構成的碼一定滿足即時碼的充要條件，因為從根到葉所走的路徑各不相同，而且中間節(jié)點不安排為碼字，所以一定滿足對前綴的限制。6.2 非延長碼非延長碼2013 秋季 信息11Inf Theory & Coding-張祖平2626滿樹滿樹 每個碼字的聯(lián)枝數(shù)

18、均相同時每個碼字的聯(lián)枝數(shù)均相同時( (定長碼定長碼) )非滿樹非滿樹 當碼字的聯(lián)枝數(shù)不同時當碼字的聯(lián)枝數(shù)不同時( (變長碼變長碼) ) 全樹全樹 每個中間節(jié)點的后續(xù)分支數(shù)均為每個中間節(jié)點的后續(xù)分支數(shù)均為m 非全樹非全樹 有些中間節(jié)點的后續(xù)分支數(shù)不足有些中間節(jié)點的后續(xù)分支數(shù)不足m滿樹滿樹非全樹非全樹樹根樹根終節(jié)點終節(jié)點中間節(jié)點中間節(jié)點非滿樹，全樹非滿樹，全樹6.2 非延長碼非延長碼2013 秋季 信息11Inf Theory & Coding-張祖平2727 0 1 2 0 1 2 0 1 2 0 1 20 1 20 1 2三進制碼樹三進制碼樹6.2 非延長碼非延長碼2013 秋季 信息11In

19、f Theory & Coding-張祖平2828S：s1，s2，s9，A=0，1，2，q=36.2 非延長碼非延長碼2013 秋季 信息11Inf Theory & Coding-張祖平2929 設原始信源符號集為S:S1,S2,Sq，碼元符號集為x:x1,x2,xr，碼字集合為W:W1,W2,Wq，其碼長分別為L1,L2,Lq；則單義可譯碼存在的充要條件為碼長組合滿足 Kraft 不等式，即： 11qilirr是碼元進制數(shù)q是信源符號數(shù)l為碼字長度。 例：設二進制碼樹中X (a1， a2 ， a3 ， a4 )，碼長 L11，L22，L32，L43，應用上述判斷定理： 4122319222

20、2218iLi不存在滿足這種不存在滿足這種 Li的單義可譯碼的單義可譯碼6.3 單義可譯定理單義可譯定理2013 秋季 信息11Inf Theory & Coding-張祖平3030例：設二進制碼樹中X (a1， a2)，碼長 L11，L22，L33，L43，應用上述判斷定理： 412331222221iLia1=1 0 1 0 1 0 1a2=01a3=001a4=000這種Li的單義可譯碼是存在的用樹的方式嘗試構造，葉節(jié)點如1，01，001，000 單義可譯碼；但不能作為單義可譯碼的判據(jù)，如1，01，101，000 不是單義可譯碼；6.3 單義可譯定理單義可譯定理2013 秋季 信息11I

21、nf Theory & Coding-張祖平31關于關于Kraft不等式不等式 滿足Kraft不等式的碼長組合一定能構成至少一種單義可譯碼。 單義碼的碼長組合一定滿足Kraft不等式，否則無法構成單義可譯碼。 有些碼字的碼長組合雖滿足Kraft不等式，但不是單義可譯碼。 Kraft不等式不能用來判斷是否是單義可譯碼，但不滿足該不等式的一定不是單義可譯碼。316.3 單義可譯定理單義可譯定理2013 秋季 信息11Inf Theory & Coding-張祖平32321C這些碼中哪些是單義可譯碼？哪些碼是非延長碼？6.3 單義可譯定理單義可譯定理2013 秋季 信息11Inf Theory &

22、Coding-張祖平33333112345623:6 2163:22222216463:164CCC1244135236:224 21:25 21:25 21CCC C2不是即時碼C5不是唯一可譯碼，C5是奇異碼又根據(jù)碼樹構造碼字的方法 C1， C3， C6的碼字均處于終端節(jié)點 他們是即時碼C4不全是終端節(jié)點6.3 單義可譯定理單義可譯定理2013 秋季 信息11Inf Theory & Coding-張祖平34通信的有效性通信的有效性 單義可譯碼、非延長碼解決了編碼的一一對應和即時譯碼問題。 人們還要求提高通信的效率，希望通信中每個碼能攜帶更多信息量。 對于已知信源 S 可用碼符號 X 進行

23、變長編碼，而且對同一信源可有多種非延長碼或單義可譯碼。選擇哪一種最好呢？ 因此我們結合信源空間、信源熵引出了平均碼長。341212,( ),(),()( )qqsssSP sP sP sP s() ()( ) ( )( )log( )iiiiiiH XE I Xp x I xp xp x 信源空間信源熵6.4 平均碼長與有效性平均碼長與有效性2013 秋季 信息11Inf Theory & Coding-張祖平3535見書上例題。概率大的信源符號要用碼長小的碼字，概率小的信源符號要用碼長大的碼字6.4 平均碼長與有效性平均碼長與有效性2013 秋季 信息11Inf Theory & Codin

24、g-張祖平3636平均碼長3.14比特/符號，信息傳輸率0.8309平均碼長2.74比特/符號，信息傳輸率0.9522計算平均碼長和信息傳輸率6.4 平均碼長與有效性平均碼長與有效性2013 秋季 信息11Inf Theory & Coding-張祖平37緊致碼（最佳碼）緊致碼（最佳碼） 對于某一信源和某一碼符號集來說，若有一個單義可譯碼，其平均長度小于所有其他單義可譯碼的平均長度，稱為緊致碼（最佳碼） 。 無失真信源編碼的基本問題轉化為找出緊致碼（最佳碼） 。 最佳碼也就是緊致碼的平均長度不是可以無限制縮小的，在理論上是有它的極限值的（在無失真信源編碼的條件下）376.5 平均碼長界限定理平

25、均碼長界限定理2013 秋季 信息11Inf Theory & Coding-張祖平3838上界下界證明與例題見書6.5 平均碼長界限定理平均碼長界限定理2013 秋季 信息11Inf Theory & Coding-張祖平3939表明碼符號數(shù)為r的碼符號集合編出的非延長碼的平均碼長下界值，在數(shù)值上等于r進制信息單位的信源熵值。也就是說平均碼長下限值在數(shù)值上取決于給定的信源的信息熵。信源給定，這個信源的的平均碼長下限值就確定了，改進編碼方法無法進一步提高有效性，只能對編碼對象，即信源做文章6.5 平均碼長界限定理平均碼長界限定理2013 秋季 信息11Inf Theory & Coding-張

26、祖平40406.5 平均碼長界限定理平均碼長界限定理2013 秋季 信息11Inf Theory & Coding-張祖平41416.6 香農(nóng)碼香農(nóng)碼2013 秋季 信息11Inf Theory & Coding-張祖平42421. 將信源符號按概率排序：將信源符號按概率排序：p(a1)p(a2)p(an)；2. 計算第計算第i個碼字個碼字( (之前之前) )的累加概率的累加概率pa(xj)3. 確定第確定第i個碼字的碼長個碼字的碼長ni( (整數(shù)整數(shù)) )：- -log2p(xi) ni 1-log2p(xi)4.4.將累加概率將累加概率pa(xj)變?yōu)槎M制數(shù)，并取小數(shù)點后變?yōu)槎M制數(shù)，并

27、取小數(shù)點后ni位，即為位，即為ai的編的編碼碼 說明說明 j j=1=1時，時， pa(a1) = p(a0) =0j j=2=2時，時， pa(a2) = p(a1) + p(a0) = p(a1) ) j j=3=3時，時， pa(a3) = p(a2) + p(a1) + p(a0) 因而因而pa(aj)表示：表示：aj之前之前( (不含不含aj) )的各概率之和的各概率之和100()( ),1,., ,()0jajiip ap ajnp a6.6 香農(nóng)碼香農(nóng)碼2013 秋季 信息11Inf Theory & Coding-張祖平43第四步舉例第四步舉例 累加概率Pi=0.57，變成二進

28、制數(shù)，為0.1001。 轉換的方法是：用Pi乘以2，如果整數(shù)部分有進位，則小數(shù)點后第一位為1，否則為0，將其小數(shù)部分再做同樣的處理，得到小數(shù)點后的第二位，依此類推，直到得到了滿足要求的位數(shù)，或者沒有小數(shù)部分了為止。 對應結果：現(xiàn)在Pi=0.57，乘以2為1.14，整數(shù)部分有進位，所以小數(shù)點后第一位為1，將小數(shù)部分即0.14再乘以2，得0.28，沒有整數(shù)進位，所以小數(shù)點后第二位為0，依此類推，可得到其對應的二進制數(shù)為0.1001。436.6 香農(nóng)碼香農(nóng)碼2013 秋季 信息11Inf Theory & Coding-張祖平4444123456,()05

29、XxxxxxxP X例例: : 有一單符號離散無記憶信源，編二進制香農(nóng)碼有一單符號離散無記憶信源，編二進制香農(nóng)碼6.6 香農(nóng)碼香農(nóng)碼2013 秋季 信息11Inf Theory & Coding-張祖平45450001100101110111110可以看出，編碼所得的碼字，沒有相同的，所以是非奇異碼也沒有一個碼字是其它碼字的前綴，所以是即時碼（非延長碼），也是單義可譯碼。用樹圖構造出來可以看出符合非延長碼特點。0.2522(0.20.15)30.1040.0552.7n 621()()log()2.42325iiiH Xp ap a ()2.420.89622.7H XRn平均信息傳輸率 平均

30、碼長與信息熵香農(nóng)碼編碼效香農(nóng)碼編碼效率并不是很高，率并不是很高，不是最佳碼，不是最佳碼，為什么？為什么？圖上可以看出圖上可以看出來嗎？來嗎？碼符號/信源符號6.6 香農(nóng)碼香農(nóng)碼2013 秋季 信息11Inf Theory & Coding-張祖平4646信源共有7個符號組成，其概率如表所示，求二進制香農(nóng)碼，平均碼長和信息傳輸率。信源消息符號信源消息符號xi符號概率符號概率p(xi)x1 0.20 x2 0.19x3 0.18x4 0.17x5 0.15x6 0.10 x7 0.016.6 香農(nóng)碼香農(nóng)碼2013 秋季 信息11Inf Theory & Coding-張祖平4747xip(xi)累

31、加累加Pi-log2 p(xi)碼字長度碼字長度Ki 碼碼 字字x10.2002.343000 x13001x30.180.392.483011x40.170.572.563100 x50.150.742.743101x60.100.893.3441110 x70.010.996.667111111071( )3.14iiiKp x K()2.610.8313.14H XRK6.6 香農(nóng)碼香農(nóng)碼2013 秋季 信息11Inf Theory & Coding-張祖平4848費諾編碼也是一種常見的信源編碼方法。費諾編碼也是一種常見的信源編碼方法。編碼步驟如下：編碼步驟如下：(

32、1)(1)將概率按從大到小的順序排列，令將概率按從大到小的順序排列，令 p(a1) p(a2) p(an)(2)(2)按編碼進制數(shù)將概率分組，使每組概率盡可能接近或相按編碼進制數(shù)將概率分組，使每組概率盡可能接近或相等。如編二進制碼就分成兩組，編等。如編二進制碼就分成兩組，編m m進制碼就分成進制碼就分成m m組。組。(3)(3)給每一組分配一位碼元。給每一組分配一位碼元。(4)(4)將每一分組再按同樣原則劃分，重復步驟將每一分組再按同樣原則劃分，重復步驟2 2和和3 3，直至概，直至概率不再可分為止。率不再可分為止。6.7 費諾碼費諾碼2013 秋季 信息11Inf Theory & Codi

33、ng-張祖平4949例例 設有一單符號離散信源設有一單符號離散信源, ,對該信源編二進制費諾碼。對該信源編二進制費諾碼。123456,()05XaaaaaaP X二進制費諾編碼 信源符號 概率 編碼 碼字 碼長 x1 0.25 0 00 2 x2 0.25 0 1 01 2 x3 0.20 0 10 2 x4 0.15 0 110 3 x5 0.10 0 1110 4 x6 0.05 1 1 1 1 1111 4 大概率用短碼大概率用短碼6.7 費諾碼費諾碼2013 秋季 信息11Inf Theory & Coding-張祖平5050該信源的熵為該信

34、源的熵為平均碼長為平均碼長為編碼效率為編碼效率為 本例中費諾編碼有較高的編碼效率。費諾碼比較適合于本例中費諾編碼有較高的編碼效率。費諾碼比較適合于每次分組概率都很接近每次分組概率都很接近的信源。特別是對每次的信源。特別是對每次分組概率都相分組概率都相等等的信源進行編碼時，可達到理想的編碼效率。的信源進行編碼時，可達到理想的編碼效率。621()( )log( )2.45(/)iiiH Xp ap a 比特 符號61( )2.4(/)iiiLp a k比特 符號()2.423350.98912.45H XRK6.7 費諾碼費諾碼2013 秋季 信息11Inf Theory & Coding-張祖平

35、5151題中碼字還可用碼樹來表示，如圖所示。題中碼字還可用碼樹來表示，如圖所示。6.7 費諾碼費諾碼2013 秋季 信息11Inf Theory & Coding-張祖平5252信源共有7個符號組成，其概率如表所示，求二進制費諾碼，平均碼長和信息傳輸率。信源消息符號信源消息符號xi符號概率符號概率p(xi)x1 0.20 x2 0.19x3 0.18x4 0.17x5 0.15x6 0.10 x7 0.016.7 費諾碼費諾碼2013 秋季 信息11Inf Theory & Coding-張祖平5353消 息 符消 息 符號號ai各 個 消各 個 消息概率息概率 p(ai)第一次第一次分組分組

36、第二次第二次分組分組第三次第三次分組分組第四次第四次分組分組二元二元碼字碼字碼長碼長Kia10.2000002a20.19100103a30.1810113a40.1710102a50.15101103a60.101011104a70.0111111474. 2)(71iiiKapK953. 074. 261. 2)(KXHR6.7 費諾碼費諾碼2013 秋季 信息11Inf Theory & Coding-張祖平5454信源共有8個符號組成，其概率如表所示，求二進制費諾碼，平均碼長和信息傳輸率。1234567811111111()448816161616aaaaaaaaXP X6.7 費諾碼

37、費諾碼2013 秋季 信息11Inf Theory & Coding-張祖平5555平均碼長平均碼長 81( )0.25 2 2 0.125 2 3 0.0625 4 42.75iiiLp a k 編碼效率編碼效率()1H XRK信源熵信源熵 H(X)=2.75 bit/sign 每次兩分組的概率正好相等每次兩分組的概率正好相等，效率最高，效率最高6.7 費諾碼費諾碼2013 秋季 信息11Inf Theory & Coding-張祖平56香農(nóng)碼與費諾碼總結香農(nóng)碼與費諾碼總結 香農(nóng)第一編碼定理給出了碼字的平均長度的下界和上界。 但并不是說大于這上界不能構成單義可譯碼，而是因為我們總是希望盡可能

38、短。 也就是說，定理給出的是最佳碼（比其他單義可譯碼平均碼長都小的編碼）的最短平均碼長的下界和上界，并指出這個最短的平均碼長與信源熵是有關的。 無失真信源編碼的基本問題轉化為找出緊致碼（最佳碼） 。 最佳編碼基本思想： 將概率大的信息符號編以短的碼字，概率小的符號編以長的碼字。 最佳碼的編碼主要方法： 香農(nóng)（Shannon）、費諾（Fano）、哈夫曼（Huffman）編碼等。 香農(nóng)碼：編碼唯一，但通常效率不高，學術意義大于實際意義； 費諾碼：由于賦碼元時的任意性，因此編出的碼字不是唯一的；構造碼樹時自頂向下；編碼效率高于香農(nóng)碼，適合于對分組概率相等或接近的信源編碼； 香農(nóng)碼和費諾碼都不是真正意

39、義上的最佳碼，哈夫曼編碼實現(xiàn)了最佳編碼。566.7 費諾碼費諾碼2013 秋季 信息11Inf Theory & Coding-張祖平5757哈夫曼哈夫曼1953年于年于MIT獲得科學博士學位獲得科學博士學位哈夫曼編碼是哈夫曼編碼是1951年，他在研究生階段課程（信年，他在研究生階段課程（信息論與編碼）的課程大作業(yè)中提出的，哈夫曼使息論與編碼）的課程大作業(yè)中提出的，哈夫曼使用自底向上的方法構建二叉樹，避免了次優(yōu)算法用自底向上的方法構建二叉樹，避免了次優(yōu)算法Shannon-Fano編碼的最大弊端編碼的最大弊端自頂向下構自頂向下構建樹，該算法廣泛應用于數(shù)據(jù)壓縮和計算機安全建樹，該算法廣泛應用于數(shù)據(jù)

40、壓縮和計算機安全領域。領域。離開離開MIT后，哈夫曼來到加利福尼亞大學的計算后，哈夫曼來到加利福尼亞大學的計算機系任教。機系任教。哈夫曼從未為此算法申請過專利或其它相關能夠哈夫曼從未為此算法申請過專利或其它相關能夠為他帶來經(jīng)濟利益的東西，他將他全部的精力放為他帶來經(jīng)濟利益的東西，他將他全部的精力放在教學上，以他自己的話來說，在教學上，以他自己的話來說，“我所要帶來的我所要帶來的就是我的學生。就是我的學生?！盌avid A. Huffman(1925-1999)6.8 Huffman編碼編碼2013 秋季 信息11Inf Theory & Coding-張祖平58還記得數(shù)據(jù)結構中的哈夫曼碼嗎？還

41、記得數(shù)據(jù)結構中的哈夫曼碼嗎？哈夫曼編碼是最佳碼（即平均碼長最?。┕蚵幋a是最佳碼（即平均碼長最?。?怎么證明這一點？哈夫曼在1952年的原始論文中并沒有給出證明 后人給出了不同的證明方法特點：特點： 自底向上構造碼樹 把碼長小的碼字分配給出現(xiàn)頻率高的信源字符 在編碼過程中需要構造虛擬節(jié)點 每次縮減信源的最長兩個碼字有相同的碼長。586.8 Huffman編碼編碼2013 秋季 信息11Inf Theory & Coding-張祖平59(1) (1) 將信源符號按概率從大到小的順序排列，令將信源符號按概率從大到小的順序排列，令 p(a1) p(a2) p(an)(2) (2) 給兩個概率最小的

42、信源符號給兩個概率最小的信源符號p( (an-1) )和和p( (an) )各分配一個碼位各分配一個碼位“0 0”和和“1 1”，將這兩個信源符號合并成一個新符號，并用這兩，將這兩個信源符號合并成一個新符號，并用這兩個最小的概率之和作為新符號的概率，結果得到一個只包含個最小的概率之和作為新符號的概率，結果得到一個只包含( (q1) )個信源符號的新信源。稱為個信源符號的新信源。稱為信源的第一次縮減信源信源的第一次縮減信源，用，用S1表示。表示。(3)(3)將縮減信源將縮減信源S1的符號仍按概率從大到小順序排列，重復步驟的符號仍按概率從大到小順序排列，重復步驟2 2，得到只含，得到只含( (q2

43、) )個符號的縮減信源個符號的縮減信源S2。(4)(4)重復上述步驟，直至縮減信源只剩兩個符號為止，此時所剩重復上述步驟，直至縮減信源只剩兩個符號為止，此時所剩兩個符號的概率之和必為兩個符號的概率之和必為1 1。然后從最后一級縮減信源開始，依。然后從最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號所對應的碼字。編碼路徑向前返回，就得到各信源符號所對應的碼字。596.8 Huffman編碼編碼2013 秋季 信息11Inf Theory & Coding-張祖平60601 . 01 . 02 . 02 . 04 . 054321aaaaaPX0.4 0.4 0.4 1.0 0.2 0.

44、2 0.40.2 0.2 0.20.1 0.110101010aip(ai)碼字碼字Wi1a10.40a20.210a30.2111a40.11101a50.111006.8 Huffman編碼編碼2013 秋季 信息11Inf Theory & Coding-張祖平61611 . 01 . 02 . 02 . 04 . 054321aaaaaPX2 . 2)(71iiiKapK 碼元碼元/符號符號 ()0.965H XRK平均碼長、編碼效率平均碼長、編碼效率aip(ai)碼字碼字Wi1a10.40a20.210a30.2111a40.11101a50.111006.8 Huffman編碼編碼

45、2013 秋季 信息11Inf Theory & Coding-張祖平62621 . 01 . 02 . 02 . 04 . 054321aaaaaPX0.4 0.4 0.4 1.0 0.2 0.2 0.40.2 0.2 0.20.1 0.101010101aip(ai)碼字碼字Wi2a10.41a20.201a30.2000a40.10010a50.1001101106.8 Huffman編碼編碼2013 秋季 信息11Inf Theory & Coding-張祖平63631 . 01 . 02 . 02 . 04 . 054321aaaaaPXaip(ai)碼字碼字Wi2a10.41a20

46、.201a30.2000a40.10010a50.100112 . 2)(71iiiKapK 碼元碼元/符號符號 ()0.965H XRK平均碼長、編碼效率平均碼長、編碼效率6.8 Huffman編碼編碼2013 秋季 信息11Inf Theory & Coding-張祖平64641 . 01 . 02 . 02 . 04 . 054321aaaaaPXaip(ai)碼字碼字Wi3a10.400a20.210a30.211a40.1010a50.10110.4 0.4 1.0 0.2 0.4 0.40.2 0.2 0.20.1 0.20.1010101016.8 Huffman編碼編碼2013

47、 秋季 信息11Inf Theory & Coding-張祖平65651 . 01 . 02 . 02 . 04 . 054321aaaaaPX2 . 2)(71iiiKapK 碼元碼元/符號符號 ()0.965H XRK平均碼長、編碼效率平均碼長、編碼效率aip(ai)碼字碼字Wi3a10.400a20.210a30.211a40.1010a50.10116.8 Huffman編碼編碼2013 秋季 信息11Inf Theory & Coding-張祖平66哈夫曼編碼形式不是唯一的，用方差選擇較好的編碼哈夫曼編碼形式不是唯一的，用方差選擇較好的編碼 由于0，1順序可以不同，導致不一樣 由于出

48、現(xiàn)合并后等概率情況，排序位置不同，導致不一樣aip(ai)碼字碼字Wi1碼字碼字Wi2碼字碼字Wi3a10.40100a20.2100110a30.211100011a40.111010010010a50.111000011011W2和和w3編碼的方差不同編碼的方差不同，進行哈夫進行哈夫曼編碼時，為得到曼編碼時，為得到碼方差碼方差最小的碼，最小的碼，應使合并的信源符號位于縮減信源序應使合并的信源符號位于縮減信源序列列盡可能高的位置盡可能高的位置上，以減少再次合上，以減少再次合并的次數(shù)，充分利用短碼。并的次數(shù)，充分利用短碼。 qiiiilKkapKkE1222)(221.36l230.16l方差

49、越小，說明各個碼的長度方差越小，說明各個碼的長度都比較接近平均長度，這樣編都比較接近平均長度，這樣編碼器和解碼器就可以比較簡單碼器和解碼器就可以比較簡單6.8 Huffman編碼編碼2013 秋季 信息11Inf Theory & Coding-張祖平67信源共有7個符號組成，其概率如表所示，求二進制哈夫曼編碼，平均碼長和信息傳輸率。信源消息符號信源消息符號xi符號概率符號概率p(xi)x1 0.20 x2 0.19x3 0.18x4 0.17x5 0.15x6 0.10 x7 0.016.8 Huffman編碼編碼2013 秋季 信息11Inf Theory & Coding-張祖平6868

50、0.20 0.20 0.26 0.35 0.39 0.61 1.00.19 0.19 0.20 0.26 0.35 0.390.18 0.18 0.19 0.20 0.260.17 0.17 0.18 0.190.15 0.15 0.170.10 0.110.010101010101016.8 Huffman編碼編碼2013 秋季 信息11Inf Theory & Coding-張祖平6969信源信源符號符號符號符號概率概率 編編 碼碼 過過 程程碼字碼字碼碼長長0.201020.191120.1800030.1700130.1501030.10011040.0101114010.200.19

51、50.110.280.1701010.260.350.200.19010.350.260.39010.390.61011x2x3x4x5x6x7x6.8 Huffman編碼編碼2013 秋季 信息11Inf Theory & Coding-張祖平70700.050.250.69 1011001011001符號碼元/72. 2)(71iiiKxpK碼元/9596. 072. 261. 2)(bitKXHR采用碼樹形式進行哈夫曼編碼的過程中，由于代表信源符號的節(jié)點都是終端節(jié)點，因此

52、其編碼不可能是其它終端節(jié)點對應的編碼的前綴。哈夫曼編碼總是把概率大的符號安排在離根節(jié)點近的終端節(jié)點，所以平均碼長短。6.8 Huffman編碼編碼2013 秋季 信息11Inf Theory & Coding-張祖平71平均碼長=2*0.24+2*0.2+2*0.18+2*0.16+2*0.14+2*0.08=2碼符號/信源符號定長編碼？這樣編碼效率高嗎？為什么？6.8 Huffman編碼編碼2013 秋季 信息11Inf Theory & Coding-張祖平7272 0 1 2 0 1 2 0 1 2 0 1 2w1w2w3w4w5w6？很明顯可以使用“0”這個短碼來作為概率最大的S1的編

53、碼，為什么編碼結果卻沒有用到呢？因為最后一次縮減，沒有把碼符號集中所有符號都用上，最后一次縮減是針對大概率信源符號的，是短碼，短碼沒有充分利用，反而優(yōu)先把小概率的信源符號，是長碼，用上了所有碼符號集中的符號。6.8 Huffman編碼編碼2013 秋季 信息11Inf Theory & Coding-張祖平7373 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2非全樹非全樹全樹全樹m進制的全樹的終端葉節(jié)點數(shù)進制的全樹的終端葉節(jié)點數(shù)( (碼碼個數(shù)個數(shù)) ) m + k(m-1), k = 0,1,2,.( (每從一個節(jié)點分出每從一個節(jié)點分出m枝枝, , 就增加就增加m-1-1個終端個終端) )當信源符號數(shù)當信源符號數(shù) n，n m+k(m-1)時，時，令令 s = m+k(m-1)-n, , s m-1-1，為，為構成全樹所缺少的碼字構成全樹所缺少的碼字( (分支分支) )數(shù)，數(shù)，必須在信源符號集合中補上概率必須在信源符號集合中補上概率為為0 0的的s個虛假符號個虛假符號w1w2w3w4w5w66.8 Huffman編