無失真的信源編碼

無失真的信源編碼第1頁，課件共50頁，創(chuàng)作于2023年2月8.1霍夫曼（Huffman）碼設(shè)離散無記憶信源二進制香農(nóng)碼的編碼步驟如下：將信源符號按概率從大到小的順序排列，為方便起見，令p(x1)≥p(x2)≥…≥p(xn)令p(x0)=0，用pa(xj)，j=i+1表示第i個碼字的累加概率，則：確定滿足下列不等式的整數(shù)ki，并令ki為第i個碼字的長度－log2

p(xn)≤ki<－log2

p(xn)+1將pa(xj)用二進制表示，并取小數(shù)點后ki

位作為符號xi的編碼。第2頁，課件共50頁，創(chuàng)作于2023年2月例有一單符號離散無記憶信源對該信源編二進制香農(nóng)碼。其編碼過程如下表所示。8.1霍夫曼（Huffman）碼第3頁，課件共50頁，創(chuàng)作于2023年2月計算出給定信源香農(nóng)碼的平均碼長若對上述信源采用等長編碼，要做到無失真譯碼，每個符號至少要用3個比特表示。相比較，香農(nóng)編碼對信源進行了壓縮。由離散無記憶信源熵定義，可計算出：對上述信源采用香農(nóng)編碼的信息率為編碼效率為信源熵和信息率之比。則可以看出，編碼效率并不是很高。8.1霍夫曼（Huffman）碼第4頁，課件共50頁，創(chuàng)作于2023年2月第六節(jié)費諾編碼費諾編碼也是一種常見的信源編碼方法。編碼步驟如下：將概率按從大到小的順序排列，令p(x1)≥p(x2)≥…≥p(xn)按編碼進制數(shù)將概率分組，使每組概率盡可能接近或相等。如編二進制碼就分成兩組，編m進制碼就分成m組。給每一組分配一位碼元。將每一分組再按同樣原則劃分，重復(fù)步驟2和3，直至概率不再可分為止。第5頁，課件共50頁，創(chuàng)作于2023年2月第六節(jié)費諾編碼例設(shè)有一單符號離散信源對該信源編二進制費諾碼。編碼過程如下表。第6頁，課件共50頁，創(chuàng)作于2023年2月第六節(jié)費諾編碼該信源的熵為平均碼長為編碼效率為本例中費諾編碼有較高的編碼效率。費諾碼比較適合于每次分組概率都很接近的信源。特別是對每次分組概率都相等的信源進行編碼時，可達到理想的編碼效率。第7頁，課件共50頁，創(chuàng)作于2023年2月第六節(jié)費諾編碼題中碼字還可用碼樹來表示，如圖所示。第8頁，課件共50頁，創(chuàng)作于2023年2月第七節(jié)霍夫曼編碼

