第5章-信源編碼

第1頁(yè)2024/3/20DepartmentofElectronicsandInformation,NCUTSongPeng第五章

──────────────

信源編碼技術(shù)5.1最佳變長(zhǎng)編碼5.2編碼的實(shí)現(xiàn)5.3編碼方法簡(jiǎn)介5.7LZ(Lempel-Ziv)碼5.8LZW碼第2頁(yè)2024/3/20編碼的目的香農(nóng)編碼定理雖然指出了理想編碼器的存在性，但是并沒(méi)有給出實(shí)用碼的結(jié)構(gòu)及構(gòu)造方法；編碼理論是為了解決這一問(wèn)題而發(fā)展起來(lái)的科學(xué)理論；編碼的目的是為了優(yōu)化通信系統(tǒng)，使這些指標(biāo)達(dá)到最佳；通信系統(tǒng)的性能指標(biāo)主要是有效性、可靠性、安全性和經(jīng)濟(jì)性，除了經(jīng)濟(jì)性外，這些指標(biāo)是信息論研究的對(duì)象。按不同的編碼目的，編碼分為三類：信源編碼、信道編碼和安全編碼（密碼）。引言第3頁(yè)2024/3/20編碼的目的信源編碼：提高通信有效性為目的的編碼。通過(guò)壓縮信源的冗余度實(shí)現(xiàn)。采用的一般方法是壓縮每個(gè)信源符號(hào)的平均比特?cái)?shù)或信源的碼率。即同樣多的信息用較少的碼率傳送，使單位時(shí)間內(nèi)傳送的平均信息量增加，從而提高通信的有效性。信道編碼：提高信息傳輸?shù)目煽啃詾槟康牡木幋a。通過(guò)增加信源的冗余度實(shí)現(xiàn)。采用的一般方法是增大碼率（帶寬）。與信源編碼正好相反。保密編碼：提高通信系統(tǒng)的安全性為目的的編碼。通過(guò)加密和解密實(shí)現(xiàn)。從信息論的觀點(diǎn)出發(fā)，“加密”可視為增熵的過(guò)程，“解密”可視為減熵的過(guò)程。引言第4頁(yè)2024/3/20信源編碼概述(1)信源編碼的理論基礎(chǔ)信源編碼理論是信息論的一個(gè)重要分支，其理論基礎(chǔ)是信源編碼的兩個(gè)定理。無(wú)失真信源編碼定理：是離散信源/數(shù)字信號(hào)編碼的基礎(chǔ)；限失真信源編碼定理：是連續(xù)信源/模擬信號(hào)編碼的基礎(chǔ)。引言第5頁(yè)2024/3/20信源編碼概述(2)信源編碼的分類根據(jù)信源特性離散信源編碼：獨(dú)立信源編碼，可做到無(wú)失真編碼；連續(xù)信源編碼：獨(dú)立信源編碼，只能做到限失真信源編碼；相關(guān)信源編碼：非獨(dú)立信源編碼。根據(jù)壓縮的特性冗余度壓縮編碼：可逆壓縮，經(jīng)編譯碼后可以無(wú)失真地恢復(fù)。熵壓縮編碼：不可逆壓縮。引言第6頁(yè)2024/3/20信源編碼概述(3)數(shù)據(jù)壓縮概貌引言第7頁(yè)2024/3/205.1最佳變長(zhǎng)編碼

根據(jù)信源編碼理論，將能夠荷載一定信息量且碼字的平均長(zhǎng)度最短、可分離的變長(zhǎng)碼字集合稱為最佳變長(zhǎng)碼。最佳變長(zhǎng)碼編碼的基本原則是：概率大的信源符號(hào)分配短的碼字，概率小的信源符號(hào)分配長(zhǎng)的碼字，從而使平均碼長(zhǎng)最短。具有代表性的變長(zhǎng)編碼方法有香農(nóng)碼、費(fèi)諾碼和哈夫曼碼等。第8頁(yè)2024/3/205.1.1香農(nóng)編碼

設(shè)離散無(wú)記憶信源：二進(jìn)制香農(nóng)碼的編碼步驟如下：將信源符號(hào)按概率從大到小的順序排列，令：p(x1)≥p(x2)≥…≥p(xn)

令P(x1)=0，用Pa(xj)，j=i+1表示第i個(gè)碼字的累加概率，則：確定滿足下列不等式的整數(shù)ki，并令ki為第i個(gè)碼字的長(zhǎng)度－log2

p(xi)≤ki<1－log2

p(xi)

將Pa(xj)用二進(jìn)制表示，并取小數(shù)點(diǎn)后ki

位作為符號(hào)xi的編碼。5.1最佳變長(zhǎng)編碼第9頁(yè)2024/3/205.1.1香農(nóng)編碼[例5.1.1]：有一單符號(hào)離散無(wú)記憶信源：對(duì)信源編二進(jìn)制香農(nóng)碼。其編碼過(guò)程如表5.1.1所示。計(jì)算出給定信源香農(nóng)碼的平均碼長(zhǎng)：若對(duì)上述信源采用等長(zhǎng)編碼，要做到無(wú)失真譯碼，每個(gè)符號(hào)至少要用3個(gè)比特表示。相比較，香農(nóng)編碼對(duì)信源進(jìn)行了壓縮。由離散無(wú)記憶信源熵定義，可計(jì)算出信源上熵為：5.1最佳變長(zhǎng)編碼第10頁(yè)2024/3/205.1.1香農(nóng)編碼[例5.1.1]：對(duì)信源采用香農(nóng)編碼的信息率為：編碼效率為信源熵和信息率之比。則：編碼效率并不是很高。5.1最佳變長(zhǎng)編碼第11頁(yè)2024/3/205.1.2費(fèi)諾編碼將概率按從大到小的順序排列，令：p(x1)≥p(x2)≥…≥p(xn)按編碼進(jìn)制數(shù)將概率分組，使每組概率盡可能接近或相等。如編二進(jìn)制碼就分成兩組，編m進(jìn)制碼就分成m組。給每一組分配一位碼元。將每一分組再按同樣原則劃分，重復(fù)步驟2和3，直至概率不再可分為止。5.1最佳變長(zhǎng)編碼第12頁(yè)2024/3/205.1.2費(fèi)諾編碼[例5.1.2A]：設(shè)有一單符號(hào)離散信源對(duì)信源編二進(jìn)制費(fèi)諾碼。編碼過(guò)程如表5.1.2A。信源的熵為：5.1最佳變長(zhǎng)編碼第13頁(yè)2024/3/20[例5.1.2A]平均碼長(zhǎng)為：對(duì)信源采用費(fèi)諾編碼的信息率為：編碼效率為：本例中費(fèi)諾編碼有較高的編碼效率。費(fèi)諾碼比較適合于每次分組概率都很接近的信源。特別是對(duì)每次分組概率都相等的信源進(jìn)行編碼時(shí)，可達(dá)到理想的編碼效率。5.1.2費(fèi)諾編碼5.1最佳變長(zhǎng)編碼第14頁(yè)2024/3/205.1.2費(fèi)諾編碼[例5.1.2B]：有一單符號(hào)離散無(wú)記憶信源對(duì)該信源編二進(jìn)制費(fèi)諾碼，編碼過(guò)程如表5.1.2B。信源熵為：H(X)=2.75(比特/符號(hào))平均碼長(zhǎng)為：編碼效率為η=1。之所以如此，因?yàn)槊看嗡謨山M的概率恰好相等。5.1最佳變長(zhǎng)編碼第15頁(yè)2024/3/205.1.3哈夫曼編碼(1)將信源符號(hào)按概率從大到小的順序排列，令：p(x1)≥p(x2)≥…≥p(xn)(2)

