信息論與編碼張祖平/ZhangZuping電子信息工程系SchoolofInformationScienceandEngineering,CentralSouthUniversity,zpzhang@InformationTheory&Coding第六章無(wú)失真信源編碼2013秋季信息111InfTheory&Coding-張祖平本章主要內(nèi)容

(MainContent)6.1單義可譯碼6.2非延長(zhǎng)碼6.3單義可譯定理6.4平均碼長(zhǎng)與有效性6.5平均碼長(zhǎng)的界限定理6.8霍夫曼（Huffman）編碼6.0編碼概述6.6香農(nóng)碼6.7費(fèi)諾碼2013秋季信息112InfTheory&Coding-張祖平

信源信源編碼信道編碼信道譯碼信源譯碼信宿信道6.0編碼概述2013秋季信息113InfTheory&Coding-張祖平4生活中編碼實(shí)例?

學(xué)號(hào)、身份證號(hào)碼、一卡通、漢語(yǔ)等編碼。編碼實(shí)質(zhì)：信息的組織方式。對(duì)信源的原始符號(hào)按一定的數(shù)學(xué)規(guī)則進(jìn)行變換。結(jié)論:信息無(wú)處不在，編碼無(wú)處不在。6.0編碼概述2013秋季信息114InfTheory&Coding-張祖平通信的基本問題：通信的基本問題：如何高速、高質(zhì)地傳送信息。高速和高質(zhì)＝有效性和可靠性。通信的還需要解決的問題：1：解決信源發(fā)出的消息不適合信道的傳輸，信源編碼2：希望信道可以盡快的傳輸信息，信源編碼的編碼效率3：信道中有噪聲，進(jìn)入信道以前需要加入抗干擾能力，信道編碼總結(jié)得到：信息質(zhì)量一定時(shí)，如何提高信息傳輸速度（提高編碼效率或壓縮比）----信源編碼（本章討論問題），提高信息傳輸?shù)挠行?。信道傳輸速度一定時(shí)，如何提高信息傳輸質(zhì)量（抗干擾能力），----信道編碼（下一章討論），提高信息傳輸?shù)目煽啃浴?6.0編碼概述2013秋季信息115InfTheory&Coding-張祖平信源編碼定義將信源輸出的消息符號(hào)進(jìn)行有效變換，使其成為適合信道傳輸?shù)姆?hào)序列，且使該序列組成的新信源的冗余度盡可能地減少。信源編碼目的符號(hào)變換：使信源輸出符號(hào)與信道的輸入符號(hào)相匹配。減少冗余：提高通信的有效性，就是針對(duì)信源輸出符號(hào)序列的統(tǒng)計(jì)特性，尋找一定的把信源輸出符號(hào)序列變換為最短碼字序列的方法。信源編碼基本方法（1）解除相關(guān)性：使序列中的各個(gè)符號(hào)盡可能地互相獨(dú)立。比如：一個(gè)英文單詞視為系列符號(hào)從而消除單詞內(nèi)部字母之間的相關(guān)性。（2）概率均勻化：使編碼中各個(gè)符號(hào)出現(xiàn)的概率盡可能地相等，盡可能縮短出現(xiàn)概率大的信源符號(hào)的碼字，壓縮每個(gè)信源符號(hào)的平均比特?cái)?shù)。即同樣多的信息用較少的碼率傳送，使單位時(shí)間內(nèi)傳送的平均信息量增加，從而提高通信的有效性。66.0編碼概述2013秋季信息116InfTheory&Coding-張祖平信源編碼的兩大定理信源編碼理論是信息論的一個(gè)重要分支，其理論基礎(chǔ)是兩個(gè)定理。無(wú)失真信源編碼定理：是離散信源/數(shù)字信號(hào)編碼的基礎(chǔ)；無(wú)失真編碼是可逆的，即當(dāng)信源符號(hào)變換成代碼以后，可以從代碼無(wú)失真地恢復(fù)出原信源符號(hào)。限失真信源編碼定理：是連續(xù)信源/模擬信號(hào)編碼的基礎(chǔ)，如語(yǔ)音、圖像等信號(hào)。在連續(xù)信源的情況下，由于信源的信息量趨于無(wú)限，顯然不能用離散符號(hào)序列來(lái)完成無(wú)失真編碼，而只能進(jìn)行限失真編碼。香農(nóng)信息論三大定理無(wú)失真信源編碼定理為第一極限定理；信道編碼定理（離散和連續(xù)信道）稱為第二極限定理；限失真信源編碼定理稱為第三極限定理。76.0編碼概述2013秋季信息117InfTheory&Coding-張祖平編碼器的數(shù)學(xué)模型8編碼器可以看作這樣一個(gè)系統(tǒng)，它的輸入端為原始信源S，其符號(hào)集為；而信道所能傳輸?shù)姆?hào)集為。編碼器的功能是用符號(hào)集X中的元素，將原始信源的符號(hào)變換為相應(yīng)的碼字符號(hào)，所以編碼器輸出端的符號(hào)集為

