信息論基礎(chǔ)-信源編碼

數(shù)據(jù)壓縮和信源編碼3.1等長碼3.2

變長編碼3.3哈夫曼碼3.4算術(shù)碼

香農(nóng)-費(fèi)諾碼3.5通用信源編碼

LZW算法習(xí)題三10.概述是第一個(gè)能夠找到的好的變長碼.原則：按照符號出現(xiàn)的概率從大到小排序，然后將其分成兩個(gè)出現(xiàn)概率相同或幾乎相同的子集—一個(gè)子集的編碼均以0打頭，另一個(gè)子集的編碼均以1打頭；然后把每個(gè)子集再分成兩個(gè)更小的子集，同樣確定所有碼字的第二位，依次循環(huán).

算術(shù)碼—Shannon-Fano-Elias碼2算術(shù)碼—Shannon-Fano-Elias碼例130.概述平均碼長：0.25×2+0.20×2+0.15×3+0.15×3+0.10×3+

0.10×4+0.05×4=2.7bits/symbol.熵：-（0.25log0.25+0.20log0.20+0.15log0.15+0.15log0.15+0.10log0.10+0.10log0.10+0.05log0.05≈2.67.這是一個(gè)較好的結(jié)果！

算術(shù)碼—Shannon-Fano-Elias碼4算術(shù)碼—Shannon-Fano-Elias碼例25算術(shù)碼—Shannon-Fano-Elias碼例361.基本思路用二進(jìn)制小數(shù)表示信源的概率分布，如果概率分布取值大，則它的二進(jìn)制位數(shù)就低；另外，為了使算術(shù)碼具有前綴性（無尾隨后綴），對概率分布采用累計(jì)求和計(jì)算.

算術(shù)碼—Shannon-Fano-Elias碼72.編碼方法1）將信源符號X={a1,a2,……,aq}依次排列（不要求以概率大小排序）；2）計(jì)算各符號的修正累積分函數(shù)值

3）確定各信源符號所對應(yīng)碼字的碼長4）將F(ak)表示為二進(jìn)制小數(shù)，并用小數(shù)點(diǎn)后的l(ak)位作為ak的碼字.<若后面有尾數(shù)，要進(jìn)位>算術(shù)碼—Shannon-Fano-Elias碼[x]代表不小于x的整數(shù)若二進(jìn)制小數(shù)后面有尾數(shù)，則截?cái)?例1：若信源的概率分布為，取信號字母表為，求信源的算術(shù)碼.算術(shù)碼—Shannon-Fano-Elias碼9例1：若信源的概率分布為，取信號字母表為，求信源的算術(shù)碼.算術(shù)碼—Shannon-Fano-Elias碼10例1：若信源的概率分布為，取信號字母表為，求信源的算術(shù)碼.算術(shù)碼—Shannon-Fano-Elias碼1011例2

有一單符號離散無記憶信源對該信源編二進(jìn)制香農(nóng)-費(fèi)諾碼.其編碼過程如下表所示：算術(shù)碼—Shannon-Fano-Elias碼12算術(shù)碼—Shannon-Fano-Elias碼13計(jì)算出給定信源香農(nóng)碼的平均碼長若對上述信源采用等長編碼，要做到無失真譯碼，每個(gè)符號至少要用3個(gè)比特表示。相比較，香農(nóng)編碼對信源進(jìn)行了壓縮。由離散無記憶信源熵定義，可計(jì)算出：對上述信源采用香農(nóng)編碼的信息率為編碼效率為信源熵和信息率之比。則可以看出，編碼效率并不是很高。算術(shù)碼—Shannon-Fano-Elias碼14思考（一）：用Shannon-Fano-Elias碼方法將信源編成二元變長唯一可譯碼，并計(jì)算其碼率.算術(shù)碼—Shannon-Fano-Elias碼15算術(shù)碼—Shannon-Fano-Elias碼思考（二）：有兩個(gè)信源X和Y如下：1)分別用霍夫曼碼編成二元變長惟一可譯碼，并計(jì)算其編碼效率。*)用Shannon-Fano碼編成二元變長惟一可譯碼16思考（二）：有兩個(gè)信源X和Y如下：2)分別用Shannon-Fano-Elias編碼法編成二元變長惟一可澤碼．并計(jì)算編碼效率.3)從X，Y兩種不同信源來比較這三種編碼方法的優(yōu)缺點(diǎn)算術(shù)碼—Shannon-Fano-Elias碼17思考（二）：信源X的二元霍夫曼編碼：算術(shù)碼—Shannon-Fano-Elias碼18算術(shù)碼—Shannon-Fano-Elias碼19思考（二）：信源X的二元霍夫曼編碼：其平均碼長