信源的第一次縮減：給兩個(gè)概率最小的信源符號(hào)p(xn－1)和p(xn)各分配一個(gè)碼元“0”和“1”，將這兩個(gè)信源符號(hào)合并成一個(gè)新符號(hào)，并用這兩個(gè)最小的概率之和作為新符號(hào)的概率，結(jié)果得到一個(gè)只包含(n－1)個(gè)信源符號(hào)的新信源，用S1表示。(3)將縮減信源S1的符號(hào)仍按概率從大到小順序排列，重復(fù)步驟(2)，得到只含(n－2)個(gè)符號(hào)的縮減信源S2。(4)重復(fù)上述步驟，直至縮減信源只剩兩個(gè)符號(hào)為止，此時(shí)所剩兩個(gè)符號(hào)的概率之和必為1。然后從最后一級(jí)縮減信源開(kāi)始，依編碼路徑向前返回，可得各信源符號(hào)所對(duì)應(yīng)的碼字。編碼步驟：5.1最佳變長(zhǎng)編碼第16頁(yè)2024/3/201.二進(jìn)制哈夫曼編碼[例5.1.3]對(duì)以下信源進(jìn)行哈夫曼編碼。在讀取碼字時(shí)，一定要從后向前讀，此時(shí)編出來(lái)的碼字才是可分離的異前置碼。若從前向后讀取碼字，則碼字不可分離。信源符號(hào)ai概率p(ai)碼字Wi碼長(zhǎng)Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104a70.01011145.1最佳變長(zhǎng)編碼第17頁(yè)2024/3/201.二進(jìn)制哈夫曼編碼[例5.1.3]對(duì)以下信源進(jìn)行哈夫曼編碼。0.20 0.200.260.350.390.611.00.190.190.200.260.350.390.180.180.190.200.260.170.170.180.190.150.150.170.100.110.010101010101010.200.190.180.170.150.100.011011000001010011001115.1最佳變長(zhǎng)編碼第18頁(yè)2024/3/201.二進(jìn)制哈夫曼編碼[例5.1.3A]設(shè)單符號(hào)離散無(wú)記憶信源如下，要求對(duì)信源編二進(jìn)制哈夫曼碼。在讀取碼字時(shí)，一定要從后向前讀，此時(shí)編出來(lái)的碼字才是可分離的異前置碼。若從前向后讀取碼字，則碼字不可分離。5.1最佳變長(zhǎng)編碼第19頁(yè)2024/3/201.二進(jìn)制哈夫曼編碼[例5.1.3A]信源熵為：平均碼長(zhǎng)為：編碼效率為：若采用定長(zhǎng)編碼，碼長(zhǎng)K=3，則編碼效率：哈夫曼的編碼效率提高了12.7%。5.1最佳變長(zhǎng)編碼第20頁(yè)2024/3/201.二進(jìn)制哈夫曼編碼

注意：哈夫曼的編法并不惟一。每次對(duì)縮減信源兩個(gè)概率最小的符號(hào)分配“0”和“1”碼元是任意的，所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性，即能得到可分離碼字。不同的碼元分配，得到的具體碼字不同，但碼長(zhǎng)ki不變，平均碼長(zhǎng)也不變，所以沒(méi)有本質(zhì)區(qū)別；縮減信源時(shí)，若合并后的新符號(hào)概率與其他符號(hào)概率相等，從編碼方法上來(lái)說(shuō)，這幾個(gè)符號(hào)的次序可任意排列，編出的碼都是正確的，但得到的碼字不相同。不同的編法得到的碼字長(zhǎng)度ki也不盡相同。5.1最佳變長(zhǎng)編碼第21頁(yè)2024/3/201.二進(jìn)制哈夫曼編碼[例5.1.3B]：?jiǎn)畏?hào)離散無(wú)記憶信源用兩種不同的方法對(duì)其編二進(jìn)制哈夫曼碼。方法一：合并后的新符號(hào)排在其它相同概率符號(hào)的后面。5.1最佳變長(zhǎng)編碼第22頁(yè)2024/3/201.二進(jìn)制哈夫曼編碼[例5.1.3B]：?jiǎn)畏?hào)離散無(wú)記憶信源用兩種不同的方法對(duì)其編二進(jìn)制哈夫曼碼。方法二：合并后的新符號(hào)排在其它相同概率符號(hào)的前面。5.1最佳變長(zhǎng)編碼第23頁(yè)2024/3/201.二進(jìn)制哈夫曼編碼