霍夫曼(Huffman)編碼是一種效率比較高的變長無失真信源編碼方法。編碼步驟二進制哈夫曼編碼m進制哈夫曼編碼第9頁，課件共50頁，創(chuàng)作于2023年2月第七節(jié)霍夫曼編碼——編碼步驟將信源符號按概率從大到小的順序排列，令p(x1)≥p(x2)≥…≥p(xn)給兩個概率最小的信源符號p(xn-1)和p(xn)各分配一個碼位“0”和“1”，將這兩個信源符號合并成一個新符號，并用這兩個最小的概率之和作為新符號的概率，結(jié)果得到一個只包含(n－1)個信源符號的新信源。稱為信源的第一次縮減信源，用S1表示。將縮減信源S1的符號仍按概率從大到小順序排列，重復(fù)步驟2，得到只含(n－2)個符號的縮減信源S2。重復(fù)上述步驟，直至縮減信源只剩兩個符號為止，此時所剩兩個符號的概率之和必為1。然后從最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號所對應(yīng)的碼字。第10頁，課件共50頁，創(chuàng)作于2023年2月第七節(jié)霍夫曼編碼——二進制哈夫曼編碼例設(shè)單符號離散無記憶信源如下，要求對信源編二進制霍夫曼碼。編碼過程如下圖（后頁）。在圖中讀取碼字的時候，一定要從后向前讀，此時編出來的碼字才是可分離的異前置碼。若從前向后讀取碼字，則碼字不可分離。第11頁，課件共50頁，創(chuàng)作于2023年2月第七節(jié)霍夫曼編碼——二進制哈夫曼編碼第12頁，課件共50頁，創(chuàng)作于2023年2月第七節(jié)霍夫曼編碼——二進制哈夫曼編碼將上圖左右顛倒過來重畫一下，即可得到二進制哈夫曼碼的碼樹。第13頁，課件共50頁，創(chuàng)作于2023年2月信源熵為：平均碼長為編碼效率為若采用定長編碼，碼長K=3，則編碼效率可見哈夫曼的編碼效率提高了12.7%。第七節(jié)霍夫曼編碼——二進制哈夫曼編碼第14頁，課件共50頁，創(chuàng)作于2023年2月第七節(jié)霍夫曼編碼——二進制哈夫曼編碼注意：哈夫曼的編法并不惟一。每次對縮減信源兩個概率最小的符號分配“0”和“1”碼元是任意的，所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性，即能得到可分離碼字。不同的碼元分配，得到的具體碼字不同，但碼長ki不變，平均碼長也不變，所以沒有本質(zhì)區(qū)別；縮減信源時，若合并后的新符號概率與其他符號概率相等，從編碼方法上來說，這幾個符號的次序可任意排列，編出的碼都是正確的，但得到的碼字不相同。不同的編法得到的碼字長度ki也不盡相同。第15頁，課件共50頁，創(chuàng)作于2023年2月例：單符號離散無記憶信源，用兩種不同的方法對其編二進制哈夫曼碼。siliWi概率s1s2s3s4s512344101000001000110.40.20.20.10.10.40.20.20.20.40.40.20.60.4010101方法一：合并后的新符號排在其它相同概率符號的后面。第七節(jié)霍夫曼編碼——二進制哈夫曼編碼第16頁，課件共50頁，創(chuàng)作于2023年2月siliWi概率s1s2s3s4s512344101000001000110.40.20.20.10.10.40.20.20.20.40.40.20.60.4010101