稱為碼字，為碼字的碼元個(gè)數(shù)，稱為碼字的碼字長(zhǎng)度，簡(jiǎn)稱碼長(zhǎng)。碼字的集合C稱為碼書。

稱為碼元。編碼器6.0編碼概述2013秋季信息118InfTheory&Coding-張祖平單義可譯碼若碼的任意一串有限長(zhǎng)的碼符號(hào)序列只能被惟一地譯成所對(duì)應(yīng)的信源符號(hào)序列，則此碼稱為惟一可譯碼（單義可譯碼）否則就稱為非惟一可譯碼或非單義可譯碼。比如：信源S的符號(hào)集是英文字母和標(biāo)點(diǎn)而信道只能傳輸0,1序列，即信道要求的信源其符號(hào)集只能包含0和1我們需要用0和1組成的碼字來(lái)表示S中的英文字母和標(biāo)點(diǎn)要求1：碼字要與S中的每種字符一一對(duì)應(yīng)要求2：碼字序列要與S的N個(gè)符號(hào)組成的序列一一對(duì)應(yīng)6.1單義可譯碼2013秋季信息119InfTheory&Coding-張祖平10碼1：W(1)碼2：W(2)碼3：W(3)碼4：W(4)碼5：W(5)00011100110010010100001011110000001二元碼：若碼符號(hào)集X＝{0，1}，即：碼元只有2種取值可能、所有碼字都是二元序列，則稱為二元碼。二元碼是數(shù)字通信和計(jì)算機(jī)中最常用的一種碼。二元信道：一種最簡(jiǎn)單的邏輯信道（信源編碼器），信道的基本符號(hào)集為{0，1}，輸入、輸出符號(hào)都只有這兩種取值。二元信源：信源輸出符號(hào)只有這兩種取值。6.1單義可譯碼2013秋季信息1110InfTheory&Coding-張祖平11碼1：W(1)碼2：W(2)碼3：W(3)碼4：W(4)碼5：W(5)00011100110010010100001011110000001奇異碼非奇異碼：若一組碼中所有碼字都不相同(即所有信源符號(hào)映射到不同的碼符號(hào)序列，不同信源符號(hào)可分辨)，則稱為非奇異碼。奇異碼：反之，若碼組中含有相同的碼字則為奇異碼。6.1單義可譯碼2013秋季信息1111InfTheory&Coding-張祖平12碼1：W(1)碼2：W(2)碼3：W(3)碼4：W(4)碼5：W(5)000111001100100101000010111100000016.1單義可譯碼

2013秋季信息1112InfTheory&Coding-張祖平13碼1：W(1)碼2：W(2)碼3：W(3)碼4：W(4)碼5：W(5)00011100110010010100001011110000001定長(zhǎng)碼（等長(zhǎng)碼）：若一組碼中所有碼字的碼長(zhǎng)都相同，則稱為定長(zhǎng)碼。因?yàn)殚L(zhǎng)度相同，相當(dāng)于每個(gè)碼字后有一個(gè)無(wú)形的逗號(hào)(點(diǎn)),又叫逗號(hào)(點(diǎn))碼。變長(zhǎng)碼：若一組碼中所有碼字的碼長(zhǎng)各不相同，則稱為變長(zhǎng)碼。非奇異的等長(zhǎng)碼一定是單義可譯碼6.1單義可譯碼2013秋季信息1113InfTheory&Coding-張祖平14碼1：W(1)碼2：W(2)碼3：W(3)碼4：W(4)碼5：W(5)00011100110010010100001011110000001奇異碼

