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

信息論與編碼理論基礎(chǔ)第三章2023/4/261第1頁(yè)，共195頁(yè)，2023年，2月20日，星期一

信源發(fā)出的消息序列通常不能直接送給信道傳輸，需要經(jīng)過(guò)信源編碼和信道編碼。

2023/4/262第2頁(yè)，共195頁(yè)，2023年，2月20日，星期一信道編碼在傳輸過(guò)程中噪聲和干擾在所難免，為了降低差錯(cuò)率，提高傳送的可靠性，在信道編碼器中可以引入冗余度，在信道解碼端就可以利用此冗余度來(lái)盡可能地重建輸入序列?？煽啃裕涸黾尤哂?023/4/263第3頁(yè)，共195頁(yè)，2023年，2月20日，星期一信源編碼對(duì)信源進(jìn)行壓縮、擾亂和加密，用最少的碼字最安全地傳輸最大的信息量：有效性和安全性：去除冗余如何對(duì)信源進(jìn)行建模？（如隨機(jī)過(guò)程）如何測(cè)量信源的內(nèi)容？（熵）如何表示一個(gè)信源？（編碼：碼字設(shè)計(jì)）2023/4/264第4頁(yè)，共195頁(yè)，2023年，2月20日，星期一為什么需要信源編碼/數(shù)據(jù)壓縮數(shù)字化視頻和音頻等媒體信息的數(shù)據(jù)量很大數(shù)字音頻格式頻帶范圍（Hz）取樣頻率（kHz）樣本精度（bit）聲道數(shù)原始碼率（Kb/s）電話300~340088164調(diào)頻（FM）廣播20~1500022.03162705.6激光唱盤(pán)（CD）20~2000044.11621411.2數(shù)字視頻格式每秒幀數(shù)圖像分辨率（像素）樣本精度（bit）亮度信號(hào)原始碼率（Mb/s）CIF格式的亮度信號(hào)30352*288824.33HDTV亮度信號(hào)一例601920*10808995.32023/4/265第5頁(yè)，共195頁(yè)，2023年，2月20日，星期一為什么需要信源編碼/數(shù)據(jù)壓縮減少存儲(chǔ)空間文件壓縮、圖像壓縮、語(yǔ)音壓縮、視頻壓縮…減少傳輸時(shí)間2023/4/266第6頁(yè)，共195頁(yè)，2023年，2月20日，星期一信源編碼/數(shù)據(jù)壓縮的例子：

摩爾斯式電碼19世紀(jì)中葉，由SamuelMorse發(fā)明每個(gè)字符用“.”或“–”表示觀察：一些字符比另外一些字符出現(xiàn)的頻率更高，如“a,e”比“z,q”出現(xiàn)的頻率高因此，為了減少發(fā)送信息的平均時(shí)間，用較短的序列表示出現(xiàn)頻率高的字符，較長(zhǎng)的序列表示出現(xiàn)頻率低的字符e:.,a:.–q:--.-,j:.---2023/4/267第7頁(yè)，共195頁(yè)，2023年，2月20日，星期一為什么可以進(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后常跟有字母U2023/4/268第8頁(yè)，共195頁(yè)，2023年，2月20日，星期一例：空間冗余圖像中存在大面積部分相似或完全一樣的像素pmf2023/4/269第9頁(yè)，共195頁(yè)，2023年，2月20日，星期一例：時(shí)間冗余視頻圖像前后幾幀的內(nèi)容變化不大（位置可能不同，可用運(yùn)動(dòng)估計(jì)方法找到對(duì)應(yīng)位置）2023/4/2610第10頁(yè)，共195頁(yè)，2023年，2月20日，星期一例：結(jié)構(gòu)冗余圖像中物體表面紋理等結(jié)構(gòu)存在冗余2023/4/2611第11頁(yè)，共195頁(yè)，2023年，2月20日，星期一怎樣進(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ì)定出的可接收準(zhǔn)則或保真度準(zhǔn)則，計(jì)算要保留多少有關(guān)信源輸出的信息量，以及如何表示它們，這就是限定失真的信源編碼問(wèn)題。2023/4/2612第12頁(yè)，共195頁(yè)，2023年，2月20日，星期一第三章：信源編碼（一）

離散信源無(wú)失真編碼§3.1信源及其分類(lèi)§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼§3.4最佳不等長(zhǎng)編碼2023/4/2613第13頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.1信源及其分類(lèi)信源的概念

:信源就是信息的來(lái)源。注意：在一個(gè)固定的時(shí)刻，信源發(fā)出的是一個(gè)隨機(jī)變量。隨著時(shí)間的延續(xù)，信源發(fā)出一個(gè)又一個(gè)隨機(jī)變量，稱之為一個(gè)隨機(jī)過(guò)程。

因此，可以用概率空間來(lái)描述信源。

2023/4/2614第14頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.1信源及其分類(lèi)離散信源信源每隔一個(gè)定長(zhǎng)時(shí)間段就發(fā)出一個(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ú)記憶信源。2023/4/2615第15頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.1信源及其分類(lèi)（總結(jié)：離散無(wú)記憶簡(jiǎn)單信源就是時(shí)間離散、事件離散、各隨機(jī)變量獨(dú)立同分布的信源。課程學(xué)習(xí)所面對(duì)的信源將主要是離散無(wú)記憶簡(jiǎn)單信源）一般的信源

連續(xù)信源：有時(shí)間連續(xù)的信源，也有事件連續(xù)的信源；有記憶信源：信源在不同時(shí)刻發(fā)出的隨機(jī)變量相互依賴；有限記憶信源：在有限時(shí)間差內(nèi)的信源隨機(jī)變量相互依賴；非簡(jiǎn)單信源：信源在不同時(shí)刻發(fā)出的隨機(jī)變量具有不同的概率分布。馬爾可夫信源：信源隨機(jī)過(guò)程是馬爾可夫過(guò)程。2023/4/2616第16頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.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ī)向量(U1U2…UL)的事件有KL個(gè)：{(u1u2…uL)|其中每個(gè)分量ul跑遍{a1,a2,…,aK}}。P((U1U2…UL)=(u1u2…uL))=P(U1=u1)P(U2=u2)…P(UL=uL)=P(U1=u1)P(U1=u2)…P(U1=uL)=q(u1)q(u2)…q(uL)（2）D元編碼：設(shè)有一個(gè)含D個(gè)字母的字母表，對(duì)于(U1U2…UL)的每一個(gè)事件(u1u2…uL)，都用一個(gè)字母串(c1c2…)來(lái)表示。