這兩種編碼哪一種更好呢，我們來計算一下二者的碼長。方法二：合并后的新符號排在其它相同概率符號的前面。第七節(jié)霍夫曼編碼——二進制哈夫曼編碼第17頁，課件共50頁，創(chuàng)作于2023年2月兩種編碼的平均碼長是一樣的，都是2.2，那一種更好呢，我們可以計算一下平均碼長的方差。定義碼字長度的方差σ2：第七節(jié)霍夫曼編碼——二進制哈夫曼編碼第18頁，課件共50頁，創(chuàng)作于2023年2月第七節(jié)霍夫曼編碼——二進制哈夫曼編碼可見：第二種編碼方法的碼長方差要小許多。意味著第二種編碼方法的碼長變化較小，比較接近于平均碼長。第一種方法編出的5個碼字有4種不同的碼長；第二種方法編出的碼長只有兩種不同的碼長；顯然，第二種編碼方法更簡單、更容易實現(xiàn)，所以更好。結(jié)論：在哈夫曼編碼過程中，對縮減信源符號按概率由大到小的順序重新排列時，應(yīng)使合并后的新符號盡可能排在靠前的位置，這樣可使合并后的新符號重復(fù)編碼次數(shù)減少，使短碼得到充分利用。第19頁，課件共50頁，創(chuàng)作于2023年2月第七節(jié)霍夫曼編碼——m進制哈夫曼編碼“全樹”概念定義：碼樹圖中每個中間節(jié)點后續(xù)的枝數(shù)為m時稱為全樹；若有些節(jié)點的后續(xù)枝數(shù)不足m，就稱為非全樹。二進制碼不存在非全樹的情況，因為后續(xù)枝數(shù)是一時，這個枝就可以去掉使碼字長度縮短。對m進制編碼：若所有碼字構(gòu)成全樹，可分離的碼字數(shù)（信源個數(shù)）必為m+k(m－1)。k為信源縮減次數(shù)。若信源所含的符號數(shù)n不能構(gòu)成m進制全樹，必須增加s個不用的碼字形成全樹。顯然s<m－1，若s=m－1，意味著某個中間節(jié)點之后只有一個分枝，為了節(jié)約碼長，這一分枝可以省略。第20頁，課件共50頁，創(chuàng)作于2023年2月第七節(jié)霍夫曼編碼——m進制哈夫曼編碼在編m進制哈夫曼碼時為了使平均碼長最短，必須使最后一步縮減信源有m個信源符號。非全樹時，有s個碼字不用：第一次對最小概率符號分配碼元時就只取(m－s)個，分別配以0,1,…,m－s－1，把這些符號的概率相加作為一個新符號的概率，與其它符號一起重新排列。以后每次就可以取m個符號，分別配以0,1,…,m－1；…；如此下去，直至所有概率相加得1為止，即得到各符號的m進制碼字。第21頁，課件共50頁，創(chuàng)作于2023年2月第七節(jié)霍夫曼編碼——m進制哈夫曼編碼例：對如下單符號離散無記憶信源(例5.4.1)編三進制哈夫曼碼。這里：m=3，n=8令k=3，m+k(m－1)=9，則s=9－n=9－8=1所以第一次取m－s=2個符號進行編碼。第22頁，課件共50頁，創(chuàng)作于2023年2月第七節(jié)霍夫曼編碼——m進制哈夫曼編碼第23頁，課件共50頁，創(chuàng)作于2023年2月第七節(jié)霍夫曼編碼——m進制哈夫曼編碼平均碼長為：信息率為：編碼效率為：可見：哈夫曼的編碼效率相當高，對編碼器的要求也簡單得多。第24頁，課件共50頁，創(chuàng)作于2023年2月一些結(jié)論香農(nóng)碼、費諾碼、哈夫曼碼都考慮了信源的統(tǒng)計特性，使經(jīng)常出現(xiàn)的信源符號對應(yīng)較短的碼字，使信源的平均碼長縮短，從而實現(xiàn)了對信源的壓縮；香農(nóng)碼有系統(tǒng)的、惟一的編碼方法，但在很多情況下編碼效率不是很高；費諾碼和哈夫曼碼的編碼方法都不惟一；費諾碼比較適合于對分組概率相等或接近的信源編碼；哈夫曼碼對信源的統(tǒng)計特性沒有特殊要求，編碼效率比較高，對編碼設(shè)備的要求也比較簡單，因此綜合性能優(yōu)于香農(nóng)碼和費諾碼。第25頁，課件共50頁，創(chuàng)作于2023年2月第八節(jié)游程編碼、算術(shù)編碼香農(nóng)編碼、費諾編碼、哈夫曼編碼主要是針對無記憶信源。當信源有記憶時上述編碼效率不高；游程編碼對相關(guān)信源編碼更有效；香農(nóng)編碼、費諾編碼、哈夫曼編碼屬于無失真信源編碼；游程編碼屬于限失真信源編碼。第26頁，課件共50頁，創(chuàng)作于2023年2月第八節(jié)游程編碼、算術(shù)編碼、冗余編碼游程：數(shù)字序列中連續(xù)出現(xiàn)相同符號的一段。二元序列的游程：只有“0”和“1”兩種符號。連“0”這一段稱為“0”游程，它的長度稱為游程長度L(0)；連“1”這一段稱為“1”游程，它的游程長度用L(1)表示。游程編碼①二元獨立序列游程長度概率若規(guī)定二元序列總是從“0”開始。對于隨機序列，游程長度是隨機的其取值可為1,2,3,…，直至無窮。游程長度序列/游程序列：用交替出現(xiàn)的“0”游程和“1”游程長度表示任意二元序列。游程變換：是一種一一對應(yīng)的變換，也是可逆變換。例如：二元序列：000101110010001…，可變換成如下游程序列：31132131第27頁，課件共50頁，創(chuàng)作于2023年2月第八節(jié)游程編碼、算術(shù)編碼、冗余編碼游程變換減弱了原序列符號間的相關(guān)性。游程變換將二元序列變換成了多元序列；這樣就適合于用其他方法，如哈夫曼編碼，進一步壓縮信源，提高通信效率。編碼方法：首先測定“0”游程長度和“1”游程長度的概率分布，即以游程長度為元素，構(gòu)造一個新的信源；對新的信源（游程序列）進行哈夫曼編碼。游程編碼第28頁，課件共50頁，創(chuàng)作于2023年2月第八節(jié)游程編碼、算術(shù)編碼、冗余編碼②二元獨立序列游程長度的熵若二元序列的概率特性已知，由于二元序列與游程變換序列的一一對應(yīng)性，可計算出游程序列的概率特性。令“0”和“1”的概率分別為p0和p1，則“0”游程長度L(0)的概率為