[例5.1.3B]：?jiǎn)畏?hào)信源編二進(jìn)制哈夫曼碼，編碼效率主要決定于信源熵和平均碼長(zhǎng)之比。對(duì)相同的信源編碼，其熵是一樣的，采用不同的方法，得到的平均碼長(zhǎng)可能不同。平均碼長(zhǎng)越短，編碼效率就越高。方法一的平均碼長(zhǎng)為：方法二的平均碼長(zhǎng)為：可見(jiàn)，本例兩種方法的平均碼長(zhǎng)相同，所以編碼效率相同。5.1最佳變長(zhǎng)編碼第24頁(yè)2024/3/201.二進(jìn)制哈夫曼編碼討論：碼字長(zhǎng)度的方差σ2：長(zhǎng)度ki與平均碼長(zhǎng)之差的平方的數(shù)學(xué)期望，即：方法一碼字長(zhǎng)度方差：方法二碼字長(zhǎng)度方差：哪種方法更好？5.1最佳變長(zhǎng)編碼第25頁(yè)2024/3/201.二進(jìn)制哈夫曼編碼比較：第二種編碼方法的碼長(zhǎng)方差要小許多。第二種編碼方法的碼長(zhǎng)變化較小，比較接近于平均碼長(zhǎng)。第一種方法編出的5個(gè)碼字有4種不同的碼長(zhǎng)；第二種方法編出的碼長(zhǎng)只有兩種不同的碼長(zhǎng)；第二種編碼方法更簡(jiǎn)單、更容易實(shí)現(xiàn)，所以更好。結(jié)論：在哈夫曼編碼過(guò)程中，對(duì)縮減信源符號(hào)按概率由大到小的順序重新排列時(shí)，應(yīng)使合并后的新符號(hào)盡可能排在靠前的位置，這樣可使合并后的新符號(hào)重復(fù)編碼次數(shù)減少，使短碼得到充分利用。哈夫曼碼是用概率匹配方法進(jìn)行信源編碼。哈夫曼碼的編碼方法保證了概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的符號(hào)對(duì)應(yīng)于長(zhǎng)碼，充分利用了短碼；縮減信源的最后二個(gè)碼字總是最后一位不同，從而保證了哈夫曼碼是即時(shí)碼。5.1最佳變長(zhǎng)編碼第26頁(yè)2024/3/202.m進(jìn)制哈夫曼編碼(1)“全樹(shù)”概念定義：碼樹(shù)圖中每個(gè)中間節(jié)點(diǎn)后續(xù)的枝數(shù)為m時(shí)稱為全樹(shù)；若有些節(jié)點(diǎn)的后續(xù)枝數(shù)不足m，就稱為非全樹(shù)。二進(jìn)制碼不存在非全樹(shù)的情況，因?yàn)楹罄m(xù)枝數(shù)是1時(shí)，這個(gè)枝就可以去掉使碼字長(zhǎng)度縮短。m進(jìn)制編碼：若所有碼字構(gòu)成全樹(shù)，可分離的碼字?jǐn)?shù)（信源個(gè)數(shù)）必為n=m+q(m－1)。q為信源縮減次數(shù)。若信源所含的符號(hào)數(shù)n不能構(gòu)成m進(jìn)制全樹(shù)，必須增加s個(gè)不用的碼字形成全樹(shù)。顯然s<m－1，若s=m－1，意味著某個(gè)中間節(jié)點(diǎn)之后只有一個(gè)分枝，為了節(jié)約碼長(zhǎng)，這一分枝可以省略。5.1最佳變長(zhǎng)編碼第27頁(yè)2024/3/202.m進(jìn)制哈夫曼編碼(1)“全樹(shù)”概念在編m進(jìn)制哈夫曼碼時(shí)為了使平均碼長(zhǎng)最短，必須使最后一步縮減信源有m個(gè)信源符號(hào)。非全樹(shù)時(shí)，有s個(gè)碼字不用：第一次對(duì)最小概率符號(hào)分配碼元時(shí)就只取(m－s)個(gè)，分別配以0,1,…,m-s-1，把這些符號(hào)的概率相加作為一個(gè)新符號(hào)的概率，與其它符號(hào)一起重新排列。以后每次就可以取m個(gè)符號(hào)，分別配以0,1,…,m-1；如此下去，直至所有概率相加得1為止，即得到各符號(hào)的m進(jìn)制碼字。5.1最佳變長(zhǎng)編碼第28頁(yè)2024/3/202.m進(jìn)制哈夫曼編碼(2)舉例對(duì)如下單符號(hào)離散無(wú)記憶信源編三進(jìn)制哈夫曼碼。已知：m=3，n=8n=m+q(m－1)=8，令q=3，則s=9－n=9－8=1所以第一次取m－s=2個(gè)符號(hào)進(jìn)行編碼。5.1最佳變長(zhǎng)編碼第29頁(yè)2024/3/202.m進(jìn)制哈夫曼編碼(2)舉例5.1最佳變長(zhǎng)編碼第30頁(yè)2024/3/202.m進(jìn)制哈夫曼編碼(2)舉例平均碼長(zhǎng)為：信息率為：編碼效率為：可見(jiàn)：哈夫曼的編碼效率相當(dāng)高，對(duì)編碼器的要求也簡(jiǎn)單得多。5.1最佳變長(zhǎng)編碼第31頁(yè)2024/3/202.m進(jìn)制哈夫曼編碼(3)結(jié)論香農(nóng)碼、費(fèi)諾碼、哈夫曼碼都考慮了信源的統(tǒng)計(jì)特性，使經(jīng)常出現(xiàn)的信源符號(hào)對(duì)應(yīng)較短的碼字，使信源的平均碼長(zhǎng)縮短，從而實(shí)現(xiàn)了對(duì)信源的壓縮；香農(nóng)碼有系統(tǒng)的、惟一的編碼方法，但在很多情況下編碼效率不是很高;費(fèi)諾碼和哈夫曼碼的編碼方法都不惟一；費(fèi)諾碼比較適合于對(duì)分組概率相等或接近的信源編碼，費(fèi)諾碼也可以編m進(jìn)制碼，但m越大，信源的符號(hào)數(shù)越多，可能的編碼方案就越多，編碼過(guò)程就越復(fù)雜，有時(shí)短碼未必能得到充分利用；哈夫曼碼對(duì)信源的統(tǒng)計(jì)特性沒(méi)有特殊要求，編碼效率比較高，對(duì)編碼設(shè)備的要求也比較簡(jiǎn)單，因此綜合性能優(yōu)于香農(nóng)碼和費(fèi)諾碼。5.1最佳變長(zhǎng)編碼第32頁(yè)2024/3/205.2編碼的實(shí)現(xiàn)前面介紹了幾種變長(zhǎng)編碼的方法。變長(zhǎng)碼可以有效提高編碼效率，是因?yàn)樽冮L(zhǎng)碼利用了信源統(tǒng)計(jì)冗余指導(dǎo)編碼的結(jié)果。實(shí)際上，上述幾種變長(zhǎng)編碼只是產(chǎn)生編碼使用的碼表，并不是真正意義上的編碼實(shí)現(xiàn)。為了實(shí)現(xiàn)信息傳輸，信源編碼產(chǎn)生的碼流傳輸?shù)叫潘拗笆紫纫M(jìn)行譯碼，即按照先后順序再現(xiàn)或者重建信源發(fā)送的消息符號(hào)。對(duì)于譯碼器而言，必須知道信源編碼使用的碼表和每個(gè)碼字對(duì)應(yīng)的長(zhǎng)度Ki等相關(guān)信息，才能夠?qū)崿F(xiàn)正確譯碼。

第33頁(yè)2024/3/205.2編碼的實(shí)現(xiàn)對(duì)于給定的信源，根據(jù)信源統(tǒng)計(jì)特性進(jìn)行編碼，采用上述變長(zhǎng)碼編碼方法產(chǎn)生碼表，然后再對(duì)信源輸出序列進(jìn)行編碼，這種編碼系統(tǒng)組成如圖5.1所示。圖5.1信源變長(zhǎng)碼編碼原理框圖第34頁(yè)2024/3/205.2編碼的實(shí)現(xiàn)分析給定信源統(tǒng)計(jì)特性，得到信源統(tǒng)計(jì)規(guī)律；根據(jù)統(tǒng)計(jì)特性，碼表產(chǎn)生器進(jìn)行編碼，得到每個(gè)信源符號(hào)或者符號(hào)序列對(duì)應(yīng)的碼字和碼長(zhǎng)，即產(chǎn)生碼表；將序列符號(hào)、序列長(zhǎng)度、碼字及碼長(zhǎng)等信息按照約定規(guī)則經(jīng)過(guò)信道傳輸給譯碼器；信源編碼器根據(jù)碼表產(chǎn)生器產(chǎn)生的碼表，對(duì)給定信源輸出符號(hào)序列按照先后順序進(jìn)行編碼，產(chǎn)生碼流(碼字序列)，并經(jīng)過(guò)信道將碼流傳輸給譯碼器；信源譯碼器根據(jù)接收到的序列符號(hào)、序列長(zhǎng)度、碼字和碼長(zhǎng)，對(duì)接收到的碼流進(jìn)行譯碼，再現(xiàn)或者重建信源發(fā)送的消息。信源編碼的具體步驟如下：第35頁(yè)2024/3/205.2編碼的實(shí)現(xiàn)序列符號(hào)、序列長(zhǎng)度、碼字和碼長(zhǎng)這些輔助信息的傳輸增加了額外的信息量。假設(shè)信源的熵為H(X)，實(shí)際編碼的平均碼長(zhǎng)為，信源輸出符號(hào)序列個(gè)數(shù)為M，輔助信息長(zhǎng)度為Ka，那么實(shí)際編碼效率為理想的編碼效率為實(shí)際中很少使用這種編碼實(shí)現(xiàn)方案。實(shí)際信源編碼框圖如圖5.2所示。圖5.2實(shí)際信源編碼框圖第36頁(yè)2024/3/205.2編碼的實(shí)現(xiàn)離散無(wú)記憶信源：假設(shè)碼表產(chǎn)生使用的編碼概率空間(也稱為碼表概率空間)為每個(gè)消息符號(hào)對(duì)應(yīng)碼字的長(zhǎng)度為Ki。對(duì)于給定的離散無(wú)記憶信源X，實(shí)際的概率空間為如果采用碼表概率空間編碼，那么信源X編碼的實(shí)際平均碼長(zhǎng)為第37頁(yè)2024/3/205.2編碼的實(shí)現(xiàn)只有當(dāng)兩種統(tǒng)計(jì)特性相近時(shí)，信源編碼的平均碼長(zhǎng)才滿足其中M為信源的輸出符號(hào)個(gè)數(shù)。所以，采用約定碼表進(jìn)行編碼是一種有效的編碼方法。反之，編碼效率下降。例:采用表5.5的碼表對(duì)給定信源進(jìn)行編碼，信源輸出數(shù)據(jù)長(zhǎng)度M=1000，5種信源符號(hào)的頻次如表5.6所示，根據(jù)頻次可以計(jì)算各個(gè)符號(hào)出現(xiàn)的概率。第38頁(yè)2024/3/205.2編碼的實(shí)現(xiàn)實(shí)際編碼的平均碼長(zhǎng)為比特/符號(hào)根據(jù)統(tǒng)計(jì)概率，計(jì)算出給定信源的熵為