2023/4/2617第17頁(yè)，共195頁(yè)，2023年，2月20日，星期一碼長(zhǎng)：碼字所含碼元的個(gè)數(shù)等長(zhǎng)編碼：所有碼字均有相同的碼長(zhǎng)N，對(duì)應(yīng)的碼叫做等長(zhǎng)碼(FLC，F(xiàn)ixedLengthcode)；否則為變長(zhǎng)編碼。編碼器碼字:每一個(gè)事件(u1u2…uL)所對(duì)應(yīng)的字母串(c1c2…)。

編碼器模型：D個(gè)字母的字母表A信源2023/4/2618第18頁(yè)，共195頁(yè)，2023年，2月20日，星期一熵是隨機(jī)變量平均不確定性的一個(gè)測(cè)度，表示了描述這個(gè)隨機(jī)變量所需要的平均比特?cái)?shù)2023/4/2619第19頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.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。2023/4/2620第20頁(yè)，共195頁(yè)，2023年，2月20日，星期一無(wú)錯(cuò)編碼（唯一可譯碼）(U1U2…UL)的不同事件用不同的碼字來(lái)表示。能夠?qū)崿F(xiàn)無(wú)錯(cuò)編碼的充要條件是DN≥KL。（即NlogD/L≥logK）這里N/L表示每個(gè)信源符號(hào)所需要的碼符號(hào)數(shù)；logD是一個(gè)碼符號(hào)所能載荷的最大信息量；N/L≥logK/logD說(shuō)明對(duì)于等長(zhǎng)唯一可譯碼平均每個(gè)信源符號(hào)至少需要logK/logD個(gè)碼符號(hào)對(duì)其進(jìn)行編碼變換；（NlogD）/L是編碼后平均每個(gè)信源符號(hào)所能載荷的信息量的最大值，稱為編碼速率，記為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ò)編碼

(U1U2…UL)的有些不同事件用相同的碼字來(lái)表示。編碼是一種由消息集到碼字集的映射2023/4/2621第21頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼無(wú)錯(cuò)編碼的最低代價(jià)當(dāng)R=(NlogD)/L≥logK時(shí)，能夠?qū)崿F(xiàn)無(wú)錯(cuò)編碼。（DN≥KL）當(dāng)R<H(U1)時(shí)，無(wú)論怎樣編碼都是有錯(cuò)編碼。這是因?yàn)镽<H(U1)≤logK。（DN<KL）注意：有錯(cuò)編碼的譯碼方法與“譯碼錯(cuò)誤”概率當(dāng)使用有錯(cuò)編碼時(shí)，必須給出譯碼方法（即：一個(gè)碼字可能表示幾個(gè)不同的事件，究竟翻譯成哪個(gè)事件）?！白g碼錯(cuò)誤”的概率定義為

pe=P{(U1U2…UL)=(u1u2…uL)|(u1u2…uL)的碼字在譯碼時(shí)并不譯為自身}。2023/4/2622第22頁(yè)，共195頁(yè)，2023年，2月20日，星期一上述分析時(shí)，我們完全沒(méi)有考慮信源的統(tǒng)計(jì)特性，（也就是信源符號(hào)出現(xiàn)的概率以及信源符號(hào)之間的依賴關(guān)系，即信源的冗余度）而是認(rèn)為信源符號(hào)獨(dú)立等概；若注意每個(gè)信源信源符號(hào)包含的平均信息量為H(U)，編碼時(shí)若D個(gè)符號(hào)獨(dú)立等概，則每個(gè)碼元符號(hào)所能載荷的信息量最大，碼長(zhǎng)最短，所以理論上最小碼長(zhǎng)N只要滿足(NlogD)/L≥H(U)就可以實(shí)現(xiàn)無(wú)信息損失，即當(dāng)logK>R>H(U1)時(shí)，雖然無(wú)論怎樣編碼都是有錯(cuò)編碼，但可以適當(dāng)?shù)鼐幋a和譯碼使譯碼錯(cuò)誤的概率pe任意小。這就是所謂“漸進(jìn)無(wú)錯(cuò)編碼”?！?.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼2023/4/2623第23頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼我們以英文電報(bào)為例，由于英文字母之間有很強(qiáng)的關(guān)聯(lián)性，當(dāng)用字母組合成不同的英文字母序列時(shí)，并不是所有的字母組合都是有意義的單詞，若再把單詞組合成更長(zhǎng)的字母序列時(shí)，也不是任意的單詞組合都是有意義的句子，因此，在足夠長(zhǎng)的英文字母序列中，就有許多無(wú)用和無(wú)意義的序列，這些信源序列出現(xiàn)的概率等于零或任意小，那么在編碼時(shí)，對(duì)于那些無(wú)用的字母組合，無(wú)意義的句子都可以不編碼，從而提高傳輸效率，但同時(shí)，會(huì)引入一定的誤差，但是當(dāng)L足夠大時(shí)，這種誤差概率就可以任意小，可做到幾乎無(wú)失真編碼。2023/4/2624第24頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼漸進(jìn)無(wú)錯(cuò)編碼（簡(jiǎn)單地說(shuō)就是：當(dāng)R>H(U1)時(shí)，可以適當(dāng)?shù)鼐幋a和譯碼使得譯碼錯(cuò)誤的概率pe任意小。嚴(yán)格地說(shuō)就是：）設(shè)給定了編碼設(shè)備的編碼速率R0，R0>H(U1)。則對(duì)任意的ε>0，總存在一個(gè)L0，使得對(duì)任意的L>L0，都有對(duì)(U1U2…UL)的等長(zhǎng)編碼和對(duì)應(yīng)的譯碼方法，滿足實(shí)際的編碼速率R=NlogD/L≤R0，譯碼錯(cuò)誤的概率pe<ε。2023/4/2625第25頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼不能漸進(jìn)無(wú)錯(cuò)的編碼（簡(jiǎn)單地說(shuō)就是：當(dāng)R<H(U1)時(shí)，無(wú)論怎樣編碼和譯碼都不能使譯碼錯(cuò)誤的概率pe任意小。嚴(yán)格地說(shuō)就是：）