p[L(0)]=p0L(0)－1p1

式中L(0)=1,2,…,在計算p[L(0)]時必然已有“0”出現(xiàn)，否則就不是“0”游程，若下一個符號是“1”，則游程長度為1，其概率是p1=1－p0；若下一個符號為“0”、再下一個符號為“1”，則游程長度為2，其概率將為p0p1

；依此類推。游程編碼第29頁，課件共50頁，創(chuàng)作于2023年2月第八節(jié)游程編碼、算術(shù)編碼、冗余編碼游程編碼游程長度至少是1，理論上，游程長度可以是無窮，但很長的游程實際出現(xiàn)的概率非常小。同理可得“1”游程長度L(1)的概率為：P[L(1)]=p1L(1)-1p0“0”游程長度的熵：第30頁，課件共50頁，創(chuàng)作于2023年2月第八節(jié)游程編碼、算術(shù)編碼、冗余編碼③二元獨立序列的平均游程長度“0”游程序列的平均游程長度同理可得“1”游程長度的熵和平均游程長度游程編碼第31頁，課件共50頁，創(chuàng)作于2023年2月第八節(jié)游程編碼、算術(shù)編碼、冗余編碼游程編碼④二元獨立序列的熵“0”游程序列的熵與“1”游程長度的熵之和除以它們的平均游程長度之和，即為對應(yīng)原二元序列的熵H(X)游程變換后符號熵沒有變。因為游程變換是一一對應(yīng)的可逆變換，所以變換后熵值不變。第32頁，課件共50頁，創(chuàng)作于2023年2月第八節(jié)游程編碼、算術(shù)編碼、冗余編碼游程變換有較好的去相關(guān)效果，因而對游程序列進行哈夫曼編碼可獲得較高的編碼效率。假設(shè)“0”游程長度的哈夫曼編碼效率為η0，“1”游程長度的哈夫曼編碼效率為η1，由編碼效率的定義和式(5.4.9)可得對應(yīng)二元序列的編碼效率（信源熵和信息率之比為編碼效率η=H(X)/R）當“0”游程和“1”游程的編碼效率都很高時，采用游程編碼的效率也很高，至少不會低于較小的那個效率。要想編碼效率盡可能高，應(yīng)盡可能提高熵值較大的游程編碼效率。游程編碼第33頁，課件共50頁，創(chuàng)作于2023年2月第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼算術(shù)編碼不同于哈夫曼碼，它是非分組（非塊）碼。它從全序列出發(fā)，考慮符號之間的關(guān)系來進行編碼。算術(shù)編碼利用了累積概率的概念。算術(shù)碼主要的編碼方法是計算輸入信源符號序列所對應(yīng)的區(qū)間。因為在編碼過程中，每輸入一個符號要進行乘法和加法運算，所以稱此編碼方法為算術(shù)編碼。二元序列的算術(shù)編碼可用于黑白圖像的編碼，例如傳真。第34頁，課件共50頁，創(chuàng)作于2023年2月第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼設(shè)信源符號集A={a1,a2,…,an}，其相應(yīng)概率分布為P(ai)，

