多媒體技術(shù)-圖像與視頻壓縮(1)資料

1、 第七章 圖像(t xin)與視頻壓縮（1）共八十頁(yè)第七章 圖像(t xin)與視頻壓縮1 通用(tngyng)數(shù)據(jù)壓縮2 多媒體數(shù)據(jù)壓縮共八十頁(yè)1 通用(tngyng)數(shù)據(jù)壓縮1.1 數(shù)據(jù)壓縮概述1.2 數(shù)據(jù)壓縮主要(zhyo)方法游程編碼統(tǒng)計(jì)編碼字典編碼共八十頁(yè)數(shù)據(jù)壓縮(sh j y su)-定義 “數(shù)據(jù)壓縮(sh j y su)”在漢英詞典中的解釋： data compression (A method of reducing the amount of memory required to store data by encoding it and minimizing redunda

2、ncy. Compressed data takes less time to transmit, but more computation time to restore it to its original form when needed for processing.)共八十頁(yè)數(shù)據(jù)壓縮(sh j y su)-作用 通俗地說(shuō)，就是用最少的數(shù)碼來(lái)表示信號(hào)。其作用是：能較快地傳輸各種信號(hào)，如傳真、Modem通信等；在現(xiàn)有的通信干線并行開(kāi)通更多的多媒體業(yè)務(wù)，如各種增值業(yè)務(wù)；緊縮數(shù)據(jù)(shj)存儲(chǔ)容量，如CDROM、VCD和DVD等；降低發(fā)信機(jī)功率，這對(duì)于多媒體移動(dòng)通信系統(tǒng)尤為重要。由此看來(lái)，通

3、信時(shí)間、傳輸帶寬、存儲(chǔ)空間甚至發(fā)射能量，都可能成為數(shù)據(jù)壓縮的目的。 共八十頁(yè)數(shù)據(jù)壓縮(sh j y su)-概要 在計(jì)算機(jī)科學(xué)和信息論中，數(shù)據(jù)壓縮或者信源編碼(bin m)是按照特定的編碼(bin m)機(jī)制用比未經(jīng)編碼(bin m)少的數(shù)據(jù)位元（或者其它信息相關(guān)的單位）表示信息的過(guò)程。例如，如果我們將“compression”編碼為“comp”那么這篇文章可以用較少的數(shù)據(jù)位表示。一種流行的壓縮實(shí)例是許多計(jì)算機(jī)都在使用的ZIP 文件格式，它不僅僅提供了壓縮的功能，而且還作為歸檔工具Archive使用，能夠?qū)⒃S多文件存儲(chǔ)到同一個(gè)文件中。共八十頁(yè)數(shù)據(jù)壓縮(sh j y su)-概要 對(duì)于任何形式的通

4、信來(lái)說(shuō)，只有當(dāng)信息的發(fā)送方和接受方都能夠理解編碼機(jī)制的時(shí)候壓縮數(shù)據(jù)通信才能夠工作。例如，只有當(dāng)接受方知道這篇文章需要用英語(yǔ)(yn y)字符解釋的時(shí)候這篇文章才有意義。同樣，只有當(dāng)接受方知道編碼方法的時(shí)候他才能夠理解壓縮數(shù)據(jù)。一些壓縮算法利用了這個(gè)特性，在壓縮過(guò)程中對(duì)數(shù)據(jù)進(jìn)行加密，例如利用密碼加密，以保證只有得到授權(quán)的一方才能正確地得到數(shù)據(jù)。共八十頁(yè)數(shù)據(jù)壓縮(sh j y su)-概要 數(shù)據(jù)壓縮能夠?qū)崿F(xiàn)是因?yàn)槎鄶?shù)現(xiàn)實(shí)世界的數(shù)據(jù)都有各種冗余。例如，字母“e”在英語(yǔ)中比字母“z”更加常用，字母“q”后面是“z”的可能性非常小。無(wú)損壓縮算法(sun f)通常利用利用了統(tǒng)計(jì)冗余，這樣就能更加簡(jiǎn)練地、但仍