非奇異的等長(zhǎng)碼一定是單義可譯碼都是非奇異的且都是單義可譯碼6.1單義可譯碼2013秋季信息1114InfTheory&Coding-張祖平15碼4：W(4)碼5：W(5)11100110000110000001W4，W5都是非奇異的且都是單義可譯碼非即時(shí)碼：如果接收端收到一個(gè)完整的碼字后不能立即譯碼，必須結(jié)合后續(xù)的碼元序列才能進(jìn)行譯碼，稱為非即時(shí)碼。如碼4，收到10無(wú)法判斷結(jié)束。即時(shí)碼：在譯碼時(shí)，如果當(dāng)前已經(jīng)接收到一個(gè)完整的碼元序列之后，無(wú)需參考后續(xù)的碼元符號(hào)、立即能夠確定對(duì)應(yīng)的碼字，這種碼制稱為即時(shí)碼。如碼5，每個(gè)碼字最后符號(hào)都是1，收到1好像逗(點(diǎn))號(hào)，又叫逗號(hào)(點(diǎn))碼。6.2非延長(zhǎng)碼2013秋季信息1115InfTheory&Coding-張祖平16碼4：W(4)碼5：W(5)11100110000110000001異前綴碼/非延長(zhǎng)碼：即時(shí)碼要求任何一個(gè)碼字都不是其他碼字的前綴部分，所以也叫做異前綴碼/非延長(zhǎng)碼，反之就叫延長(zhǎng)碼。即時(shí)碼（異前綴碼）一定可以單義可譯碼。因?yàn)?，如果沒有一個(gè)碼字是其他碼字的前綴，則在譯碼過程中，當(dāng)收到一個(gè)完整碼字的碼符號(hào)序列時(shí)，無(wú)需考慮下一個(gè)符號(hào)，就能直接把它譯成對(duì)應(yīng)的碼字或信源符號(hào)。所有碼非奇異碼單義可譯碼即時(shí)碼6.2非延長(zhǎng)碼2013秋季信息1116InfTheory&Coding-張祖平17怎樣構(gòu)建非延長(zhǎng)碼？可用“樹圖法/碼樹”來(lái)構(gòu)建非延長(zhǎng)碼

6.2非延長(zhǎng)碼2013秋季信息1117InfTheory&Coding-張祖平q=4,r=2,n1=1,n2=2,n3=3,n4=401得到一階節(jié)點(diǎn)標(biāo)記每條樹枝樹枝數(shù)為rW1可以二選一186.2非延長(zhǎng)碼2013秋季信息1118InfTheory&Coding-張祖平q=4,r=2,n1=1,n2=2,n3=3,n4=4010011該選哪個(gè)節(jié)點(diǎn)？196.2非延長(zhǎng)碼2013秋季信息1119InfTheory&Coding-張祖平q=4,r=2,n1=1,n2=2,n3=3,n4=4010011該選哪個(gè)節(jié)點(diǎn)？206.2非延長(zhǎng)碼2013秋季信息1120InfTheory&Coding-張祖平q=4,r=2,n1=1,n2=2,n3=3,n4=4010011011216.2非延長(zhǎng)碼2013秋季信息1121InfTheory&Coding-張祖平q=4,r=2,n1=1,n2=2,n3=3,n4=4010011011w1=1w2=01w3=001w4=0001未用盡226.2非延長(zhǎng)碼2013秋季信息1122InfTheory&Coding-張祖平q=4,r=2,n1=1,n2=2,n3=3,n4=40101011w1=1w2=01w3=001w4=0001未用盡236.2非延長(zhǎng)碼2013秋季信息1123InfTheory&Coding-張祖平24根：樹的最上端樹枝的個(gè)數(shù)為r，r=2為二元碼樹01001111010010001碼5的樹圖ABCD中間節(jié)點(diǎn)（空心）節(jié)點(diǎn)：樹枝的終端，從節(jié)點(diǎn)生出樹枝，每個(gè)節(jié)點(diǎn)伸出r個(gè)枝終端節(jié)點(diǎn)（實(shí)心）碼字：從根到終端節(jié)點(diǎn)對(duì)應(yīng)的碼符號(hào)，又稱樹葉q=4,r=2,n1=1,n2=2,n3=3,n4=4w1=1w2=01w3=001w4=00016.2非延長(zhǎng)碼2013秋季信息1124InfTheory&Coding-張祖平25該樹的5個(gè)終端節(jié)點(diǎn)W1,W2,W3,W4,W5分別表示5個(gè)二進(jìn)制碼字0，100，111，1010，1011碼樹的性質(zhì)：任一即時(shí)碼都可用樹圖表示。即時(shí)碼不是惟一的。單義可譯碼成為即時(shí)碼的充要條件是其中任何一個(gè)碼字都不是其他碼字的前綴，按樹圖法構(gòu)成的碼一定滿足即時(shí)碼的充要條件，因?yàn)閺母饺~所走的路徑各不相同，而且中間節(jié)點(diǎn)不安排為碼字，所以一定滿足對(duì)前綴的限制。6.2非延長(zhǎng)碼2013秋季信息1125InfTheory&Coding-張祖平26滿樹——

每個(gè)碼字的聯(lián)枝數(shù)均相同時(shí)(定長(zhǎng)碼)非滿樹——

當(dāng)碼字的聯(lián)枝數(shù)不同時(shí)(變長(zhǎng)碼)全樹——

每個(gè)中間節(jié)點(diǎn)的后續(xù)分支數(shù)均為m

