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

信息論與編碼理論基礎(chǔ)第三章2023/7/301第1頁，課件共195頁，創(chuàng)作于2023年2月

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

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

摩爾斯式電碼19世紀(jì)中葉，由SamuelMorse發(fā)明每個字符用“.”或“–”表示觀察：一些字符比另外一些字符出現(xiàn)的頻率更高，如“a,e”比“z,q”出現(xiàn)的頻率高因此，為了減少發(fā)送信息的平均時間，用較短的序列表示出現(xiàn)頻率高的字符，較長的序列表示出現(xiàn)頻率低的字符e:.,a:.–q:--.-,j:.---2023/7/307第7頁，課件共195頁，創(chuàng)作于2023年2月為什么可以進行信源編碼/數(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后常跟有字母U2023/7/308第8頁，課件共195頁，創(chuàng)作于2023年2月例：空間冗余圖像中存在大面積部分相似或完全一樣的像素pmf2023/7/309第9頁，課件共195頁，創(chuàng)作于2023年2月例：時間冗余視頻圖像前后幾幀的內(nèi)容變化不大（位置可能不同，可用運動估計方法找到對應(yīng)位置）2023/7/3010第10頁，課件共195頁，創(chuàng)作于2023年2月例：結(jié)構(gòu)冗余圖像中物體表面紋理等結(jié)構(gòu)存在冗余2023/7/3011第11頁，課件共195頁，創(chuàng)作于2023年2月怎樣進行信源編碼無失真編碼:若要求將信源輸出在接收端精確地重現(xiàn)出來，即保證信源輸出所攜帶的信息全部無損地傳達給信宿，就要對信源進行無失真編碼。無失真編碼只是對信源冗余度進行壓縮，并不改變信源熵，它能保證信源序列經(jīng)無擾信道傳輸后，得到無失真的恢復(fù)。限定失真編碼：在實際傳信中，要精確的復(fù)制出信源的輸出是不可能的，根據(jù)信源－信宿對定出的可接收準(zhǔn)則或保真度準(zhǔn)則，計算要保留多少有關(guān)信源輸出的信息量，以及如何表示它們，這就是限定失真的信源編碼問題。2023/7/3012第12頁，課件共195頁，創(chuàng)作于2023年2月第三章：信源編碼（一）

離散信源無失真編碼§3.1信源及其分類§3.2離散無記憶（簡單）信源的等長編碼§3.3離散無記憶（簡單）信源的不等長編碼§3.4最佳不等長編碼2023/7/3013第13頁，課件共195頁，創(chuàng)作于2023年2月§3.1信源及其分類信源的概念

:信源就是信息的來源。注意：在一個固定的時刻，信源發(fā)出的是一個隨機變量。隨著時間的延續(xù)，信源發(fā)出一個又一個隨機變量，稱之為一個隨機過程。

因此，可以用概率空間來描述信源。

2023/7/3014第14頁，課件共195頁，創(chuàng)作于2023年2月§3.1信源及其分類離散信源信源每隔一個定長時間段就發(fā)出一個隨機變量；隨著時間的延續(xù)，信源發(fā)出的是隨機變量序列…U-2U-1U0U1U2…，

其中

Uk為第k個時間段發(fā)出的隨機變量；每個Uk都是一個離散型的隨機變量。離散無記憶信源隨機變量…、U-2、U-1、U0、U1、U2、…相互獨立的離散信源。離散無記憶隨機變量…、U-2、U-1、U0、U1、U2、…簡單信源具有相同的概率分布的離散無記憶信源。2023/7/3015第15頁，課件共195頁，創(chuàng)作于2023年2月§3.1信源及其分類（總結(jié)：離散無記憶簡單信源就是時間離散、事件離散、各隨機變量獨立同分布的信源。課程學(xué)習(xí)所面對的信源將主要是離散無記憶簡單信源）一般的信源

連續(xù)信源：有時間連續(xù)的信源，也有事件連續(xù)的信源；有記憶信源：信源在不同時刻發(fā)出的隨機變量相互依賴；有限記憶信源：在有限時間差內(nèi)的信源隨機變量相互依賴；非簡單信源：信源在不同時刻發(fā)出的隨機變量具有不同的概率分布。馬爾可夫信源：信源隨機過程是馬爾可夫過程。2023/7/3016第16頁，課件共195頁，創(chuàng)作于2023年2月§3.2離散無記憶（簡單）信源的等長編碼（1）設(shè)有一個離散無記憶簡單信源，信源發(fā)出的隨機變量序列為：…U-2U-1U0U1U2…。設(shè)信源隨機變量U1的事件有K個：{a1,a2,…,aK}，則L維信源隨機向量(U1U2…UL)的事件有KL個：{(u1u2…uL)|其中每個分量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è)有一個含D個字母的字母表，對于(U1U2…UL)的每一個事件(u1u2…uL)，都用一個字母串(c1c2…)來表示。

2023/7/3017第17頁，課件共195頁，創(chuàng)作于2023年2月碼長：碼字所含碼元的個數(shù)等長編碼：所有碼字均有相同的碼長N，對應(yīng)的碼叫做等長碼(FLC，F(xiàn)ixedLengthcode)；否則為變長編碼。編碼器碼字:每一個事件(u1u2…uL)所對應(yīng)的字母串(c1c2…)。

編碼器模型：D個字母的字母表A信源2023/7/3018第18頁，課件共195頁，創(chuàng)作于2023年2月熵是隨機變量平均不確定性的一個測度，表示了描述這個隨機變量所需要的平均比特數(shù)2023/7/3019第19頁，課件共195頁，創(chuàng)作于2023年2月§3.2離散無記憶（簡單）信源的等長編碼例：離散無記憶簡單信源發(fā)出的隨機變量序列為：…U-2U-1U0U1U2…。其中U1的事件有3個：{晴,云,陰}。(U1U2)有9個事件

{（晴晴），（晴云），（晴陰），（云晴），（云云），（云陰），（陰晴），（陰云），（陰陰）}。用字母表{0,1}對(U1U2)的事件進行2元編碼如下：（晴晴）→0000，（晴云）→0001，（晴陰）→0011，（云晴）→0100，（云云）→0101，（云陰）→0111，（陰晴）→1100，（陰云）→1101，（陰陰）→1111。2023/7/3020第20頁，課件共195頁，創(chuàng)作于2023年2月無錯編碼（唯一可譯碼）(U1U2…UL)的不同事件用不同的碼字來表示。能夠?qū)崿F(xiàn)無錯編碼的充要條件是DN≥KL。（即NlogD/L≥logK）這里N/L表示每個信源符號所需要的碼符號數(shù)；logD是一個碼符號所能載荷的最大信息量；N/L≥logK/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

