1、實(shí)用的無失真信源編碼實(shí)用的無失真信源編碼LZWLZW壓縮編碼壓縮編碼信息理論與編碼工程技術(shù)學(xué)院工程技術(shù)學(xué)院電氣與電子信息系電氣與電子信息系郭堃郭堃Page 2課程簡(jiǎn)介課程簡(jiǎn)介 尋找信息傳輸過程中的共同規(guī)律，以尋找信息傳輸過程中的共同規(guī)律，以提高信息傳輸?shù)奶岣咝畔鬏數(shù)挠行杂行浴⒖煽啃钥煽啃院秃捅Ｃ苄员Ｃ苄裕剐畔鬏斚到y(tǒng)達(dá)到最優(yōu)化。使信息傳輸系統(tǒng)達(dá)到最優(yōu)化。 本次課內(nèi)容概要本次課內(nèi)容概要Page 3信源編碼信源編碼LZWLZW編碼編碼1、LZW編碼思想2、LZW編碼方法LZWLZW編碼特點(diǎn)編碼特點(diǎn) 莫爾斯電碼莫爾斯電碼Page 4一、信源編碼一、信源編碼信源編碼簡(jiǎn)介信源編碼簡(jiǎn)介 信源編碼就

2、是把信源符號(hào)變換到碼符號(hào)的一種映射。 編碼的目的就是將原始數(shù)據(jù)進(jìn)行壓縮，達(dá)到提高通信效率的目的。 信源編碼分為：無失真壓縮編碼和限失真壓縮編碼兩種。Page 5常見的無失真信源編碼方法常見的無失真信源編碼方法“游程編碼”、“霍夫曼編碼”、 “算術(shù)編碼”、“LZW編碼”概率匹配壓縮原理概率匹配壓縮原理 根據(jù)信源的統(tǒng)計(jì)特性，用短碼來代替頻繁出現(xiàn)的原始數(shù)據(jù)，從而達(dá)到壓縮的目的。 Page 6 在70年代末以前，以霍夫曼編碼霍夫曼編碼為代表的概率匹配壓縮模型在數(shù)據(jù)壓縮領(lǐng)域一直占據(jù)著統(tǒng)治地位。這類編碼屬于靜態(tài)概率編碼，需要預(yù)知原始消息的概率分布。但大多數(shù)信源的概率是很難預(yù)知，甚至概率分布是變動(dòng)的。二、二

3、、LZWLZW編碼編碼Page 71977 年，以色列人Ziv 和 Lempel提出了全新的一個(gè)壓縮技術(shù)被稱為 LZ77 算法。1985年由美國(guó)人Welch在LZ77算法基礎(chǔ)上提出LZW編碼算法并進(jìn)入實(shí)用階段。它們的思路和字典頗為相似，因此，人們將基于這一思路的編碼方法稱作字典式字典式編碼編碼。其在壓縮效果上大大超過了霍夫曼編碼，其壓縮和解壓縮的速度也異常驚人，打破了霍夫曼編碼一統(tǒng)天下的局面。Page 8LZWLZW編碼實(shí)際應(yīng)用編碼實(shí)際應(yīng)用至今，幾乎我們?nèi)粘Ｊ褂玫乃型ㄓ脡嚎s工具最終都?xì)w結(jié)為以LZW算法為核心。（1）圖像壓縮：GIF、TIFF、PNG（2）計(jì)算機(jī)數(shù)據(jù)壓縮：ZIP、RAR、7-Z

4、IPPage 91 1、LZWLZW編碼思想編碼思想絕大多數(shù)原始信息有很多重復(fù)數(shù)據(jù)，如文本文檔、圖片、程序代碼等。如果用一些簡(jiǎn)單的編碼代替這些數(shù)據(jù)，就可以實(shí)現(xiàn)壓縮，編碼與數(shù)據(jù)的對(duì)應(yīng)表就是字典。基本思想基本思想：構(gòu)造一個(gè)字典，將原始信息中出現(xiàn)的字符串，以單詞的形式存儲(chǔ)在字典中，以索引形式給出編碼。解碼時(shí)對(duì)根據(jù)索引，通過查字典，轉(zhuǎn)換為原始信息。Page 10例如，對(duì)“Data Compression”進(jìn)行編碼以牛津詞典為例子，查詞典發(fā)現(xiàn)“Data”出現(xiàn)在第271頁第13個(gè)字；“Compression”出現(xiàn)在第213頁第8個(gè)字。Data CompressionData Compression（271

5、,13271,13）（）（213,8213,8）Page 11Data CompressionData Compression（271,13271,13）（）（213,8213,8）牛津詞典共1354頁，每頁不超過64字，頁碼用11位二進(jìn)制數(shù)表示，每頁第幾個(gè)用6位二進(jìn)制數(shù)表示，則2個(gè)單詞用34位數(shù)據(jù)表示。而原始數(shù)據(jù)若用8位ASCII碼表示，數(shù)據(jù)為16*8=128位。壓縮比為128/34=3.8倍。Page 12 LZW壓縮有三個(gè)重要的對(duì)象：數(shù)據(jù)流、編碼流和字典（編譯表）。2 2、LZWLZW編碼方法編碼方法編碼器編碼器數(shù)據(jù)流編碼流字典譯碼器譯碼器Page 13字典的產(chǎn)生字典的產(chǎn)生字典不是事先創(chuàng)

6、建好的，而是根據(jù)原始文件數(shù)據(jù)動(dòng)態(tài)創(chuàng)建的。提取原始文本文件數(shù)據(jù)中的不同字符，分成一段一段。將這些段存入字典，然后用字典中段的索引來替代原始文本文件數(shù)據(jù)中的相應(yīng)分段，減少原始數(shù)據(jù)大小。Page 14段號(hào)段號(hào) 短語短語編碼步驟：編碼步驟：（1）新建一個(gè)字典，讀取第一個(gè)符號(hào)作為第一段短語存入字典；取下一符號(hào)作為新的段起點(diǎn)繼續(xù)分段。AACDBBAACDDB1A234567ACDBBAACDDB數(shù)據(jù)流數(shù)據(jù)流0A 1C編碼流編碼流（2）若現(xiàn)有的段與字典中的短語相同時(shí)，再取緊跟后面的一個(gè)符號(hào)組成新的段，把該段作為短語存入字典。重復(fù)該過程直到編碼結(jié)束。0D 0B 4A 2D 3B碼字前綴的段號(hào)結(jié)束符號(hào),對(duì)于單符號(hào)的短語，相應(yīng)的段號(hào)為0。Page 15n無損壓縮，適