非全樹——

有些中間節(jié)點(diǎn)的后續(xù)分支數(shù)不足m滿樹非全樹樹根終節(jié)點(diǎn)中間節(jié)點(diǎn)非滿樹，全樹6.2非延長(zhǎng)碼2013秋季信息1126InfTheory&Coding-張祖平27012012012012012012三進(jìn)制碼樹6.2非延長(zhǎng)碼2013秋季信息1127InfTheory&Coding-張祖平練習(xí)28S：｛s1，s2，…，s9｝，A=｛0，1，2｝，q=36.2非延長(zhǎng)碼2013秋季信息1128InfTheory&Coding-張祖平29設(shè)原始信源符號(hào)集為S:{S1,S2,…Sq}，碼元符號(hào)集為x:{x1,x2,…,xr}，碼字集合為W:{W1,W2,…Wq}，其碼長(zhǎng)分別為L(zhǎng)1,L2,…,Lq；則單義可譯碼存在的充要條件為碼長(zhǎng)組合滿足Kraft不等式，即：

r是碼元進(jìn)制數(shù)q是信源符號(hào)數(shù)l為碼字長(zhǎng)度。

例：設(shè)二進(jìn)制碼樹中X(a1，a2，a3，a4)，碼長(zhǎng)L1＝1，L2＝2，L3＝2，L4＝3，應(yīng)用上述判斷定理：不存在滿足這種Li的單義可譯碼6.3單義可譯定理2013秋季信息1129InfTheory&Coding-張祖平30例：設(shè)二進(jìn)制碼樹中X(a1，a2)，碼長(zhǎng)L1＝1，L2＝2，L3＝3，L4＝3，應(yīng)用上述判斷定理：a1=1

01

01

01a2=01a3=001a4=000這種Li的單義可譯碼是存在的用樹的方式嘗試構(gòu)造，葉節(jié)點(diǎn)如{1，01，001，000}

單義可譯碼；但不能作為單義可譯碼的判據(jù)，如{1，01，101，000}不是單義可譯碼；6.3單義可譯定理2013秋季信息1130InfTheory&Coding-張祖平關(guān)于Kraft不等式滿足Kraft不等式的碼長(zhǎng)組合一定能構(gòu)成至少一種單義可譯碼。單義碼的碼長(zhǎng)組合一定滿足Kraft不等式，否則無(wú)法構(gòu)成單義可譯碼。有些碼字的碼長(zhǎng)組合雖滿足Kraft不等式，但不是單義可譯碼。Kraft不等式不能用來(lái)判斷是否是單義可譯碼，但不滿足該不等式的一定不是單義可譯碼。316.3單義可譯定理2013秋季信息1131InfTheory&Coding-張祖平練習(xí)32這些碼中哪些是單義可譯碼？哪些碼是非延長(zhǎng)碼？6.3單義可譯定理2013秋季信息1132InfTheory&Coding-張祖平練習(xí)33C2不是即時(shí)碼C5不是唯一可譯碼，C5是奇異碼又根據(jù)碼樹構(gòu)造碼字的方法

C1，C3，C6的碼字均處于終端節(jié)點(diǎn)他們是即時(shí)碼C4不全是終端節(jié)點(diǎn)6.3單義可譯定理2013秋季信息1133InfTheory&Coding-張祖平通信的有效性單義可譯碼、非延長(zhǎng)碼解決了編碼的一一對(duì)應(yīng)和即時(shí)譯碼問題。人們還要求提高通信的效率，希望通信中每個(gè)碼能攜帶更多信息量。對(duì)于已知信源S可用碼符號(hào)X進(jìn)行變長(zhǎng)編碼，而且對(duì)同一信源可有多種非延長(zhǎng)碼或單義可譯碼。選擇哪一種最好呢？因此我們結(jié)合信源空間、信源熵引出了平均碼長(zhǎng)。34信源空間信源熵6.4平均碼長(zhǎng)與有效性2013秋季信息1134InfTheory&Coding-張祖平35

見書上例題。概率大的信源符號(hào)要用碼長(zhǎng)小的碼字，概率小的信源符號(hào)要用碼長(zhǎng)大的碼字6.4平均碼長(zhǎng)與有效性2013秋季信息1135InfTheory&Coding-張祖平練習(xí)36平均碼長(zhǎng)3.14比特/符號(hào)，信息傳輸率0.8309平均碼長(zhǎng)2.74比特/符號(hào)，信息傳輸率0.9522計(jì)算平均碼長(zhǎng)和信息傳輸率6.4平均碼長(zhǎng)與有效性2013秋季信息1136InfTheory&Coding-張祖平緊致碼（最佳碼）對(duì)于某一信源和某一碼符號(hào)集來(lái)說(shuō)，若有一個(gè)單義可譯碼，其平均長(zhǎng)度小于所有其他單義可譯碼的平均長(zhǎng)度，稱為緊致碼（最佳碼）。無(wú)失真信源編碼的基本問題轉(zhuǎn)化為找出緊致碼（最佳碼）。最佳碼也就是緊致碼的平均長(zhǎng)度不是可以無(wú)限制縮小的，在理論上是有它的極限值的（在無(wú)失真信源編碼的條件下）37

