信息論與編碼理論基礎(chǔ)(第三章)

1、通信系統(tǒng)模型2022/8/101 信源發(fā)出的消息序列通常不能直接送給信道傳輸，需要經(jīng)過信源編碼和信道編碼。 2022/8/102信道編碼在傳輸過程中噪聲和干擾在所難免，為了降低差錯率，提高傳送的可靠性，在信道編碼器中可以引入冗余度，在信道解碼端就可以利用此冗余度來盡可能地重建輸入序列?？煽啃裕涸黾尤哂?022/8/103信源編碼對信源進行壓縮、擾亂和加密，用最少的碼字最安全地傳輸最大的信息量：有效性和安全性：去除冗余如何對信源進行建模？（如隨機過程）如何測量信源的內(nèi)容？（熵）如何表示一個信源？（編碼：碼字設(shè)計）2022/8/104為什么需要信源編碼/數(shù)據(jù)壓縮數(shù)字化視頻和音頻等媒體信息的數(shù)據(jù)量很

2、大數(shù)字音頻格式頻帶范圍（Hz）取樣頻率（kHz）樣本精度（bit）聲道數(shù)原始碼率（Kb/s）電話300340088164調(diào)頻（FM）廣播201500022.03162705.6激光唱盤（CD）202000044.11621411.2數(shù)字視頻格式每秒幀數(shù)圖像分辨率（像素）樣本精度（bit）亮度信號原始碼率（Mb/s）CIF格式的亮度信號30352*288824.33HDTV亮度信號一例601920*10808995.32022/8/105為什么需要信源編碼/數(shù)據(jù)壓縮減少存儲空間文件壓縮、圖像壓縮、語音壓縮、視頻壓縮減少傳輸時間2022/8/106信源編碼/數(shù)據(jù)壓縮的例子： 摩爾斯式電碼19世紀(jì)中

3、葉，由 Samuel Morse發(fā)明每個字符用“ .” 或“” 表示觀察：一些字符比另外一些字符出現(xiàn)的頻率更高，如 “a, e”比“z, q”出現(xiàn)的頻率高因此，為了減少發(fā)送信息的平均時間，用較短的序列表示出現(xiàn)頻率高的字符，較長的序列表示出現(xiàn)頻率低的字符e: . , a: . q: - - . - , j: . - - - 2022/8/107為什么可以進行信源編碼/數(shù)據(jù)壓縮自然界中的大多數(shù)數(shù)據(jù)都是冗余的： 任何非隨機選擇的數(shù)據(jù)都有一定結(jié)構(gòu)，可利用這種結(jié)構(gòu)得到數(shù)據(jù)的更緊致表示統(tǒng)計冗余：大多數(shù)常見的壓縮算法都是利用該冗余字母冗余：英文中字母E最常出現(xiàn)，而Z很少出現(xiàn)文本冗余：字母Q后常跟有字母U20

4、22/8/108例：空間冗余圖像中存在大面積部分相似或完全一樣的像素pmf2022/8/109例：時間冗余視頻圖像前后幾幀的內(nèi)容變化不大（位置可能不同，可用運動估計方法找到對應(yīng)位置）2022/8/1010例：結(jié)構(gòu)冗余圖像中物體表面紋理等結(jié)構(gòu)存在冗余2022/8/1011怎樣進行信源編碼無失真編碼:若要求將信源輸出在接收端精確地重現(xiàn)出來，即保證信源輸出所攜帶的信息全部無損地傳達給信宿，就要對信源進行無失真編碼。無失真編碼只是對信源冗余度進行壓縮，并不改變信源熵，它能保證信源序列經(jīng)無擾信道傳輸后，得到無失真的恢復(fù)。限定失真編碼：在實際傳信中，要精確的復(fù)制出信源的輸出是不可能的，根據(jù)信源信宿對定出的

5、可接收準(zhǔn)則或保真度準(zhǔn)則，計算要保留多少有關(guān)信源輸出的信息量，以及如何表示它們，這就是限定失真的信源編碼問題。2022/8/1012第三章：信源編碼（一）離散信源無失真編碼3.1 信源及其分類3.2 離散無記憶（簡單）信源的等長編碼3.3 離散無記憶（簡單）信源的不等長編碼3.4 最佳不等長編碼2022/8/10133.1 信源及其分類信源的概念 :信源就是信息的來源。注意：在一個固定的時刻，信源發(fā)出的是一個隨機變量。隨著時間的延續(xù)，信源發(fā)出一個又一個隨機變量，稱之為一個隨機過程。 因此，可以用概率空間來描述信源。 2022/8/10143.1 信源及其分類離散信源 信源每隔一個定長時間段就發(fā)出

6、一個隨機變量； 隨著時間的延續(xù)，信源發(fā)出的是隨機變量序列U-2U-1U0U1U2， 其中 Uk為第k個時間段發(fā)出的隨機變量； 每個Uk都是一個離散型的隨機變量。離散無記憶信源 隨機變量、U-2、U-1、U0、U1、U2、 相互獨立的離散信源。離散無記憶 隨機變量、U-2、U-1、U0、U1、 U2、 簡單信源 具有相同的概率分布的離散無記憶信源。2022/8/10153.1 信源及其分類（總結(jié)：離散無記憶簡單信源就是時間離散、事件離散、各隨機變量獨立同分布的信源。課程學(xué)習(xí)所面對的信源將主要是離散無記憶簡單信源）一般的信源 連續(xù)信源：有時間連續(xù)的信源，也有事件連續(xù)的信源；有記憶信源：信源在不同時