5、然是完整地表示發(fā)送方的數(shù)據(jù)。 如果允許一定程度的保真度損失，那么還可以實(shí)現(xiàn)進(jìn)一步的壓縮。例如，人們看圖畫(huà)或者電視畫(huà)面的時(shí)候可能并不會(huì)注意到一些細(xì)節(jié)并不完善。同樣，兩個(gè)音頻錄音采樣序列可能聽(tīng)起來(lái)一樣，但實(shí)際上并不完全一樣。有損壓縮算法在帶來(lái)微小差別的情況下使用較少的位數(shù)表示圖像、視頻或者音頻。共八十頁(yè)數(shù)據(jù)壓縮(sh j y su)-概要 由于可以幫助減少如硬盤(pán)空間與連接帶寬這樣的昂貴資源的消耗，所以壓縮非常重要，然而壓縮需要消耗信息處理資源，這也可能是費(fèi)用昂貴的。所以數(shù)據(jù)壓縮機(jī)制的設(shè)計(jì)需要在壓縮能力、失真度、所需計(jì)算資源以及(yj)其它需要考慮的不同因素之間進(jìn)行折衷。共八十頁(yè)數(shù)據(jù)壓縮(sh j

6、y su)-應(yīng)用 一種非常簡(jiǎn)單的壓縮方法是行程長(zhǎng)度編碼，這種方法使用數(shù)據(jù)及數(shù)據(jù)長(zhǎng)度這樣簡(jiǎn)單的編碼代替同樣的連續(xù)數(shù)據(jù)，這是無(wú)損數(shù)據(jù)壓縮的一個(gè)實(shí)例。這種方法經(jīng)常(jngchng)用于辦公計(jì)算機(jī)以更好地利用磁盤(pán)空間、或者更好地利用計(jì)算機(jī)網(wǎng)絡(luò)中的帶寬。對(duì)于電子表格、文本、可執(zhí)行文件等這樣的符號(hào)數(shù)據(jù)來(lái)說(shuō)，無(wú)損是一個(gè)非常關(guān)鍵的要求，因?yàn)槌艘恍┯邢薜那闆r，大多數(shù)情況下即使是一個(gè)數(shù)據(jù)位的變化都是無(wú)法接受的。共八十頁(yè)數(shù)據(jù)壓縮(sh j y su)-應(yīng)用 對(duì)于視頻和音頻數(shù)據(jù)，只要不損失數(shù)據(jù)的重要部分一定程度的質(zhì)量下降是可以接受的。通過(guò)利用人類(lèi)感知系統(tǒng)的局限，能夠大幅度得節(jié)約存儲(chǔ)空間并且得到的結(jié)果質(zhì)量與原始數(shù)據(jù)質(zhì)

7、量相比并沒(méi)有明顯的差別。這些有損數(shù)據(jù)壓縮方法通常需要在壓縮速度、壓縮數(shù)據(jù)大小以及質(zhì)量損失三者之間進(jìn)行折衷。 有損圖像壓縮用于數(shù)碼相機(jī)(sh m xin j)中，大幅度地提高了存儲(chǔ)能力，同時(shí)圖像質(zhì)量幾乎沒(méi)有降低。用于DVD的有損MPEG-2編解碼視頻壓縮也實(shí)現(xiàn)了類(lèi)似的功能。共八十頁(yè)數(shù)據(jù)壓縮(sh j y su)-應(yīng)用 在有損音頻壓縮中，心理聲學(xué)的方法用來(lái)去除信號(hào)中聽(tīng)不見(jiàn)或者很難聽(tīng)見(jiàn)的成分。人類(lèi)語(yǔ)音的壓縮經(jīng)常使用更加專業(yè)的技術(shù)，因此人們有時(shí)也將“語(yǔ)音壓縮”或者“語(yǔ)音編碼”作為一個(gè)獨(dú)立的研究領(lǐng)域(ln y)與“音頻壓縮”區(qū)分開(kāi)來(lái)。不同的音頻和語(yǔ)音壓縮標(biāo)準(zhǔn)都屬于音頻編解碼范疇。例如語(yǔ)音壓縮用于因特網(wǎng)電

8、話，而音頻壓縮被用于CD翻錄并且使用 MP3 播放器解碼。共八十頁(yè)數(shù)據(jù)壓縮(sh j y su)-理論 壓縮的理論基礎(chǔ)是信息論（它與算法信息論密切相關(guān)）以及率失真理論，這個(gè)領(lǐng)域的研究(ynji)工作主要是由 Claude Shannon 奠定的，他在二十世紀(jì)四十年代末期及五十年代早期發(fā)表了這方面的基礎(chǔ)性的論文。 Doyle 和 Carlson 在2000年寫(xiě)道數(shù)據(jù)壓縮“是所有的工程領(lǐng)域最簡(jiǎn)單、最優(yōu)美的設(shè)計(jì)理論之一”。密碼學(xué)與編碼理論也是密切相關(guān)的學(xué)科，數(shù)據(jù)壓縮的思想與統(tǒng)計(jì)推斷也有很深的淵源。共八十頁(yè)數(shù)據(jù)壓縮(sh j y su)-理論 許多無(wú)損數(shù)據(jù)壓縮系統(tǒng)都可以看作是四步模型，有損數(shù)據(jù)壓縮系統(tǒng)