設(shè)給定了編碼設(shè)備的編碼速率R0，R0<H(U1)。則無(wú)論怎樣編碼和譯碼都不能同時(shí)滿足實(shí)際的編碼速率R≤R0，譯碼錯(cuò)誤的概率pe任意小。2023/4/2626第26頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼----典型序列設(shè)…U-2U-1U0U1U2…是離散無(wú)記憶（簡(jiǎn)單）信源的輸出隨機(jī)變量序列。設(shè)U1的概率分布為。。。。取Vl是Ul的如下函數(shù)：當(dāng)Ul=ak時(shí)，Vl=loga(1/qk)。則隨機(jī)變量序列…V-2V-1V0V1V2…相互獨(dú)立，具有相同的概率分布：

2023/4/2627第27頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼取IL是(V1V2…VL)的如下函數(shù)：則①I(mǎi)L最終是(U1U2…UL)的函數(shù)；②③因此有切比雪夫不等式：對(duì)任意ε>0有P{H(U1)-ε≤IL≤H(U1)+ε}≥2023/4/2628第28頁(yè)，共195頁(yè)，2023年，2月20日，星期一切比雪夫不等式注：切比雪夫2023/4/2629第29頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼取定L0使得，則當(dāng)L≥L0時(shí)總有因此當(dāng)L≥L0時(shí)總有這樣的一些事件序列，

H(U1)-ε≤IL≤H(U1)+ε，而且P{H(U1)-ε≤IL≤H(U1)+ε}≥1-ε。說(shuō)明當(dāng)L足夠大時(shí)，信源序列的自信息量的均值以概率1收斂于信源熵。當(dāng)L足夠大時(shí)，在信源序列中必有一些消息序列其自信息量的均值與信源熵之差小于ε，而對(duì)另外一些信源序列其差≥ε

，因此，可以把信源序列分成兩個(gè)互補(bǔ)的子集。2023/4/2630第30頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼定義3.2.1(p57)定義TU(L,ε)={(u1u2…uL)|H(U1)-ε≤IL≤H(U1)+ε}，稱TU(L,ε)為ε-典型序列集。稱TU(L,ε)的補(bǔ)集為非ε-典型序列集。

（綜上所述有）定理3.2.1(信源劃分定理，p58)對(duì)任意ε>0，取L0使得則當(dāng)L≥L0時(shí)總有P{(U1U2…UL))=(u1u2…uL)|(u1u2…uL)∈TU(L,ε)}≥1-ε。2023/4/2631第31頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（簡(jiǎn)記H(U)=H(U1)。設(shè)以下的對(duì)數(shù)都是以2為底的。）系3.2.1(特定典型序列出現(xiàn)的概率，p58)若一個(gè)特定的事件(u1u2…uL)∈TU(L,ε)，則2-L(H(U)+ε)≤P{(U1U2…UL)=(u1u2…uL)}≤2-L(H(U)-ε)。證明設(shè)(u1u2…uL)∈TU(L,ε)。注意到此時(shí)H(U)-ε≤IL≤H(U)+ε，2023/4/2632第32頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼所以2023/4/2633第33頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼系3.2.2(典型序列的數(shù)量，p58)(1-ε)2L(H(U)-ε)≤|TU(L,ε)|≤2L(H(U)+ε)。證明一方面，2023/4/2634第34頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼另一方面，2023/4/2635第35頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼P{(U1U2…UL))=(u1u2…uL)|(u1u2…uL)∈TU(L,ε)}≥1-ε。系3.2.1(特定典型序列出現(xiàn)的概率)2-L(H(U)+ε)≤P{(U1U2…UL)=(u1u2…uL)}≤2-L(H(U)-ε)。系3.2.2(典型序列的數(shù)量)(1-ε)2L(H(U)-ε)≤|TU(L,ε)|≤2L(H(U)+ε)。2023/4/2636第36頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.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í)，才等于信源熵。2023/4/2637第37頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼補(bǔ)充引理設(shè)給定一個(gè)R0>H(U)。對(duì)每個(gè)正整數(shù)L，對(duì)應(yīng)地取整數(shù)N=[R0L]（R0L的下取整）。則0≤R0L-N<1即0≤R0-N/L<1/L，故N/L≤R0，limL→+∞N/L=R0。任取正數(shù)ε≤(R0-H(U))/2，存在正整數(shù)L0，當(dāng)L>L0時(shí)N/L≥R0-ε＝R0-(R0-H(U))/2=H(U)+(R0-H(U))/2≥H(U)+ε。P{(U1U2…UL)∈TU(L,ε)}≥1-ε。（由定理3.2.1）2023/4/2638第38頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼定理3.2.2(無(wú)錯(cuò)編碼正定理，p60)

給定編碼設(shè)備的編碼速率R0，R0>H(U)。則對(duì)任意的ε>0，總存在一個(gè)L0，使得對(duì)任意的L>L0，都有對(duì)(U1U2…UL)的2元等長(zhǎng)編碼方法和對(duì)應(yīng)的譯碼方法，①實(shí)際的編碼速率R滿足R0≥R>H(U)，②“譯碼錯(cuò)誤”的概率pe<ε。2023/4/2639第39頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼證明首先聲明，所有的對(duì)數(shù)計(jì)算都是以2為底的。此時(shí)實(shí)際的編碼速率為R=N/L。任取正數(shù)ε≤(R0-H(U))/2，取補(bǔ)充引理所描述的L0，則