P(ai)>0(i=1,2,…,n)信源符號的累積分布函數(shù)為：所得累積分布函數(shù)為每臺級的下界值，則其區(qū)間為[0,1)左閉右開區(qū)間。

F(a1)=0

F(a2)=P(a1)

F(a3)=P(a1)+P(a2)

…當A={0,1}二元信源時：F(0)=0，F(xiàn)(1)=P(0)第35頁，課件共50頁，創(chuàng)作于2023年2月第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼計算二元無記憶信源序列的累積分布函數(shù)初始時：在[0,1)區(qū)間內(nèi)由F(1)劃分成二個子區(qū)間[0,F(1))和[F(1),1)，F(xiàn)(1)=P(0)。子區(qū)間[0,F(1))的寬度為A(0)=P(0)，對應(yīng)于信源符號“0”；子區(qū)間[F(1),1)的寬度為A(1)=P(1)，對應(yīng)于信源符號“1”；若輸入符號序列的第一個符號為s=“0”，落入[0,F(1))區(qū)間，得累積分布函數(shù)F(s=“0”)=F(0)=0；

第36頁，課件共50頁，創(chuàng)作于2023年2月第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼輸入第二個符號為“1”，s=“01”s=“01”所對應(yīng)的區(qū)間是在區(qū)間[0,F(1))中進行分割；符號序列“00”對應(yīng)的區(qū)間寬度為:A(00)=A(0)P(0)=P(0)P(0)=P(00)；對應(yīng)的區(qū)間為[0,F(s=“01”))。符號序列“01”對應(yīng)的區(qū)間寬度為

A(01)=A(0)P(1)=P(0)P(1)=P(01)=A(0)－A(00)；對應(yīng)的區(qū)間為[F(s=“01”),F(1))。累積分布函數(shù)F(s=“01”)=P(00)=P(0)P(0)第37頁，課件共50頁，創(chuàng)作于2023年2月第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼第38頁，課件共50頁，創(chuàng)作于2023年2月第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼

輸入第三個符號為“1”：輸入序列可記做s1=“011”（若第三個符號輸入為“0”，可記做s0=“010”）；現(xiàn)在，輸入序列s1=“011”對應(yīng)的區(qū)間是對區(qū)間[F(s),F(1))進行分割；序列s0=“010”對應(yīng)的區(qū)間寬度為

A(s=“010”)=A(s=“01”)P(0)=A(s)P(0)

其對應(yīng)的區(qū)間為[F(s),F(s)+A(s)P(0))；序列s1=“011”對應(yīng)的區(qū)間寬度為

A(s=“011”)=A(s)P(1)=A(s=“01”)－A(s=“010”)=A(s)－A(s0)

其對應(yīng)的區(qū)間為[F(s)+A(s)P(0),F(1))；符號序列s1=“011”的累積分布函數(shù)為F(s1)=F(s)+A(s)P(0)；若第三個符號輸入為“0”，符號序列s0=“010”的區(qū)間下界值仍為F(s)，得符號序列s0=“010”的累積分布函數(shù)為F(s0)=F(s)。第39頁，課件共50頁，創(chuàng)作于2023年2月第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼歸納當已知前面輸入符號序列為s，若接著再輸入一個符號“0”，序列s0的累積分布函數(shù)為：F(s0)=F(s)對應(yīng)區(qū)間寬度為：A(s0)=A(s)P(0)若接著輸入的一個符號是“1”，序列的累積分布函數(shù)為：F(s1)=F(s)+A(s)P(0)對應(yīng)區(qū)間寬度為：A(s1)=A(s)P(1)=A(s)－A(s0)第40頁，課件共50頁，創(chuàng)作于2023年2月第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼符號序列對應(yīng)的區(qū)間寬度A(s=“0”)=P(0)A(s=“1”)=1－A(s=“0”)=P(1)A(s=“00”)=P(00)=A(0)P(0)=P(0)P(0)A(s=“01”)=A(s=“0”)－A(s=“00”)=P(01)=A(0)P(1)=P(0)P(1)A(s=“10”)=P(10)=A(1)P(0)=P(1)P(0)A(s=“11”)=A(s=“1”)－A(s=“10”)=P(11)=A(s=“1”)P(1)=P(1)P(1)A(s=“010”)=A(s=“01”)P(0)=P(01)P(0)＝P(010)A(s=“011”)=A(s=“01”)-A(s=“010”)=A(s=“01”)P(1)=P(01)P(1)=P(011)