編碼效率算術(shù)碼—Shannon-Fano-Elias碼20思考（二）：信源Y的二元霍夫曼編碼：算術(shù)碼—Shannon-Fano-Elias碼21算術(shù)碼—Shannon-Fano-Elias碼22思考（二）：信源Y的二元霍夫曼編碼：其平均碼長

編碼效率算術(shù)碼—Shannon-Fano-Elias碼23思考（二）：信源X的Shannon-Fano編碼：算術(shù)碼—Shannon-Fano-Elias碼24算術(shù)碼—Shannon-Fano-Elias碼25思考（二）：信源X的Shannon-Fano編碼：其平均碼長

編碼效率算術(shù)碼—Shannon-Fano-Elias碼26思考（二）：信源Y的Shannon-Fano碼：算術(shù)碼—Shannon-Fano-Elias碼27算術(shù)碼—Shannon-Fano-Elias碼28思考（二）：信源Y的Shannon-Fano碼：其平均碼長

編碼效率算術(shù)碼—Shannon-Fano-Elias碼29思考（二）：信源X的Shannon-Fano-Elias編碼：其平均碼長

編碼效率算術(shù)碼—Shannon-Fano-Elias碼30思考（二）：信源Y的Shannon-Fano-Elias碼：其平均碼長

編碼效率算術(shù)碼—Shannon-Fano-Elias碼31思考（二）：從信源X和Y的三種不同編碼方法可以看出：Huffman編碼所得平均碼長最短，編碼效率最高；Shannon-Fano-Elias編碼所得平均碼長最長，其編碼效率最差；而Shannon-Fano碼居中。算術(shù)碼—Shannon-Fano-Elias碼32

Huffman碼其編碼時(shí)短碼得到充分利用，而且一定是概率大的信源符號對應(yīng)于短碼，概率小的信源符號對應(yīng)于長碼：所以，其平均碼長最短。

Shannon-Fano-Elias編碼方法雖然概率大的符號其碼長短，概率小的符號其碼長長，但它短碼沒有被充分利用。所以，其平均碼長增大。算術(shù)碼—Shannon-Fano-Elias碼33

Shannon-Fano碼也是一種較好的編碼方法．如信源Y的Shannon-Fano碼與Huffman碼的編碼效率一樣好。而信源X的Shannon-Fano碼的編碼效率比其Huffman碼的編碼效率降低極少。這是因?yàn)樾旁碮在Shannon-Fano碼編程過程中分兩大組時(shí)“概率和”相差不多(為0.49與0.51)：而信源X在編碼過程中每次分兩組時(shí)，其“概率和”相差較遠(yuǎn)(第一次為0.57和0.43；第二次上面分組為0.2和

0.37，下面分組為0.17和0.26)。算術(shù)碼—Shannon-Fano-Elias碼34數(shù)據(jù)壓縮和信源編碼3.1等長碼3.2

變長編碼3.3哈夫曼碼3.4算術(shù)碼3.5通用信源編碼習(xí)題三香農(nóng)-費(fèi)諾碼;香農(nóng)-費(fèi)諾-埃里斯碼35編碼理論（實(shí)例）以數(shù)字電視這一熱門話題為例.

36數(shù)字電視的主要核心技術(shù)包括信源編碼、信道編碼和顯示技術(shù)，它們分別解決數(shù)字電視節(jié)目在初始制作、中間傳播和終端呈現(xiàn)三個(gè)主要環(huán)節(jié)上的問題。通俗地說就是滿足了我們拍片子、播節(jié)目、看電視的需要。編碼理論（實(shí)例）37信源編碼技術(shù)解決的重點(diǎn)問題是數(shù)字音視頻海量數(shù)據(jù)的編碼壓縮問題。眾所周知，數(shù)字化視頻的原始數(shù)據(jù)量是十分龐大的，例如，標(biāo)準(zhǔn)清晰度的數(shù)字視頻每秒的數(shù)據(jù)量超過200M