7、刻發(fā)出的隨機變量相互依賴；有限記憶信源：在有限時間差內(nèi)的信源隨機變量相互依賴；非簡單信源：信源在不同時刻發(fā)出的隨機變量具有不同的 概率分布。馬爾可夫信源：信源隨機過程是馬爾可夫過程。 2022/8/10163.2 離散無記憶（簡單）信源的等長編碼（1）設(shè)有一個離散無記憶簡單信源，信源發(fā)出的隨機變量序列為：U-2U-1U0U1U2。 設(shè)信源隨機變量U1的事件有K個：a1, a2, , aK，則L維信源隨機向量(U1U2UL)的事件有KL個：(u1u2uL)|其中每個分量ul跑遍a1, a2, , aK。P(U1U2UL)=(u1u2uL)=P(U1=u1)P(U2=u2) P(UL=uL)=P(

8、U1=u1)P(U1=u2) P(U1=uL)=q(u1)q(u2) q(uL)（2） D元編碼：設(shè)有一個含D個字母的字母表，對于(U1U2UL)的每一個事件(u1u2uL)，都用一個字母串(c1c2)來表示。 2022/8/1017碼長：碼字所含碼元的個數(shù) 等長編碼：所有碼字均有相同的碼長N，對應(yīng)的碼 叫做等長碼(FLC，F(xiàn)ixed Length code)；否則為變長編碼。編碼器碼字:每一個事件(u1u2uL)所對應(yīng)的字母串(c1c2) 。 編碼器模型：D個字母的字母表A信源2022/8/1018熵是隨機變量平均不確定性的一個測度，表示了描述這個隨機變量所需要的平均比特數(shù)2022/8/10

9、193.2 離散無記憶（簡單）信源的等長編碼例：離散無記憶簡單信源發(fā)出的隨機變量序列為：U-2U-1U0U1U2。其中U1的事件有3個：晴, 云, 陰。(U1U2)有9個事件 （晴晴），（晴云），（晴陰），（云晴），（云云），（云陰），（陰晴），（陰云）， （陰陰）。用字母表0, 1對(U1U2)的事件進行2元編碼如下： （晴晴）0000，（晴云）0001，（晴陰）0011， （云晴）0100，（云云）0101，（云陰）0111， （陰晴）1100，（陰云）1101，（陰陰）1111。2022/8/1020無錯編碼 （唯一可譯碼） (U1U2UL)的不同事件用不同的碼字來表示。 能夠?qū)崿F(xiàn)無錯編

10、碼的充要條件是DNKL。（即NlogD/LlogK）這里N/L表示每個信源符號所需要的碼符號數(shù)； logD是一個碼符號所能載荷的最大信息量；N/LlogK/logD說明對于等長唯一可譯碼平均每個信源符號至少需要logK/logD個碼符號對其進行編碼變換；（NlogD）/L是編碼后平均每個信源符號所能載荷的信息量的最大值，稱為編碼速率，記為R. 關(guān)于編碼速率的說明： 由編碼速率的計算公式R=NlogD/L，似乎可以任意設(shè)置N和L，進而可以任意設(shè)置編碼速率。事實上存在著編碼設(shè)備的性能指標(biāo)：編碼速率R0。這就是說，選擇N和L，必須使得實際的編碼速率NlogD/L不能超過編碼設(shè)備的編碼速率R0 。有錯

11、編碼 (U1U2UL)的有些不同事件用相同的碼字來表示。編碼是一種由消息集到碼字集的映射2022/8/10213.2 離散無記憶（簡單）信源的等長編碼無錯編碼的最低代價當(dāng)R=(NlogD)/LlogK時，能夠?qū)崿F(xiàn)無錯編碼。 （DNKL）當(dāng)RH(U1)時，無論怎樣編碼都是有錯編碼。這是因為RH(U1)logK。 （DNRH(U1)時，雖然無論怎樣編碼都是有錯編碼，但可以適當(dāng)?shù)鼐幋a和譯碼使譯碼錯誤的概率pe任意小。這就是所謂“漸進無錯編碼”。3.2 離散無記憶（簡單）信源的等長編碼2022/8/10233.2 離散無記憶（簡單）信源的等長編碼我們以英文電報為例，由于英文字母之間有很強的關(guān)聯(lián)性，當(dāng)用

12、字母組合成不同的英文字母序列時，并不是所有的字母組合都是有意義的單詞，若再把單詞組合成更長的字母序列時，也不是任意的單詞組合都是有意義的句子，因此，在足夠長的英文字母序列中，就有許多無用和無意義的序列，這些信源序列出現(xiàn)的概率等于零或任意小，那么在編碼時，對于那些無用的字母組合，無意義的句子都可以不編碼，從而提高傳輸效率，但同時，會引入一定的誤差，但是當(dāng)L足夠大時，這種誤差概率就可以任意小，可做到幾乎無失真編碼。2022/8/10243.2 離散無記憶（簡單）信源的等長編碼漸進無錯編碼 （簡單地說就是：當(dāng)RH(U1)時，可以適當(dāng)?shù)鼐幋a和譯碼使得譯碼錯誤的概率pe任意小。嚴(yán)格地說就是：） 設(shè)給定了

13、編碼設(shè)備的編碼速率R0，R0H(U1)。則對任意的0，總存在一個L0，使得對任意的LL0，都有對(U1U2UL)的等長編碼和對應(yīng)的譯碼方法，滿足實際的編碼速率R=NlogD/LR0，譯碼錯誤的概率pe。2022/8/10253.2 離散無記憶（簡單）信源的等長編碼不能漸進無錯的編碼 （簡單地說就是：當(dāng)RH(U1)時，無論怎樣編碼和譯碼都不能使譯碼錯誤的概率pe任意小。嚴(yán)格地說就是： ） 設(shè)給定了編碼設(shè)備的編碼速率R0，R00有PH(U1)-ILH(U1)+2022/8/1028切比雪夫不等式注：切比雪夫2022/8/10293.2 離散無記憶（簡單）信源的等長編碼取定L0使得 ，則當(dāng)LL0時總

14、有因此當(dāng)LL0時總有這樣的一些事件序列， H(U1)-ILH(U1)+，而且PH(U1)-ILH(U1)+1-。說明當(dāng)L足夠大時，信源序列的自信息量的均值以概率1收斂于信源熵。當(dāng)L足夠大時，在信源序列中必有一些消息序列其自信息量的均值與信源熵之差小于，而對另外一些信源序列其差 ，因此，可以把信源序列分成兩個互補的子集。 2022/8/10303.2 離散無記憶（簡單）信源的等長編碼定義3.2.1(p57) 定義TU(L, )=(u1u2uL)|H(U1)-ILH(U1)+， 稱TU(L, )為-典型序列集。 稱TU(L, )的補集為非-典型序列集。 （綜上所述有）定理3.2.1(信源劃分定理，

15、p58) 對任意0，取L0使得則當(dāng)LL0時總有P(U1U2UL) )=(u1u2uL)| (u1u2uL) TU(L, )1-。 2022/8/10313.2 離散無記憶（簡單）信源的等長編碼（簡記H(U)=H(U1)。設(shè)以下的對數(shù)都是以2為底的。）系3.2.1(特定典型序列出現(xiàn)的概率，p58) 若一個特定的事件(u1u2uL)TU(L, )，則2-L(H(U)+)P(U1U2UL)=(u1u2uL)2-L(H(U)-)。 證明 設(shè)(u1u2uL)TU(L, )。注意到此時H(U)-ILH(U)+，2022/8/10323.2 離散無記憶（簡單）信源的等長編碼所以2022/8/10333.2