|TU(L,ε)|≤2L(H(U)+ε)

（由系3.2.2）≤2N(由補(bǔ)充引理的(1))

這就是說(shuō)，典型序列集TU(L,ε)中的事件的個(gè)數(shù)不超過(guò)長(zhǎng)度為N的2元碼字的數(shù)量2N。因此，可以做如下的編碼：將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è)事件。2023/4/2640第40頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼對(duì)應(yīng)的譯碼：所有的碼字均譯為它所表示的TU(L,ε)中的事件。結(jié)論：①實(shí)際的編碼速率R滿足R0≥R>H(U)；②“譯碼錯(cuò)誤”的概率pe=P((U1U2…UL)不屬于TU(L,ε))=1-P((U1U2…UL)∈TU(L,ε))<ε。得證。

定理3.2.2(無(wú)錯(cuò)編碼反定理，p60)設(shè)給定編碼設(shè)備的編碼速率R0，滿足R0<H(U)。當(dāng)限制實(shí)際的編碼速率R≤R0時(shí)，無(wú)論怎樣編碼和譯碼都不能使“譯碼錯(cuò)誤”的概率任意小。（沒(méi)有證明）2023/4/2641第41頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼漸進(jìn)無(wú)錯(cuò)編碼的要求給定離散無(wú)記憶簡(jiǎn)單信源：…U-2U-1U0U1U2…；給定編碼設(shè)備的編碼速率R0，滿足R0>H(U)；給定一個(gè)任意小的正數(shù)ε>0；要求：選擇合適的L，N，對(duì)(U1U2…UL)進(jìn)行合適的2元N長(zhǎng)編碼，使得

①實(shí)際的編碼速率R=N/L滿足R≤R0；

②“譯碼錯(cuò)誤”的概率pe<ε。2023/4/2642第42頁(yè)，共195頁(yè)，2023年，2月20日，星期一漸進(jìn)無(wú)錯(cuò)編碼的步驟①由U1的概率分布計(jì)算②取L滿足。③取整數(shù)N=[R0L]（R0L下取整）。④取典型序列集2023/4/2643第43頁(yè)，共195頁(yè)，2023年，2月20日，星期一漸進(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,ε)中的事件。（注解：顯然滿足R≤R0；|TU(L,ε)|≤2N，因此碼字足夠用；譯碼錯(cuò)誤的概率為pe=P((U1U2…UL)=(u1u2…uL)|(u1u2…uL)不屬于TU(L,ε))<ε；一般來(lái)說(shuō)，ε越小，要求L越大，因此對(duì)應(yīng)的N越大。）2023/4/2644第44頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼例設(shè)，則2023/4/2645第45頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼設(shè)給定編碼設(shè)備的編碼速率R0=0.5。則R0>0.037587148=H(U1)。希望：①2元編碼的實(shí)際編碼速率R≤R0；②譯碼錯(cuò)誤的概率不超過(guò)ε。其中取ε=0.1。找L使得2023/4/2646第46頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.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)事件(u1u2…uL)中a1的個(gè)數(shù)為k，a2的個(gè)數(shù)為L(zhǎng)-k時(shí)，2023/4/2647第47頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼事件(u1u2…uL)屬于典型序列集TU(L,0.1)；當(dāng)且僅當(dāng)2023/4/2648第48頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼當(dāng)事件(u1u2…u253)中a1的個(gè)數(shù)不超過(guò)4時(shí)，(u1u2…u253)∈TU(253,0.1)；否則(u1u2…u253)不屬于TU(253,0.1)。(u1u2…u253)∈TU(253,0.1)的概率不小于0.9；(u1u2…u253)∈TU(253,0.1)的個(gè)數(shù)為2023/4/2649第49頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼對(duì)L=253，對(duì)應(yīng)地取整數(shù)N=[R0L]=126。則N/L<R0，這就是說(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.355557444<2126，碼字足夠用。2元編碼的譯碼方法：將碼字譯為它所表示的TU(253,0.1)中的事件(u1u2…u253)。于是，譯碼錯(cuò)誤的概率為P((u1u2…u253)不屬于TU(253,0.1))≤ε=0.1。2023/4/2650第50頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼取ε=0.05。找L使得即L=2020。取ε=0.01。找L使得即L=252435。2023/4/2651第51頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼不等長(zhǎng)編碼：對(duì)信源輸出的消息采用不同長(zhǎng)度的碼字來(lái)表示。不等長(zhǎng)編碼的優(yōu)越性:編碼使得最常出現(xiàn)的消息的碼長(zhǎng)最短，不常出現(xiàn)的消息的碼長(zhǎng)較長(zhǎng)，這種編碼方法得到的平均碼長(zhǎng)會(huì)比較短，進(jìn)而從總體上減少碼字的長(zhǎng)度。不等長(zhǎng)編碼的特殊問(wèn)題----唯一可譯性，或者叫做可識(shí)別性。對(duì)于一個(gè)碼，如果存在一種譯碼方法，使任意若干個(gè)碼字所組成的字母串只能唯一地被翻譯成這幾個(gè)碼字所對(duì)應(yīng)的事件序列。這個(gè)碼就被稱為是唯一可譯的。解決方案：適當(dāng)?shù)鼐幋a，使得每個(gè)碼字都具有識(shí)別標(biāo)記。2023/4/2652第52頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼平均碼字長(zhǎng)度。設(shè)信源隨機(jī)變量U的概率分布為{ak,q(ak),k=1~K}，事件ak對(duì)應(yīng)的碼字長(zhǎng)度為nk，則平均碼字長(zhǎng)度為希望小。解決方案：概率大的事件用短碼字。實(shí)時(shí)譯碼：能及時(shí)完成每個(gè)碼字的接收譯碼，即譯碼延遲要??；容量限制：為了和一個(gè)等速信源匹配，還需要考慮緩存的問(wèn)題。2023/4/2653第53頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼唯一可譯性的兩種解決方法定義3.3.2(p63)若①事件與碼字一一對(duì)應(yīng)；②每個(gè)碼字的開(kāi)頭部分都是一個(gè)相同的字母串；③這個(gè)字母串僅僅出現(xiàn)在碼字的開(kāi)頭，不出現(xiàn)在碼字的其它部位，也不出現(xiàn)在兩個(gè)碼字的結(jié)合部。則稱這個(gè)字母串為逗號(hào)，稱此碼為逗點(diǎn)碼。定義3.3.4(p63)若①事件與碼字一一對(duì)應(yīng)；②每個(gè)碼字都不是另一個(gè)碼字的開(kāi)頭部分（字頭）。則稱此碼為異字頭碼。2023/4/2654第54頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼注解逗點(diǎn)碼顯然是唯一可譯的，識(shí)別碼字的方法為：見(jiàn)到逗號(hào)就識(shí)別為一個(gè)碼字的開(kāi)始。異字頭碼也是唯一可譯的，識(shí)別碼字的方法為：見(jiàn)到一個(gè)碼字就識(shí)別為一個(gè)碼字。（許多具體的異字頭碼有更加簡(jiǎn)便的識(shí)別碼字的方法）2023/4/2655第55頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼例觀察表3.3.1(p64)。事件概率碼A碼B碼C碼Da10.50000a20.25011001a30.125100110011a40.125101111101112023/4/2656第56頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼碼A不是唯一可譯的。碼B不是唯一可譯的。碼C是唯一可譯的，識(shí)別碼字的方法為：見(jiàn)“0”或“111”就是一個(gè)碼字的結(jié)束。實(shí)際上，碼C是異字頭碼。碼D是唯一可譯的，識(shí)別碼字的方法為：見(jiàn)“0”就是一個(gè)碼字的開(kāi)始。實(shí)際上，碼D是逗點(diǎn)碼，其中“0”是逗號(hào)。碼C不是逗點(diǎn)碼。碼D不是異字頭碼。碼C的平均碼長(zhǎng)比碼D的平均碼長(zhǎng)?。捍aC的平均碼長(zhǎng)為1×0.5+2×0.25+3×0.125+3×0.125=1.75；碼D的平均碼長(zhǎng)為1×0.5+2×0.25+3×0.125+4×0.125=1.875。2023/4/2657第57頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼異字頭碼的第一種構(gòu)造方法：Shannon-Fano編碼法（D元編碼，字母表為{0,1,…,D-1}）