信源符號序列s所對應(yīng)區(qū)間的寬度等于符號序列s的概率P(s)。第41頁，課件共50頁，創(chuàng)作于2023年2月第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼二元信源符號序列的累積分布函數(shù)的遞推公式F(sr)=F(s)+P(s)F(r)(r=0,1)

sr表示已知前面信源符號序列為s，接著再輸入符號為rF(0)=0，F(xiàn)(1)=P(0)F(s0)=F(s)F(s1)=F(s)+P(s)F(1)=F(s)+P(s)P(0)A(sr)=P(sr)=P(s)P(r)(r=0,1)A(s0)=P(s0)=P(s)P(0)A(s1)=P(s1)=P(s)P(1)第42頁，課件共50頁，創(chuàng)作于2023年2月第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼舉例：已輸入二元符號序列為s=“011”，接著再輸入符號為“1”，得序列累積分布函數(shù)為：

F(s1)=F(0111)=F(s=“011”)+P(011)P(0)=F(s=“01”)+P(01)P(0)+P(011)P(0)=F(s=“0”)+P(0)P(0)+P(01)P(0)+P(011)P(0)=0+P(00)+P(010)+P(0110)

對應(yīng)的區(qū)間寬度為

A(s1)=P(s=“011”)P(1)=P(011)P(1)=P(0111)上述整個分析過程可用圖5.6.1描述式(5.6.1)和(5.6.2)是可遞推運算，在實際中，只需兩個存儲器，把P(s)和F(s)存下來，然后，根據(jù)輸入符號和式(5.6.1)、(5.6.2)更新兩個存儲器中的數(shù)值。因此在編碼過程中，每輸入一個符號要進行乘法和加法運算，所以稱為算術(shù)編碼。第43頁，課件共50頁，創(chuàng)作于2023年2月第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼第44頁，課件共50頁，創(chuàng)作于2023年2月第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼

通過關(guān)于信源符號序列的累積分布函數(shù)的計算，把區(qū)間分割成許多小區(qū)間，不同的信源符號序列對應(yīng)不同的區(qū)間為[F(s),F(s)+P(s))?？扇⌒^(qū)間內(nèi)的一點來代表這序列。編碼方法：將符號序列的累積分布函數(shù)寫成二進位的小數(shù)，取小數(shù)點后k位，若后面有尾數(shù)，就進位到第k位，這樣得到的一個數(shù)C，并使k滿足舉例第45頁，課件共50頁，創(chuàng)作于2023年2月第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼編碼效率這樣選取的數(shù)值C，一般根據(jù)二進小數(shù)截去尾數(shù)的影響得

C－F(s)<1/2k，當在l以后沒有尾數(shù)時C=F(s)。

F(s)+1/2k>C而P(s)≥1/2k信源符號序列對應(yīng)區(qū)間的上界為F(s)+P(s)≥F(s)+1/2k>C可見，數(shù)值在區(qū)間[F(s),F(s)+P(s))內(nèi)。而信源符號序列對應(yīng)的不同區(qū)間（左封右開）是不重疊的，所以編得的碼是即時碼。第46頁，課件共50頁，創(chuàng)作于2023年2月第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼算術(shù)編碼的編碼效率很高。當信源符號序列很長時，L很大時，平均碼長接近