H(X)=2.182比特/符號(hào)實(shí)際編碼效率為第39頁(yè)2024/3/205.2編碼的實(shí)現(xiàn)改變編碼使用的碼表，采用表5.4的碼表進(jìn)行編碼。比特/符號(hào)實(shí)際編碼效率為比較兩者可以看出，由于給定信源的統(tǒng)計(jì)規(guī)律與產(chǎn)生碼表使用的統(tǒng)計(jì)規(guī)律不相同，采用兩種碼表編碼產(chǎn)生的平均碼長(zhǎng)、編碼效率各不相同。由于碼2的碼方差小于碼1的碼方差，因此根據(jù)碼2編碼得到平均碼長(zhǎng)和編碼效率都好于碼1。平均碼長(zhǎng)為第40頁(yè)2024/3/205.2編碼的實(shí)現(xiàn)如果直接根據(jù)信源統(tǒng)計(jì)特性進(jìn)行哈夫曼編碼，則平均碼長(zhǎng)為比特/符號(hào)編碼效率為顯然，相對(duì)于直接對(duì)給定信源進(jìn)行編碼的效率η，采用給定碼表對(duì)給定信源進(jìn)行編碼的編碼效率η′(比如上述的η1、η2)有所降低，即滿足

η≥η′但是η的計(jì)算沒(méi)有考慮附加信息的影響。第41頁(yè)2024/3/205.3編碼方法簡(jiǎn)介5.3.1游程編碼1.游程編碼對(duì)象和性質(zhì)香農(nóng)編碼、費(fèi)諾編碼、哈夫曼編碼主要是針對(duì)無(wú)記憶信源。當(dāng)信源有記憶時(shí)上述編碼效率不高；游程編碼對(duì)相關(guān)信源編碼更有效；香農(nóng)編碼、費(fèi)諾編碼、哈夫曼編碼屬于無(wú)失真信源編碼；游程編碼屬于限失真信源編碼。第42頁(yè)2024/3/202.游程編碼的定義

游程：數(shù)字序列中連續(xù)出現(xiàn)相同符號(hào)的一段。二元序列的游程：只有“0”和“1”兩種符號(hào)。連“0”這一段稱為“0”游程，它的長(zhǎng)度稱為游程長(zhǎng)度L(0)；連“1”這一段稱為“1”游程，它的游程長(zhǎng)度用L(1)表示。游程編碼第43頁(yè)2024/3/203.二元獨(dú)立序列(1)基本概念若規(guī)定二元序列總是從“0”開(kāi)始，第一個(gè)游程是“0”游程，則第二個(gè)游程必為“1”游程，第三個(gè)又是“0”游程……。對(duì)于隨機(jī)序列，游程長(zhǎng)度是隨機(jī)的，其取值可為1,2,3,…，直至無(wú)窮。游程長(zhǎng)度序列

（游程序列）：用交替出現(xiàn)的“0”游程和“1”游程長(zhǎng)度表示任意二元序列。游程變換：是一種一一對(duì)應(yīng)的變換，也是可逆變換。例如：二元序列：000101110010001…

可變換成如下游程序列：31132131游程變換減弱了原序列符號(hào)間的相關(guān)性。游程編碼第44頁(yè)2024/3/203.二元獨(dú)立序列(1)基本概念

游程變換將二元序列變換成了多元序列；這樣就適合于用其他方法，如哈夫曼編碼，進(jìn)一步壓縮信源，提高通信效率。

編碼方法首先測(cè)定“0”游程長(zhǎng)度和“1”游程長(zhǎng)度的概率分布，即以游程長(zhǎng)度為元素，構(gòu)造一個(gè)新的信源；對(duì)新的信源（游程序列）進(jìn)行哈夫曼編碼。多元序列也可以變換成游程序列，如m元序列可有m種游程。但是變換成游程序列時(shí)，需要增加標(biāo)志位才能區(qū)分游程序列中的“長(zhǎng)度”是m種游程中的哪一個(gè)的長(zhǎng)度，否則，變換就不可逆。這樣，增加的標(biāo)志位可能會(huì)抵消壓縮編碼得到的好處。所以，對(duì)多元序列進(jìn)行游程變換的意義不大。游程編碼第45頁(yè)2024/3/203.二元獨(dú)立序列(2)二元獨(dú)立序列游程長(zhǎng)度的概率和熵若二元序列的概率特性已知，由于二元序列與游程變換序列的一一對(duì)應(yīng)性，可計(jì)算出游程序列的概率特性。令“0”和“1”的概率分別為p0和p1，則“0”游程長(zhǎng)度L(0)的概率為：p[L(0)]=p0L(0)－1p1

式中L(0)=1,2,…

在計(jì)算p[L(0)]時(shí)必然已有“0”出現(xiàn)，否則就不是“0”游程，若下一個(gè)符號(hào)是“1”，則游程長(zhǎng)度為1，其概率是p1=1－p0；若下一個(gè)符號(hào)為“0”、再下一個(gè)符號(hào)為“1”，則游程長(zhǎng)度為2，其概率將為p0p1

；依此類推。游程編碼第46頁(yè)2024/3/203.二元獨(dú)立序列(2)二元獨(dú)立序列游程長(zhǎng)度的概率和熵游程長(zhǎng)度至少是1，理論上，游程長(zhǎng)度可以是無(wú)窮，但很長(zhǎng)的游程實(shí)際出現(xiàn)的概率非常小。同理可得“1”游程長(zhǎng)度L(1)的概率為：P[L(1)]=p1L(1)－1p0游程編碼第47頁(yè)2024/3/203.二元獨(dú)立序列(2)二元獨(dú)立序列游程長(zhǎng)度的概率和熵“0”游程長(zhǎng)度的熵：游程編碼第48頁(yè)2024/3/203.二元獨(dú)立序列(3)二元獨(dú)立序列的平均游程長(zhǎng)度“0”游程序列的平均游程長(zhǎng)度：同理可得“1”游程長(zhǎng)度的熵和平均游程長(zhǎng)度：游程編碼第49頁(yè)2024/3/203.二元獨(dú)立序列(4)二元獨(dú)立序列的熵“0”游程序列的熵與“1”游程序列的熵之和除以它們的平均游程長(zhǎng)度之和，即為游程變換后的熵H(X)游程變換后符號(hào)熵沒(méi)有變。因?yàn)橛纬套儞Q是一一對(duì)應(yīng)的可逆變換，所以變換后熵值不變，這也說(shuō)明變換后的游程序列是獨(dú)立序列。對(duì)于有相關(guān)性的二元序列，也可以證明變換后的游程序列是獨(dú)立序列，并且也有如下結(jié)論：但此時(shí)H[L(0)]，H[L(1)]，l0和l1的具體表達(dá)形式不同，它們是相關(guān)符號(hào)的聯(lián)合概率和條件概率的函數(shù)。游程編碼第50頁(yè)2024/3/204.游程編碼的效率游程變換有較好的去相關(guān)效果，因而對(duì)游程序列進(jìn)行哈夫曼編碼可獲得較高的編碼效率。假設(shè)“0”游程長(zhǎng)度的哈夫曼編碼效率為η0，“1”游程長(zhǎng)度的哈夫曼編碼效率為η1，由編碼效率的定義和下式可得對(duì)應(yīng)二元序列的編碼效率（信源熵和信息率之比為編碼效率η=H(X)/R）當(dāng)“0”游程和“1”游程的編碼效率都很高時(shí)，采用游程編碼的效率也很高，至少不會(huì)低于較小的那個(gè)效率。要想編碼效率盡可能高，應(yīng)盡可能提高熵值較大的游程編碼效率。游程編碼第51頁(yè)2024/3/205.長(zhǎng)碼的截?cái)嗵幚矸椒ɡ碚撋?，游程長(zhǎng)度可從1到無(wú)窮，要建立游程長(zhǎng)度和碼字之間的一一對(duì)應(yīng)的碼表較困難。一般情況下，游程越長(zhǎng)，出現(xiàn)的概率越??；當(dāng)游程長(zhǎng)度趨向于無(wú)窮時(shí)，出現(xiàn)的概率也趨于0。按照哈夫曼編碼規(guī)則，概率越小，碼字越長(zhǎng)。但小概率的碼字對(duì)平均碼長(zhǎng)影響較小。所以在實(shí)際應(yīng)用時(shí)，常對(duì)長(zhǎng)碼采用截?cái)嗵幚淼姆椒?。游程編碼第52頁(yè)2024/3/201.算術(shù)編碼的特點(diǎn)及應(yīng)用算術(shù)編碼不同于哈夫曼碼，它是非分組（非塊）碼。它從全序列出發(fā)，考慮符號(hào)之間的關(guān)系進(jìn)行編碼。算術(shù)編碼利用了累積概率的概念。算術(shù)碼主要的編碼方法是計(jì)算輸入信源符號(hào)序列所對(duì)應(yīng)的區(qū)間。因?yàn)樵诰幋a過(guò)程中，每輸入一個(gè)符號(hào)要進(jìn)行乘法和加法運(yùn)算，所以稱此編碼方法為算術(shù)編碼。二元序列的算術(shù)編碼可用于黑白圖像的編碼，例如傳真。5.3.2算術(shù)編碼第53頁(yè)2024/3/202.累積分布函數(shù)F(s)及對(duì)應(yīng)的區(qū)間設(shè)信源符號(hào)集A={a1,a2,…,an}，其相應(yīng)概率分布為P(ai)，P(ai)>0(i=1,2,…,n)信源符號(hào)的累積分布函數(shù)為：所得累積分布函數(shù)為每臺(tái)級(jí)的下界值，則其區(qū)間為[0,1)左閉右開(kāi)區(qū)間。