6.5平均碼長(zhǎng)界限定理2013秋季信息1137InfTheory&Coding-張祖平38

上界下界證明與例題見書6.5平均碼長(zhǎng)界限定理2013秋季信息1138InfTheory&Coding-張祖平39

表明碼符號(hào)數(shù)為r的碼符號(hào)集合編出的非延長(zhǎng)碼的平均碼長(zhǎng)下界值，在數(shù)值上等于r進(jìn)制信息單位的信源熵值。也就是說(shuō)平均碼長(zhǎng)下限值在數(shù)值上取決于給定的信源的信息熵。信源給定，這個(gè)信源的的平均碼長(zhǎng)下限值就確定了，改進(jìn)編碼方法無(wú)法進(jìn)一步提高有效性，只能對(duì)編碼對(duì)象，即信源做文章6.5平均碼長(zhǎng)界限定理2013秋季信息1139InfTheory&Coding-張祖平40

6.5平均碼長(zhǎng)界限定理2013秋季信息1140InfTheory&Coding-張祖平41

6.6香農(nóng)碼2013秋季信息1141InfTheory&Coding-張祖平421.將信源符號(hào)按概率排序：p(a1)≥p(a2)≥…≥p(an)；2.計(jì)算第i個(gè)碼字(之前)的累加概率pa(xj)3.確定第i個(gè)碼字的碼長(zhǎng)ni(整數(shù))：-log2p(xi)≤

ni

＜1-log2p(xi)4.將累加概率pa(xj)變?yōu)槎M(jìn)制數(shù)，并取小數(shù)點(diǎn)后ni位，即為ai的編碼[說(shuō)明]j=1時(shí)，pa(a1)=p(a0)=0 j=2時(shí)，pa(a2)=p(a1)+p(a0)=p(a1) j=3時(shí)，pa(a3)=p(a2)+p(a1)+p(a0)

因而pa(aj)表示：aj之前(不含aj)的各概率之和6.6香農(nóng)碼2013秋季信息1142InfTheory&Coding-張祖平第四步舉例累加概率Pi=0.57，變成二進(jìn)制數(shù)，為0.1001…。轉(zhuǎn)換的方法是：用Pi乘以2，如果整數(shù)部分有進(jìn)位，則小數(shù)點(diǎn)后第一位為1，否則為0，將其小數(shù)部分再做同樣的處理，得到小數(shù)點(diǎn)后的第二位，依此類推，直到得到了滿足要求的位數(shù)，或者沒有小數(shù)部分了為止。對(duì)應(yīng)結(jié)果：現(xiàn)在Pi=0.57，乘以2為1.14，整數(shù)部分有進(jìn)位，所以小數(shù)點(diǎn)后第一位為1，將小數(shù)部分即0.14再乘以2，得0.28，沒有整數(shù)進(jìn)位，所以小數(shù)點(diǎn)后第二位為0，依此類推，可得到其對(duì)應(yīng)的二進(jìn)制數(shù)為0.1001…。436.6香農(nóng)碼2013秋季信息1143InfTheory&Coding-張祖平44例:有一單符號(hào)離散無(wú)記憶信源，編二進(jìn)制香農(nóng)碼6.6香農(nóng)碼2013秋季信息1144InfTheory&Coding-張祖平450001100101110111110可以看出，編碼所得的碼字，沒有相同的，所以是非奇異碼也沒有一個(gè)碼字是其它碼字的前綴，所以是即時(shí)碼（非延長(zhǎng)碼），也是單義可譯碼。用樹圖構(gòu)造出來(lái)可以看出符合非延長(zhǎng)碼特點(diǎn)。平均信息傳輸率平均碼長(zhǎng)與信息熵香農(nóng)碼編碼效率并不是很高，不是最佳碼，為什么？圖上可以看出來(lái)嗎？碼符號(hào)/信源符號(hào)

6.6香農(nóng)碼2013秋季信息1145InfTheory&Coding-張祖平練習(xí)46信源共有7個(gè)符號(hào)組成，其概率如表所示，求二進(jìn)制香農(nóng)碼，平均碼長(zhǎng)和信息傳輸率。信源消息符號(hào)xi符號(hào)概率p(xi)x1