（1）將源隨機(jī)變量的事件按概率從大到小排成一行。（2）將此行切分為D段（可能有空段），分別賦予標(biāo)號(hào)“0”到“D-1”，稱為1級(jí)標(biāo)號(hào)。（3）將每個(gè)非空段再切分為D段（可能有空段），分別賦予標(biāo)號(hào)“0”到“D-1”，稱為2級(jí)標(biāo)號(hào)。（4）將每個(gè)非空段再切分為D段（可能有空段），分別賦予標(biāo)號(hào)“0”到“D-1”，稱為3級(jí)標(biāo)號(hào)?！?023/4/2658第58頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼如此一直到每個(gè)非空段不能再分（只含有一個(gè)事件）為止。此時(shí)，一個(gè)事件的碼字就是這個(gè)事件所在的段的標(biāo)號(hào)序列，從1級(jí)標(biāo)號(hào)到末級(jí)標(biāo)號(hào)。（當(dāng)然，那些空段和它們的標(biāo)號(hào)序列是沒(méi)有用的，要去掉）為了使平均碼長(zhǎng)小，每次切分段時(shí)應(yīng)使D段的概率盡可能相近。2023/4/2659第59頁(yè)，共195頁(yè)，2023年，2月20日，星期一Shannon-Fano編碼例子cabcedeacacdeddaaabaababaaabbacdebaceada共40個(gè)字母頻度a-16，b-7，c-6，d-6，e-51)將給定符號(hào)按照其頻率從大到小排序。a-16b-7c-6d-6e–52)將序列分成左右兩部分，使得左部頻率總和盡可能接近右部頻率總和。有：(a,b),(c,d,e)2023/4/2660第60頁(yè)，共195頁(yè)，2023年，2月20日，星期一Shannon-Fano編碼例子3)我們把第二步中劃分出的上部作為二叉樹(shù)的左子樹(shù)，記0，下部作為二叉樹(shù)的右子樹(shù)，記1。4)分別對(duì)左右子樹(shù)重復(fù)23兩步，直到所有的符號(hào)都成為二叉樹(shù)的樹(shù)葉為止。bacde00101011a00b01c10d110e1112023/4/2661第61頁(yè)，共195頁(yè)，2023年，2月20日，星期一Shannon-Fano編碼例子編碼結(jié)果Cabcedeacacdeddaaabaababaaabbacdebaceada1000011011111011100100010......長(zhǎng)91bit采用3bit等長(zhǎng)編碼需120bit2023/4/2662第62頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼異字頭碼的第二種構(gòu)造方法：Huffman編碼法（D元編碼，字母表為{0,1,…,D-1}）（1）將概率最小的D個(gè)事件分別賦予標(biāo)號(hào)“0”到“D-1”。（2）將這D個(gè)事件合并為一個(gè)事件，其概率為這D個(gè)事件概率之和。重復(fù)（1）-（2），直到事件的個(gè)數(shù)等于D。將這D個(gè)事件分別賦予標(biāo)號(hào)“0”到“D-1”。編碼完畢。此時(shí)，一個(gè)事件的碼字是這個(gè)事件從最后標(biāo)號(hào)開(kāi)始到最先標(biāo)號(hào)為止的標(biāo)號(hào)序列。（當(dāng)然要去掉那些0概率事件和它們的標(biāo)號(hào)序列）2023/4/2663第63頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼（為什么Shannon-Fano碼和Huffman碼都是異字頭碼？請(qǐng)看p71圖3.4.1，p71圖3.4.2。這些圖都是樹(shù)，稱為碼樹(shù)，碼樹(shù)上的每個(gè)碼字都在樹(shù)梢。這種形狀保證了碼是異字頭碼。如果不是異字頭碼，則有的碼字就不在樹(shù)梢，而在中間節(jié)點(diǎn)。）定理3.3.1(Kraft不等式，p65)設(shè)信源隨機(jī)變量共有K個(gè)事件。則：各碼字長(zhǎng)度分別為n1、n2、…、nK的D元異字頭碼存在的充分必要條件是2023/4/2664第64頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼證明不妨設(shè)n1≤n2≤…≤nK。則各碼字長(zhǎng)度分別為n1、n2、…、nK的D元異字頭碼存在；當(dāng)且僅當(dāng)：存在這樣一個(gè)D叉樹(shù)，樹(shù)上有一個(gè)n1級(jí)樹(shù)梢，再有一個(gè)n2級(jí)樹(shù)梢，…，再有一個(gè)nK級(jí)樹(shù)梢；當(dāng)且僅當(dāng)：存在nK級(jí)D叉滿樹(shù)，樹(shù)上有個(gè)nK級(jí)樹(shù)梢，再有個(gè)nK級(jí)樹(shù)梢，…，再有個(gè)nK級(jí)樹(shù)梢；當(dāng)且僅當(dāng)：2023/4/2665第65頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼定理3.3.2(p66)（設(shè)信源隨機(jī)變量共有K個(gè)事件）。則：一個(gè)唯一可譯的、各碼字長(zhǎng)度分別為n1、n2、…、nK的D元不等長(zhǎng)碼存在的充分必要條件是這說(shuō)明雖然異字頭碼屬于唯一可譯碼，但在碼長(zhǎng)的選擇上，并不比異字頭碼有什么更寬松的條件，在碼長(zhǎng)的選擇上，兩者是一致的。2023/4/2666第66頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼定理3.3.3(p67)任一唯一可譯的D元不等長(zhǎng)碼總滿足存在唯一可譯的D元不等長(zhǎng)碼滿足2023/4/2667第67頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼證明設(shè)信源隨機(jī)變量U的概率分布為如果唯一可譯的D元不等長(zhǎng)碼的碼字長(zhǎng)度為則2023/4/2668第68頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼因此。另一方面，取n1、n2、…、nK，則：由于，存在碼字長(zhǎng)度為的唯一可譯的D元不等長(zhǎng)碼。2023/4/2669第69頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼但此時(shí)2023/4/2670第70頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼定理3.3.3的結(jié)論的推廣(p68)現(xiàn)在對(duì)信源隨機(jī)向量UL=(U1U2…UL)做唯一可譯的D元不等長(zhǎng)碼。此時(shí)UL的事件的個(gè)數(shù)為KL。則任一唯一可譯的D元不等長(zhǎng)碼總滿足存在唯一可譯的D元不等長(zhǎng)碼滿足2023/4/2671第71頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼定義編碼速率R和編碼效率η分別為