F(a1)=0

F(a2)=P(a1)

F(a3)=P(a1)+P(a2)…當(dāng)A={0,1}二元信源時(shí)：F(0)=0F(1)=P(0)算術(shù)編碼第54頁(yè)2024/3/202.累積分布函數(shù)F(s)及對(duì)應(yīng)的區(qū)間

計(jì)算二元無(wú)記憶信源序列的累積分布函數(shù)初始時(shí)：在[0,1)區(qū)間內(nèi)由F(1)劃分成二個(gè)子區(qū)間[0,F(1))和[F(1),1)，F(xiàn)(1)=P(0)。

子區(qū)間[0,F(1))的寬度為：A(0)=P(0)，對(duì)應(yīng)于信源符號(hào)“0”；子區(qū)間[F(1),1)的寬度為：A(1)=P(1)，對(duì)應(yīng)于信源符號(hào)“1”；若輸入符號(hào)序列的第一個(gè)符號(hào)為

s=“0”，落入[0,F(1))區(qū)間，得累積分布函數(shù)

F(s=“0”)=F(0)=0；圖示算術(shù)編碼第55頁(yè)2024/3/202.累積分布函數(shù)F(s)及對(duì)應(yīng)的區(qū)間

計(jì)算二元無(wú)記憶信源序列的累積分布函數(shù)輸入第二個(gè)符號(hào)為“1”，s=“01”s=“01”所對(duì)應(yīng)的區(qū)間是在區(qū)間[0,F(1))中進(jìn)行分割；符號(hào)序列“00”對(duì)應(yīng)的區(qū)間寬度為：

A(00)=A(0)P(0)=P(0)P(0)=P(00)

對(duì)應(yīng)的區(qū)間為：[0,F(s=“01”))

符號(hào)序列“01”對(duì)應(yīng)的區(qū)間寬度為：

A(01)=A(0)P(1)=P(0)P(1)=P(01)

對(duì)應(yīng)的區(qū)間為：[F(s=“01”),F(1))

累積分布函數(shù)：F(s=“01”)=P(0)P(0)=P(00)圖示算術(shù)編碼第56頁(yè)2024/3/202.累積分布函數(shù)F(s)及對(duì)應(yīng)的區(qū)間

計(jì)算二元無(wú)記憶信源序列的累積分布函數(shù)輸入第三個(gè)符號(hào)為“1”：輸入序列可記做s1=“011”，對(duì)應(yīng)的區(qū)間是對(duì)區(qū)間[F(s),F(1))進(jìn)行分割；序列s0=“010”對(duì)應(yīng)的區(qū)間寬度為：

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

P(0)=A(s)

P(0)

其對(duì)應(yīng)的區(qū)間為：[F(s),F(s)+A(s)

P(0))

序列s1=“011”對(duì)應(yīng)的區(qū)間寬度為：A(s=“011”)=A(s)

P(1)

其對(duì)應(yīng)的區(qū)間為：[F(s)+A(s)

P(0),F(1))

符號(hào)序列s1=“011”的累積分布函數(shù)為：F(s1)=F(s)+A(s)

P(0)

若第三個(gè)符號(hào)輸入為“0”，符號(hào)序列s0=“010”的區(qū)間下界值仍為F(s)，得符號(hào)序列s0=“010”的累積分布函數(shù)為F(s0)=F(s)。圖示算術(shù)編碼第57頁(yè)2024/3/202.累積分布函數(shù)F(s)及對(duì)應(yīng)的區(qū)間

計(jì)算二元無(wú)記憶信源序列的累積分布函數(shù)歸納當(dāng)已知前面輸入符號(hào)序列為s，若接著再輸入一個(gè)符號(hào)“0”，序列s0的累積分布函數(shù)為：F(s0)=F(s)

對(duì)應(yīng)區(qū)間寬度為：A(s0)=A(s)

P(0)

若接著輸入的一個(gè)符號(hào)是“1”，序列的累積分布函數(shù)為：F(s1)=F(s)+A(s)

P(0)

對(duì)應(yīng)區(qū)間寬度為：A(s1)=A(s)

P(1)圖示算術(shù)編碼第58頁(yè)2024/3/202.累積分布函數(shù)F(s)及對(duì)應(yīng)的區(qū)間

計(jì)算二元無(wú)記憶信源序列的累積分布函數(shù)歸納符號(hào)序列對(duì)應(yīng)的區(qū)間寬度

A(s=“0”)=P(0)A(s=“1”)=1－A(0)=P(1)A(s=“00”)=P(00)=A(0)P(0)=P(0)P(0)A(s=“01”)=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”)=P(11)=A(1)P(1)=P(1)P(1)A(s=“010”)=A(01)P(0)=P(01)P(0)＝P(010)A(s=“011”)=A(01)P(1)=P(01)P(1)=P(011)

信源符號(hào)序列s所對(duì)應(yīng)區(qū)間的寬度等于符號(hào)序列s的概率P(s)。算術(shù)編碼第59頁(yè)2024/3/203.信源序列累積分布函數(shù)的遞推公式算術(shù)編碼二元信源符號(hào)序列的累積分布函數(shù)的遞推公式F(sr)=F(s)+P(s)

F(r)(r=0,1)sr表示已知前面信源符號(hào)序列為s，接著再輸入符號(hào)為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)第60頁(yè)2024/3/20例1：已輸入二元符號(hào)序列為s=“011”，接著再輸入符號(hào)為“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)

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

A(s1)=P(s=“011”)

P(1)=P(011)P(1)=P(0111)F(s1)=F(s)+P(s)

P(0)A(s1)=P(s1)=P(s)

P(1)3.信源序列累積分布函數(shù)的遞推公式圖示算術(shù)編碼第61頁(yè)2024/3/20上述整個(gè)分析過(guò)程可用下圖描述3.信源序列累積分布函數(shù)的遞推公式圖示返回算術(shù)編碼第62頁(yè)2024/3/20在實(shí)際中，只需兩個(gè)存儲(chǔ)器，把P(s)和F(s)存下來(lái)，然后，根據(jù)輸入符號(hào)和遞推公式更新兩個(gè)存儲(chǔ)器中的數(shù)值。因此在編碼過(guò)程中，每輸入一個(gè)符號(hào)要進(jìn)行乘法和加法運(yùn)算，所以稱為算術(shù)編碼。遞推公式如下：F(sr)=F(s)+P(s)