9、通常包含更多的步驟，例如它包括預(yù)測(cè)、頻率(pnl)變換以及量化。 Lempel-Ziv（LZ）壓縮方法是最流行的無(wú)損存儲(chǔ)算法之一。DEFLATE是 LZ 的一個(gè)變體，它針對(duì)解壓速度與壓縮率進(jìn)行了優(yōu)化，雖然它的壓縮速度可能非常緩慢，PKZIP、gzip 以及 PNG 都在使用EFLATE。LZW （Lempel-Ziv-Welch）是 Unisys 的專利，直到2003年6月專利到期限，這種方法用于 GIF 圖像。 共八十頁(yè)數(shù)據(jù)壓縮(sh j y su)-理論 最好的壓縮工具將概率模型預(yù)測(cè)結(jié)果用于算術(shù)編碼。算術(shù)編碼由 Jorma Rissanen 發(fā)明，并且由 Witten、Neal 以及(yj

10、) Cleary 將它轉(zhuǎn)變成一個(gè)實(shí)用的方法。這種方法能夠?qū)崿F(xiàn)比眾人皆知的哈夫曼算法更好的壓縮，并且它本身非常適合于自適應(yīng)數(shù)據(jù)壓縮，自適應(yīng)數(shù)據(jù)壓縮的預(yù)測(cè)與上下文密切相關(guān)。算術(shù)編碼已經(jīng)用于二值圖像壓縮標(biāo)準(zhǔn) JBIG、文檔壓縮標(biāo)準(zhǔn) DejaVu。文本 輸入系統(tǒng) Dasher 是一個(gè)逆算術(shù)編碼器。共八十頁(yè)1 通用(tngyng)數(shù)據(jù)壓縮1.1 數(shù)據(jù)壓縮概述(i sh)1.2 數(shù)據(jù)壓縮主要方法游程編碼統(tǒng)計(jì)編碼字典編碼共八十頁(yè)游程(yu chn)編碼（RLE）思想：如果數(shù)據(jù)項(xiàng)d在輸入流中出現(xiàn)n次，則以單個(gè)字符對(duì)nd替換n次出現(xiàn)者。這個(gè)連續(xù)出現(xiàn)的數(shù)據(jù)項(xiàng)叫做游程n，這種數(shù)據(jù)壓縮方法稱為(chn wi)游程編碼

11、或RLERLE文本壓縮RLE圖像壓縮共八十頁(yè)RLE文本(wnbn)壓縮 2. all is too well 2. a2l is t2o we2l一個(gè)解決方法就是在重復(fù)部分前綴一個(gè)特殊的提示字符(z f)，我們用作提示，則字符串被替換成: 2. a2l is t2o we2l共八十頁(yè) RLE 文本壓縮的步驟 讀入第一個(gè)字符后，計(jì)數(shù)值為1，保存(bocn)該字符。將后續(xù)字符與已保存(bocn)者相比較，相同則重復(fù)計(jì)數(shù)器加1。如果讀入一個(gè)不同字符，則操作取決于重復(fù)次數(shù)：如果次數(shù)很小，把已保存的字符寫(xiě)入壓縮文件，保存新讀入的字符；否則先寫(xiě)一個(gè)，在輸出重復(fù)次數(shù)及被保存的字符。下圖是游程文本壓縮器的流程

12、圖共八十頁(yè) 共八十頁(yè) RLE 文本解壓的步驟：一旦讀入一個(gè)(y )，則立即讀入重復(fù)次數(shù)及實(shí)際字符，并在輸出流中重復(fù)寫(xiě)該字符n次。共八十頁(yè) 共八十頁(yè) RLE 方法(fngf)存在的問(wèn)題普通英文中并沒(méi)有多少重復(fù)。有許多雙寫(xiě)，但是很少有3次重復(fù)的。 在輸入流中，字符可能(knng)是文本的一部分，此時(shí)必須選一個(gè)不同的提示字符。由于重復(fù)計(jì)數(shù)值以字節(jié)形式寫(xiě)在輸出流中，只能計(jì)到255。共八十頁(yè) RLE的壓縮比 假設(shè)待壓縮字符長(zhǎng)度為N，字符中包含M次重復(fù)，每次重復(fù)的平均長(zhǎng)度為L(zhǎng)。M次中的每一次重復(fù)可用3字節(jié)(z ji)代替，因此，壓縮后字符串的長(zhǎng)度為N-M(L-3)，壓縮因子為 N/(N-M(L-3)如果N

13、=1000,M=10,L=4,則壓縮因子1.01， 如果N=1000,M=50,L=10 壓縮因子1.538共八十頁(yè)RLE圖像壓縮二值圖像灰度圖像彩色圖像 RLE圖像壓縮基于這樣的事實(shí)：如果我們?cè)谠搱D像中隨機(jī)(su j)選擇一個(gè)像素，其相鄰像素色彩相同的可能性很大，因此壓縮器逐行掃描位圖，搜索色彩相同之像素的游程。共八十頁(yè)二值圖像(t xin)假設(shè)圖像(t xin)從黑像素或白像素開(kāi)始，按行掃描位圖，給出黑白像素的游程。例如：開(kāi)始17個(gè)白像素，其后跟隨一個(gè)黑像素，再跟55個(gè)白像素等，則把17，1，55，寫(xiě)入壓縮流。共八十頁(yè)灰度圖像(t xin)12,12,12,12,12,12,12,12,1