0.20x2

0.19x3

0.18x4

0.17x5

0.15x6

0.10x7

0.016.6香農(nóng)碼2013秋季信息1146InfTheory&Coding-張祖平47xip(xi)累加Pi-log2

p(xi)碼字長(zhǎng)度Ki碼字x10.2002.343000x20.190.22.413001x30.180.392.483011x40.170.572.563100x50.150.742.743101x60.100.893.3441110x70.010.996.66711111106.6香農(nóng)碼2013秋季信息1147InfTheory&Coding-張祖平48費(fèi)諾編碼也是一種常見的信源編碼方法。編碼步驟如下：(1)將概率按從大到小的順序排列，令

p(a1)≥p(a2)≥…≥p(an)(2)按編碼進(jìn)制數(shù)將概率分組，使每組概率盡可能接近或相等。如編二進(jìn)制碼就分成兩組，編m進(jìn)制碼就分成m組。(3)給每一組分配一位碼元。(4)將每一分組再按同樣原則劃分，重復(fù)步驟2和3，直至概率不再可分為止。6.7費(fèi)諾碼2013秋季信息1148InfTheory&Coding-張祖平49例設(shè)有一單符號(hào)離散信源,對(duì)該信源編二進(jìn)制費(fèi)諾碼。二進(jìn)制費(fèi)諾編碼

信源符號(hào)

概率

編碼

碼字

碼長(zhǎng)

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費(fèi)諾碼2013秋季信息1149InfTheory&Coding-張祖平50該信源的熵為平均碼長(zhǎng)為編碼效率為本例中費(fèi)諾編碼有較高的編碼效率。費(fèi)諾碼比較適合于每次分組概率都很接近的信源。特別是對(duì)每次分組概率都相等的信源進(jìn)行編碼時(shí)，可達(dá)到理想的編碼效率。6.7費(fèi)諾碼2013秋季信息1150InfTheory&Coding-張祖平51題中碼字還可用碼樹來(lái)表示，如圖所示。6.7費(fèi)諾碼2013秋季信息1151InfTheory&Coding-張祖平練習(xí)52信源共有7個(gè)符號(hào)組成，其概率如表所示，求二進(jìn)制費(fèi)諾碼，平均碼長(zhǎng)和信息傳輸率。信源消息符號(hào)xi符號(hào)概率p(xi)x1

0.20x2

0.19x3

0.18x4

0.17x5

0.15x6

0.10x7

0.016.7費(fèi)諾碼2013秋季信息1152InfTheory&Coding-張祖平練習(xí)53消息符號(hào)ai各個(gè)消息概率p(ai)第一次分組第二次分組第三次分組第四次分組二元碼字碼長(zhǎng)Kia10.2000002a20.19100103a30.1810113a40.1710102a50.15101103a60.101011104a70.011111146.7費(fèi)諾碼2013秋季信息1153InfTheory&Coding-張祖平練習(xí)54信源共有8個(gè)符號(hào)組成，其概率如表所示，求二進(jìn)制費(fèi)諾碼，平均碼長(zhǎng)和信息傳輸率。6.7費(fèi)諾碼2013秋季信息1154InfTheory&Coding-張祖平練習(xí)55平均碼長(zhǎng)

