信息論與編碼無失真信源編碼.ppt

第4章 無失真信源編碼,前面的章節(jié)中，我們對信息問題從理論的角度進(jìn)行了一些度量和分析。從本章開始，我們將討論在信息論的基礎(chǔ)上進(jìn)行各種編碼。 本章主要介紹編碼的基本概念，信源編碼的基本思路與主要方法，以無失真、統(tǒng)計(jì)編碼為主，期望通過本章學(xué)習(xí)能建立起信源壓縮編碼的基本概念。,第4章 編碼類型,（1）在不失真或允許一定失真條件下，如何提高信息傳輸速度，這種編碼稱為信源編碼。根據(jù)是否允許失真，信源編碼又可以分為無失真信源編碼（當(dāng)失真可以逼近于0時(shí)，在信息論中也當(dāng)做無失真編碼討論）和限失真信源編碼。 （2）在信道受到干擾的情況下，如何增加信號(hào)的抗干擾能力，同時(shí)又使得信息的有效傳輸率最大，達(dá)到這種目的的編碼稱為信道編碼。它是為了對抗信道中的噪音和衰減，通過增加冗余，如校驗(yàn)碼等，來提高抗干擾能力以及糾錯(cuò)能力。,第4章 編碼類型,（3）在可以監(jiān)聽的信道上如何進(jìn)行安全的通信，使得在信道上監(jiān)聽的人也無法獲取消息，需要進(jìn)行加密。對應(yīng)的加密轉(zhuǎn)換方法稱為加密編碼。,4.1 編碼器和相關(guān)概念,為了分析方便和突出問題的重點(diǎn)，當(dāng)研究信源編碼時(shí)，我們把信道編碼和譯碼看成是信道的一部分，從而突出信源編碼。同樣，在研究信道編碼時(shí)，可以將信源編碼和譯碼看成是信源和信宿的一部分，從而突出信道編碼。對于加密編碼也是如此。簡單地說，通信系統(tǒng)模型中的各種編碼都是可選的，我們可以忽略其他編碼，而專門討論我們研究的那種編碼。,4.1.1 碼的分類,圖4-1 信源編碼器模型,4.1.1 碼的分類,圖4-2 碼的分類,4.1.1 常用碼的定義,1. 二元碼和r元碼,若碼符號(hào)集為X=0;1，所有碼字都是一些二元序列，則稱為二元碼（Binary Code） 2. 等長碼,若一組碼中所有碼字的碼長都相同，即li=l(i=1,2,q)，則稱為等長碼（定長碼，fixed length code） 3. 變長碼，若一組碼組中所有碼字的碼長各不相同，則稱為變長碼（variable length codes）,4.1.1 常用碼的定義,4. 非奇異碼，若一組碼中所有碼字都不相同，則稱為非奇異碼（nonsingular code，nonsigular code） 5. 奇異碼，若一組碼中有相同的碼字，則稱為奇異碼。該碼可能具有什么用途，又有什么缺陷？ 6. 唯一可譯碼 7. 非即時(shí)碼和即時(shí)碼 8.分組碼與非分組碼,4.1.2 碼樹,對于給定碼字的全體集合 C=W1,W2,Wq，可以用碼樹來描述。碼樹有助于研究唯一可譯碼的判別。,圖4-3 碼樹圖,4.1.3 Kraft不等式,利用碼樹可以判斷給定的碼是否為惟一可譯碼，但需要畫出碼樹。在實(shí)際中，我們可以利用克拉夫特（又譯克勞夫特，Kraft）不等式，直接根據(jù)各碼字的長度來判斷惟一可譯碼是否存在，即各碼字的長度應(yīng)符合克拉夫特不等式：,4.1.3 Kraft不等式,定理4-1 Kraft定理：對于碼符號(hào)為X=x1,x2,xr的任意唯一可譯碼，其碼字為W1,W2,Wq，所對應(yīng)的碼長為l1，l2，lq，則必定滿足克拉夫特不等式 定理4-2 將碼C中所有可能的尾隨后綴組成一個(gè)集合F，當(dāng)且僅當(dāng)集合F中沒有包含任一碼字，則可判斷此碼C為唯一可譯碼。,4.2 定長編碼,定理4-3 定長（等長）編碼定理：由L個(gè)符號(hào)組成的、每個(gè)符號(hào)熵為HL(X)的無記憶平穩(wěn)信源符號(hào)序列X1X2X3XL用KL個(gè)符號(hào)Y1Y2YKL（每個(gè)符號(hào)有m中可能值）進(jìn)行定長變碼。對任意，只要?jiǎng)t當(dāng)L足夠大時(shí)，必可使譯碼差錯(cuò)小于；反之，當(dāng) 時(shí)，譯碼差錯(cuò)一定是有限值，當(dāng)L足夠大時(shí)，譯碼幾乎必定出錯(cuò)。,4.2 定長編碼,4.2 定長編碼,例4-3設(shè)離散無記憶信源概率空間為 信源熵為,4.2 定長編碼,自信息方差為,4.2 定長編碼,對信源符號(hào)采用定長二元編碼，要求編碼效率，無記憶信源有 因此 可以得到 如果要求譯碼錯(cuò)誤概率， 則 由此可見，在對編碼效率和譯碼錯(cuò)誤概率的要求不是十分苛刻的情況下，就需要個(gè)信源符號(hào)一起進(jìn)行編碼，這對存儲(chǔ)和處理技術(shù)的要求太高，目前還無法實(shí)現(xiàn)。,4.3 變長編碼,定理4-4 香農(nóng)單符號(hào)變長編碼定理：若離散無記憶信源的符號(hào)熵為H(S)，每個(gè)信源符號(hào)用r進(jìn)制碼元進(jìn)行變長編碼，一定存在一種無失真編碼（唯一可譯編碼）方法，其碼字的平均長度滿足：,4.3 變長編碼,定理4-5 香農(nóng)離散平穩(wěn)無記憶序列變長編碼定理，即： 若對信源離散無記憶信源S的N次擴(kuò)展信源SN進(jìn)行編碼，則總可以找到一種編碼方法，構(gòu)成惟一可譯碼，使信源S中每個(gè)信源符號(hào)所需的平均碼長滿足：,4.3.1 編碼空間,在信源編碼的時(shí)候，我們可以如何使得編碼最短，但是越短的編碼，也容易造成唯一不可譯。以異前綴編碼為例，如果編的過短，會(huì)使得大量的碼字不可用，如果較長，則影響不大。為了便于理解，我們這里提出一種新概念-編碼空間。,4.3.1 編碼空間,實(shí)際上它是一個(gè)相對量，是指一個(gè)編碼占用的可以使用的編碼的比例，考慮異前綴編碼，顯然一個(gè)二進(jìn)制的編碼，如果將0作為碼字，所有以0開頭的編碼都不能再用，則有一半的編碼將不能繼續(xù)作為碼字，如果是兩位，則有四分之一的碼字不能使用，對于十進(jìn)制，一個(gè)一位的十進(jìn)制占用的比例為十分之一，依此，一個(gè)n位的k進(jìn)制占用的編碼空間為1/kn，當(dāng)占用的編碼空間小于等于1的時(shí)候，異前綴碼是可能存在的，如果大于1，則不可能存在。,4.3.2 香農(nóng)碼,香農(nóng)第一定理指出，選擇每個(gè)碼字的長度Ki滿足下式的整數(shù)： logmpiKi1logmpi 例4-4設(shè)無記憶信源的概率空間為：,4.3.2 香農(nóng)碼,以二進(jìn)制編碼為例，香農(nóng)編碼方法如下： 將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列 p(u1)p(u2) p(un) 確定碼長Ki (整數(shù)) ： Mi= 取整； Ki =Mi+1,如果 Mi是小數(shù)； Ki =Mi, 如果Mi是整數(shù) 為了編成唯一可譯碼，計(jì)算第i個(gè)消息的累加概率,4.3.2 香農(nóng)碼, 將累加概率Pi變換成二進(jìn)制數(shù)。 取pi二進(jìn)制數(shù)的小數(shù)點(diǎn)后Ki位即為該消息符號(hào)的二進(jìn)制數(shù)。 例4-5 對 信源進(jìn)行香農(nóng)編碼。,4.3.2 香農(nóng)碼,4.3.2 香農(nóng)碼,以i=3為例，計(jì)算各符號(hào)的碼字長度： K3=log0.2=3 累加概率P4=0.7 0.10110 101,4.3.2 香農(nóng)碼,4.3.2 香農(nóng)碼,香農(nóng)編碼給予你什么啟示？ 香農(nóng)編碼中如何保證編碼是異前綴的？ 香農(nóng)編碼何時(shí)可以達(dá)到無損壓縮的理論極限？ 考慮有記憶和無記憶信源序列概率（概率和條件概率）分布具有平穩(wěn)性，對單個(gè)符號(hào)進(jìn)行本編碼和對序列進(jìn)行編碼，編碼的效率相比較如何？,4.3.3 費(fèi)諾碼,費(fèi)諾碼屬于概率匹配編碼，又稱為香農(nóng)-費(fèi)諾碼（Shannon-Fano編碼），但它一般也不是最佳的編碼方法。編碼過程如下： (1)信源符號(hào)以概率遞減的次序排列起來; (2)將排列好的信源符號(hào)按概率值劃分成兩大組，使每組的概率之和接近于相等，并對每組各賦予一個(gè)二元碼符號(hào)“0“和“1“; (3)將每一大組的信源符號(hào)再分成兩組，使劃分后的兩個(gè)組的概率之和接近于相等，再分別賦予一個(gè)二元碼符號(hào); (4)依次下去，直至每個(gè)小組只剩一個(gè)信源符號(hào)為止; (5)信源符號(hào)所對應(yīng)的碼字即為費(fèi)諾碼。,4.3.3 費(fèi)諾碼,例4-6 對信源 進(jìn)行費(fèi)諾編碼 表4-2是忽略了排序過程的編碼，4-3排序。,4.3.3 費(fèi)諾碼,費(fèi)諾碼具有如下的性質(zhì)： 費(fèi)諾碼的編碼方法實(shí)際上是一種構(gòu)造碼樹的方法，所以費(fèi)諾碼是即時(shí)碼。 費(fèi)諾碼考慮了信源的統(tǒng)計(jì)特性，使概率大的信源符號(hào)能對應(yīng)碼長較短的碼字，從而有效地提高了編碼效率。 費(fèi)諾碼不一定是最佳碼。,4.3.4 哈夫曼碼,哈夫曼編碼的步驟如下： 統(tǒng)計(jì)信源消息符號(hào)的概率，將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列 p(u1)p(u2)p(un) 取兩個(gè)概率最小的字母分別配以0和1兩碼元，并將這兩個(gè)概率相加作為一個(gè)新字母的概率，與未分配的二進(jìn)符號(hào)的字母重新排隊(duì)，合并后的信源稱為縮減信源。 對重排后的兩個(gè)概率最小符號(hào)重復(fù)步驟的過程。 不斷繼續(xù)上述過程，直到最后兩個(gè)符號(hào)配以0和1為止。 從最后一級(jí)開始，逆向向前返回得到各個(gè)信源符號(hào)所對應(yīng)的碼元序列，即相應(yīng)的碼字。,例4-7 給定離散信源如下：,例4-7 給定離散信源如下：,4.4 其他實(shí)用基于統(tǒng)計(jì)的信源編碼方法,在編碼理論的指導(dǎo)下，先后出現(xiàn)了許多性能優(yōu)良的編碼方法，本節(jié)介紹一些實(shí)用的統(tǒng)計(jì)編碼方法。前面所討論的無失真編碼，都是建立在信源符號(hào)與碼字一一對應(yīng)的基礎(chǔ)上的，這種編碼方法我們通常稱為塊碼或分組碼，此時(shí)信源符號(hào)一般應(yīng)是多元的，而且不考慮信源符號(hào)之間的相關(guān)性。如果要對最常見的二元序列進(jìn)行編碼，則需采用游程編碼或合并信源符號(hào)等方法，把二元序列轉(zhuǎn)換成多值符號(hào)，轉(zhuǎn)換后這些多值符號(hào)之間的相關(guān)性也是不予考慮的。這就使信源編碼的匹配原則不能充分滿足，編碼效率一般就不高。為了克服這種局限性，就需要跳出分組碼的范疇，研究非分組碼的編碼方法。下面要介紹的游程編碼和算術(shù)編碼即為非分組碼。,4.4.1 游程編碼,游程是指符號(hào)序列中各個(gè)符號(hào)連續(xù)重復(fù)出現(xiàn)而形成符號(hào)串的長度，又稱游程長度或游長。 游程編碼(Run-Length Coding，簡記RLC)就是將這種符號(hào)序列映射成游程長度和對應(yīng)符號(hào)序列的位置的標(biāo)志序列。如果知道了游程長度和對應(yīng)符號(hào)序列的位置的標(biāo)志序列，就可以完全恢復(fù)出原來的符號(hào)序列。,4.4.2 算術(shù)編碼,在算術(shù)編碼中，信源符號(hào)和碼字間的一一對應(yīng)關(guān)系并不存在，它是一種從整個(gè)符號(hào)序列出發(fā)，采用遞推形式進(jìn)行編碼的方法。算術(shù)編碼（Arithmetic Coding）跳出了分組編碼的范疇，從全序列出發(fā)，采用遞推形式的連續(xù)編碼。,4.4.2 算術(shù)編碼,算術(shù)編碼的基本原理是將編碼的消息表示成實(shí)數(shù)0和1之間的一個(gè)間隔（Interval），消息越長，編碼表示它的間隔就越小，表示這一間隔所需的二進(jìn)制位就越多。 1、算術(shù)碼的主要概念 2、累積概率,4.4.2 算術(shù)編碼,圖4-9信源符號(hào)序列的累積分布函數(shù)F(s)及其對應(yīng)的區(qū)間,4.4.2 算術(shù)編碼,4.5 通用編碼,哈夫曼編碼與算術(shù)編碼都要預(yù)先知道信源符號(hào)的概率分布。實(shí)際問題中往往無法知道或沒有必要去統(tǒng)計(jì)信源各個(gè)符號(hào)的概率，希望有一種通用的非概率的編碼方法。 我們把這種不依靠概率知識(shí)就能進(jìn)行壓縮編碼的方法叫做通用編碼（Universal Coding）。由于通用，因而具有普遍適用性。它已經(jīng)成為一種應(yīng)用廣泛的文件壓縮技術(shù)。現(xiàn)已找到多種通用編碼方法，如目前在計(jì)算機(jī)上常用的ZIP、RAR等。,4.5.1 LZ77與LZSS編碼,LZ77和LZSS編碼屬于指針編碼，其原理為：當(dāng)待編字符串在早先輸出的數(shù)據(jù)流中已經(jīng)出現(xiàn)過時(shí)，則不必重復(fù)輸出，而用指向早先那個(gè)字符串（稱為匹配字符串）的指針（指示匹配字符串的位置）來代替。 LZ77算法原理為：所找到的最長的匹配字符串，用指針(x, y)來表示，并用它代替當(dāng)前待編字符串。其中：x表示匹配字符串出現(xiàn)在當(dāng)前待編字符串之前的位置（按字符個(gè)數(shù)計(jì)算)，y表示匹配字符串的長度。C表示當(dāng)前待編字符串的下一個(gè)待編字符。因?yàn)楫?dāng)前匹配字符串再接上這個(gè)字符后，就成為前面找不到的字符串了。,4.5.2 LZ78與LZW編碼,LZ78與LZW編碼都屬于字典編碼。 LZ78采用了一種完全不同的字典建立方案，取消了文本窗口，保留以前建立的字典，只有當(dāng)新字符串出現(xiàn)時(shí)才將字符串加入字典中。 LZ78的編碼方法是從空的字典開始，字典給每一個(gè)短語編號(hào)。讀入字符，并在字典中搜索。輸出搜索中發(fā)現(xiàn)的最長字符串的編號(hào)，然后緊接著輸出未匹配的第一個(gè)字符，同時(shí)將發(fā)現(xiàn)的最長匹配字符和未匹配的第一個(gè)字符組成一個(gè)新短語并編入字典中，賦以新的編號(hào)，為下一個(gè)字符串編碼做準(zhǔn)備。,4.5.3 常用壓縮文件格式,