14、2,35,76,112,67,87,87,87,5,5,5,5,5,5,1, 被壓縮為9，12，35，76，112，67，3，87，6，5，1，我們要區(qū)分是含灰度值的字節(jié)和含計(jì)數(shù)值的字節(jié)，解決(jiju)方法如下：共八十頁(yè)區(qū)分(qfn)灰度值和游程的方法如果圖像限制為只有128級(jí)灰度，我們可以用每個(gè)字節(jié)中的一位來(lái)表示該字節(jié)所含的是灰度值還是計(jì)數(shù)值。如果灰度級(jí)為256，則可降為255，保留一個(gè)值作標(biāo)志，至于(zhy)每個(gè)游程計(jì)數(shù)字節(jié)之前。每字節(jié)均加一位，以表示該字節(jié)所含是灰度值還是計(jì)數(shù)值。此時(shí)這些附加位每8個(gè)累計(jì)為一組，每組先于其所屬的8個(gè)字節(jié)寫(xiě)到輸出流中共八十頁(yè)彩色圖像對(duì)于(duy)彩色圖像，

15、通常將每像素存為3個(gè)字節(jié)，代表其紅、綠、藍(lán)3基色的強(qiáng)度，因此把像素分成3個(gè)序列，每一序列分別游程編碼。（171,85,34）、(172,85,35)、(172,85,30)、(173,85,33)共八十頁(yè)各行單獨(dú)(dnd)編碼的原因有時(shí)用戶只查看圖像的一般形狀不需要細(xì)節(jié)，各行單獨(dú)編碼可以各行解碼。逐步(zhb)重建可以只抽取圖像的一部分合并兩幅圖像不必先解碼共八十頁(yè)1 通用(tngyng)數(shù)據(jù)壓縮1.1 數(shù)據(jù)壓縮概述(i sh)1.2 數(shù)據(jù)壓縮主要方法游程編碼統(tǒng)計(jì)編碼字典編碼共八十頁(yè)統(tǒng)計(jì)(tngj)編碼香農(nóng)-費(fèi)諾編碼(bin m)哈夫曼編碼算術(shù)編碼共八十頁(yè)香農(nóng)-費(fèi)諾編碼(bin m)信息的度量

16、變長(zhǎng)碼特性(txng)香農(nóng)費(fèi)諾編碼共八十頁(yè)信息(xnx)的度量給定一個(gè)k位十進(jìn)制數(shù)和一個(gè)k位二進(jìn)制數(shù)，一個(gè)很自然的問(wèn)題是，這兩個(gè)k數(shù)位(shwi)包含了多少信息？這可以通過(guò)計(jì)算它們?yōu)楸硎就粋€(gè)數(shù)而各自所需的位數(shù)來(lái)回答。 共八十頁(yè)給定一個(gè)n進(jìn)制數(shù)，有 ，即1位n進(jìn)制數(shù)所含的信息相當(dāng)于 位二進(jìn)制數(shù)包含的信息。如果(rgu)發(fā)射機(jī)傳送一個(gè)符號(hào)需要1/s單位時(shí)間，則其傳送速率是每單位時(shí)間s個(gè)符號(hào)。在一個(gè)單位時(shí)間內(nèi)發(fā)射機(jī)可以發(fā)出s個(gè)符號(hào)，包含的信息量是 位。我們用 表示信息量，單位為位數(shù)/單位時(shí)間。信息(xnx)的度量共八十頁(yè)假設(shè) 在數(shù)據(jù)(shj)中出現(xiàn)的概率是 ，自然有 在 的等概率特例下，由 可推出