F(r)(r=0,1)A(sr)=P(sr)=P(s)

P(r)(r=0,1)3.信源序列累積分布函數(shù)的遞推公式算術(shù)編碼第63頁(yè)2024/3/20

通過(guò)關(guān)于信源符號(hào)序列的累積分布函數(shù)的計(jì)算，把區(qū)間分割成許多小區(qū)間，不同的信源符號(hào)序列對(duì)應(yīng)不同的區(qū)間。可取小區(qū)間內(nèi)的一點(diǎn)來(lái)代表這序列。編碼方法：將符號(hào)序列的累積分布函數(shù)寫(xiě)成二進(jìn)位的小數(shù)，取小數(shù)點(diǎn)后k位，若后面有尾數(shù)，就進(jìn)位到第k位，這樣得到的一個(gè)數(shù)C，并使k滿足：舉例：4.算術(shù)編碼方法算術(shù)編碼第64頁(yè)2024/3/20

編碼效率算術(shù)編碼的編碼效率很高。當(dāng)信源符號(hào)序列很長(zhǎng)時(shí)，L很大時(shí)，平均碼長(zhǎng)接近信源的熵。4.算術(shù)編碼方法算術(shù)編碼第65頁(yè)2024/3/20譯碼就是一系列比較過(guò)程，每一步比較C－F(s)與P(s)P(0)。

F(s0)=F(s)F(s1)=F(s)+P(s)

P(0)s—前面已譯出的序列串

P(s)—序列串s對(duì)應(yīng)的寬度F(s)是序列串s的累積分布函數(shù)，即為s對(duì)應(yīng)區(qū)間的下界；P(s)P(0)是此區(qū)間內(nèi)下一個(gè)輸入為符號(hào)“0”所占的子區(qū)間寬度；若C－F(s)<P(s)P(0)則譯輸出符號(hào)為“0”；若C－F(s)>P(s)P(0)則譯輸出符號(hào)為“1”。5.算術(shù)編碼的譯碼算術(shù)編碼第66頁(yè)2024/3/205.算術(shù)編碼的譯碼算術(shù)編碼

例2

設(shè)二元獨(dú)立信源求信源序列S=1010的算術(shù)編碼。信源序列1010算術(shù)編碼的相關(guān)數(shù)據(jù)如下表所示。解：信源符號(hào)的積累概率F(0)＝0；F(1)＝0.25,序列F(S)p(S)L序列碼字?01010.010.1111100.010.001130101010.0100110.001001301110100.0100110.00001001501010第67頁(yè)2024/3/205.算術(shù)編碼的譯碼算術(shù)編碼信源序列1010算術(shù)編碼的過(guò)程如下。（1）設(shè)（2）輸入信源序列的第一個(gè)符號(hào)1：

（3）輸入信源序列的第二個(gè)符號(hào)0：

（4）輸入信源序列的第三個(gè)符號(hào)1：

（5）輸入信源序列的第四個(gè)符號(hào)0：

第68頁(yè)2024/3/205.算術(shù)編碼的譯碼算術(shù)編碼信源序列1010的算術(shù)編碼圖解序列F(S)p(S)L序列碼字?01010.010.1111100.010.001130101010.0100110.001001301110100.0100110.00001001501010第69頁(yè)2024/3/205.算術(shù)編碼的譯碼算術(shù)編碼

例3

離散無(wú)記憶信源X的概率空間為信源輸出符號(hào)序列{a2a3a1a2}，描述算術(shù)編碼實(shí)現(xiàn)的過(guò)程。

(2)對(duì)第二個(gè)符號(hào)x2=a3進(jìn)行編碼，得到

C2=C1+A1P3=0.5+0.25×0.75=0.6875

A2=A1p3=0.25×0.125=0.03125解:首先計(jì)算條件累計(jì)概率P3=p1+p2=0.5+0.25=0.75P4=p1+p2+p3=0.5+0.25+0.125=0.875

P1=0P2=p1=0.5令C0=0（），A0=1（）。

(1)對(duì)第一個(gè)符號(hào)x1=a2進(jìn)行編碼，得到

C1=C0+A0P2=P2=0.5A1=A0p2=p2=0.25第70頁(yè)2024/3/205.算術(shù)編碼的譯碼算術(shù)編碼(6)因?yàn)镃4=0.10110010，

取小數(shù)點(diǎn)后面8位二進(jìn)制數(shù)據(jù)作為輸出碼字。(3)對(duì)第三個(gè)符號(hào)x3=a1進(jìn)行編碼，得到

C3=C2+A2P1=0.6875+0.03125×0=0.6875

A3=A2p1=0.03125×0.5=0.015625(5)求碼長(zhǎng)：(4)對(duì)第三個(gè)符號(hào)x4=a2進(jìn)行編碼，得到

C4=C3+A3P2=0.6875+0.015625×0.5=0.6953125=(0.10110010)2

A4=A3p2=0.015625×0.25=0.00390625

W=10110010

整個(gè)編碼過(guò)程用下圖表示。第71頁(yè)2024/3/205.算術(shù)編碼的譯碼算術(shù)編碼譯碼：(1)010.50.750.875a1a2a3a4譯為a2；(2)譯為a3；用符號(hào)a2對(duì)應(yīng)區(qū)間的長(zhǎng)度去除碼字與符號(hào)a2的左端點(diǎn)值的差，即(3)譯為a1；用符號(hào)a3對(duì)應(yīng)區(qū)間的長(zhǎng)度去除碼字與符號(hào)a3的左端點(diǎn)值的差，即(4)譯為a2；用符號(hào)a1對(duì)應(yīng)區(qū)間的長(zhǎng)度去除碼字與符號(hào)a1的左端點(diǎn)值的差，即碼字10110010（0.6953125）對(duì)應(yīng)的序列為a2

a3a1a2。第72頁(yè)2024/3/20例4：有四個(gè)符號(hào)a，b，c，d構(gòu)成簡(jiǎn)單序列S＝abda，各符號(hào)及其對(duì)應(yīng)概率如下表，算術(shù)編解碼過(guò)程如下：5.算術(shù)編碼的譯碼算術(shù)編碼符號(hào)符號(hào)概率pi符號(hào)累積概率Pja0.100(1/2)0.000b0.010(1/4)0.100c0.001(1/8)0.110d0.001(1/8)0.111設(shè)起始狀態(tài)為空序列?，則A(?)＝1，C(?)＝0。第73頁(yè)2024/3/205.算術(shù)編碼的譯碼算術(shù)編碼L=7，C(abda)即為編碼后的碼字0101110。

第74頁(yè)2024/3/205.算術(shù)編碼的譯碼算術(shù)編碼譯碼C(abda)=0.010111<0.1

[0，0.1]，第一個(gè)符號(hào)為a。

放大至[0,1](×pa-1)：C(abda)×21＝0.10111

[0.1，0.110]，第二個(gè)符號(hào)為b。去掉累積概率Pb：0.10111-0.1=0.00111放大至[0，1](×pb-1)：0.00111×22=0.111

[0.111，1]，第三個(gè)符號(hào)為d。去掉累積概率Pd：0.111-0.111=0放大至[0，1](×pd-1)：0×24＝0

[0，0.1]，第四個(gè)符號(hào)為a。第75頁(yè)2024/3/205.算術(shù)編碼的譯碼算術(shù)編碼A(

)A(a)abcdA(a,b)abcdabcdA(a,b,d)C(

)0(Pa)pa