bit，高清晰度數(shù)字電視每秒的數(shù)據(jù)量超過1G

bit。編碼理論（實(shí)例）38信源編碼技術(shù)解決的重點(diǎn)問題是數(shù)字音視頻海量數(shù)據(jù)的編碼壓縮問題。高清晰度數(shù)字電視簡稱高清電視（HDTV）簡單的說，是指圖像水平清晰度大于720線、采用的是16:9顯示方式的數(shù)字電視系統(tǒng)。從世界范圍來看，目前高清電視主要包括1080i和720p這兩種格式，兩者圖像的長寬比都是16：9，因此這符合人眼視覺的“黃金分割法則”。作為隔行掃描的1080i的分辨率則是1920×1080；720p是逐行掃描，分辨率為1280×720。

編碼理論（實(shí)例）39數(shù)字音視頻要在消費(fèi)電子產(chǎn)品中得到應(yīng)用，必須采用先進(jìn)的壓縮編碼算法進(jìn)行大幅度壓縮。而反映壓縮效率的壓縮比也就成為數(shù)字電視乃至數(shù)字音視頻產(chǎn)業(yè)的“基本指數(shù)”。編碼理論（實(shí)例）40打個(gè)形象的比方，信源編碼就好像制作壓縮餅干的技術(shù)，如何將普通面粉制作成壓縮餅干就是“編碼”過程——擠掉冗余成分，只保留有效成分且體積（或所占用資源）盡可能??；而“譯碼”就是一個(gè)還原過程，將壓縮餅干恢復(fù)到常態(tài)供給食用，并保證營養(yǎng)（或信息）損失盡可能少。

編碼理論（實(shí)例）41MP3（MPEGAudioLayer）是一種以高保真為前提下實(shí)現(xiàn)的高效壓縮技術(shù)。它采用了特殊的數(shù)據(jù)壓縮算法對原先的音頻信號進(jìn)行處理，使數(shù)碼音頻文件的大小僅為原來的十幾分之一，而音樂的質(zhì)量卻沒有什么變化，幾乎接近于CD唱盤的質(zhì)量。一分鐘的WAVE格式的文件有十幾兆，而一分鐘MP3格式的音頻文件僅有一兆左右。編碼理論（實(shí)例）42MP3技術(shù)使在較小的存儲(chǔ)空間內(nèi)，存儲(chǔ)大量的音頻數(shù)據(jù)成為可能：一張CD唱盤存儲(chǔ)的音樂與一盒卡帶差不多，若用MP3格式來存儲(chǔ)，則可存上百首。播放MP3流行的軟件有很多，最流行的播放器要算是WINAMP。我們自己也可以制作MP3。在超級解霸中提供了一個(gè)CD壓縮工具，用它可以將CD音軌直接轉(zhuǎn)換成MP3音樂。此外比如：WinPlay等。