17、： 假定數(shù)據(jù)是由 到 所生成的字符串，這樣一個(gè)集合就是(jish)一個(gè)有n個(gè)符號(hào)的字母表。信息的度量共八十頁(yè) 在數(shù)據(jù)中出現(xiàn)的概率是 ，那么它在單位時(shí)間內(nèi)平均(pngjn)出現(xiàn)了 次，因此它對(duì)H的貢獻(xiàn)是那么n個(gè)符號(hào)對(duì)H的貢獻(xiàn)之和是： 這里H表示信息量，是單位時(shí)間傳送的符號(hào)位數(shù)。所以一個(gè)n進(jìn)制符號(hào)所含有(hn yu)的信息量就是H/S（因其需要1/s時(shí)間傳送一個(gè)符號(hào)）或 ，稱為被傳送數(shù)據(jù)的熵（entropy）信息的度量共八十頁(yè)變長(zhǎng)碼 符號(hào) 概率(gil) 編碼1 編碼2 0.49 1 1 0.25 01 01 0.25 010 000 0.01 001 001共八十頁(yè)因而遵循以下兩條規(guī)則(guz)

18、就可以設(shè)計(jì)變長(zhǎng)碼：（1）把短碼賦給出現(xiàn)頻率高的字符；（2）遵循前綴性。共八十頁(yè)香農(nóng)費(fèi)諾編碼(bin m)按概率把符號(hào)從大到小排序?qū)⑦@些符號(hào)劃分成概率幾乎相同的兩個(gè)子集一個(gè)(y )子集以開(kāi)始，另一個(gè)(y )以開(kāi)始在按照同樣的步驟劃分這兩個(gè)子集，一直到子集不能被劃分共八十頁(yè)香農(nóng)-費(fèi)諾編碼(bin m) 概率(gil) 步驟 碼字 1. 0.25 1 1 :11 2. 0.20 1 0 :10 3. 0.15 0 1 1 :011 4. 0.15 0 1 0 :010 5. 0.10 0 0 1 :001 6. 0.10 0 0 0 1 :0001 7. 0.05 0 0 0 0 :0000共八十頁(yè)

19、練習(xí)(linx)首先從第3個(gè)和第4個(gè)符號(hào)中間(zhngjin)劃分子集，計(jì)算平均碼長(zhǎng)？共八十頁(yè)統(tǒng)計(jì)(tngj)編碼香農(nóng)-費(fèi)諾編碼(bin m)哈夫曼編碼算術(shù)編碼共八十頁(yè)哈夫曼編碼(Huffman Coding)是可變長(zhǎng)編碼(VLC)的一種。 Huffman于1952年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來(lái)構(gòu)造異字頭的平均長(zhǎng) 度最短的碼字，有時(shí)稱之為最佳編碼 在計(jì)算機(jī)信息處理中，“哈夫曼編碼”是一種一致性編碼法（又稱熵編碼法），用于數(shù)據(jù)的無(wú)損耗壓縮。這一術(shù)語(yǔ)是指使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個(gè)(y )符號(hào)）進(jìn)行編碼。這張編碼表的特殊之處在于，它是根據(jù)每一個(gè)(y )源字符出

20、現(xiàn)的估算概率而建立起來(lái)的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長(zhǎng)的編碼，這便使編碼之后的字符串的平均期望長(zhǎng)度降低，從而達(dá)到無(wú)損壓縮數(shù)據(jù)的目的）。 哈夫曼（Huffman）碼共八十頁(yè) 例如，在英文中e出現(xiàn)概率很高，而z出現(xiàn)概率則最低。 當(dāng)利用(lyng)哈夫曼編碼對(duì)一篇英文進(jìn)行壓縮時(shí)，e極有可能用一個(gè)位(bit)來(lái)表示，而z則可能花去25個(gè)位（不是26）。用普通的表示方法時(shí)，每個(gè)英文字母均占用一個(gè)字節(jié)（byte），即8個(gè)位。 二者相比，e使用了一般編碼的1/8的長(zhǎng)度，z則使用了3倍多。倘若我們能實(shí)現(xiàn)對(duì)于英文中各個(gè)字母出現(xiàn)概率的較準(zhǔn)確的估算，就可以大幅度提高無(wú)損壓縮的比例。 哈

21、夫曼（Huffman）碼共八十頁(yè) 哈夫曼壓縮是個(gè)無(wú)損的壓縮算法，一般用來(lái)壓縮文本(wnbn)和程序文件。哈夫曼壓縮屬于可變代碼長(zhǎng)度算法一族。意思是個(gè)體符號(hào)（例如，文本(wnbn)文件中的字符）用一個(gè)特定長(zhǎng)度的位序列替代。因此，在文件中出現(xiàn)頻率高的符號(hào)，使用短的位序列，而那些很少出現(xiàn)的符號(hào)，則用較長(zhǎng)的位序列。 哈夫曼（Huffman）碼共八十頁(yè)一、二進(jìn)制哈夫曼編碼1.步驟(bzhu)(1) 信源符號(hào)按概率分布大小，以遞減次序排列； (2) 取兩個(gè)最小的概率，分別賦以“0”,“1”;然后把這兩個(gè)概率值相加，作為新概率值與其他概率重新排序(3) 按重排概率值，重復(fù)(2), 直到概率和達(dá)到1為止(4)

