【正文】 111 要求：畫(huà)出碼樹(shù)！ ? 將下列消息按二元費(fèi)諾方法編碼并計(jì)算編碼效率 ? 分別進(jìn)行二元先農(nóng)編碼和費(fèi)諾編碼，并計(jì)算編碼效率 }0 6 2 ,0 6 2 ,1 2 ,0 6 2 ,0 6 2 ,1 2 {)(},{ 87654321??XPxxxxxxxxX?????????????????12811281641321161814121)(87654321 xxxxxxxxXPX112 ? M=(m1 m2 m3 m4 m5 m6) ? P(m)=( ) ? 進(jìn)行霍夫曼編碼 113 s y m b o lb i txpxpXHiii/128l o g1281128l o g128164l o g64132l o g32116l o g1618l o g814l o g412l o g21)(l o g)()(22222222812??????????????????? ??xi p(xi) pa(xi) ki 碼字 x1 0 1 0 x2 2 10 x3 3 110 x4 4 1110 x5 5 11110 x6 6 111110 x7 7 1111110 x8 7 1111111 114 xi p(xi) 編碼 碼字 ki x1 0 0 1 x2 1 0 10 2 x3 1 0 110 3 x4 1 0 1110 4 x5 1 0 11110 5 x6 1 0 111110 6 x7 1 0 1111110 7 x8 1 1111111 7 %1 009 9 )()(9 71 28171 281664153214161381241121)(?????????????????????? ?KXHRXHxpkKiii?115 ? H= L= ? 編碼效率 =1 116 117 ? 118 ? 。 ?????????????)()(0010)()()(aapAaAPACaC??????????????????0 0 )()()()()(bbpaAabAPaAaCabC104 常用信源編碼方法簡(jiǎn)介 ?????????????????0 0 0 0 0 )()(0 1 0 1 1 )()()(ddpabAabdAPabAabCabdC105 常用信源編碼方法簡(jiǎn)介 ?????????????????0 0 0 0 0 0 0 0 0 0 )()(0 1 0 1 1 0 0 0 0 1 0 1 1 )()()(aapabdAa b d aAPabdAabdCa b d aCC(abda)即為編碼后的碼字 010111 106 常用信源編碼方法簡(jiǎn)介 A(?) A(a) a b c d A(a,b) a b c d a b c d A(a,b,d) C(?) 0(Pa) pa Pb pb Pc pc Pd pd 1 C(0) C(a,b,d) C(a,b) 算術(shù)編碼過(guò)程 107 常用信源編碼方法簡(jiǎn)介 譯碼 ?C(abda)=?[0,] 第一個(gè)符號(hào)為 a 放大至 [0,1]( pa1)： ?C(abda) 21＝ ?[,] 第二個(gè)符號(hào)為 b 去掉累積概率 Pb： = 108 常用信源編碼方法簡(jiǎn)介 ? 放大至 [0,1]( p b1)： 22= ?[,1] 第三個(gè)符號(hào)為 d ? 去掉累積概率 Pd： =0 放大至 [0,1]( p d1)： 0 24＝ 0 ?[0,] 第四個(gè)符號(hào)為 a 109 常用信源編碼方法簡(jiǎn)介 算術(shù)編碼從性能上看具有許多優(yōu)點(diǎn)，特別是由于所需的參數(shù)很少，不象哈夫曼編碼那樣需要一個(gè)很大的碼表，常設(shè)計(jì)成自適應(yīng)算術(shù)編碼來(lái)針對(duì)一些信源概率未知或非平穩(wěn)情況。 平均代碼長(zhǎng)度接近 S的熵值 。 把積累概率 P(S)寫(xiě)成二進(jìn)位的小數(shù) ， 取其前 L位 。 DCT變換，行游程編碼， DPCM，幀間預(yù)測(cè)編碼及霍夫曼編碼等編碼方法，因技術(shù)上的成熟，已被有關(guān)國(guó)際組織定為壓縮編碼的主要方法。在幀間預(yù)測(cè)編碼中，大碼率壓縮的預(yù)測(cè)幀及雙向預(yù)測(cè)幀的采用，也是利用了人眼對(duì)運(yùn)動(dòng)圖像細(xì)節(jié)不敏感的特性。對(duì)視覺(jué)冗余度的壓縮通常已反映在各種具體的壓縮編碼過(guò)程中。因此，包含在色度信號(hào)，圖像高頻信號(hào)和運(yùn)動(dòng)圖像中的一些數(shù)據(jù)并不能對(duì)增加圖像相對(duì)于人眼的清晰度作出貢獻(xiàn)，而被認(rèn)為是多余的，這就是視覺(jué)冗余度。 94 視頻壓縮 ? 視覺(jué)冗余度的壓縮：視覺(jué)冗余度是相對(duì)于人眼的視覺(jué)特性而言的。目前圖像壓縮中的預(yù)測(cè)編碼主要用于幀間壓縮編碼，方法是先根據(jù)一個(gè)子塊的運(yùn)動(dòng)矢量求出下一幀對(duì)應(yīng)子塊的預(yù)測(cè)值及其與實(shí)際值的差值，接收端根據(jù)運(yùn)動(dòng)矢量及差值恢復(fù)出原圖像。在實(shí)際的壓縮編碼中， DPCM主要用于各圖像子塊在 DCT變換后的直流系數(shù)的傳送。在知道了一個(gè)象素點(diǎn)的值后，利用此象素點(diǎn)的值及其與后一象素點(diǎn)的值的差值就可求出后一象素點(diǎn)的值。目前在圖像壓縮編碼中，行游程編碼并不直接對(duì)圖像數(shù)據(jù)進(jìn)行編碼，主要用于對(duì)量 化后的 DCT系數(shù)進(jìn)行編碼。 ? 視頻圖像中經(jīng)常出現(xiàn)一連串連續(xù)的象素點(diǎn)具有相同值的情況，典型的如彩條，彩場(chǎng)信號(hào)等。通過(guò)頻域變換，可以將原圖像信號(hào)用直流分量及少數(shù)低頻交流分量的系數(shù)來(lái)表 示，這就是變換編碼中的正交余弦變換 DCT的方法。圖像的空間相關(guān)性表示相鄰象素點(diǎn)取值變化緩慢。 霍夫曼編碼雖然壓縮比不高，約為 ： 1，但好處是無(wú)損壓縮，目前在圖像壓縮編碼中被廣泛采用。 90 常用信源編碼方法簡(jiǎn)介 ?多元序列也存在相應(yīng)的游程序列 ?多元序列變換成游程序列再進(jìn)行壓縮編碼沒(méi)有多大意義 ?游程編碼只適用于二元序列，對(duì)于多元信源，一般不能直接利用游程編碼 91 視頻壓縮 ? ：對(duì)于一串由許多數(shù)值構(gòu)成的數(shù)據(jù)來(lái)說(shuō)，如果其中某些值經(jīng)常出現(xiàn)，而另外一些值很少出現(xiàn)，則這種由取值上的統(tǒng)計(jì)不均勻性就構(gòu)成了統(tǒng)計(jì)冗余度，可以對(duì)之進(jìn)行壓縮。 實(shí)際上迄今尚無(wú)合適的可實(shí)現(xiàn)的編碼方法可接近 R(D)這個(gè)界 。 因而就不能象無(wú)損編碼那樣從證明過(guò)程中引出概率匹配的編碼方法 。 反之 ，若 RR(D)， 則無(wú)論采用什么樣的編碼方法 ，其譯碼失真必大于 D。 85 限失真信源編碼定理 信息率失真函數(shù)給出了失真小于 D時(shí)所必須具有的最小信息率 R(D)； 只要信息率大于 R(D)，一定可以找到一種編碼，使譯碼后的失真小于 D。但是 哈夫曼 卻從未為此算法申請(qǐng)過(guò)專(zhuān)利或其它相關(guān)能夠?yàn)樗麕?lái)經(jīng)濟(jì)利益的東西，他將他全部的精力放在教學(xué)上，以他自己的話(huà)來(lái)說(shuō)， “我所要帶來(lái)的就是我的學(xué)生。 離開(kāi) MIT后， 哈夫曼 來(lái)到加利福尼亞 大學(xué) 的計(jì)算機(jī)系任教，并為此系的學(xué)術(shù)做出了許多杰出的工作。而 哈夫曼 選擇了后者，原因很簡(jiǎn)單，因?yàn)榻鉀Q一個(gè)大 作業(yè) 可能比期未考試更容易通過(guò)。 1950年， 哈夫曼 在 MIT的信息理論與 編碼 研究生班學(xué)習(xí)。 他發(fā)明的 哈夫曼編碼 能夠使我們通常的數(shù)據(jù)傳輸數(shù)量減少到最小。在他的一 ? 生中，他對(duì)于有限狀態(tài)自動(dòng)機(jī)，開(kāi)關(guān)電路，異步過(guò)程 ?