編碼理論（實(shí)例）43而信道就是信源的通路，信道編碼就相當(dāng)于壓縮餅干的運(yùn)輸方式，用飛機(jī)、汽車、火車都可以將餅干從廠家運(yùn)送到消費(fèi)者手中，但選擇何種運(yùn)輸方式就相當(dāng)于采用哪種信道編碼標(biāo)準(zhǔn)，目的地一致，但在成本和效率上會(huì)有各種差別。編碼理論（實(shí)例）44由此可見，信源編碼是數(shù)字電視的基礎(chǔ)，離開了信源編碼去談信道編碼就是無源之水、無本之木。編碼理論（實(shí)例）45編碼理論（實(shí)例）數(shù)字電視就是指從演播室到發(fā)射、傳輸、接收的所有環(huán)節(jié)都是使用數(shù)字電視信號或?qū)υ撓到y(tǒng)所有的信號傳播都是通過由0、1數(shù)字串所構(gòu)成的數(shù)字流來傳播的，數(shù)字信號的傳播速率是每秒19.39兆字節(jié)，如此大的數(shù)據(jù)流的傳遞保證了數(shù)字電視的高清晰度，克服了模擬電視的先天不足。同時(shí)還由于數(shù)字電視可以允許幾種制式信號的同時(shí)存在，每個(gè)數(shù)字頻道下又可分為幾個(gè)子頻道，從而既可以用一個(gè)大數(shù)據(jù)流--每秒19.39兆字節(jié)，也可將其分為幾個(gè)分流：46編碼理論（實(shí)例）例如4個(gè)，每個(gè)的速度就是每秒4.85兆字節(jié)，這樣雖然圖像的清晰度要大打折扣，卻可大大增加信息的種類，滿足不同的需求。例如在轉(zhuǎn)播一場體育比賽時(shí)，觀眾需要高清晰度的圖像，電視臺(tái)就應(yīng)采用每秒19.39兆字節(jié)的傳播；而在進(jìn)行新聞廣播時(shí)，觀眾注意的是新聞內(nèi)容而不是播音員的形象，所以沒必要采用那么高的清晰度，這時(shí)只需每秒3兆字節(jié)的速度就可以了，剩下16.39兆字節(jié)可用來傳輸別的內(nèi)容。47

以視頻為例：視頻能夠壓縮的根本原因在于視頻數(shù)據(jù)具有較高的冗余度，壓縮就是指冗余的消除，主要基于兩種技術(shù)：統(tǒng)計(jì)學(xué)和心理視覺。編碼理論（實(shí)例）48消除統(tǒng)計(jì)冗余的基本依據(jù)是視頻數(shù)字化過程在時(shí)間和空間上采用了規(guī)則的采樣過程。視頻畫面數(shù)字化為規(guī)則的像素陣列，其密集程度適于表征每點(diǎn)最高的空間頻率，而絕大多數(shù)畫面幀包含非常少甚至不含這種最高頻率的細(xì)節(jié)。同樣，所選的幀頻能夠表征場景中最快的運(yùn)動(dòng)，而理想的壓縮系統(tǒng)只要描述場景所必需的瞬時(shí)運(yùn)動(dòng)即可。編碼理論（實(shí)例）49簡言之，理想的壓縮系統(tǒng)能夠動(dòng)態(tài)適應(yīng)視頻在時(shí)間和空間上的變化，所需要的數(shù)據(jù)量遠(yuǎn)低于數(shù)字化采樣所產(chǎn)生的原始數(shù)據(jù)。編碼理論（實(shí)例）50

壓縮效果的評價(jià)標(biāo)準(zhǔn)有主觀評價(jià)和客觀評價(jià)兩種，各有優(yōu)缺點(diǎn)。主觀評判是聘請專門的評價(jià)人員來比較壓縮之后再恢復(fù)的視聽效果和原始效果的差異，通常是在專門的視聽環(huán)境中按照一定的規(guī)則進(jìn)行主觀評分?？陀^評判則是通過一種具體的算法來統(tǒng)計(jì)多媒體數(shù)據(jù)壓縮結(jié)果的損失，例如信噪比SNR（即信號與噪聲之比的對數(shù)）。編碼理論（實(shí)例）51主觀評判和客觀評判有時(shí)相差很大，因此衡量一個(gè)算法的好壞就需要在這二者之間找到一個(gè)平衡點(diǎn)。對一套標(biāo)準(zhǔn)的評價(jià)，通常開發(fā)過程中采用客觀評價(jià)的方法，但最終要得到主觀評價(jià)的確認(rèn)。

編碼理論（實(shí)例）52數(shù)據(jù)壓縮和信源編碼3.1等長碼3.2

變長編碼3.3哈夫曼碼3.4算術(shù)碼

香農(nóng)-費(fèi)諾碼3.5通用信源編碼

LZW算法習(xí)題三53對于統(tǒng)計(jì)特性已知的平穩(wěn)信源，有Huffman碼和算術(shù)碼等高效編碼方法.但是，它們存在以下共同問題：①在編碼時(shí)必須知道信源的概率分布，這在許多情況下是不可能的；②它們對無記憶信源較為合適，而實(shí)際應(yīng)用中的信源一般都具有記憶性；因此如何利用信源的記憶性提高它的壓縮率是信源編碼所必需考慮的問題.