16、離散無記憶（簡單）信源的等長編碼系3.2.2(典型序列的數(shù)量，p58) (1-)2L(H(U)-)|TU(L, )|2L(H(U)+)。證明 一方面，2022/8/10343.2 離散無記憶（簡單）信源的等長編碼另一方面，2022/8/10353.2 離散無記憶（簡單）信源的等長編碼 P(U1U2UL) )=(u1u2uL)| (u1u2uL) TU(L, )1-。系3.2.1(特定典型序列出現(xiàn)的概率)2-L(H(U)+)P(U1U2UL)=(u1u2uL)2-L(H(U)-)。系3.2.2(典型序列的數(shù)量) (1-)2L(H(U)-)|TU(L, )|2L(H(U)+)。2022/8/103

17、63.2 離散無記憶（簡單）信源的等長編碼典型序列集非典型序列集序列集合定理3.2.1，系3.2.1以及系3.2.2就說明：所有典型序列的概率和接近于1，是高概率集；典型序列集中各序列出現(xiàn)的概率近似相等；每個典型序列中一個信源符號的平均信息量接近于信源熵；當(dāng)L達到無限時，才等于信源熵。2022/8/10373.2 離散無記憶（簡單）信源的等長編碼補充引理 設(shè)給定一個R0H(U)。對每個正整數(shù)L，對應(yīng)地取整數(shù)N=R0L（R0L的下取整）。則0R0L-N1 即 0R0-N/LL0時N/LR0-R0- (R0 -H(U)/2=H(U)+(R0-H(U)/2H(U)+。P(U1U2UL)TU(L, )

18、1-。 （由定理3.2.1）2022/8/10383.2 離散無記憶（簡單）信源的等長編碼定理3.2.2(無錯編碼正定理，p60) 給定編碼設(shè)備的編碼速率R0，R0H(U)。則對任意的0，總存在一個L0，使得對任意的LL0，都有對(U1U2UL)的2元等長編碼方法和對應(yīng)的譯碼方法，實際的編碼速率R滿足R0RH(U)，“譯碼錯誤”的概率peH(U)；“譯碼錯誤”的概率pe=P(U1U2UL)不屬于TU(L, )=1-P(U1U2UL)TU(L, )。得證。 定理3.2.2(無錯編碼反定理，p60) 設(shè)給定編碼設(shè)備的編碼速率R0，滿足R0H(U)；給定一個任意小的正數(shù)0；要求：選擇合適的L，N，對

19、(U1U2UL)進行合適的2元N長編碼，使得實際的編碼速率R=N/L滿足RR0；“譯碼錯誤”的概率pe。2022/8/1042漸進無錯編碼的步驟由U1的概率分布計算取L滿足 。取整數(shù)N=R0L（R0L下取整）。取典型序列集2022/8/1043漸進無錯編碼的步驟將TU(L, )中的事件用不同的N長2元碼字來表示，而將TU(L, )以外的事件用一個固定的N長2元碼字來表示，這個固定的N長2元碼字已經(jīng)用來表示了TU(L, )中的某個事件。譯碼時，所有的碼字均譯為它所表示的TU(L, )中的事件。（注解：顯然滿足RR0；| TU(L, ) | 2N，因此碼字足夠用；譯碼錯誤的概率為pe=P(U1U2

20、UL)=(u1u2uL)| (u1u2uL)不屬于TU(L, )0.037587148=H(U1)。希望：2元編碼的實際編碼速率RR0；譯碼錯誤的概率不超過。其中取=0.1。找L使得2022/8/10463.2 離散無記憶（簡單）信源的等長編碼取L=253即可。再取N=R0L=126。將TU(L, )中的事件用不同的N長2元碼字來表示，而將TU(L, )以外的事件用一個固定的N長2元碼字來表示，這個固定的N長2元碼字已經(jīng)用來表示了TU(L, )中的某個事件。譯碼時，所有的碼字均譯為它所表示的TU(L, )中的事件。另一方面， TU(L, )中的事件有更加簡單的表達方式。當(dāng)事件(u1u2uL)中

21、a1的個數(shù)為k，a2的個數(shù)為L-k時，2022/8/10473.2 離散無記憶（簡單）信源的等長編碼事件(u1u2uL)屬于典型序列集TU(L, 0.1)；當(dāng)且僅當(dāng)2022/8/10483.2 離散無記憶（簡單）信源的等長編碼當(dāng)事件(u1u2u253)中a1的個數(shù)不超過4時， (u1u2u253)TU(253, 0.1)；否則(u1u2u253)不屬于TU(253, 0.1)。(u1u2u253)TU(253, 0.1)的概率不小于0.9；(u1u2u253)TU(253, 0.1)的個數(shù)為2022/8/10493.2 離散無記憶（簡單）信源的等長編碼對L=253，對應(yīng)地取整數(shù)N=R0L=12

22、6。則N/LR0，這就是說2元編碼的實際編碼速率并未超出編碼設(shè)備的編碼速率。2元編碼的編碼方法： 將TU(253, 0.1)中的事件用不同的126長碼字表示；將TU(253, 0.1)外的事件用同一個126長碼字表示，該碼字已經(jīng)用于表示了TU(253, 0.1)中的一個事件。由于|TU(253, 0.1)|233.355557444qb，其碼長也具有不等式nanb。 現(xiàn)在將事件a和b交換碼字，其它事件的碼字保持不變。此時2元異字頭碼S 變成新的2元異字頭碼T。由于碼S與碼T中事件a和b之外的其它事件的碼字保持不變，因而它們對平均碼長的貢獻不變，而碼S 中事件a和b的碼字對平均碼長的貢獻為qan

23、a+qbnb；碼T中事件a和b的碼字對平均碼長的貢獻為qanb+qbna。(qana+qbnb)-(qanb+qbna)=(qa-qb)(na-nb)0。 這就是說，碼S 的平均碼長碼T 的平均碼長。因而碼S 不是最佳2元異字頭碼。 用反證法已經(jīng)證明了補充引理2。 2022/8/10763.4 最佳不等長編碼補充引理3 設(shè)信源隨機變量U的最佳2元異字頭碼S ，則最長的碼字至少有兩個。證明 如果2元異字頭碼S 的最長的碼字竟然只有一個。 設(shè)這個碼字為c，是事件a的碼字。 現(xiàn)在將c的最后一位去掉，成為c，將c仍然作為事件a的碼字。其它事件的碼字保持不變。此時2元異字頭碼S 變成新的2元碼T。注意到

24、以下兩點：碼T仍然是2元異字頭碼；碼S 的平均碼長碼T 的平均碼長。 因而碼S 不是最佳2元異字頭碼。用反證法已經(jīng)證明了補充引理3。2022/8/1077aa2022/8/10783.4 最佳不等長編碼補充引理4 最佳2元異字頭碼S可以滿足以下兩條：（1）概率最小的兩個事件碼字最長，且長度相等；（2）它們的碼字僅僅最后一位不同。證明 取概率最小的事件a。在剩下的事件中取概率最小的事件b。根據(jù)補充引理2和補充引理3，事件a和事件b的碼字最長，且長度相等。這就是說，最佳2元異字頭碼S顯然滿足第（1）條。 關(guān)于第（2）條，分以下三種情形來討論：2022/8/10793.4 最佳不等長編碼情形一事件a

25、和事件b的碼字僅僅最后一位不同。此時：最佳2元異字頭碼S 滿足第（2）條。補充引理4得證。情形二事件a和事件b的碼字不是僅僅最后一位不同，但有第三個事件c，其碼字與事件a的碼字僅僅最后一位不同。此時：將事件b與事件c交換碼字，得到新的2元異字頭碼T。碼T與碼S平均碼長相同，因此碼T也是最佳2元異字頭碼，且碼T滿足第（1）條和第（2）條。情形三事件a和事件b的碼字不是僅僅最后一位不同，也沒有第三個事件c，其碼字與事件a的碼字僅僅最后一位不同。此時：將事件b的碼字換為與事件a的碼字僅僅最后一位不同，得到新的碼T。碼T 也是2元異字頭碼。碼T與碼S平均碼長相同，因此碼T也是最佳2元異字頭碼，且碼T滿

26、足第（1）條和第（2）條。2022/8/1080abacb3.4 最佳不等長編碼abcabab2022/8/1081Huffman編碼的最佳性定理3.4.1：對于給定信源，存在有最佳惟一可譯二元碼，其最小概率的兩個碼字CK-1和CK的長度最長且相等，它們之間僅最后一位碼元取值不同(一個為0，另一個為1)。 2022/8/10823.4 最佳不等長編碼補充定理 設(shè)信源隨機變量U有K個事件， K3。取出兩個概率最小的事件：事件a和事件b。將事件a與事件b合并成一個事件e， e的概率為事件a與事件b的概率之和；而將信源隨機變量U的其它事件和其對應(yīng)的概率保持不變。這樣得到了新的信源隨機變量U。找到U的

27、一個最佳2元異字頭碼R。將碼R中事件e的碼字后面分別添加0和1，分別作為事件a和事件b各自的碼字；而將碼R中其它事件的碼字保持不變。這樣得到了U的2元碼R。則：碼R是U的最佳2元異字頭碼。2022/8/10833.4 最佳不等長編碼證明 首先說明， 碼R是U的2元異字頭碼。 碼R中，每個碼字都在樹梢，對事件e的碼字后面分別添加0和1后，得到碼R， 碼R中，由事件e的碼字后面分別添加0和1得到的兩個碼字對應(yīng)于碼數(shù)中的兩個新的葉子節(jié)點，位于樹梢；而其它碼字顯然也在樹梢。 綜上所述，碼R是U的2元異字頭碼。 接下來說明，對輔助集U 為最佳的碼，對原始消息集U也是最佳的。2022/8/1084設(shè)原始信

28、源隨機變量新的信源隨機變量3.4 最佳不等長編碼2022/8/10853.4 最佳不等長編碼若C1，C2，CK-1是信源U 的最佳碼，相應(yīng)碼長為n1，n2，nK-1，則對信源U的碼字C1，C2, CK的碼長為nk= nk kK2nk= nK-1+1 k=K, K1同時兩信源各事件出現(xiàn)的概率滿足關(guān)系式：pk= pk kK2pK+pK-1= pK-12022/8/10863.4 最佳不等長編碼 2022/8/10873.4 最佳不等長編碼補充定理給出了一種構(gòu)造信源隨機變量U的最佳2元異字頭碼的方法：取出兩個概率最小的事件a和事件b，分別標(biāo)號為0和1；然后將事件a和事件b合并成事件e，因此將信源隨機

29、變量U合并成U；尋找U的最佳2元異字頭碼；然后將該碼中事件e的碼字后面分別添加事件a和事件b的標(biāo)號（0和1），分別成為事件a和事件b的碼字。這種構(gòu)造方法正是2元Huffman編碼。換句話說，定理 對信源隨機變量U的2元Huffman編碼是最佳2元異字頭碼，因而是在唯一可譯前提下的最佳2元不等長編碼。2022/8/10883.4 最佳不等長編碼2元Huffman編碼法（字母表0, 1）（1）將概率最小的2個事件分別賦予標(biāo)號“0”和“1”。（2）將這2個事件合并為一個事件，其概率為2個事件概率之和。重復(fù)（1）-（2），直到合并為所剩的事件為2個。將這2事件分別賦予標(biāo)號“0”和“1”。編碼完畢。此時

30、，一個事件的碼字是這個事件從最后標(biāo)號開始到最先標(biāo)號為止的標(biāo)號序列。2022/8/1089例：Huffman編碼過程2022/8/1090例：Huffman編碼過程2022/8/1091P59 Shannon-Fano編碼例子采用Huffman編碼a 16b 7c 6d 6e 511132401010101a 0b 100c 101d 110e 111總比特數(shù)88，信源熵為86.601bit2022/8/1092Huffman編碼Shannon-Fano編碼構(gòu)造二叉樹是自樹根到樹葉，很難保證最佳性。Huffman編碼則是從樹葉到樹根，是最佳的2022/8/1093總結(jié)Huffman需要知道信源的

31、概率分布，這在實際中有時是比較困難的。采用半靜態(tài)模型、自適應(yīng)模型、markov模型，部分匹配預(yù)測模型等等解決這一問題。2022/8/1094D元Huffman編碼D元碼全數(shù)的端節(jié)點數(shù)為D+m(D-1)由Huffman編碼的最佳性知空缺的端節(jié)點應(yīng)當(dāng)是碼長最長的端節(jié)點共有K個符號，設(shè)第一次需要合并的消息個數(shù)為R，空缺數(shù)為BB個R個2022/8/1095D元Huffman編碼 K+B=D+m(D-1)，因而K-2=m(D-1)+D-2-B 注意R+B=D，有 0BD-2， 0D-2-BD-2 因而D-2-B=(K-2)mod(D-1)即 R-2=(K-2)mod(D-1)B個R個2022/8/109

32、6Huffman 編碼效率高，運算速度快，實現(xiàn)方式靈活，從 20 世紀(jì) 60 年代至今，在數(shù)據(jù)壓縮領(lǐng)域得到了廣泛的應(yīng)用。今天，在許多知名的壓縮工具和壓縮算法（如 WinRAR 、 gzip 和 JPEG ）里，都有 Huffman 編碼的身影。不過， Huffman 編碼所得的編碼長度只是對信息熵計算結(jié)果的一種近似，還無法真正逼近信息熵的極限。正因為如此，現(xiàn)代壓縮技術(shù)通常只將 Huffman 作為最終的編碼手段，而非數(shù)據(jù)壓縮算法的全部。同時科學(xué)家們一直沒有放棄向信息熵極限挑戰(zhàn)的理想。 1968 年前后， P. Elias 發(fā)展了 Shannon 和 Fano 的編碼方法，構(gòu)造出從數(shù)學(xué)角度看來更

33、為完美的 Shannon-Fano-Elias 編碼。沿著這一編碼方法的思路， 1976 年， J. Rissanen 提出了一種可以成功地逼近信息熵極限的編碼方法算術(shù)編碼。算術(shù)編碼2022/8/1097算術(shù)編碼Shannon-Fano編碼，Huffman編碼的編碼方法：首先對信源的各事件進行編碼，然后再對輸入的消息序列進行編碼變換。算術(shù)編碼：首先假設(shè)一個信源的概率模型,隨后直接把整個輸入的消息編碼為一個(0.0 n 1.0)內(nèi)的小區(qū)間，在編碼的過程中，消息序列集中的每個元素都用來縮短這個區(qū)間，消息序列集中的元素越多,所得到的區(qū)間就越小，當(dāng)區(qū)間變小時，就需要更多的數(shù)位來表示這個區(qū)間，這就是區(qū)間

34、作為代碼的原理。2022/8/1098使用算術(shù)編碼的壓縮算法通常先要對信源符號的概率進行估計，然后再編碼。這個估計越準(zhǔn)，編碼結(jié)果就越接近最優(yōu)的結(jié)果。 例: 對一個簡單的信號源進行觀察，得到的統(tǒng)計模型如下：60% 的機會出現(xiàn)符號 中性 20% 的機會出現(xiàn)符號 陽性 10% 的機會出現(xiàn)符號 陰性 10% 的機會出現(xiàn)符號 數(shù)據(jù)結(jié)束符. 算術(shù)編碼2022/8/1099在得到信源隨機變量U的事件集的概率分布P(ak)，(k=0,1, K-1)之后，我們需要定義信源符號的分布函數(shù) ，(k=0, 1, , K-1)。 其中F(a0)=0； F(a1)=P(a0)；F(a2)=P(a0)+P(a1)； F(a

35、K-1)=P(a0)+P(a1)+ +P(aK-2)。 隨后，編碼過程的每一步，除了最后一步，都是相同的。算術(shù)編碼2022/8/10100編碼器通常需要考慮下面三種數(shù)據(jù)：下一個要編碼的符號 當(dāng)前的區(qū)間(在編第一個符號之前，這個區(qū)間是0,1), 但是之后每次編碼區(qū)間都會變化) 模型中在這一步可能出現(xiàn)的各個符號的概率分布編碼器利用信源符號的分布函數(shù)將當(dāng)前的區(qū)間分成若干子區(qū)間，區(qū)間之間的分隔線為信源符號的分布函數(shù)，每個子區(qū)間的長度與可能出現(xiàn)的對應(yīng)符號的概率成正比。當(dāng)前要編碼的符號對應(yīng)的子區(qū)間成為下一步編碼的初始區(qū)間。算術(shù)編碼2022/8/10101例: 對于前面提出的4符號模型:中性對應(yīng)的區(qū)間是 0

36、, 0.6) 陽性對應(yīng)的區(qū)間是 0.6, 0.8) 陰性對應(yīng)的區(qū)間是 0.8, 0.9) 數(shù)據(jù)結(jié)束符對應(yīng)的區(qū)間是 0.9, 1) 當(dāng)所有的符號都編碼完畢，最終得到的結(jié)果區(qū)間即唯一的確定了已編碼的符號序列。任何人使用該區(qū)間和模型參數(shù)即可以解碼重建得到該符號序列。算術(shù)編碼2022/8/10102算術(shù)碼再以二元信源輸出序列01110的編碼為例P(0)P(1)F(0)F(1)01算術(shù)編碼2022/8/10103算術(shù)碼P(00)P(01)F(0)F(01)F(1)P(010)P(011)F(011)P(0110)P(0111)F(0111)P(01110)P(01111)F(01111)算術(shù)編碼2022

