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

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

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

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

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

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

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

7、刻發(fā)出的隨機(jī)變量相互依賴(lài)；有限記憶信源：在有限時(shí)間差內(nèi)的信源隨機(jī)變量相互依賴(lài)；非簡(jiǎn)單信源：信源在不同時(shí)刻發(fā)出的隨機(jī)變量具有不同的 概率分布。馬爾可夫信源：信源隨機(jī)過(guò)程是馬爾可夫過(guò)程。 2022/8/10163.2 離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（1）設(shè)有一個(gè)離散無(wú)記憶簡(jiǎn)單信源，信源發(fā)出的隨機(jī)變量序列為：U-2U-1U0U1U2。 設(shè)信源隨機(jī)變量U1的事件有K個(gè)：a1, a2, , aK，則L維信源隨機(jī)向量(U1U2UL)的事件有KL個(gè)：(u1u2uL)|其中每個(gè)分量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è)有一個(gè)含D個(gè)字母的字母表，對(duì)于(U1U2UL)的每一個(gè)事件(u1u2uL)，都用一個(gè)字母串(c1c2)來(lái)表示。 2022/8/1017碼長(zhǎng)：碼字所含碼元的個(gè)數(shù) 等長(zhǎng)編碼：所有碼字均有相同的碼長(zhǎng)N，對(duì)應(yīng)的碼 叫做等長(zhǎng)碼(FLC，F(xiàn)ixed Length code)；否則為變長(zhǎng)編碼。編碼器碼字:每一個(gè)事件(u1u2uL)所對(duì)應(yīng)的字母串(c1c2) 。 編碼器模型：D個(gè)字母的字母表A信源2022/8/1018熵是隨機(jī)變量平均不確定性的一個(gè)測(cè)度，表示了描述這個(gè)隨機(jī)變量所需要的平均比特?cái)?shù)2022/8/10

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

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

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

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

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

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

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

16、離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼系3.2.2(典型序列的數(shù)量，p58) (1-)2L(H(U)-)|TU(L, )|2L(H(U)+)。證明 一方面，2022/8/10343.2 離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼另一方面，2022/8/10353.2 離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼 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 離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼典型序列集非典型序列集序列集合定理3.2.1，系3.2.1以及系3.2.2就說(shuō)明：所有典型序列的概率和接近于1，是高概率集；典型序列集中各序列出現(xiàn)的概率近似相等；每個(gè)典型序列中一個(gè)信源符號(hào)的平均信息量接近于信源熵；當(dāng)L達(dá)到無(wú)限時(shí)，才等于信源熵。2022/8/10373.2 離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼補(bǔ)充引理 設(shè)給定一個(gè)R0H(U)。對(duì)每個(gè)正整數(shù)L，對(duì)應(yīng)地取整數(shù)N=R0L（R0L的下取整）。則0R0L-N1 即 0R0-N/LL0時(shí)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 離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼定理3.2.2(無(wú)錯(cuò)編碼正定理，p60) 給定編碼設(shè)備的編碼速率R0，R0H(U)。則對(duì)任意的0，總存在一個(gè)L0，使得對(duì)任意的LL0，都有對(duì)(U1U2UL)的2元等長(zhǎng)編碼方法和對(duì)應(yīng)的譯碼方法，實(shí)際的編碼速率R滿(mǎn)足R0RH(U)，“譯碼錯(cuò)誤”的概率peH(U)；“譯碼錯(cuò)誤”的概率pe=P(U1U2UL)不屬于TU(L, )=1-P(U1U2UL)TU(L, )。得證。 定理3.2.2(無(wú)錯(cuò)編碼反定理，p60) 設(shè)給定編碼設(shè)備的編碼速率R0，滿(mǎn)足R0H(U)；給定一個(gè)任意小的正數(shù)0；要求：選擇合適的L，N，對(duì)

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

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

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

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

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

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

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

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

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

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

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

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