任一唯一可譯的D元不等長(zhǎng)碼總滿足存在唯一可譯的D元不等長(zhǎng)碼滿足注解不等長(zhǎng)編碼與等長(zhǎng)編碼具有相似的性質(zhì)：當(dāng)L增大時(shí)，對(duì)UL的編碼可以更加節(jié)省編碼速率。但節(jié)省編碼速率的下限是H(U)。2023/4/2672第72頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼例3.3.1（見(jiàn)p68）做2元編碼。設(shè)；H(U)=0.811。U概率碼字平均碼長(zhǎng)編碼速率編碼效率a13/40(1×3/4+1×1/4)/1=110.811a21/41U2概率碼字平均碼長(zhǎng)編碼速率編碼效率a1a19/1601×9/16+2×3/16+3×3/16+3×1/16=27/1627/32=0.843750.961a1a23/1610a2a13/16110a2a21/161112023/4/2673第73頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.4最佳不等長(zhǎng)編碼2023/4/2674第74頁(yè)，共195頁(yè)，2023年，2月20日，星期一Huffman編碼的最佳性補(bǔ)充引理1：由3.3節(jié)的定理3.3.1和定理3.3.2知每個(gè)唯一可譯的不等長(zhǎng)碼都可以找到一個(gè)碼長(zhǎng)相同的異字頭碼，因而尋找最佳2元不等長(zhǎng)碼，只要尋找最佳2元異字頭碼即可。所謂最佳：是指在所有可能的編碼方法中，其編碼得到的平均碼長(zhǎng)最短。2023/4/2675第75頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.4最佳不等長(zhǎng)編碼補(bǔ)充引理2信源隨機(jī)變量U的最佳2元異字頭碼S

，一定滿足以下論斷：“事件的概率越大，對(duì)應(yīng)的碼字越短”。證明如果2元異字頭碼S

竟然不完全滿足以上論斷，則存在兩個(gè)事件a和b，其概率具有不等式qa>qb，其碼長(zhǎng)也具有不等式na>nb?，F(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)為qana+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。2023/4/2676第76頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.4最佳不等長(zhǎng)編碼補(bǔ)充引理3設(shè)信源隨機(jī)變量U的最佳2元異字頭碼S

，則最長(zhǎng)的碼字至少有兩個(gè)。證明如果2元異字頭碼S

的最長(zhǎng)的碼字竟然只有一個(gè)。設(shè)這個(gè)碼字為c，是事件a的碼字?，F(xiàn)在將c的最后一位去掉，成為c’，將c’仍然作為事件a的碼字。其它事件的碼字保持不變。此時(shí)2元異字頭碼S