編碼效率信源熵H(X)=2.75bit/sign每次兩分組的概率正好相等，效率最高6.7費(fèi)諾碼2013秋季信息1155InfTheory&Coding-張祖平香農(nóng)碼與費(fèi)諾碼總結(jié)香農(nóng)第一編碼定理給出了碼字的平均長(zhǎng)度的下界和上界。但并不是說(shuō)大于這上界不能構(gòu)成單義可譯碼，而是因?yàn)槲覀兛偸窍ＭM可能短。也就是說(shuō)，定理給出的是最佳碼（比其他單義可譯碼平均碼長(zhǎng)都小的編碼）的最短平均碼長(zhǎng)的下界和上界，并指出這個(gè)最短的平均碼長(zhǎng)與信源熵是有關(guān)的。無(wú)失真信源編碼的基本問題轉(zhuǎn)化為找出緊致碼（最佳碼）。最佳編碼基本思想：將概率大的信息符號(hào)編以短的碼字，概率小的符號(hào)編以長(zhǎng)的碼字。最佳碼的編碼主要方法：香農(nóng)（Shannon）、費(fèi)諾（Fano）、哈夫曼（Huffman）編碼等。香農(nóng)碼：編碼唯一，但通常效率不高，學(xué)術(shù)意義大于實(shí)際意義；費(fèi)諾碼：由于賦碼元時(shí)的任意性，因此編出的碼字不是唯一的；構(gòu)造碼樹時(shí)自頂向下；編碼效率高于香農(nóng)碼，適合于對(duì)分組概率相等或接近的信源編碼；香農(nóng)碼和費(fèi)諾碼都不是真正意義上的最佳碼，哈夫曼編碼實(shí)現(xiàn)了最佳編碼。566.7費(fèi)諾碼2013秋季信息1156InfTheory&Coding-張祖平57哈夫曼1953年于MIT獲得科學(xué)博士學(xué)位哈夫曼編碼是1951年，他在研究生階段課程（信息論與編碼）的課程大作業(yè)中提出的，哈夫曼使用自底向上的方法構(gòu)建二叉樹，避免了次優(yōu)算法Shannon-Fano編碼的最大弊端──自頂向下構(gòu)建樹，該算法廣泛應(yīng)用于數(shù)據(jù)壓縮和計(jì)算機(jī)安全領(lǐng)域。離開MIT后，哈夫曼來(lái)到加利福尼亞大學(xué)的計(jì)算機(jī)系任教。哈夫曼從未為此算法申請(qǐng)過專利或其它相關(guān)能夠?yàn)樗麕?lái)經(jīng)濟(jì)利益的東西，他將他全部的精力放在教學(xué)上，以他自己的話來(lái)說(shuō)，“我所要帶來(lái)的就是我的學(xué)生?！盌avidA.Huffman(1925-1999)6.8Huffman編碼2013秋季信息1157InfTheory&Coding-張祖平還記得數(shù)據(jù)結(jié)構(gòu)中的哈夫曼碼嗎？？哈夫曼編碼是最佳碼（即平均碼長(zhǎng)最小）怎么證明這一點(diǎn)？哈夫曼在1952年的原始論文中并沒有給出證明后人給出了不同的證明方法特點(diǎn)：自底向上構(gòu)造碼樹把碼長(zhǎng)小的碼字分配給出現(xiàn)頻率高的信源字符在編碼過程中需要構(gòu)造虛擬節(jié)點(diǎn)每次縮減信源的最長(zhǎng)兩個(gè)碼字有相同的碼長(zhǎng)。586.8Huffman編碼2013秋季信息1158InfTheory&Coding-張祖平(1)將信源符號(hào)按概率從大到小的順序排列，令

p(a1)≥p(a2)≥…≥p(an)(2)給兩個(gè)概率最小的信源符號(hào)p(an-1)和p(an)各分配一個(gè)碼位“0”和“1”，將這兩個(gè)信源符號(hào)合并成一個(gè)新符號(hào)，并用這兩個(gè)最小的概率之和作為新符號(hào)的概率，結(jié)果得到一個(gè)只包含(q－1)個(gè)信源符號(hào)的新信源。稱為信源的第一次縮減信源，用S1表示。(3)將縮減信源S1的符號(hào)仍按概率從大到小順序排列，重復(fù)步驟2，得到只含(q－2)個(gè)符號(hào)的縮減信源S2。(4)重復(fù)上述步驟，直至縮減信源只剩兩個(gè)符號(hào)為止，此時(shí)所剩兩個(gè)符號(hào)的概率之和必為1。然后從最后一級(jí)縮減信源開始，依編碼路徑向前返回，就得到各信源符號(hào)所對(duì)應(yīng)的碼字。596.8Huffman編碼2013秋季信息1159InfTheory&Coding-張祖平600.40.4

0.4

0.61.00.20.2

0.4

0.40.20.2

0.20.10.2

0.110101010aip(ai)碼字Wi1a10.40a20.210a30.2111a40.11101a50.111006.8Huffman編碼2013秋季信息1160InfTheory&Coding-張祖平61

碼元/符號(hào)

平均碼長(zhǎng)、編碼效率aip(ai)碼字Wi1a10.40a20.210a30.2111a40.11101a50.111006.8Huffman編碼2013秋季信息1161InfTheory&Coding-張祖平620.40.4

0.4

0.61.00.20.2

0.4

0.40.20.2

0.20.10.2

0.101010101aip(ai)碼字Wi2a10.41a20.201a30.2000a40.10010a50.1001101106.8Huffman編碼2013秋季信息1162InfTheory&Coding-張祖平63aip(ai)碼字Wi2a10.41a20.201a30.2000a40.10010a50.10011

碼元/符號(hào)

平均碼長(zhǎng)、編碼效率6.8Huffman編碼2013秋季信息1163InfTheory&Coding-張祖平64aip(ai)碼字Wi3a10.400a20.210a30.211a40.1010a50.10110.40.4

0.4

0.61.00.20.20.40.40.20.2

0.20.10.20.1010101016.8Huffman編碼2013秋季信息1164InfTheory&Coding-張祖平65

碼元/符號(hào)