31、概率分布，這在實(shí)際中有時(shí)是比較困難的。采用半靜態(tài)模型、自適應(yīng)模型、markov模型，部分匹配預(yù)測(cè)模型等等解決這一問(wèn)題。2022/8/1094D元Huffman編碼D元碼全數(shù)的端節(jié)點(diǎn)數(shù)為D+m(D-1)由Huffman編碼的最佳性知空缺的端節(jié)點(diǎn)應(yīng)當(dāng)是碼長(zhǎng)最長(zhǎng)的端節(jié)點(diǎn)共有K個(gè)符號(hào)，設(shè)第一次需要合并的消息個(gè)數(shù)為R，空缺數(shù)為BB個(gè)R個(gè)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個(gè)R個(gè)2022/8/109

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

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

34、作為代碼的原理。2022/8/1098使用算術(shù)編碼的壓縮算法通常先要對(duì)信源符號(hào)的概率進(jìn)行估計(jì)，然后再編碼。這個(gè)估計(jì)越準(zhǔn)，編碼結(jié)果就越接近最優(yōu)的結(jié)果。 例: 對(duì)一個(gè)簡(jiǎn)單的信號(hào)源進(jìn)行觀察，得到的統(tǒng)計(jì)模型如下：60% 的機(jī)會(huì)出現(xiàn)符號(hào) 中性 20% 的機(jī)會(huì)出現(xiàn)符號(hào) 陽(yáng)性 10% 的機(jī)會(huì)出現(xiàn)符號(hào) 陰性 10% 的機(jī)會(huì)出現(xiàn)符號(hào) 數(shù)據(jù)結(jié)束符. 算術(shù)編碼2022/8/1099在得到信源隨機(jī)變量U的事件集的概率分布P(ak)，(k=0,1, K-1)之后，我們需要定義信源符號(hào)的分布函數(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)。 隨后，編碼過(guò)程的每一步，除了最后一步，都是相同的。算術(shù)編碼2022/8/10100編碼器通常需要考慮下面三種數(shù)據(jù)：下一個(gè)要編碼的符號(hào) 當(dāng)前的區(qū)間(在編第一個(gè)符號(hào)之前，這個(gè)區(qū)間是0,1), 但是之后每次編碼區(qū)間都會(huì)變化) 模型中在這一步可能出現(xiàn)的各個(gè)符號(hào)的概率分布編碼器利用信源符號(hào)的分布函數(shù)將當(dāng)前的區(qū)間分成若干子區(qū)間，區(qū)間之間的分隔線(xiàn)為信源符號(hào)的分布函數(shù)，每個(gè)子區(qū)間的長(zhǎng)度與可能出現(xiàn)的對(duì)應(yīng)符號(hào)的概率成正比。當(dāng)前要編碼的符號(hào)對(duì)應(yīng)的子區(qū)間成為下一步編碼的初始區(qū)間。算術(shù)編碼2022/8/10101例: 對(duì)于前面提出的4符號(hào)模型:中性對(duì)應(yīng)的區(qū)間是 0