22、 由后向前排列碼序，即得哈夫曼編碼哈夫曼（Huffman）碼共八十頁(yè)2. 例題 x1 0.4 x2 0.2 x3 0.2 x4 0.1 x5 0.1平均(pngjn)碼長(zhǎng)碼方差12=E(li-L)2=p(xi) (li-L)2 = 1.36 0.20.40.61.001010101X:p(x)(0.4,0.2,0.2,0.1,0.1)（合并(hbng)后概率下放）哈夫曼（Huffman）碼01100000100011共八十頁(yè)方法一：合并后的新符號(hào)排在其它相同概率(gil)符號(hào)的后面；哈夫曼（Huffman）碼共八十頁(yè) 3. 上例00 x1 0.4 10 x2 0.211 x3 0.2010 x

23、4 0.1011 x5 0.1010.20.40.61.0010101（合并(hbng)后概率上放）哈夫曼（Huffman）碼共八十頁(yè) 3. 上例00 x1 0.4 10 x2 0.211 x3 0.2010 x4 0.1011 x5 0.1 平均碼長(zhǎng) 碼方差22 = 0.16 兩法平均碼長(zhǎng)相同(xin tn)，故信息率R、冗余度相同；但碼方差不同，碼方差小要好.010.20.40.61.0010101（合并(hbng)后概率上放）哈夫曼（Huffman）碼共八十頁(yè)方法二：合并后的新符號(hào)排在其它相同(xin tn)概率符號(hào)的前面.哈夫曼（Huffman）碼共八十頁(yè)兩種編碼的平均碼長(zhǎng)是一樣的，都

24、是2.2，那一種更好呢，我們可以(ky)計(jì)算一下平均碼長(zhǎng)的方差。定義(dngy)碼字長(zhǎng)度的方差2：哈夫曼（Huffman）碼共八十頁(yè)可見(jiàn)：第二種編碼方法的碼長(zhǎng)方差要小許多。意味著第二種編碼方法的碼長(zhǎng)變化較小，比較接近于平均碼長(zhǎng)。第一種方法編出的5個(gè)碼字有4種不同的碼長(zhǎng)；第二種方法編出的碼長(zhǎng)只有兩種不同的碼長(zhǎng)；顯然，第二種編碼方法更簡(jiǎn)單、更容易實(shí)現(xiàn)，所以更好。結(jié)論：在哈夫曼編碼過(guò)程中，對(duì)縮減(sujin)信源符號(hào)按概率由大到小的順序重新排列時(shí)，應(yīng)使合并后的新符號(hào)盡可能排在靠前的位置，這樣可使合并后的新符號(hào)重復(fù)編碼次數(shù)減少，使短碼得到充分利用。哈夫曼（Huffman）碼共八十頁(yè) 3. 上例00 x

25、1 0.4 10 x2 0.211 x3 0.2010 x4 0.1011 x5 0.1 平均碼長(zhǎng) 結(jié)論 碼方差22 = 0.16 兩法平均碼長(zhǎng)相同(xin tn)，故信息率R、冗余度相同；但碼方差不同，碼方差小要好.010.20.40.61.0010101（合并(hbng)后概率上放）哈夫曼（Huffman）碼共八十頁(yè)定理：在變長(zhǎng)編碼中，若各碼字長(zhǎng)度嚴(yán)格按照所對(duì)應(yīng)符號(hào)出現(xiàn)概率的大小逆序排列，則其平均(pngjn)長(zhǎng)度為最小。結(jié)論：哈夫曼編碼方法，它完全依據(jù)字符出現(xiàn)概率來(lái)構(gòu)造平均長(zhǎng)度最短的異字頭碼字，有時(shí)稱之為最佳編碼。 哈夫曼（Huffman）碼共八十頁(yè) 應(yīng)該指出的是，由霍夫曼編碼(bin

26、m)過(guò)程編出的最佳碼不是唯一的，但其平均碼長(zhǎng)是一樣的，故不影響編碼(bin m)效率與數(shù)據(jù)壓縮性能。 此外，由于碼長(zhǎng)不等，還存在一個(gè)輸入與輸出的速率匹配問(wèn)題。解決的辦法是設(shè)置一定容量的緩沖寄存器。 而隨著微電子與計(jì)算技術(shù)的發(fā)展，霍夫曼編碼已可做成單片IC，并成為許多國(guó)際標(biāo)準(zhǔn)中的主要技術(shù)內(nèi)核之一。能夠用較低的處理代價(jià)，來(lái)?yè)Q取昂貴的通信開(kāi)銷(xiāo)，是完全值得的。哈夫曼（Huffman）碼方差(fn ch)最小者最佳共八十頁(yè)0.60010.090.130.190.230.371.00101010101010100 x5 0.070101 x6 0.0600010 x7 0.0500011 x8 0.040