變成新的2元碼T。注意到以下兩點(diǎn)：碼T仍然是2元異字頭碼；碼S

的平均碼長(zhǎng)>碼T的平均碼長(zhǎng)。因而碼S

不是最佳2元異字頭碼。用反證法已經(jīng)證明了補(bǔ)充引理3。2023/4/2677第77頁(yè)，共195頁(yè)，2023年，2月20日，星期一aa2023/4/2678第78頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.4最佳不等長(zhǎng)編碼補(bǔ)充引理4最佳2元異字頭碼S可以滿足以下兩條：（1）概率最小的兩個(gè)事件碼字最長(zhǎng)，且長(zhǎng)度相等；（2）它們的碼字僅僅最后一位不同。證明取概率最小的事件a。在剩下的事件中取概率最小的事件b。根據(jù)補(bǔ)充引理2和補(bǔ)充引理3，事件a和事件b的碼字最長(zhǎng)，且長(zhǎng)度相等。這就是說(shuō)，最佳2元異字頭碼S顯然滿足第（1）條。

關(guān)于第（2）條，分以下三種情形來(lái)討論：2023/4/2679第79頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.4最佳不等長(zhǎng)編碼情形一事件a和事件b的碼字僅僅最后一位不同。此時(shí)：最佳2元異字頭碼S

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

也是2元異字頭碼。碼T與碼S平均碼長(zhǎng)相同，因此碼T也是最佳2元異字頭碼，且碼T滿足第（1）條和第（2）條。2023/4/2680第80頁(yè)，共195頁(yè)，2023年，2月20日，星期一abacb§3.4最佳不等長(zhǎng)編碼abcabab2023/4/2681第81頁(yè)，共195頁(yè)，2023年，2月20日，星期一Huffman編碼的最佳性定理3.4.1：對(duì)于給定信源，存在有最佳惟一可譯二元碼，其最小概率的兩個(gè)碼字CK-1和CK的長(zhǎng)度最長(zhǎng)且相等，它們之間僅最后一位碼元取值不同(一個(gè)為0，另一個(gè)為1)。2023/4/2682第82頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.4最佳不等長(zhǎng)編碼補(bǔ)充定理設(shè)信源隨機(jī)變量U有K個(gè)事件，K≥3。取出兩個(gè)概率最小的事件：事件a和事件b。將事件a與事件b合并成一個(gè)事件e，e的概率為事件a與事件b的概率之和；而將信源隨機(jī)變量U的其它事件和其對(duì)應(yīng)的概率保持不變。這樣得到了新的信源隨機(jī)變量U’。找到U’的一個(gè)最佳2元異字頭碼R’。將碼R’中事件e的碼字后面分別添加0和1，分別作為事件a和事件b各自的碼字；而將碼R’中其它事件的碼字保持不變。這樣得到了U的2元碼R。則：碼R是U的最佳2元異字頭碼。2023/4/2683第83頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.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也是最佳的。2023/4/2684第84頁(yè)，共195頁(yè)，2023年，2月20日，星期一設(shè)原始信源隨機(jī)變量新的信源隨機(jī)變量§3.4最佳不等長(zhǎng)編碼2023/4/2685第85頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.4最佳不等長(zhǎng)編碼若C’1，C’2，…，C’K-1是信源U‘的最佳碼，相應(yīng)碼長(zhǎng)為n’1，n’2，…，n’K-1，則對(duì)信源U的碼字C1，C2,…,CK的碼長(zhǎng)為nk=n’k

k≤K–2nk=n’K-1+1k=K,K–1同時(shí)兩信源各事件出現(xiàn)的概率滿足關(guān)系式：pk=p’k

k≤K–2pK+pK-1=p’K-12023/4/2686第86頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.4最佳不等長(zhǎng)編碼

2023/4/2687第87頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.4最佳不等長(zhǎng)編碼補(bǔ)充定理給出了一種構(gòu)造信源隨機(jī)變量U的最佳2元異字頭碼的方法：取出兩個(gè)概率最小的事件a和事件b，分別標(biāo)號(hào)為0和1；然后將事件a和事件b合并成事件e，因此將信源隨機(jī)變量U合并成U’；尋找U’的最佳2元異字頭碼；然后將該碼中事件e的碼字后面分別添加事件a和事件b的標(biāo)號(hào)（0和1），分別成為事件a和事件b的碼字。這種構(gòu)造方法正是2元Huffman編碼。換句話說(shuō)，定理對(duì)信源隨機(jī)變量U的2元Huffman編碼是最佳2元異字頭碼，因而是在唯一可譯前提下的最佳2元不等長(zhǎng)編碼。2023/4/2688第88頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.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í)，一個(gè)事件的碼字是這個(gè)事件從最后標(biāo)號(hào)開(kāi)始到最先標(biāo)號(hào)為止的標(biāo)號(hào)序列。2023/4/2689第89頁(yè)，共195頁(yè)，2023年，2月20日，星期一例：Huffman編碼過(guò)程2023/4/2690第90頁(yè)，共195頁(yè)，2023年，2月20日，星期一例：Huffman編碼過(guò)程2023/4/2691第91頁(yè)，共195頁(yè)，2023年，2月20日，星期一P59Shannon-Fano編碼例子采用Huffman編碼a16b7c6d6e511132401010101a0b100c101d110e111總比特?cái)?shù)88，信源熵為86.601bit2023/4/2692第92頁(yè)，共195頁(yè)，2023年，2月20日，星期一Huffman編碼Shannon-Fano編碼構(gòu)造二叉樹(shù)是自樹(shù)根到樹(shù)葉，很難保證最佳性。Huffman編碼則是從樹(shù)葉到樹(shù)根，是最佳的2023/4/2693第93頁(yè)，共195頁(yè)，2023年，2月20日，星期一總結(jié)Huffman需要知道信源的概率分布，這在實(shí)際中有時(shí)是比較困難的。采用半靜態(tài)模型、自適應(yīng)模型、markov模型，部分匹配預(yù)測(cè)模型等等解決這一問(wèn)題。2023/4/2694第94頁(yè)，共195頁(yè)，2023年，2月20日，星期一D元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è)2023/4/2695第95頁(yè)，共195頁(yè)，2023年，2月20日，星期一D元Huffman編碼K+B=D+m(D-1)，因而K-2=m(D-1)+D-2-B