36、, 0.6) 陽(yáng)性對(duì)應(yīng)的區(qū)間是 0.6, 0.8) 陰性對(duì)應(yīng)的區(qū)間是 0.8, 0.9) 數(shù)據(jù)結(jié)束符對(duì)應(yīng)的區(qū)間是 0.9, 1) 當(dāng)所有的符號(hào)都編碼完畢，最終得到的結(jié)果區(qū)間即唯一的確定了已編碼的符號(hào)序列。任何人使用該區(qū)間和模型參數(shù)即可以解碼重建得到該符號(hào)序列。算術(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ù)碼信源符號(hào)序列u對(duì)應(yīng)區(qū)間的寬度等于符號(hào)序列的概率信源符號(hào)序列u對(duì)應(yīng)區(qū)間的左端點(diǎn)為算術(shù)編碼2022/8/10105F(u)將0,1)分割成許多小區(qū)間，以小區(qū)間的左端點(diǎn)數(shù)值的二進(jìn)制小數(shù)表示該序列，同時(shí)要將該小數(shù)的小數(shù)位數(shù)截?cái)酁閘位，截?cái)嘁?guī)則為： l位后面只要有非0的余數(shù)就要向第l位進(jìn)位。 最后得到了小數(shù)0.t。將t作為事件u=(u1u2uL)的碼字。碼字長(zhǎng)度l為算術(shù)編碼2022/8/10106算術(shù)編碼則即因而即2022/8/10107例: 下面對(duì)使用前面提到的4符號(hào)模型進(jìn)行編碼的一段信息進(jìn)行解碼。編碼的結(jié)果是0.538(為了容易理解，這里使用十進(jìn)制而不是二進(jìn)制；我們也假設(shè)得到的

38、結(jié)果的位數(shù)恰好夠我們解碼)。類(lèi)似于編碼的過(guò)程，我們從區(qū)間0,1)開(kāi)始，使用相同的概率模型，將它分成四個(gè)子區(qū)間。中性對(duì)應(yīng)的區(qū)間是 0, 0.6) 陽(yáng)性對(duì)應(yīng)的區(qū)間是 0.6, 0.8) 陰性對(duì)應(yīng)的區(qū)間是 0.8, 0.9) 數(shù)據(jù)結(jié)束符對(duì)應(yīng)的區(qū)間是 0.9, 1) 算術(shù)編碼的譯碼2022/8/10108分?jǐn)?shù)0.538落在中性所在的子區(qū)間0,0.6)；這表明編碼器所讀的第一個(gè)符號(hào)必然是中性，這樣就可以將它作為消息的第一個(gè)符號(hào)記下來(lái)。 算術(shù)編碼的譯碼2022/8/10109然后我們將區(qū)間0,0.6)再分成四個(gè)子區(qū)間：中性的區(qū)間是 0, 0.36) - 0, 0.6) 的 60% 陽(yáng)性的區(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ū)間；所以消息的第二個(gè)符號(hào)一定是陰性。 算術(shù)編碼的譯碼2022/8/10110再一次將當(dāng)前區(qū)間劃分成四個(gè)子區(qū)間：中性 的區(qū)間是 0.48, 0.516) 陽(yáng)性 的區(qū)間是 0.516, 0.528) 陰性 的區(qū)間是 0.528, 0.534) 數(shù)據(jù)結(jié)束符的區(qū)間是 0.534, 0.540). 分?jǐn)?shù) 0.538 落在符號(hào)數(shù)據(jù)結(jié)束符的區(qū)間；所以，這一定是下一個(gè)符號(hào)。由

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

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

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

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

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

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

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

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

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

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

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

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

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

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

54、“含有恰好三個(gè)al的長(zhǎng)為100的序列”，作為它們各自的不同碼字。則錯(cuò)誤概率不會(huì)超過(guò)2022/8/10134習(xí)題課3.4 對(duì)于有4個(gè)字母的離散無(wú)記憶源有兩個(gè)碼A和B，參看下表。試問(wèn)：(a) 各碼是否滿(mǎn)足異字頭條件?是否為唯一可譯碼?(b) 當(dāng)收到1時(shí)得到多少關(guān)于字母a1的信息?(c) 當(dāng)收到1時(shí)得到多少關(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就是一個(gè)碼字的末尾。碼B的譯碼規(guī)則是

55、：1就是一個(gè)碼字的開(kāi)頭。2022/8/10136習(xí)題課(b) “當(dāng)收到1時(shí)得到多少關(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時(shí)得

56、到多少關(guān)于信源的平均信息”，這是求信源隨機(jī)變量U與事件“收到1”的（半平均）互信息量。以碼A為例。I(收到1；U)=2022/8/101383.6 令離散無(wú)記憶信源如上。(a) 求對(duì)U（即U1）的最佳二元碼、平均碼長(zhǎng)和編碼效率。(b) 求對(duì)U2 （即U1U2）的最佳二元碼、平均碼長(zhǎng)和編碼效率。(c) 求對(duì)U3 （即U1U2U3 ）的最佳二元碼、平均碼長(zhǎng)和編碼效率。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）的最佳二元碼平均碼長(zhǎng)和編碼效率：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）的最佳二元碼平均碼長(zhǎng)：2022/8/10171（U1U2U3）的最佳二元碼編碼效率：2022/8/101723.9 設(shè)離散無(wú)記憶信源如上。試求其二元和三元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個(gè)R個(gè)2022/8/10174習(xí)題課三元Huffm