[計(jì)算機(jī)軟件及應(yīng)用]第5章信源編碼ppt(參考版)
2025-02-23 22:16本頁(yè)面
【正文】 ? 算術(shù)碼主要的編碼方法是計(jì)算輸入信源符號(hào)序列所 對(duì)應(yīng)的區(qū)間。它 從全序列出發(fā)，考慮符號(hào)之間的關(guān)系來(lái)進(jìn)行編碼。 算術(shù)編碼 ? 算術(shù)編碼是近十多年來(lái)發(fā)展迅速的一種無(wú)失真信源 編碼，它與最佳的哈夫曼碼相比，理論性能稍加遜 色，而實(shí)際壓縮率和編碼效率卻往往還優(yōu)于哈夫曼 碼，且實(shí)現(xiàn)簡(jiǎn)單，故很受工程上的重視。 游程變換將二元序列變換成了多元序列；這樣 就適合于用其他方法，如哈夫曼編碼，進(jìn)一步 壓縮信源，提高通信效率。 游程變換：是一種一一對(duì)應(yīng)的變換，也是可逆變換。 ? 如是二元信源，則對(duì)于任意小的 ε＞ 0 ，每一個(gè)信 源符號(hào)的平均碼長(zhǎng)滿足如下公式： 常用信源編碼方法簡(jiǎn)介 游程編碼 游程：數(shù)字序列中連續(xù)出現(xiàn)相同符號(hào)的一段。 m =3 ， n =8 無(wú)法滿足 n = s ( m 1) + m s =3 ， q =1 q + n = s ( m 1) + m 第一次取 m q =2 個(gè)符號(hào)進(jìn)行編碼 平均碼長(zhǎng) 信息傳輸率 編碼效率 ? 香農(nóng)碼、費(fèi)諾碼、哈夫曼碼都考慮了信源的統(tǒng)計(jì)特 性，使經(jīng)常出現(xiàn)的信源符號(hào)對(duì)應(yīng)較短的碼字，使平 均碼長(zhǎng)縮短，從而實(shí)現(xiàn)了對(duì)信源的壓縮； ? 香農(nóng)碼有系統(tǒng)的、惟一的編碼方法，費(fèi)諾碼和哈夫 曼碼的編碼方法都不惟一； ? 費(fèi)諾碼比較適合于對(duì)分組概率相等或接近的信源編 碼，費(fèi)諾碼也可以編 m 進(jìn)制碼，但 m 越大，信源的符 號(hào)數(shù)越多，可能的編碼方案就越多，編碼過(guò)程就越 復(fù)雜，有時(shí)短碼未必能得到充分利用； ? 哈夫曼碼對(duì)信源的統(tǒng)計(jì)特性沒(méi)有特殊要求，編碼效 率比較高，對(duì)編碼設(shè)備的要求也比較簡(jiǎn)單，因此綜 合性能優(yōu)于香農(nóng)碼和費(fèi)諾碼。以后每次取 m 個(gè)符號(hào)，分別配以 0,1,…, m 1；如此下去，直至所有 概率相加得 1 為止，即得到各符號(hào)的 m 進(jìn)制碼字。 m 進(jìn)制哈夫曼編碼 在編 m 進(jìn)制哈夫曼碼時(shí)，為了使短碼得到充分利用， 使平均碼長(zhǎng)最短，必須使最后一步的縮減信源有 m 個(gè) 信源符號(hào)。 ? 縮減信源時(shí)，若合并后的新符號(hào)概率與其他符號(hào)概 率相等，從編碼方法上來(lái)說(shuō)，這幾個(gè)符號(hào)的次序可 任意排列，編出的碼都是正確的，但得到的碼字不 相同，不同的編法得到的碼字長(zhǎng)度 K i 也不盡相同。只要在各次縮減信源 中保持碼元分配的一致性，即能得到可分離碼字。 哈夫曼的編法并不惟一。 費(fèi)諾碼是從樹(shù)根開(kāi)始，把各節(jié)點(diǎn)分給某子集，若子 集已是單點(diǎn)集，它就是一片樹(shù)葉而作為碼字。 讀取碼字的時(shí)候，要從后向前讀，此 時(shí)編出來(lái)的碼字是可分離的即時(shí)碼。 H ( X ) 編碼效率 ?????????? = 1 K log 2 樹(shù)圖： 哈夫曼（ Huffman ）編碼方法 3 將信源符號(hào)按概率由大到小順序排隊(duì) 1 給兩個(gè)概率最小的符號(hào)各分配一個(gè)碼元，將其概率 2 相加后合并作為一個(gè)新的符號(hào)，與剩下的符號(hào)一 起，再重新排隊(duì) 給縮減信源中概率最小的兩個(gè)符號(hào)各分配一個(gè)碼元 3 4 重復(fù)步驟 2 、 3 直至概率和為 1 從最后一級(jí)開(kāi)始，向前返回得到各個(gè)信源符號(hào)所對(duì) 5 應(yīng)的碼元序列，即相應(yīng)的碼字。 例： 對(duì)該信源進(jìn)行二 進(jìn)制費(fèi)諾編碼。因此 平均碼長(zhǎng)一般不會(huì)最小。 例： 對(duì)前例信源進(jìn)行二進(jìn)制費(fèi)諾編碼。 將每一分組再按同樣原則劃分，重復(fù)步驟 2 和 3 ， 直至概率不再可分為止。如編二進(jìn)制碼就分成兩組，編 m 進(jìn)制 碼就分成 m 組。 不應(yīng)先規(guī)定碼長(zhǎng)，而是由碼樹(shù)來(lái)規(guī)定碼 字，可得更好的結(jié)果。 例： 有一單符號(hào)離散無(wú)記憶信源 對(duì)該信源編二 進(jìn)制香農(nóng)碼。 香農(nóng)（ Shannon ）編碼方法 1 香農(nóng)第一定理指出了平均碼長(zhǎng)與信源之間的關(guān)系，同 時(shí)也指出了可以通過(guò)編碼使平均碼長(zhǎng)達(dá)到極限值。 僅哈夫曼編碼是真正意義下的最佳編碼 哈夫曼編碼效率最高，費(fèi)諾編碼效率次之，香農(nóng) 編碼效率最低，甚至低于定長(zhǎng)編碼的效率。 最佳變長(zhǎng)編碼 凡是能載荷一定的信息量，且碼字的平均長(zhǎng)度最 短，可分離的變長(zhǎng)碼的碼字集合稱為最佳變長(zhǎng)碼。 (2) 隨著信源序列長(zhǎng)度的增加，編碼的效率越來(lái)越接 近于 1 。 ? 編碼效率的下界 為了衡量各種編碼方法與最佳碼的差距，定義碼的 剩余度為： 同前例： 設(shè)離散無(wú)記憶信源概率空間為 ? 信源熵： H ( X ) = 2 . 55 bit / 符號(hào) 要求
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1