27、11 x3 0.10000 x4 0.1001 x2 0.18 1 x1 0.4010010110101010000000001000011哈夫曼（Huffman）碼4.例題(lt)X:p(x)(0.4,0.18,0.1,0.1,0.07, 0.06,0.05,0.04)共八十頁(yè)二、D進(jìn)制哈夫曼編碼1. 編碼步驟同二進(jìn)制，但需注意兩點(diǎn)：每次取最小的D個(gè)概率,分別賦以0,1, D-1；信源符號(hào)(fho)個(gè)數(shù)r必須滿足：r=(D-1)+D. 當(dāng)r不滿足時(shí)，在信源符號(hào)集中補(bǔ)充一些對(duì)應(yīng)概率為0的符號(hào).哈夫曼（Huffman）碼共八十頁(yè) 2.例題(lt)某離散無(wú)記憶信源符號(hào)集a1,a2,a3,a4,a5

28、,a6,a7,a8，a9，已知所對(duì)應(yīng)的概率，試對(duì)其進(jìn)行四元(s yun)編碼！ 哈夫曼（Huffman）碼解：其中D=4. 若取=2可得大于9但與9最接近的正整數(shù)10，因此在編碼時(shí)加入一個(gè)零概率符號(hào).對(duì)其進(jìn)行四元編碼： 共八十頁(yè) 哈夫曼（Huffman）碼共八十頁(yè)哈夫曼碼考慮了信源的統(tǒng)計(jì)特性，使經(jīng)常出現(xiàn)的信源符號(hào)對(duì)應(yīng)較短的碼字，使信源的平均碼長(zhǎng)縮短(sudun)，從而實(shí)現(xiàn)了對(duì)信源的壓縮；哈夫曼碼的編碼方法都不惟一；哈夫曼碼對(duì)信源的統(tǒng)計(jì)特性沒(méi)有特殊要求，編碼效率比較高，因此綜合性較優(yōu).哈夫曼（Huffman）碼共八十頁(yè)Huffman碼在具體實(shí)用時(shí)，設(shè)備較復(fù)雜.在編碼器中需要增加緩沖寄存器，因?yàn)槊?/p>

29、個(gè)信源符號(hào)所對(duì)應(yīng)的碼符號(hào)長(zhǎng)度不一，負(fù)責(zé)會(huì)造成輸入和輸出不能保持平衡.優(yōu)點(diǎn)：提高編碼效率；缺點(diǎn)：需要大量緩沖設(shè)備來(lái)存儲(chǔ)這些變長(zhǎng)碼，然后再以恒定(hngdng)的碼率進(jìn)行傳送；在傳輸?shù)倪^(guò)程中如果出現(xiàn)了誤碼，容易引起錯(cuò)誤擴(kuò)散，所以要求有優(yōu)質(zhì)的信道。哈夫曼（Huffman）碼共八十頁(yè)哈夫曼碼也是譯碼的工具(gngj)：哈夫曼（Huffman）碼共八十頁(yè)0.60010.090.130.190.230.371.00101010101010100 x5 0.070101 x6 0.0600010 x7 0.0500011 x8 0.04011 x3 0.10000 x4 0.1001 x2 0.18 1 x