注意R+B=D，有

0≤B≤D-2，0≤D-2-B≤D-2

因而D-2-B=(K-2)mod(D-1)即

R-2=(K-2)mod(D-1)B個(gè)R個(gè)2023/4/2696第96頁(yè)，共195頁(yè)，2023年，2月20日，星期一Huffman編碼效率高，運(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)更為完美的Shannon-Fano-Elias編碼。沿著這一編碼方法的思路，1976年，J.Rissanen提出了一種可以成功地逼近信息熵極限的編碼方法——算術(shù)編碼。算術(shù)編碼2023/4/2697第97頁(yè)，共195頁(yè)，2023年，2月20日，星期一算術(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ū)間作為代碼的原理。2023/4/2698第98頁(yè)，共195頁(yè)，2023年，2月20日，星期一使用算術(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ù)編碼2023/4/2699第99頁(yè)，共195頁(yè)，2023年，2月20日，星期一在得到信源隨機(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(aK-1)=P(a0)+P(a1)+…+P(aK-2)。

隨后，編碼過(guò)程的每一步，除了最后一步，都是相同的。算術(shù)編碼2023/4/26100第100頁(yè)，共195頁(yè)，2023年，2月20日，星期一編碼器通常需要考慮下面三種數(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ū)間之間的分隔線為信源符號(hào)的分布函數(shù)，每個(gè)子區(qū)間的長(zhǎng)度與可能出現(xiàn)的對(duì)應(yīng)符號(hào)的概率成正比。當(dāng)前要編碼的符號(hào)對(duì)應(yīng)的子區(qū)間成為下一步編碼的初始區(qū)間。算術(shù)編碼2023/4/26101第101頁(yè)，共195頁(yè)，2023年，2月20日，星期一例:對(duì)于前面提出的4符號(hào)模型:中性對(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)當(dāng)所有的符號(hào)都編碼完畢，最終得到的結(jié)果區(qū)間即唯一的確定了已編碼的符號(hào)序列。任何人使用該區(qū)間和模型參數(shù)即可以解碼重建得到該符號(hào)序列。算術(shù)編碼2023/4/26102第102頁(yè)，共195頁(yè)，2023年，2月20日，星期一算術(shù)碼再以二元信源輸出序列01110的編碼為例P(0)P(1)F(0)F(1)01算術(shù)編碼2023/4/26103第103頁(yè)，共195頁(yè)，2023年，2月20日，星期一算術(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ù)編碼2023/4/26104第104頁(yè)，共195頁(yè)，2023年，2月20日，星期一算術(shù)碼信源符號(hào)序列u對(duì)應(yīng)區(qū)間的寬度等于符號(hào)序列的概率信源符號(hào)序列u對(duì)應(yīng)區(qū)間的左端點(diǎn)為算術(shù)編碼2023/4/26105第105頁(yè)，共195頁(yè)，2023年，2月20日，星期一F(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=(u1u2…uL)的碼字。碼字長(zhǎng)度l為算術(shù)編碼2023/4/26106第106頁(yè)，共195頁(yè)，2023年，2月20日，星期一算術(shù)編碼則即因而即2023/4/26107第107頁(yè)，共195頁(yè)，2023年，2月20日，星期一例:

下面對(duì)使用前面提到的4符號(hào)模型進(jìn)行編碼的一段信息進(jìn)行解碼。編碼的結(jié)果是0.538(為了容易理解，這里使用十進(jìn)制而不是二進(jìn)制；我們也假設(shè)得到的結(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ù)編碼的譯碼2023/4/26108第108頁(yè)，共195頁(yè)，2023年，2月20日，星期一分?jǐn)?shù)0.538落在中性所在的子區(qū)間[0,0.6)；這表明編碼器所讀的第一個(gè)符號(hào)必然是中性，這樣就可以將它作為消息的第一個(gè)符號(hào)記下來(lái)。

算術(shù)編碼的譯碼2023/4/26109第109頁(yè)，共195頁(yè)，2023年，2月20日，星期一然后我們將區(qū)間[0,0.6)再分成四個(gè)子區(qū)間：中性的區(qū)間是[0,0.36)--[0,0.6)的60%

陽(yáng)性的區(qū)間是[0.36,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ù)編碼的譯碼2023/4/26110第110頁(yè)，共195頁(yè)，2023年，2月20日，星期一再一次將當(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)。由于它也是內(nèi)部的結(jié)束符號(hào)，這也就意味著編碼已經(jīng)結(jié)束。算術(shù)編碼的譯碼2023/4/26111第111頁(yè)，共195頁(yè)，2023年，2月20日，星期一§3.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)用。2023/4/26112第112頁(yè)，共195頁(yè)，2023年，2月20日，星期一

1982年，Rissanen和G.G.Langdon一起改進(jìn)了算術(shù)編碼。之后，人們又將算術(shù)編碼與J.G.Cleary和I.H.Witten于1984年提出的部分匹配預(yù)測(cè)模型（PPM）相結(jié)合，開(kāi)發(fā)出了壓縮效果近乎完美的算法。今天，那些名為PPMC、PPMD或PPMZ并號(hào)稱壓縮效果天下第一的通用壓縮算法，實(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)行速度也很難滿足日常應(yīng)用的需求。如果不是后文將要提到的兩個(gè)猶太人，我們還不知要到什么時(shí)候才能用上WinZIP這樣方便實(shí)用的壓縮工具呢。詞典編碼方法2023/4/26113第113頁(yè)，共195頁(yè)，2023年，2月20日，