。有錯編碼

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

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

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

2023/7/3027第27頁，課件共195頁，創(chuàng)作于2023年2月§3.2離散無記憶（簡單）信源的等長編碼取IL是(V1V2…VL)的如下函數(shù)：則①IL最終是(U1U2…UL)的函數(shù)；②③因此有切比雪夫不等式：對任意ε>0有P{H(U1)-ε≤IL≤H(U1)+ε}≥2023/7/3028第28頁，課件共195頁，創(chuàng)作于2023年2月切比雪夫不等式注：切比雪夫2023/7/3029第29頁，課件共195頁，創(chuàng)作于2023年2月§3.2離散無記憶（簡單）信源的等長編碼取定L0使得，則當(dāng)L≥L0時總有因此當(dāng)L≥L0時總有這樣的一些事件序列，

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

，因此，可以把信源序列分成兩個互補的子集。2023/7/3030第30頁，課件共195頁，創(chuàng)作于2023年2月§3.2離散無記憶（簡單）信源的等長編碼定義3.2.1(p57)定義TU(L,ε)={(u1u2…uL)|H(U1)-ε≤IL≤H(U1)+ε}，稱TU(L,ε)為ε-典型序列集。稱TU(L,ε)的補集為非ε-典型序列集。

（綜上所述有）定理3.2.1(信源劃分定理，p58)對任意ε>0，取L0使得則當(dāng)L≥L0時總有P{(U1U2…UL))=(u1u2…uL)|(u1u2…uL)∈TU(L,ε)}≥1-ε。2023/7/3031第31頁，課件共195頁，創(chuàng)作于2023年2月§3.2離散無記憶（簡單）信源的等長編碼（簡記H(U)=H(U1)。設(shè)以下的對數(shù)都是以2為底的。）系3.2.1(特定典型序列出現(xiàn)的概率，p58)若一個特定的事件(u1u2…uL)∈TU(L,ε)，則2-L(H(U)+ε)≤P{(U1U2…UL)=(u1u2…uL)}≤2-L(H(U)-ε)。證明設(shè)(u1u2…uL)∈TU(L,ε)。注意到此時H(U)-ε≤IL≤H(U)+ε，2023/7/3032第32頁，課件共195頁，創(chuàng)作于2023年2月§3.2離散無記憶（簡單）信源的等長編碼所以2023/7/3033第33頁，課件共195頁，創(chuàng)作于2023年2月§3.2離散無記憶（簡單）信源的等長編碼系3.2.2(典型序列的數(shù)量，p58)(1-ε)2L(H(U)-ε)≤|TU(L,ε)|≤2L(H(U)+ε)。證明一方面，2023/7/3034第34頁，課件共195頁，創(chuàng)作于2023年2月§3.2離散無記憶（簡單）信源的等長編碼另一方面，2023/7/3035第35頁，課件共195頁，創(chuàng)作于2023年2月§3.2離散無記憶（簡單）信源的等長編碼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/7/3036第36頁，課件共195頁，創(chuàng)作于2023年2月§3.2離散無記憶（簡單）信源的等長編碼典型序列集非典型序列集序列集合定理3.2.1，系3.2.1以及系3.2.2就說明：所有典型序列的概率和接近于1，是高概率集；典型序列集中各序列出現(xiàn)的概率近似相等；每個典型序列中一個信源符號的平均信息量接近于信源熵；當(dāng)L達到無限時，才等于信源熵。2023/7/3037第37頁，課件共195頁，創(chuàng)作于2023年2月§3.2離散無記憶（簡單）信源的等長編碼補充引理設(shè)給定一個R0>H(U)。對每個正整數(shù)L，對應(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時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/7/3038第38頁，課件共195頁，創(chuàng)作于2023年2月§3.2離散無記憶（簡單）信源的等長編碼定理3.2.2(無錯編碼正定理，p60)

給定編碼設(shè)備的編碼速率R0，R0>H(U)。則對任意的ε>0，總存在一個L0，使得對任意的L>L0，都有對(U1U2…UL)的2元等長編碼方法和對應(yīng)的譯碼方法，①實際的編碼速率R滿足R0≥R>H(U)，②“譯碼錯誤”的概率pe<ε。2023/7/3039第39頁，課件共195頁，創(chuàng)作于2023年2月§3.2離散無記憶（簡單）信源的等長編碼證明首先聲明，所有的對數(shù)計算都是以2為底的。此時實際的編碼速率為R=N/L。任取正數(shù)ε≤(R0-H(U))/2，取補充引理所描述的L0，則

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

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

這就是說，典型序列集TU(L,ε)中的事件的個數(shù)不超過長度為N的2元碼字的數(shù)量2N。因此，可以做如下的編碼：將TU(L,ε)中的事件用不同的N長2元碼字來表示，而將TU(L,ε)以外的事件用一個固定的N長2元碼字來表示，這個固定的N長2元碼字已經(jīng)用來表示了TU(L,ε)中的某個事件。2023/7/3040第40頁，課件共195頁，創(chuàng)作于2023年2月§3.2離散無記憶（簡單）信源的等長編碼對應(yīng)的譯碼：所有的碼字均譯為它所表示的TU(L,ε)中的事件。結(jié)論：①實際的編碼速率R滿足R0≥R>H(U)；②“譯碼錯誤”的概率pe=P((U1U2…UL)不屬于TU(L,ε))=1-P((U1U2…UL)∈TU(L,ε))<ε。得證。

定理3.2.2(無錯編碼反定理，p60)設(shè)給定編碼設(shè)備的編碼速率R0，滿足R0<H(U)。當(dāng)限制實際的編碼速率R≤R0時，無論怎樣編碼和譯碼都不能使“譯碼錯誤”的概率任意小。（沒有證明）2023/7/3041第41頁，課件共195頁，創(chuàng)作于2023年2月§3.2離散無記憶（簡單）信源的等長編碼漸進無錯編碼的要求給定離散無記憶簡單信源：…U-2U-1U0U1U2…；給定編碼設(shè)備的編碼速率R0，滿足R0>H(U)；給定一個任意小的正數(shù)ε>0；要求：選擇合適的L，N，對(U1U2…UL)進行合適的2元N長編碼，使得

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

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

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

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

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

竟然不完全滿足以上論斷，則存在兩個事件a和b，其概率具有不等式qa>qb，其碼長也具有不等式na>nb?，F(xiàn)在將事件a和b交換碼字，其它事件的碼字保持不變。此時2元異字頭碼S

變成新的2元異字頭碼T。由于碼S與碼T中事件a和b之外的其它事件的碼字保持不變，因而它們對平均碼長的貢獻不變，而碼S

中事件a和b的碼字對平均碼長的貢獻為qana+qbnb；碼T中事件a和b的碼字對平均碼長的貢獻為qanb+qbna。(qana+qbnb)-(qanb+qbna)=(qa-qb)(na-nb)>0。這就是說，碼S

的平均碼長>碼T

的平均碼長。因而碼S

不是最佳2元異字頭碼。用反證法已經(jīng)證明了補充引理2。2023/7/3076第76頁，課件共195頁，創(chuàng)作于2023年2月§3.4最佳不等長編碼補充引理3設(shè)信源隨機變量U的最佳2元異字頭碼S

，則最長的碼字至少有兩個。證明如果2元異字頭碼S

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

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

的平均碼長>碼T的平均碼長。因而碼S

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

關(guān)于第（2）條，分以下三種情形來討論：2023/7/3079第79頁，課件共195頁，創(chuàng)作于2023年2月§3.4最佳不等長編碼情形一事件a和事件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滿足第（1）條和第（2）條。2023/7/3080第80頁，課件共195頁，創(chuàng)作于2023年2月abacb§3.4最佳不等長編碼abcabab2023/7/3081第81頁，課件共195頁，創(chuàng)作于2023年2月Huffman編碼的最佳性定理3.4.1：對于給定信源，存在有最佳惟一可譯二元碼，其最小概率的兩個碼字CK-1和CK的長度最長且相等，它們之間僅最后一位碼元取值不同(一個為0，另一個為1)。2023/7/3082第82頁，課件共195頁，創(chuàng)作于2023年2月§3.4最佳不等長編碼補充定理設(shè)信源隨機變量U有K個事件，K≥3。取出兩個概率最小的事件：事件a和事件b。將事件a與事件b合并成一個事件e，e的概率為事件a與事件b的概率之和；而將信源隨機變量U的其它事件和其對應(yīng)的概率保持不變。這樣得到了新的信源隨機變量U’。找到U’的一個最佳2元異字頭碼R’。將碼R’中事件e的碼字后面分別添加0和1，分別作為事件a和事件b各自的碼字；而將碼R’中其它事件的碼字保持不變。這樣得到了U的2元碼R。則：碼R是U的最佳2元異字頭碼。2023/7/3083第83頁，課件共195頁，創(chuàng)作于2023年2月§3.4最佳不等長編碼證明首先說明，碼R是U的2元異字頭碼。碼R’中，每個碼字都在樹梢，對事件e的碼字后面分別添加0和1后，得到碼R，碼R中，由事件e的碼字后面分別添加0和1得到的兩個碼字對應(yīng)于碼數(shù)中的兩個新的葉子節(jié)點，位于樹梢；而其它碼字顯然也在樹梢。綜上所述，碼R是U的2元異字頭碼。接下來說明，對輔助集U’為最佳的碼，對原始消息集U也是最佳的。2023/7/3084第84頁，課件共195頁，創(chuàng)作于2023年2月設(shè)原始信源隨機變量新的信源隨機變量§3.4最佳不等長編碼2023/7/3085第85頁，課件共195頁，創(chuàng)作于2023年2月§3.4最佳不等長編碼若C’1，C’2，…，C’K-1是信源U‘的最佳碼，相應(yīng)碼長為n’1，n’2，…，n’K-1，則對信源U的碼字C1，C2,…,CK的碼長為nk=n’k

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

k≤K–2pK+pK-1=p’K-12023/7/3086第86頁，課件共195頁，創(chuàng)作于2023年2月§3.4最佳不等長編碼

2023/7/3087第87頁，課件共195頁，創(chuàng)作于2023年2月§3.4最佳不等長編碼補充定理給出了一種構(gòu)造信源隨機變量U的最佳2元異字頭碼的方法：取出兩個概率最小的事件a和事件b，分別標(biāo)號為0和1；然后將事件a和事件b合并成事件e，因此將信源隨機變量U合并成U’；尋找U’的最佳2元異字頭碼；然后將該碼中事件e的碼字后面分別添加事件a和事件b的標(biāo)號（0和1），分別成為事件a和事件b的碼字。這種構(gòu)造方法正是2元Huffman編碼。換句話說，定理對信源隨機變量U的2元Huffman編碼是最佳2元異字頭碼，因而是在唯一可譯前提下的最佳2元不等長編碼。2023/7/3088第88頁，課件共195頁，創(chuàng)作于2023年2月§3.4最佳不等長編碼2元Huffman編碼法（字母表{0,1}）（1）將概率最小的2個事件分別賦予標(biāo)號“0”和“1”。（2）將這2個事件合并為一個事件，其概率為2個事件概率之和。重復(fù)（1）-（2），直到合并為所剩的事件為2個。將這2事件分別賦予標(biāo)號“0”和“1”。編碼完畢。此時，一個事件的碼字是這個事件從最后標(biāo)號開始到最先標(biāo)號為止的標(biāo)號序列。2023/7/3089第89頁，課件共195頁，創(chuàng)作于2023年2月例：Huffman編碼過程2023/7/3090第90頁，課件共195頁，創(chuàng)作于2023年2月例：Huffman編碼過程2023/7/3091第91頁，課件共195頁，創(chuàng)作于2023年2月P59Shannon-Fano編碼例子采用Huffman編碼a16b7c6d6e511132401010101a0b100c101d110e111總比特數(shù)88，信源熵為86.601bit2023/7/3092第92頁，課件共195頁，創(chuàng)作于2023年2月Huffman編碼Shannon-Fano編碼構(gòu)造二叉樹是自樹根到樹葉，很難保證最佳性。Huffman編碼則是從樹葉到樹根，是最佳的2023/7/3093第93頁，課件共195頁，創(chuàng)作于2023年2月總結(jié)Huffman需要知道信源的概率分布，這在實際中有時是比較困難的。采用半靜態(tài)模型、自適應(yīng)模型、markov模型，部分匹配預(yù)測模型等等解決這一問題。2023/7/3094第94頁，課件共195頁，創(chuàng)作于2023年2月D元Huffman編碼D元碼全數(shù)的端節(jié)點數(shù)為D+m(D-1)由Huffman編碼的最佳性知空缺的端節(jié)點應(yīng)當(dāng)是碼長最長的端節(jié)點共有K個符號，設(shè)第一次需要合并的消息個數(shù)為R，空缺數(shù)為BB個R個2023/7/3095第95頁，課件共195頁，創(chuàng)作于2023年2月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個R個2023/7/3096第96頁，課件共195頁，創(chuàng)作于2023年2月Huffman編碼效率高，運算速度快，實現(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é)角度看來更為完美的Shannon-Fano-Elias編碼。沿著這一編碼方法的思路，1976年，J.Rissanen提出了一種可以成功地逼近信息熵極限的編碼方法——算術(shù)編碼。算術(shù)編碼2023/7/3097第97頁，課件共195頁，創(chuàng)作于2023年2月算術(shù)編碼Shannon-Fano編碼，Huffman編碼的編碼方法：首先對信源的各事件進行編碼，然后再對輸入的消息序列進行編碼變換。算術(shù)編碼：首先假設(shè)一個信源的概率模型,隨后直接把整個輸入的消息編碼為一個(0.0≤n<1.0)內(nèi)的小區(qū)間，在編碼的過程中，消息序列集中的每個元素都用來縮短這個區(qū)間，消息序列集中的元素越多,所得到的區(qū)間就越小，當(dāng)區(qū)間變小時，就需要更多的數(shù)位來表示這個區(qū)間，這就是區(qū)間作為代碼的原理。2023/7/3098第98頁，課件共195頁，創(chuàng)作于2023年2月使用算術(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ù)編碼2023/7/3099第99頁，課件共195頁，創(chuàng)作于2023年2月在得到信源隨機變量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(aK-1)=P(a0)+P(a1)+…+P(aK-2)。

隨后，編碼過程的每一步，除了最后一步，都是相同的。算術(shù)編碼2023/7/30100第100頁，課件共195頁，創(chuàng)作于2023年2月編碼器通常需要考慮下面三種數(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ù)編碼2023/7/30101第101頁，課件共195頁，創(chuàng)作于2023年2月例:對于前面提出的4符號模型:中性對應(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)當(dāng)所有的符號都編碼完畢，最終得到的結(jié)果區(qū)間即唯一的確定了已編碼的符號序列。任何人使用該區(qū)間和模型參數(shù)即可以解碼重建得到該符號序列。算術(shù)編碼2023/7/30102第102頁，課件共195頁，創(chuàng)作于2023年2月算術(shù)碼再以二元信源輸出序列01110的編碼為例P(0)P(1)F(0)F(1)01算術(shù)編碼2023/7/30103第103頁，課件共195頁，創(chuàng)作于2023年2月算術(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/7/30104第104頁，課件共195頁，創(chuàng)作于2023年2月算術(shù)碼信源符號序列u對應(yīng)區(qū)間的寬度等于符號序列的概率信源符號序列u對應(yīng)區(qū)間的左端點為算術(shù)編碼2023/7/30105第105頁，課件共195頁，創(chuàng)作于2023年2月F(u)將[0,1)分割成許多小區(qū)間，以小區(qū)間的左端點數(shù)值的二進制小數(shù)表示該序列，同時要將該小數(shù)的小數(shù)位數(shù)截斷為l位，截斷規(guī)則為：

l位后面只要有非0的余數(shù)就要向第l位進位。最后得到了小數(shù)0.t。將t作為事件u=(u1u2…uL)的碼字。碼字長度l為算術(shù)編碼2023/7/30106第106頁，課件共195頁，創(chuàng)作于2023年2月算術(shù)編碼則即因而即2023/7/30107第107頁，課件共195頁，創(chuàng)作于2023年2月例:

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

算術(shù)編碼的譯碼2023/7/30109第109頁，課件共195頁，創(chuàng)作于2023年2月然后我們將區(qū)間[0,0.6)再分成四個子區(qū)間：中性的區(qū)間是[0,0.36)--[0,0.6)的60%

陽性的區(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ū)間；所以消息的第二個符號一定是陰性。算術(shù)編碼的譯碼2023/7/30110第110頁，課件共195頁，創(chuàng)作于2023年2月再一次將當(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ū)間；所以，這一定是下一個符號。由于它也是內(nèi)部的結(jié)束符號，這也就意味著編碼已經(jīng)結(jié)束。算術(shù)編碼的譯碼2023/7/30111第111頁，課件共195頁，創(chuàng)作于2023年2月§3.4最佳不等長編碼算術(shù)編碼的特點特點一當(dāng)L很大時，平均碼長接近信源熵H(U)，因此編碼效率接近上限。特點二編譯碼簡單，存儲量小，速度快。算術(shù)編碼的應(yīng)用領(lǐng)域在圖象數(shù)據(jù)壓縮標(biāo)準(zhǔn)（如JPEG）中得到廣泛應(yīng)用。2023/7/30112第112頁，課件共195頁，創(chuàng)作于2023年2月

1982年，Rissanen和G.G.Langdon一起改進了算術(shù)編碼。之后，人們又將算術(shù)編碼與J.G.Cleary和I.H.Witten于1984年提出的部分匹配預(yù)測模型（PPM）相結(jié)合，開發(fā)出了壓縮效果近乎完美的算法。今天，那些名為PPMC、PPMD或PPMZ并號稱壓縮效果天下第一的通用壓縮算法，實際上全都是這一思路的具體實現(xiàn)?？雌饋恚瑝嚎s技術(shù)的發(fā)展可以到此為止了。不幸的是，事情往往不像想象中的那樣簡單：算術(shù)編碼雖然可以獲得最短的編碼長度，但其本身的復(fù)雜性也使得算術(shù)編碼的任何具體實現(xiàn)在運行時都慢如蝸牛。即使在摩爾定律大行其道，CPU速度日新月異的今天，算術(shù)編碼程序的運行速度也很難滿足日常應(yīng)用的需求。如果不是后文將要提到的兩個猶太人，我們還不知要到什么時候才能用上WinZIP這樣方便實用的壓縮工具呢。詞典編碼方法2023/7/30113第113頁，課件共195頁，創(chuàng)作于2023年2月逆向思維永遠是科學(xué)和技術(shù)領(lǐng)域里出奇制勝的法寶。就在大多數(shù)人絞盡腦汁想改進Huffman或算術(shù)編碼，以獲得一種兼顧了運行速度和壓縮效果的“完美”編碼的時候，兩個聰明的猶太人J.Ziv和A.Lempel獨辟蹊徑，完全脫離Huffman及算術(shù)編碼的設(shè)計思路，創(chuàng)造出了一系列比Huffman編碼更有效，比算術(shù)編碼更快捷的壓縮算法。我們通常用這兩個猶太人姓氏的縮寫，將這些算法統(tǒng)稱為LZ系列算法。詞典編碼方法2023/7/30114第114頁，課件共195頁，創(chuàng)作于2023年2月說實話，LZ系列算法的思路并不新鮮，其中既沒有高深的理論背景，也沒有復(fù)雜的數(shù)學(xué)公式，它們只是簡單地延續(xù)了千百年來人們對字典的追崇