通用信源編碼541通用碼的一般理論通用編碼是指在信源概率分布不知時(shí)，對其編碼并使編碼效率很高的一種碼.基本原理：利用出現(xiàn)數(shù)據(jù)序列前后的相關(guān)性進(jìn)行壓縮.

通用信源編碼55

常用的通用碼：LZ碼及其改進(jìn)算法—LZW碼.LZ碼是1977-1978年以色列研究人員J.Ziv&A.Lempel提出的，是一種基于字典的編碼方法.1984年，T.A.Welch給出了LZ算法的實(shí)用修正形式，成為LZW算法.通用信源編碼56LZ碼的基本算法：將長度不同的符號串編成一個(gè)個(gè)新的短語(單詞)，形成短語詞典的索引表；它是一種分段編碼，其短語詞典是由前面已見到的文本分段來定義的.通用信源編碼57LZ碼的編碼步驟：①取第一個(gè)符號x作為第一段（單詞），記為（0，x）；②從第二個(gè)符號y起，分段時(shí)先查看是否與前面的短語相同（匹配）：若沒有匹配的，記為（0，y）；

若有匹配的符號，就找從該符號開始與之匹配的最大長度L，并使得匹配開始的距離ρ最近，記為（1，L,ρ）；

通用信源編碼匹配時(shí)長度優(yōu)先考慮，距離次之！58例1

設(shè)x11=a0a0a2a3a1a1a0a0a0a3a2，求它的LZ碼.解：對x1的LZ碼為（0，a0）；對x2的LZ碼為（1，1，1）;對x3的LZ碼為（0，a2）；對x4的LZ碼為（0，a3）;對x5的LZ碼為（0，a1）；對x6的LZ碼為（1，1，1）;對x7的LZ碼為（1,2,6）；對x8不編碼；對x9的LZ碼為（1，1，1）;對x10的LZ碼為（1，1，6）;對x11的LZ碼為（1，1，8）;

通用信源編碼因此，它的LZ碼為C={(0,a0),(1,1,1),……}59例1

設(shè)x11=a0a0a2a3a1a1a0a0a0a3a2，求它的LZ碼.譯碼：①由（0，a0）得到x1=a0,xn=a0；②由（1，1，1）得到x2=a0,xn=a0a0……

通用信源編碼因?yàn)椋腖Z碼為C={(0,a0),(1,1,1),……}60

常用的通用碼：LZ碼及其改進(jìn)算法—LZW碼.LZ碼是1977-1978年以色列研究人員J.Ziv&A.Lempel提出的，是一種基于字典的編碼方法.1984年，T.A.Welch給出了LZ算法的實(shí)用修正形式，成為LZW算法.

LZW就是通過建立一個(gè)字符串表,用較短的代碼來表示較長的字符串來實(shí)現(xiàn)壓縮.LZW壓縮算法是Unisys的專利,有效期到2003年.通用信源編碼61LZW算法保留了LZ的自適應(yīng)性能，壓縮效率大致相同；成為計(jì)算機(jī)文件壓縮的標(biāo)準(zhǔn)算法，已經(jīng)實(shí)現(xiàn)成為Unix操作系統(tǒng)中的標(biāo)準(zhǔn)文件壓縮程序和arc文件壓縮程序.可將典型的ASCII文本文件壓縮成原文件的一半，得到廣泛的應(yīng)用.通用信源編碼手機(jī)存儲(chǔ)備份,是ARC文件

62LZW壓縮有三個(gè)重要的對象：數(shù)據(jù)流(CharStream)、編碼流(CodeStream)和編譯表(String

Table)。在編碼時(shí)，數(shù)據(jù)流是輸入對象（文本文件的數(shù)據(jù)序列），編碼流就是輸出對象（經(jīng)過壓縮運(yùn)算的編碼數(shù)據(jù)）；在解碼時(shí)，編碼流則是輸入對象，數(shù)據(jù)流是輸出對象；而編譯表是在編碼和解碼時(shí)都須要用借助的對象。.通用信源編碼63