37、/8/10104算術(shù)碼信源符號序列u對應(yīng)區(qū)間的寬度等于符號序列的概率信源符號序列u對應(yīng)區(qū)間的左端點為算術(shù)編碼2022/8/10105F(u)將0,1)分割成許多小區(qū)間，以小區(qū)間的左端點數(shù)值的二進制小數(shù)表示該序列，同時要將該小數(shù)的小數(shù)位數(shù)截斷為l位，截斷規(guī)則為： l位后面只要有非0的余數(shù)就要向第l位進位。 最后得到了小數(shù)0.t。將t作為事件u=(u1u2uL)的碼字。碼字長度l為算術(shù)編碼2022/8/10106算術(shù)編碼則即因而即2022/8/10107例: 下面對使用前面提到的4符號模型進行編碼的一段信息進行解碼。編碼的結(jié)果是0.538(為了容易理解，這里使用十進制而不是二進制；我們也假設(shè)得到的

38、結(jié)果的位數(shù)恰好夠我們解碼)。類似于編碼的過程，我們從區(qū)間0,1)開始，使用相同的概率模型，將它分成四個子區(qū)間。中性對應(yīng)的區(qū)間是 0, 0.6) 陽性對應(yīng)的區(qū)間是 0.6, 0.8) 陰性對應(yīng)的區(qū)間是 0.8, 0.9) 數(shù)據(jù)結(jié)束符對應(yīng)的區(qū)間是 0.9, 1) 算術(shù)編碼的譯碼2022/8/10108分?jǐn)?shù)0.538落在中性所在的子區(qū)間0,0.6)；這表明編碼器所讀的第一個符號必然是中性，這樣就可以將它作為消息的第一個符號記下來。 算術(shù)編碼的譯碼2022/8/10109然后我們將區(qū)間0,0.6)再分成四個子區(qū)間：中性的區(qū)間是 0, 0.36) - 0, 0.6) 的 60% 陽性的區(qū)間是 0.36,

