數(shù)據(jù)壓縮基礎(chǔ)ppt課件-在線瀏覽
2024-12-21 22:14本頁(yè)面
【正文】 離散信源 。 信源 X1, X2, X3, X4…… 12 離散信源 ? 如果隨機(jī)序列中各個(gè)變量獨(dú)立具有相同的概率分布，則稱(chēng)為 簡(jiǎn)單 離散信源 。 信源 X1, X2, X3, X4…… {a1, a2, a3, …a m} 13 離散事件的非平均互信息量 ? y事件的發(fā)生對(duì)判斷 x事件所帶來(lái)的信息量取決于 x的先驗(yàn)概率 p(x)與 y發(fā)生后 x的后驗(yàn)概率 p(x|y)之比。 y) ? 互信息量的性質(zhì)： )()()(l o g)()|(l o g)。()。()。()2( yzxIyxIyzxI ??14 離散事件的非平均自信息量 ? 為了完全確定事件 x(使后驗(yàn)概率為 1)所必須提供的信息量稱(chēng)為 x事件的非平均自信息量 I(x) ? 非平均自信息量是隨機(jī)事件的一個(gè)固有特性，它表明了事件的先驗(yàn)不確定性大小 )(l o g)(1l o g)( xpxpxI ???)。()4( xyIyIyxIxIyxI ????I(x) I(y) I(x。()5( xyIyIxIyxI ???)。其數(shù)學(xué)期望為： ? H(X)表明了集合 X中隨機(jī)事件的平均不確定性，或者說(shuō)平均信息量。 ? 根據(jù)直覺(jué)，信源編碼的數(shù)據(jù)輸出速率（平均碼長(zhǎng)）與信源熵之間應(yīng)該有某種對(duì)應(yīng)關(guān)系。 ? 最大離散熵定理 ：當(dāng)與信源對(duì)應(yīng)的字符集中的各個(gè)字符為等概率分布時(shí)，熵具有極大值 log2m。 ?????mjjj ppxH1l og)(???mjjp1120 二進(jìn)制信源的熵 ? 二進(jìn)制信源輸出一個(gè)二進(jìn)制數(shù)碼所攜帶的平均信息量最大為 1bit。 ? 離散無(wú)記憶信源的冗余度隱含在信源符號(hào)的非等概率 分布之中。 22 編碼 信源 {X1, X2, …,X L} {a1, a2, a3, …a K} 編碼器 {Y1, Y2, …, Y N} {b1, b2, b3, …b D} {0,1} 信源字母表 碼元表 消息分組 碼字 23 平均碼長(zhǎng)與熵 ? 如果采用單字符二進(jìn)制編碼方式，設(shè)字符 aj的編碼長(zhǎng)度為 Lj， 則信源字母表的平均碼長(zhǎng)為： ? 根據(jù)前面對(duì)二進(jìn)制信源的分析，有： ????Kjjj LpL1)(1)( XHLL XH ????????????KjjjjKjj ppLp121l og 在 Lj ＝ － log2pj時(shí)，平均碼長(zhǎng)取得極小值 H(X) 24 關(guān)于離散無(wú)記憶平穩(wěn)信源的結(jié)論 ? 一階熵即為離散無(wú)記憶平穩(wěn)信源的壓縮極限。 ? 數(shù)據(jù)壓縮的基本途徑之一：使各字符的編碼長(zhǎng)度盡量等于字符的信息量。 27 關(guān)于離散有記憶平穩(wěn)信源的結(jié)論 ? 離散有記憶平穩(wěn)信源的壓縮極限為： ? 壓縮的基本途徑之二：盡量去除各分量之間的相關(guān)性，再對(duì)各分量進(jìn)行獨(dú)立編碼。 ? 壓縮的基本途徑之四：可將多個(gè)分量合并成向量，利用其聯(lián)合概率進(jìn)行編碼，聯(lián)合的分量越多越有利。 29 霍夫曼編碼 ? 具體步驟： （ 1）初始化 （ 2）合并概率最小的兩個(gè)事件 （ 3）排序 （ 4）如果事件個(gè)數(shù)大于 2則重復(fù)（ 2）和（ 3） （ 5）賦值 （ 6）編碼 30 霍夫曼編碼舉例 符號(hào) S1 S2 S3 S4 出現(xiàn)概率 1/2 1/4 1/8 1/8 等長(zhǎng)編碼 00 01 10 11 霍夫曼 0 10 110 111 H(X) = L1=2 L2= 源 S1 S2 S1 S3 S2 S1 S1 S4 等 00 01 00 10 01 00 00 11 霍 0 10 0 110 10 0 0 111 31 霍夫曼編碼的局限性 ? 利用霍夫曼編碼，每個(gè)符號(hào)的編碼長(zhǎng)度只能為整數(shù)，所以如果源符號(hào)集的概率分布不是 2負(fù) n次方的形式，則無(wú)法達(dá)到熵極限。 ? 具體步驟為： （ 1）首先將編碼字符集中的字符按照出現(xiàn)頻度和概率進(jìn)行排序。直至不可再分，即每一個(gè)葉子對(duì)應(yīng)一個(gè)字符。 33 香農(nóng)－范諾編碼舉例 A B C D E A B C D E D E 符號(hào) A B C D E 次數(shù) 15 7 7 6 5 0 1 0 1 0 0 1 1 34 算術(shù)編碼 ? Huffman 編碼的局限性： Huffman 編碼使用整數(shù)個(gè)二進(jìn)制位對(duì)符號(hào)進(jìn)行編碼，這種方法在許多情況下無(wú)法得到最優(yōu)的壓縮效果?？梢韵胂螅麄€(gè)信息的 80% 在壓縮后都幾乎相當(dāng)于理想長(zhǎng)度的 3 倍左右。消息序列中的每個(gè)元素都要用來(lái)縮短這個(gè)區(qū)間。 ? 采用算術(shù)編碼每個(gè)符號(hào)的平均編碼長(zhǎng)度可以為小數(shù)。（請(qǐng)看參考書(shū)上給出的算法） ? 算術(shù)編碼每次遞推都要做乘法，所以效率比較低。 ? 自適應(yīng)算術(shù)編碼 可以在編碼過(guò)程中根據(jù)符號(hào)出現(xiàn)的頻繁程度動(dòng)態(tài)的修改分布概率，這樣可以避免在編碼之前必須精確求出信源概率的難題。 ? 例如： RTTTTTTTTABBCDG被轉(zhuǎn)換為：R8TABBCDG， 其中“＃”作為轉(zhuǎn)義字符，表明其后所跟的字符表示長(zhǎng)度。例如00000000111111111111000001111111被轉(zhuǎn)化為一系列黑串和白串長(zhǎng)度的編碼： 81257。 41 詞典編碼 ? 詞典編碼主要利用數(shù)據(jù)本身包含許多重復(fù)的字符串的特性。 我們?nèi)绻靡恍┖?jiǎn)單的代號(hào)代替這些字符串，就可以實(shí)現(xiàn)壓縮，實(shí)際上就是利用了信源符號(hào)之間的相關(guān)性。 ? 實(shí)用的詞典編碼算法的核心就是如何動(dòng)態(tài)地形成詞典，以及如何選擇輸出格式以減小冗余。 43 LZ77算法
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1