30、1 0.40哈夫曼（Huffman）碼4.例題(lt)X:p(x)(0.4,0.18,0.1,0.1,0.07, 0.06,0.05,0.04)共八十頁(yè)10010110101010000000001000011哈夫曼（Huffman）碼4.例題(lt) X:p(x)(0.4,0.18,0.1,0.1,0.07,0.06,0.05,0.04)若接收(jishu)的字符串是：00010100101100011000101001011000110001010010110001100010100101100011共八十頁(yè)統(tǒng)計(jì)(tngj)編碼香農(nóng)-費(fèi)諾編碼(bin m)哈夫曼編碼算術(shù)編碼共八十頁(yè)算術(shù)(s

31、unsh)編碼算法思想Huffman編碼中每個(gè)符號(hào)都用整數(shù)個(gè)bits來(lái)表示，影響編碼效率。若能把一串符號(hào)作為編碼單位，則效率還可提高。符號(hào)串的區(qū)間(q jin)表示法設(shè)符號(hào)串為：bacedbbdea 則它可以映射成為0，1）中的唯一的一個(gè)子區(qū)間。共八十頁(yè)00.20.50.60.81abcdeabcdeabcdeabcde0.2b 0.5a 0.260.2360.20.23字符abcde概率0.20.30.10.20.2范圍0,0.2)0.2,0.5)0.5,0.6)0.6,0.8)0.8,1.0)共八十頁(yè)high為編碼區(qū)間的高端,low為低端,range為區(qū)間長(zhǎng)度, lowrange為字符(z

32、 f)分配區(qū)間的低端 highrange 為區(qū)間的高端。初始化： high=1,low=0,range=high-low=1 一個(gè)字符編碼后新的low和high為：Low=low+range* lowrangeHigh=low+range* highrange0子區(qū)間1lowhighrangelowrangehigh共八十頁(yè)計(jì)算過(guò)程： 1）將 0，1）區(qū)間按照概率的比例(bl)分配給五個(gè)字符，即（如圖形表示）： a= 0，0.2， b= 0.2，0.5, c= 0.5，0.6 d= 0.6，0.8 e= 0.8，1)high=1,low=0,range=high-low=1 2)輸入第一個(gè)字符

33、 b，得b.high=0.5,b.low=0.2b.range=b.high-b.low=0.3 3)將 0.2，0.5）區(qū)間按照概率的比例分配給五個(gè)字符，如圖形表示。共八十頁(yè) 4)輸入第二個(gè)字符 a，得a.high=0.26,a.low=0.2a.range=a.high-a.low=0.06 5)將 0.2，0.26）區(qū)間按照概率的比例分配給五個(gè)字符，如圖形表示。 6)輸入第三個(gè)字符 c，得c.high=0.236,c.low=0.23c.range=c.high-c.low=0.006依次重復(fù)輸入后續(xù)字符，重復(fù)執(zhí)行5)-6）步,直到輸入最后一個(gè)字符。在最后這個(gè)區(qū)間內(nèi)選擇ENDc.low

34、, 將它變成二進(jìn)制 ，去掉前面的 0 和小數(shù)點(diǎn)，我們可以(ky)輸出二進(jìn)制數(shù)這就是被壓縮后的結(jié)果。共八十頁(yè) 編碼過(guò)程首先定義Low和High兩個(gè)變量，并設(shè)置 Low0 High1當(dāng)讀入和處理字符時(shí)，Low和High按照如下方式更新 NewHigh：OldLow+RangeHighRange（X）; NewLow：OldLow+RangeLowRange（X）；其中RangeOldHighOldLow， LowRange（X）和HighRange（X）表示符號(hào)(fho)X所對(duì)應(yīng)區(qū)間的下限和上限。共八十頁(yè) 例：給出對(duì)短串“SWISS MISS”的壓縮步驟。 字符 頻率(pnl) 概率 范圍 累計(jì)頻

35、率(pnl) Total CumFreq 10 S 5 5/10=0.5 0.5,1.0) 5 W 1 0.1 0.4,0.5) 4 I 2 0.2 0.2,0.4) 2 M 1 0.1 0.1,0.2) 1 1 0.1 0.0,0.1) 0 概率和頻率表共八十頁(yè) 算法編碼過(guò)程(guchng) 字符 Low和High的計(jì)算 S L 0.0+(1-0.0) 0.5=0.5 H 0.0+(1-0.0) 1.0=1.0 W L 0.5+(1.0-0.5) 0.4=0.7 H 0.5+(1.0-0.5) 0.5=0.75 I L 0.7+(0.75-0.70) 0.2=0.71 H 0.7+(0.75

36、-0.70) 0.4=0.72 S L 0.71+(0.72-0.71) 0.5=0.715 H 0.71+(0.72-0.71) 1.0=0.72共八十頁(yè) S L 0.715+(0.72-0.715) 0.5=0.7175 H 0.715+(0.72-0.715) 1.0=0.72 L 0.7175+(0.72-0.7175) 0.0=0.7175 H 0.7175+(0.72-0.7175) 0.1=0.71775 M L 0.7175+(0.71775-0.7175) 0.1=0.717525 H 0.7175+(0.71775-0.0.7175) 0.2=0.71755 I L 0.717525+(0.71755-0.717525) 0.2=0.717530 H 0.717525+(0.71755-0.717525) 0.4=0.717535 S L0.717530+(0.717535-0.717530) 0.5=0.7