39、 0.48) - 0, 0.6) 的 20% 陰性的區(qū)間是 0.48, 0.54) - 0, 0.6) 的 10% 數(shù)據(jù)結(jié)束符的區(qū)間是 0.54, 0.6). - 0, 0.6) 的 10% 分?jǐn)?shù)0.538 在 0.48, 0.54) 區(qū)間；所以消息的第二個符號一定是陰性。 算術(shù)編碼的譯碼2022/8/10110再一次將當(dāng)前區(qū)間劃分成四個子區(qū)間：中性 的區(qū)間是 0.48, 0.516) 陽性 的區(qū)間是 0.516, 0.528) 陰性 的區(qū)間是 0.528, 0.534) 數(shù)據(jù)結(jié)束符的區(qū)間是 0.534, 0.540). 分?jǐn)?shù) 0.538 落在符號數(shù)據(jù)結(jié)束符的區(qū)間；所以，這一定是下一個符號。由

40、于它也是內(nèi)部的結(jié)束符號，這也就意味著編碼已經(jīng)結(jié)束。 算術(shù)編碼的譯碼2022/8/101113.4 最佳不等長編碼算術(shù)編碼的特點特點一 當(dāng)L很大時，平均碼長接近信源熵H(U)，因此編碼效率接近上限。特點二 編譯碼簡單，存儲量小，速度快。算術(shù)編碼的應(yīng)用領(lǐng)域在圖象數(shù)據(jù)壓縮標(biāo)準(zhǔn)（如JPEG）中得到廣泛應(yīng)用。2022/8/10112 1982 年， Rissanen 和 G. G. Langdon 一起改進了算術(shù)編碼。之后，人們又將算術(shù)編碼與 J. G. Cleary 和 I. H. Witten 于 1984 年提出的部分匹配預(yù)測模型（ PPM ）相結(jié)合，開發(fā)出了壓縮效果近乎完美的算法。今天，那些名為