平均碼長(zhǎng)、編碼效率aip(ai)碼字Wi3a10.400a20.210a30.211a40.1010a50.10116.8Huffman編碼2013秋季信息1165InfTheory&Coding-張祖平哈夫曼編碼形式不是唯一的，用方差選擇較好的編碼由于0，1順序可以不同，導(dǎo)致不一樣由于出現(xiàn)合并后等概率情況，排序位置不同，導(dǎo)致不一樣aip(ai)碼字Wi1碼字Wi2碼字Wi3a10.40100a20.2100110a30.211100011a40.111010010010a50.111000011011W2和w3編碼的方差不同，進(jìn)行哈夫曼編碼時(shí)，為得到碼方差最小的碼，應(yīng)使合并的信源符號(hào)位于縮減信源序列盡可能高的位置上，以減少再次合并的次數(shù)，充分利用短碼。

方差越小，說(shuō)明各個(gè)碼的長(zhǎng)度都比較接近平均長(zhǎng)度，這樣編碼器和解碼器就可以比較簡(jiǎn)單6.8Huffman編碼2013秋季信息1166InfTheory&Coding-張祖平練習(xí)信源共有7個(gè)符號(hào)組成，其概率如表所示，求二進(jìn)制哈夫曼編碼，平均碼長(zhǎng)和信息傳輸率。信源消息符號(hào)xi符號(hào)概率p(xi)x1

0.20x2

0.19x3

0.18x4

0.17x5

0.15x6

0.10x7

0.016.8Huffman編碼2013秋季信息1167InfTheory&Coding-張祖平練習(xí)680.20 0.200.260.350.390.611.00.190.190.200.260.350.390.180.180.190.200.260.170.170.180.190.150.150.170.100.110.010101010101016.8Huffman編碼2013秋季信息1168InfTheory&Coding-張祖平練習(xí)69信源符號(hào)符號(hào)概率編碼過程碼字碼長(zhǎng)0.201020.191120.1800030.1700130.1501030.10011040.0101114010.200.190.180.170.150.110.260.200.190.180.1701010.260.350.200.19010.350.260.39010.390.61016.8Huffman編碼2013秋季信息1169InfTheory&Coding-張祖平練習(xí)700.010.100.110.150.260.170.180.350.610.190.200.39

1011001011001采用碼樹形式進(jìn)行哈夫曼編碼的過程中，由于代表信源符號(hào)的節(jié)點(diǎn)都是終端節(jié)點(diǎn)，因此其編碼不可能是其它終端節(jié)點(diǎn)對(duì)應(yīng)的編碼的前綴。哈夫曼編碼一定是非延長(zhǎng)碼。哈夫曼編碼總是把概率大的符號(hào)安排在離根節(jié)點(diǎn)近的終端節(jié)點(diǎn)，所以平均碼長(zhǎng)短。6.8Huffman編碼2013秋季信息1170InfTheory&Coding-張祖平多元Huffman編碼平均碼長(zhǎng)=2*0.24+2*0.2+2*0.18+2*0.16+2*0.14+2*0.08=2碼符號(hào)/信源符號(hào)定長(zhǎng)編碼？這樣編碼效率高嗎？為什么？6.8Huffman編碼2013秋季信息1171InfTheory&Coding-張祖平72012012012012w1w2w3w4w5w6？很明顯可以使用“0”這個(gè)短碼來(lái)作為概率最大的S1的編碼，為什么編碼結(jié)果卻沒有用到呢？因?yàn)樽詈笠淮慰s減，沒有把碼符號(hào)集中所有符號(hào)都用上，最后一次縮減是針對(duì)大概率信源符號(hào)的，是短碼，短碼沒有充分利用，反而優(yōu)先把小概率的信源符號(hào)，是長(zhǎng)碼，用上了所有碼符號(hào)集中的符號(hào)。多元Huffman編碼6.8Huffman編碼2013秋季信息1172InfTheory&Coding-張祖平7312012012012012012非全樹全樹m進(jìn)制的全樹的終端葉節(jié)點(diǎn)數(shù)(碼個(gè)數(shù))m+k(m-1),k=0,1,2,….(每從一個(gè)節(jié)點(diǎn)分出m枝,就增加m-1個(gè)終端)當(dāng)信源符號(hào)數(shù)n，n<m+k(m-1)時(shí)，令s=[m+k(m-1)]-n,s<m-1，為構(gòu)成全樹所缺少的碼字(分支)數(shù)，必須在信源符號(hào)集合中補(bǔ)上概率為0的s個(gè)虛假符號(hào)w1w2w3w4w5w6多元Huffman編碼6.8Huffman編碼2013秋季信息1173InfTheory&Coding-張祖平74m