PbpbPcpcPdpd1C(0)C(a,b,d)C(a,b)算術(shù)編碼過(guò)程第76頁(yè)2024/3/20例5：設(shè)二元無(wú)記憶信源S={0,1}，其P(0)=1/4，P(1)=3/4。對(duì)二元序列11111100做算術(shù)編碼。[解]：P(s=11111100)=P2(0)P6(1)=(1/4)2(3/4)6F(sr)=F(s)+P(s)

F(r)F(s0)=F(s)F(s1)=F(s)+P(s)

F(1)=F(s)+P(s)

P(0)F(s)=P(0)+P(1)P(0)+P(1)2P(0)+P(1)3P(0)+P(1)4P(0)+P(1)5P(0)=0.82202=0.110100100111得C＝0.1101010得s的碼字為1101010。編碼效率：5.算術(shù)編碼的譯碼算術(shù)編碼第77頁(yè)2024/3/20舉例：5.算術(shù)編碼的譯碼算術(shù)編碼第78頁(yè)2024/3/205.4變換編碼為了提高編碼效率，同時(shí)降低編碼復(fù)雜度，可以對(duì)信源輸出的數(shù)據(jù)進(jìn)行變換，以去除數(shù)據(jù)之間的相關(guān)性，即將數(shù)據(jù)之間的相關(guān)冗余變換為系數(shù)之間的統(tǒng)計(jì)冗余。由于變換后的系數(shù)相關(guān)性減弱，因此可以使用簡(jiǎn)單編碼算法實(shí)現(xiàn)高效率的數(shù)據(jù)壓縮。正交變換可以保持熵的不變性。如果變換后的系數(shù)是整型的，則不會(huì)損失任何信息。但是一般情況下，變換后的系數(shù)是浮點(diǎn)的，就需要對(duì)系數(shù)進(jìn)行量化，得到整型系數(shù)，然后再進(jìn)行編碼。變換的目是為了去除信源輸出數(shù)據(jù)之間的相關(guān)性，或者說(shuō)是將數(shù)據(jù)之間的相關(guān)冗余映射為系數(shù)之間的統(tǒng)計(jì)冗余，從而降低系統(tǒng)編碼復(fù)雜度，提高編碼效率。第79頁(yè)2024/3/205.4.1變換的基本原理變換編碼設(shè)信源輸出一個(gè)一維消息U＝(u1，u2，…，un)，經(jīng)變換后輸出為X＝(x1，x2，…，xn)，故有：X＝PU

由正交性

AT

A＝A－1A＝I，則有：

U＝P

－1X＝P

TX

式中：

P——實(shí)正交變換矩陣；

P

T——

矩陣P的轉(zhuǎn)置矩陣；

P

－1——矩陣P的逆矩陣；

I——單位矩陣。

如果經(jīng)正交變換后，只傳送M（M<n）個(gè)樣值，而將余下的n-M個(gè)較小的樣值丟棄。這時(shí)接收端恢復(fù)的信號(hào)為式中：第80頁(yè)2024/3/205.4.1變換的基本原理變換編碼

如何選擇正交矩陣

P，使M值較小，且使被丟棄的n－M個(gè)取值足夠小，以至于既能得到最大的信源壓縮率，同時(shí)又使丟棄掉n－M個(gè)取值以后，所產(chǎn)生的誤差不超過(guò)允許的失真范圍是我們關(guān)心的問(wèn)題。正交變換的主要問(wèn)題可歸結(jié)為在一定的誤差準(zhǔn)則下，尋找最佳或準(zhǔn)最佳的正交變換，以達(dá)到最大限度地消除原消息源之間的相關(guān)性。

由矩陣代數(shù)理論可知：對(duì)于任意兩個(gè)隨機(jī)變量x,y間的相關(guān)性可以用x,y的協(xié)方差(相關(guān)距)表示。一個(gè)信源

U的各分量間的相關(guān)性可以用信源各分量間協(xié)方差矩陣ΦU表示，其定義為式中：ΦU——信源輸出

U的協(xié)方差矩陣

E［·］——數(shù)學(xué)期望；φij——ui、uj協(xié)方差。第81頁(yè)2024/3/205.4.1變換的基本原理變換編碼U的協(xié)方差矩陣

ΦU是一個(gè)實(shí)對(duì)稱矩陣，它反映矢量

U各分量間的相關(guān)性。若各分量之間互不相關(guān)，則協(xié)方差矩陣

ΦU只在主對(duì)角線上有非零元素。主對(duì)角線上的非零元素代表各分量間的方差，即自相關(guān)性；非對(duì)角線上的元素表示各分量之間的協(xié)方差，即互相關(guān)性。

由矩陣代數(shù)可知，對(duì)于一個(gè)實(shí)對(duì)稱矩陣

A(A＝AT的矩陣)，必存在一個(gè)正交矩陣

P，使得：式中：λ1,λ2,…,λn——實(shí)對(duì)稱矩陣

A的n個(gè)特征根?？梢?jiàn)正交變換能解除相關(guān)性。第82頁(yè)2024/3/205.4.1變換的基本原理變換編碼信源

U經(jīng)正交變換后的輸出

X協(xié)方差矩陣可定義為

ΦX

＝E

［(X-E［

X］)(X-E

［X］)T］＝E［(PU-E［

PU］)(PU-E［

PU］)T］

=PE［(U-E［U］)(U-E［U］)T］

P

T=PΦUP

T

式中：ΦX——信源

U正交變換后的信號(hào)X的協(xié)方差矩陣；

X——信源U經(jīng)正交變換后的矢量；

P——正交變換矩陣；

P

T—正交變換矩陣

P的轉(zhuǎn)置矩陣。第83頁(yè)2024/3/205.4.1變換的基本原理變換編碼最佳是指在一定的條件下的最佳，這些條件有客觀的也有主觀的。最佳變換是指變換后的協(xié)方差矩陣

ΦX為理想對(duì)角線矩陣，表明經(jīng)正交交換后完全消除了互相關(guān)性。準(zhǔn)最佳變換是指變換后的協(xié)方差矩陣ΦX是近似對(duì)角形矩陣。由矩陣代數(shù)的相似變換理論知，任何矩陣都可相似于約旦(Jordan)標(biāo)準(zhǔn)型矩陣。約旦標(biāo)準(zhǔn)型就是準(zhǔn)對(duì)角形矩陣，即矩陣的主對(duì)角線上均為特征值λi,i＝1，2，…，n，而在對(duì)角線下僅有若干個(gè)不為0的1值。相似變換是指總能找到一非奇異矩陣

P使得P－1AP＝B，這時(shí)稱A與B相似，如果P為正交矩陣，則有：

P－1AP＝P

T