41、 PPMC 、 PPMD 或 PPMZ 并號稱壓縮效果天下第一的通用壓縮算法，實際上全都是這一思路的具體實現(xiàn)。 看起來，壓縮技術(shù)的發(fā)展可以到此為止了。不幸的是，事情往往不像想象中的那樣簡單：算術(shù)編碼雖然可以獲得最短的編碼長度，但其本身的復(fù)雜性也使得算術(shù)編碼的任何具體實現(xiàn)在運行時都慢如蝸牛。即使在摩爾定律大行其道， CPU 速度日新月異的今天，算術(shù)編碼程序的運行速度也很難滿足日常應(yīng)用的需求。如果不是后文將要提到的兩個猶太人，我們還不知要到什么時候才能用上 WinZIP 這樣方便實用的壓縮工具呢。詞典編碼方法2022/8/10113逆向思維永遠(yuǎn)是科學(xué)和技術(shù)領(lǐng)域里出奇制勝的法寶。就在大多數(shù)人絞盡腦汁

42、想改進 Huffman 或算術(shù)編碼，以獲得一種兼顧了運行速度和壓縮效果的“完美”編碼的時候，兩個聰明的猶太人 J. Ziv 和 A. Lempel 獨辟蹊徑，完全脫離 Huffman 及算術(shù)編碼的設(shè)計思路，創(chuàng)造出了一系列比 Huffman 編碼更有效，比算術(shù)編碼更快捷的壓縮算法。我們通常用這兩個猶太人姓氏的縮寫，將這些算法統(tǒng)稱為 LZ 系列算法。 詞典編碼方法2022/8/10114說實話， LZ 系列算法的思路并不新鮮，其中既沒有高深的理論背景，也沒有復(fù)雜的數(shù)學(xué)公式，它們只是簡單地延續(xù)了千百年來人們對字典的追崇和喜好，并用一種極為巧妙的方式將字典技術(shù)應(yīng)用于通用數(shù)據(jù)壓縮領(lǐng)域。通俗地說，當(dāng)你用字

43、典中的頁碼和行號代替文章中每個單詞的時候，你實際上已經(jīng)掌握了 LZ 系列算法的真諦。這種基于字典模型的思路在表面上雖然和 Shannon 、 Huffman 等人開創(chuàng)的統(tǒng)計學(xué)方法大相徑庭，但在效果上一樣可以逼近信息熵的極限。而且，可以從理論上證明， LZ 系列算法在本質(zhì)上仍然符合信息熵的基本規(guī)律。 詞典編碼方法2022/8/10115詞典編碼方法詞典編碼方法是基于數(shù)據(jù)中許多結(jié)構(gòu)頻繁重復(fù)再現(xiàn)這一事實, 人們可以對相同符號串分配同一碼字、通過索引、或者其他諸如此類的方法編碼。70 年代末提出、80 年代中期走向?qū)嵱没腖Z 壓縮技術(shù)開創(chuàng)了現(xiàn)代詞典編碼方法, 并且已經(jīng)牢固地統(tǒng)治著通用壓縮世界。LZ