LZW壓縮算法的基本原理：提取原始文本文件數(shù)據(jù)中的不同字符，基于這些字符創(chuàng)建一個(gè)編譯表，然后用編譯表中的字符的索引來替代原始文本文件數(shù)據(jù)中的相應(yīng)字符，減少原始數(shù)據(jù)大小?？雌饋砗驼{(diào)色板圖象的實(shí)現(xiàn)原理差不多，但是應(yīng)該注意到的是，我們這里的編譯表不是事先創(chuàng)建好的，而是根據(jù)原始文件數(shù)據(jù)動(dòng)態(tài)創(chuàng)建的，解碼時(shí)還要從已編碼的數(shù)據(jù)中還原出原來的編譯表.

通用信源編碼64

LZW算法流程：

1)初始化：將所有的單字符串放入串表；

2)讀第一個(gè)輸入字符給前綴串ω

3)Step:讀下一個(gè)輸入字符K;

if沒有這樣的K(輸入已窮盡)：

碼字(ω)輸出；結(jié)束。

通用信源編碼IfωK已存在于串表中：

ωK:=ω；repeatStep；

elseωK不在于串表中:

碼字(ω)輸出；

ωK加進(jìn)串表；K:=ω；repeatStep.

65

例子：ababcbababaaaaaaa

LZW編碼：a,b,c,ab,ba,abc,cb,bab,baba,aa,aaa,aaaa

通用信源編碼66LZW碼的編碼步驟：①取第一個(gè)符號x作為第一段（單詞），記為（0，x）；②從第二個(gè)符號y起，分段時(shí)先查看是否與前面的短語相同（匹配）：若沒有匹配的，記為（0，y）；

若有匹配的符號，并與第l個(gè)碼字相同，就再取緊跟后面的一個(gè)符號z一起組成一個(gè)短語，以便與前面的短語不同，記為（l

，z

）；

通用信源編碼67例2

設(shè)x11=a0a0a2a3a1a1a0a0a0a3a2，求它的LZW碼.解：對x1的LZW碼為（0，a0）；對x2的LZW碼為（1，a2）;對x3不編碼；對x4的LZW碼為（0，a3）;對x5的LZW碼為（0，a1）；對x6的LZW碼為（4，a0

）;對x7不編碼；對x8的LZW碼為（1，a0）

；對x9不編碼;對x10的LZ碼為（3，a2

）;對x11不編碼;

通用信源編碼因此，它的LZ碼為C={(0,a0),(1,a2),……}68

LZW壓縮的特點(diǎn)

LZW碼能有效利用字符出現(xiàn)頻率冗余度進(jìn)行壓縮，且字典是自適應(yīng)生成的，但通常不能有效地利用位置冗余度。

具體特點(diǎn)如下：

l)LZW壓縮技術(shù)對于可預(yù)測性不大的數(shù)據(jù)具有較好的處理效果，常用于GIF格式的圖像壓縮，其平均壓縮比在2:1以上，最高壓縮比可達(dá)到3:1。通用信源編碼69

2)對于數(shù)據(jù)流中連續(xù)重復(fù)出現(xiàn)的字節(jié)和字串，LZW壓縮技術(shù)具有很高的壓縮比。

3)除了用于圖像數(shù)據(jù)處理以外，LZW壓縮技術(shù)還被用于文本程序等數(shù)據(jù)壓縮領(lǐng)域。

4)LZW壓縮技術(shù)有很多變體，例如常見的ARC、PKZIP高效壓縮程序。

5)對于任意寬度和像素位長度的圖像，都具有穩(wěn)定的壓縮過程。壓縮和解壓縮速度較快。

6)對機(jī)器硬件條件要求不高。

通用信源編碼70習(xí)題

若

試構(gòu)造它的LZW數(shù)據(jù)壓縮編碼.通用信源編碼71

通用信源編碼72數(shù)據(jù)壓縮和信源編碼3.1等長碼3.2

變長編碼3.3哈夫曼碼3.4算術(shù)碼

香農(nóng)-費(fèi)諾碼3.5通用信源編碼

LZW算法習(xí)題三731）(a)解：由長度滿足Kraft不等式，可知利用該數(shù)集可以構(gòu)造二進(jìn)即時(shí)碼.編碼方法：任意選取長為1的碼字：0；……習(xí)題課743）證明：最短碼字“101”不是其他碼的前綴；依次考查，碼C