AP＝B第84頁(yè)2024/3/205.4.2常用變換1.離散余弦變換（DCT）2.離散小波變換（DWT）3.卡胡南―列夫變換(KLT)第85頁(yè)2024/3/205.5現(xiàn)代靜態(tài)圖像編碼技術(shù)5.5.1編碼原理小波變換在圖像編碼方面取得成功的典型例子就是基于小波的內(nèi)嵌比特平面編碼技術(shù)，其基本思想是將小波系數(shù)按其對(duì)恢復(fù)圖像質(zhì)量的貢獻(xiàn)程度進(jìn)行排序，并按照比特平面順序編碼，而且根據(jù)目標(biāo)碼率或失真度要求隨時(shí)結(jié)束編碼。內(nèi)嵌編碼能夠?qū)崿F(xiàn)圖像的漸進(jìn)傳輸和逐步浮現(xiàn)，而且碼率控制簡(jiǎn)單。在變換編碼中，量化的目的在于使變換系數(shù)的熵盡可能減少，從而在后期編碼中取得更高的壓縮效率。但是量化過(guò)程所引起的失真會(huì)直接影響逆變換后的恢復(fù)圖像質(zhì)量。第86頁(yè)2024/3/205.5.1編碼原理現(xiàn)代靜態(tài)圖像編碼技術(shù)目前主要使用與主觀視覺(jué)較為一致的均方誤差(MSE)準(zhǔn)則來(lái)衡量恢復(fù)圖像的失真程度并指導(dǎo)編碼。由于正交變換具有變換前后歐氏范數(shù)的不變性，即式中，xi，j和分別表示原始圖像和恢復(fù)圖像的像素值，ci，j和為變換產(chǎn)生的系數(shù)，N為圖像數(shù)據(jù)個(gè)數(shù)。按照幅值大小對(duì)|ci，j|進(jìn)行排序，并將ci，j最重要的比特位優(yōu)先傳輸,以保證恢復(fù)圖像與原始圖像的最大相似程度，這就是內(nèi)嵌比特平面編碼的基本思想。第87頁(yè)2024/3/205.5.1編碼原理現(xiàn)代靜態(tài)圖像編碼技術(shù)圖5.10是一個(gè)按幅度值大小排序后變換系數(shù)的二進(jìn)制列表。表中每一列代表一個(gè)變換系數(shù)幅度值的二進(jìn)制表示，每一行代表一層比特平面，最上層為符號(hào)位(sign)，越高層的比特平面的信息權(quán)重越大，對(duì)于編碼也越重要。內(nèi)嵌比特平面編碼的次序是從最重要的位(MSB)到最不重要的位(LSB)逐層傳送比特位信息，在某個(gè)比特平面編碼時(shí)，傳送所有系數(shù)的重要位信息，直到達(dá)到所需碼率后停止。圖5.10按幅值排序的系數(shù)二進(jìn)制表示第88頁(yè)2024/3/205.5.2編碼效率現(xiàn)代靜態(tài)圖像編碼技術(shù)由圖可知，內(nèi)嵌比特平面編碼輸出的信息主要包括兩部分：排序信息和重要系數(shù)的比特位信息。其中，位信息是直接影響恢復(fù)圖像的失真大??；而排序信息反映了重要系數(shù)的空間位置。因此，內(nèi)嵌編碼中排序算法的優(yōu)劣和排序信息的處理決定了整個(gè)編碼算法的效率。

式中，RIn和RSn分別表示在比特平面n時(shí)不重要系數(shù)(排序信息)和重要系數(shù)的編碼比特?cái)?shù)。在同樣恢復(fù)圖像質(zhì)量下，對(duì)不重要系數(shù)編碼的比特?cái)?shù)越少，編碼效率越高。在內(nèi)嵌比特平面編碼中，變換系數(shù)在某個(gè)比特平面只產(chǎn)生兩種結(jié)果：重要和不重要。重要值決定恢復(fù)圖像的質(zhì)量，不重要值用來(lái)恢復(fù)原始的數(shù)據(jù)結(jié)構(gòu)，即通過(guò)它們確定重要值的位置信息。這樣編碼的總比特?cái)?shù)R可表示為：第89頁(yè)2024/3/205.5.3一般框架現(xiàn)代靜態(tài)圖像編碼技術(shù)

系數(shù)ci，j在比特平面n編碼時(shí)有下列幾種狀態(tài)：(1)首次重要，即在比特平面n的比特為第一個(gè)非零比特(2n≤|ci，j|<2n+1)。一般在ci，j首次變成重要時(shí)跟著輸出其符號(hào)位χi，j。(2)不重要，即|ci，j|<2n。通常在較高的MSB比特平面,不重要的系數(shù)很多，因此排序算法可以把大量的不重要系數(shù)構(gòu)成一個(gè)集合，輸出一個(gè)“0”比特即可。(3)以前重要，即|ci，j|≥2n+1。對(duì)于在前面的比特平面已經(jīng)重要的系數(shù)則要輸出其幅度值在當(dāng)前比特平面n的比特位信息νni，j，這個(gè)過(guò)程即稱為幅值細(xì)化。第90頁(yè)2024/3/205.5.3一般框架現(xiàn)代靜態(tài)圖像編碼技術(shù)根據(jù)系數(shù)的三個(gè)狀態(tài)，可以描述內(nèi)嵌比特平面編碼的一般框架。(1)

初始化：確定初始的MSB比特平面(2)排序：確定首次變?yōu)橹匾南禂?shù)(2n≤|ci，j|<2n+1)和不重要的系數(shù)，對(duì)于重要系數(shù)，輸出符號(hào)位χi，j；對(duì)于不重要的系數(shù)，根據(jù)一定的預(yù)測(cè)原則再劃分為可能重要和可能不重要兩類。(3)幅值細(xì)化：對(duì)于所有|ci，j|≥2n+1的系數(shù)，輸出第n層比特平面的位信息為νni，j。(4)比特平面更新：返回步驟(2)進(jìn)行n－1比特平面的編碼過(guò)程。

內(nèi)嵌比特平面編碼產(chǎn)生的符號(hào)流可以進(jìn)一步進(jìn)行熵編碼壓縮，如采用自適應(yīng)算術(shù)編碼獲得更好的壓縮性能。第91頁(yè)2024/3/205.5.4EZW算法現(xiàn)代靜態(tài)圖像編碼技術(shù)5.5.5SPIHT算法5.5.6圖像壓縮國(guó)際標(biāo)準(zhǔn)JPEG20005.6星載圖像壓縮系統(tǒng)設(shè)計(jì)第92頁(yè)2024/3/20(1)通用編碼和統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼需要精確知道信源的概率分布{pi}。統(tǒng)計(jì)編碼對(duì)于實(shí)際分布與假設(shè)分布的偏差非常靈敏；許多場(chǎng)合不知道實(shí)際信源的統(tǒng)計(jì)特性，或者信源不存在統(tǒng)計(jì)特性。通用信源編碼：與信源統(tǒng)計(jì)特性無(wú)關(guān)而且有效的編碼方法。5.7LZ(Lempel-Ziv)碼第93頁(yè)2024/3/20(2)基于字典的編碼方法LZ

碼是1977年兩位以色列研究人員，齊費(fèi)(J.Ziv)和蘭佩爾(A.Lempel)提出的，它是一種基于字典的編碼方法。至今，幾乎日常使用的所有通用壓縮工具，象ARJ，PKZip，WinZip，LHArc，RAR，GZip，ACE，ZOO，TurboZip，Compress，JAR??甚至許多硬件如網(wǎng)絡(luò)設(shè)備中內(nèi)置的壓縮算法，都可以最終歸結(jié)為這兩個(gè)以色列人的杰出貢獻(xiàn)。字典模型的思路：在對(duì)信息進(jìn)行壓縮（說(shuō)）和解壓縮（聽(tīng)）的過(guò)程中都對(duì)字典進(jìn)行查詢操作。字典壓縮模型正是基于這一思路設(shè)計(jì)實(shí)現(xiàn)的。5.7LZ(Lempel-Ziv)碼第94頁(yè)2024/3/20(2)基于字典的編碼方法

靜態(tài)字典模型的算法：對(duì)一篇中文文章壓縮，已有一本《現(xiàn)代漢語(yǔ)詞典》。首先掃描要壓縮的文章，對(duì)其中的句子進(jìn)行分詞操作，對(duì)每一個(gè)獨(dú)立的詞語(yǔ)查找它出現(xiàn)的位置，如果找到，就輸出頁(yè)碼和該詞在本頁(yè)中的序號(hào)，如果沒(méi)有找到，就輸出一個(gè)新詞。靜態(tài)字典模型的缺點(diǎn)適應(yīng)性不強(qiáng)，必須為每類不同的信息建立不同的字典；必須維護(hù)信息量并不算小的字典，這一額外的信息量影響了最終的壓縮效果。自適應(yīng)字典模型：把已經(jīng)編碼過(guò)的信息作為字典，如果要編碼的字符串曾經(jīng)出現(xiàn)過(guò)，就輸出該字符串的出現(xiàn)位置及長(zhǎng)度，否則輸出新的字符串。幾乎所有通用的字典模型都使用這種方式。5.7LZ(