44、的基本思想是: 數(shù)據(jù)中的子串可以通過用指代先前已處理數(shù)據(jù)(即歷史數(shù)據(jù)) 中相同子串的方式來描述。對歷史數(shù)據(jù)的存儲方式可以不同,例如，LZ77 采用滑動的緩沖區(qū)(或稱窗口) 記錄, LZ78 則選擇詞典方式進行登錄。應(yīng)該指出的是, 兩者的壓縮效率沒有顯著差異, 而且都是當(dāng)重復(fù)的子串越長壓縮效率越高。 2022/8/10116按照時間順序， LZ 系列算法的發(fā)展歷程大致是： Ziv 和 Lempel 于 1977 年發(fā)表題為“順序數(shù)據(jù)壓縮的一個通用算法”的論文，論文中描述的算法被后人稱為 LZ77 算法。 1978 年，二人又發(fā)表了該論文的續(xù)篇“通過可變比率編碼的獨立序列的壓縮”，描述了后來被命名

45、為 LZ78 的壓縮算法。 1984 年， T. A. Welch 發(fā)表了名為“高性能數(shù)據(jù)壓縮技術(shù)”的論文，描述了他在 Sperry 研究中心（該研究中心后來并入了 Unisys 公司）的研究成果，這是 LZ78 算法的一個變種，也就是后來非常有名的 LZW 算法。 1990 年后， T. C. Bell 等人又陸續(xù)提出了許多 LZ 系列算法的變體或改進版本。 詞典編碼方法2022/8/10117今天， LZ77 、 LZ78 、 LZW 算法以及它們的各種變體幾乎壟斷了整個通用數(shù)據(jù)壓縮領(lǐng)域，我們熟悉的 PKZIP 、 WinZIP 、 WinRAR 、 gzip 等壓縮工具以及 ZIP 、

46、GIF 、 PNG 等文件格式都是 LZ 系列算法的受益者，甚至連 PGP 這樣的加密文件格式也選擇了 LZ 系列算法作為其數(shù)據(jù)壓縮的標(biāo)準(zhǔn)。 詞典編碼方法2022/8/10118LZ編碼首先進行的操作稱為“分段”。分段是從前往后分，每次取最短長度的連續(xù)符號構(gòu)成段，并保證各段互不相同，具體步驟如下。先取一個符號分段，若與前面段相同，就再取一個符號，直至構(gòu)成一個新段.如果到最后面分不出一段，則這個分不出段的事件串也算一段，是末尾段。設(shè)信源隨機變量U的事件集為A=a1, a2, , aK?，F(xiàn)要對信源序列L維隨機變量UL=(U1U2UL)進行2元編碼。事件u=(u1u2uL)。2022/8/10119

47、其次進行的操作是“事件編號”和“段編號”。事件編號：首先將事件a1, a2, , aK分別標(biāo)號為0, 1, , K-1，隨后將這些編號寫成長度相同二進制比特串，比特串的長度都是例如，a1, a2, a3, a4, a5, a6分別標(biāo)號為000, 001, 010, 011, 100, 101。又例如， a1, a2, a3, a4, a5, a6 , a7, a8, a9分別標(biāo)號為0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000。段編號：首先將所劃分的各段按前后順序分別標(biāo)號為1, 2, , ，隨后將這些編號寫成二進制的比特串，長度為LZ編

48、碼2022/8/10120最后進行的操作是“按段進行編碼”，每個碼字分為兩個部分：段號（最后一個事件）事件編號 下面分三種情形為段賦予碼字：情形一 段如果只有一個事件，則碼字的段號為000（長度為段編號長度），碼字后一部分就是這個事件的編號。情形二 非末尾段如果有不止一個事件，則該段去掉最后一個事件就是前面曾經(jīng)出現(xiàn)過的舊段。 該段的碼字的前一部分就是這個舊段的段編號，碼字的后一部分就是最后一個事件的事件編號。情形三 末尾段如果既有不止一個事件，又是前面曾經(jīng)出現(xiàn)過的舊段，則末尾段的碼字就是該舊段的碼字。LZ編碼2022/8/10121 LZ編碼的譯碼方法非常簡單，因為碼字的長度相等，不需要識別碼

49、字之間的分界點，只需要將碼字翻譯成段即可。一個碼字如果前一部分為000，則該段只有一個事件，事件的編號就是碼字的后一部分。一個碼字如果不是最后一個碼字，而且前一部分不為000，則該段應(yīng)該是這樣的：以碼字前一部分作為段編號找到舊段，再以碼字后一部分作為事件編號找到事件，“舊段+事件”就是該段。一個碼字如果是最后一個碼字，而且該碼字在以前沒有出現(xiàn)過，則譯碼規(guī)則為如上所述。一個碼字如果是最后一個碼字，而且該碼字在以前出現(xiàn)過，則該末尾段值等同于相同碼字的舊段。LZ編碼2022/8/10122LZ編碼的特點特點一 編碼效率可以接近信息熵的上限。特點二 不需要事先知道信源的概率分布。特點三 用一種巧妙的方

50、式使用字典技術(shù)。特點四 文件越小，壓縮比例越??；文件越大，壓縮比例越大。LZ編碼2022/8/10123例3.4.4（p77）設(shè)信源隨機變量U的事件集為A=a1, a2, a3, a4。設(shè)要對信源序列(a1a2a1a3a2a4a2a4a3a1a1a4)進行2元編碼?！胺侄巍保?(a1，a2，a1a3，a2a4，a2a4a3，a1a1，a4)；“事件編號”依次為 a100， a201, a310, a411；“段編號”依次為a1a2a1a3a2a4a2a4a3a1a1a4001010011100101110111LZ編碼2022/8/10124“按段進行編碼”：a1a2a1a3a2a4a2a4a

51、3a1a1a400000000010011001011100100010000011LZ編碼2022/8/10125譯碼過程比特串“00000000010011001011100100010000011”按照碼字長度為3+2=5來分割碼字：00000，00001，00110，01011，10010，00100，00011碼字00000000010011001011100100010000011段號001010011100101110111段值a1a2a1a3a2a4a2a4a3a1a1a42022/8/10126LZ編碼設(shè)長為L的信源序列u分為M(u)個碼段，每段短語的二元碼符號長度為總碼長平

52、均+2022/8/10127LZ編碼設(shè)長度為l的段有Kl種。若把長為L的信源序列u分為M(u)個碼段后，設(shè)最長的段長為lmax，而且所有小于等于lmax 的段型全部都有，則2022/8/10128LZ編碼典型段，ak出現(xiàn)的次數(shù)為lmaxp (ak)2022/8/10129LZ編碼設(shè)較短的段型忽略不計2022/8/10130習(xí)題課3.1 試證明長度不超過N的D元不等長碼至多有D(DN1)/(D1)個碼字。 3.1的解答長度等于k的D元碼字至多有Dk個，其中k=1N。因此長度不超過N的D元碼字至多有2022/8/101313.2 以上是一個離散無記憶信源。若對其輸出的長為100的事件序列中含有兩個

53、和更少個al的序列提供不同的碼字。(a) 在等長編碼下，求二元碼的最短碼長N。(b) 求錯誤概率(誤組率)。3.2的解答(a) 長為L=100的事件序列中含有兩個和更少個al的序列，其個數(shù)為2022/8/10132習(xí)題課(b) 含有兩個和更少個al的序列擁有不同的碼字，它們的譯碼不會出現(xiàn)錯誤。因此錯誤概率(誤組率)不會超過“含有三個以上al的序列”出現(xiàn)的概率。而“含有三個以上al的序列”出現(xiàn)的概率等于2022/8/10133習(xí)題課3.2的注解 事實上，在對“含有兩個或更少個al的長為100的序列”提供不同的碼字之后,還有210-596=428個富余的碼字。這些富余的碼字如果提供給其中428 個

54、“含有恰好三個al的長為100的序列”，作為它們各自的不同碼字。則錯誤概率不會超過2022/8/10134習(xí)題課3.4 對于有4個字母的離散無記憶源有兩個碼A和B，參看下表。試問：(a) 各碼是否滿足異字頭條件?是否為唯一可譯碼?(b) 當(dāng)收到1時得到多少關(guān)于字母a1的信息?(c) 當(dāng)收到1時得到多少關(guān)于信源的平均信息?字 母概 率碼 A碼 Ba1a2a3a4 0.40.30.20.1 1010010001 1101001000 2022/8/10135習(xí)題課3.4的解答(a) 碼A是異字頭碼。碼B不是異字頭碼。碼A和碼B都是唯一可譯碼。碼A的譯碼規(guī)則是：1就是一個碼字的末尾。碼B的譯碼規(guī)則是

55、：1就是一個碼字的開頭。2022/8/10136習(xí)題課(b) “當(dāng)收到1時得到多少關(guān)于字母a1的信息”，這是求事件a1與事件“收到1”的（非平均）互信息量。以碼A為例。 P(a1)=0.4。 P(收到1)=P(a1)P(收到1|a1)+P(a2)P(收到1|a2) +P(a3)P(收到1|a3)+P(a4)P(收到1|a4) =0.41+0.3(1/2)+0.2(1/3)+0.1(1/4)=0.642。P(a1，且收到1)=P(a1)P(收到1|a1)=0.41=0.4。 所以I(a1；收到1)=log0.4/(0.40.642)=0.64155。2022/8/10137(c) “當(dāng)收到1時得

56、到多少關(guān)于信源的平均信息”，這是求信源隨機變量U與事件“收到1”的（半平均）互信息量。以碼A為例。I(收到1；U)=2022/8/101383.6 令離散無記憶信源如上。(a) 求對U（即U1）的最佳二元碼、平均碼長和編碼效率。(b) 求對U2 （即U1U2）的最佳二元碼、平均碼長和編碼效率。(c) 求對U3 （即U1U2U3 ）的最佳二元碼、平均碼長和編碼效率。2022/8/10139（U1U2U3 ）a1a1a1a1a1a2a1a2a1a2a1a1a1a1a3a1a3a1a3a1a1a1a2a2a2a1a20.1250.0750.0750.0750.0500.0500.0500.0450.

57、045a2a2a1a1a2a3a1a3a2a2a1a3a3a1a2a2a3a1a3a2a1a2a2a2a1a3a30.0450.0300.0300.0300.0300.0300.0300.0270.020a3a1a3a3a3a1a2a2a3a2a3a2a3a2a2a2a3a3a3a2a3a3a3a2a3a3a30.0200.0200.0180.0180.0180.0120.0120.0120.0082022/8/10140（U1U2）的第一種最佳二元碼2022/8/10141（U1U2）的第二種最佳二元碼2022/8/10142（U1U2）的最佳二元碼平均碼長和編碼效率：2022/8/1014

58、32022/8/101442022/8/101452022/8/101462022/8/101472022/8/101482022/8/101492022/8/101502022/8/101512022/8/101522022/8/101532022/8/101542022/8/101552022/8/101562022/8/101572022/8/101582022/8/101592022/8/101602022/8/101612022/8/101622022/8/101632022/8/101642022/8/101652022/8/101662022/8/101672022/8/1016

59、82022/8/10169（U1U2U3）的碼字a1a1a1a1a1a2a1a2a1a2a1a1a1a1a3a1a3a1a3a1a1a1a2a2a2a1a201000000001011011101000100110101011a2a2a1a1a2a3a1a3a2a2a1a3a3a1a2a2a3a1a3a2a1a2a2a2a1a3a30010001110110001100111010110111111011111001100a3a1a3a3a3a1a2a2a3a2a3a2a3a2a2a2a3a3a3a2a3a3a3a2a3a3a3001101001110001111011110011111001

60、01000010101001011000101112022/8/10170（U1U2U3）的最佳二元碼平均碼長：2022/8/10171（U1U2U3）的最佳二元碼編碼效率：2022/8/101723.9 設(shè)離散無記憶信源如上。試求其二元和三元Huffman碼。 3.9的解答 二元Huffman碼為：2022/8/10173D元Huffman編碼 K+B=D+m(D-1)，因而K-2=m(D-1)+D-2-B 注意R+B=D，有 0BD-2， 0D-2-BD-2 因而D-2-B=(K-2)mod(D-1)即 R-2=(K-2)mod(D-1)B個R個2022/8/10174習(xí)題課三元Huffm