信源編碼ppt課件-閱讀頁(yè)
2025-05-17 00:20本頁(yè)面
【正文】 i 滿足下 式，就可以得到香農(nóng)碼： 二進(jìn)制香農(nóng)碼的編碼步驟 按信源符號(hào)的概率從大到小的順序排隊(duì)，不妨設(shè)： 1 確定滿足下列不等式的整數(shù)碼長(zhǎng) K i ： 2 令 p ( a0 )=0 ，計(jì)算第 i 個(gè)消息的累加概率 P i ： 3 將累加概率 Pi 變換成二進(jìn)制數(shù)，并取小數(shù)點(diǎn)后 Ki 位 4 作為符號(hào) ai的編碼。 ? 香農(nóng)碼的平均碼長(zhǎng) ? 信源熵 ? 編碼效率 為提高編碼效率，可把 x 4 x 5 換成前面的節(jié) 點(diǎn)，可減小平均碼長(zhǎng)。 例： 設(shè)信源共 7 個(gè)符號(hào)消息，其概率如表所示： 費(fèi)諾（ Fano ）編碼方法 概率匹配 2 按信源符號(hào)的概率從大到小的順序排隊(duì)，不妨設(shè)： p ( a 1 ) ≥ p ( a 2 ) ≥ … ≥ p ( a n ) 按編碼進(jìn)制數(shù)將概率分組，使每組概率盡可能接 近或相等。 給每一組分配一位碼元。 信源符號(hào)對(duì)應(yīng)的碼字即為費(fèi)諾碼。 費(fèi)諾編碼的基本特點(diǎn) : 1) 費(fèi)諾編碼在構(gòu)造 碼樹(shù) 時(shí)，是從樹(shù)根開(kāi)始到終端節(jié) 點(diǎn)結(jié)束； 2) 由于賦碼元時(shí)的任意性，因此編出的碼字不唯一； 3) 費(fèi)諾編碼雖屬于 概率匹配 范疇，但并未嚴(yán)格遵守 匹配規(guī)則，有時(shí)出現(xiàn)概率小的碼長(zhǎng)反而小。 費(fèi)諾碼比較適合于 每次分組概率都很接近 的信源，特 別是對(duì)每次 分組概率都相等的信源 進(jìn)行編碼時(shí)，可達(dá) 到理想的編碼效率。 ? 平均碼長(zhǎng)： ? 編碼效率： 例： 二進(jìn)制費(fèi)諾編碼 信源符號(hào) 概率 編碼 碼字 碼長(zhǎng) x 1 0 0 00 2 x 2 1 01 2 x 3 0 100 3 0 x 4 1 101 3 x 5 0 1100 4 1 0 x 6 1 1101 4 1 x 7 0 1110 4 1 x 8 1 1111 4 平均碼長(zhǎng) K = 2 . 75 碼元 / 符號(hào) 每次所分兩組的 信源熵 H ( X ) = 2 . 75 bit / 符號(hào) 概率恰好相等。 例： ?試對(duì)該信源編二進(jìn)制哈夫曼碼。 平均碼長(zhǎng) 信源熵 H(X) = H (,)= bit/ 符號(hào) 編碼效率 哈夫曼編碼的基本特點(diǎn) 1) 哈夫曼編碼在構(gòu)造碼樹(shù)時(shí)，是從端點(diǎn)開(kāi)始直到樹(shù) 根結(jié)束； 2) 哈夫曼編碼采用概率匹配方法來(lái)決定各碼字長(zhǎng)度， 概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的符號(hào)對(duì)應(yīng)與長(zhǎng) 碼，充分利用了短碼，從而使平均碼長(zhǎng)最??； 3) 哈夫曼編碼時(shí)，縮減信源的最后二個(gè)碼字總是最 后一位不同，從而保證了哈夫曼碼是即時(shí)碼。 哈夫曼編碼是先給每一符號(hào)一片樹(shù)葉，逐步合并成 節(jié)點(diǎn)直到樹(shù)根。 說(shuō)明 ? 每次對(duì)概率最小的符號(hào)分配 “ 0” 和 “ 1” 碼元是任意 的，所以可得到不同的碼字。 ? 不同的碼元分配，得到的具體碼字不同，但碼長(zhǎng) K i 不變，平均碼長(zhǎng)也不變，所以沒(méi)有本質(zhì)區(qū)別。 ? 在哈夫曼編碼過(guò)程中，對(duì)縮減信源符號(hào)按概率由大 到小的順序重新排列時(shí)，應(yīng)使合并后的新符號(hào)盡可 能排在靠前的位置，這樣可使合并后的新符號(hào)重復(fù) 編碼次數(shù)減少，使短碼得到充分利用。 縮減次數(shù) 每次縮減所減少 的信源符號(hào)個(gè)數(shù) 信源符號(hào)數(shù) n 應(yīng)滿足： 不滿足時(shí)：設(shè) q個(gè)概率為 0 的信源符號(hào)，使 q+n 滿足要求 第一次對(duì)最小概率符號(hào)分配碼元時(shí)只取 (mq) 個(gè)，分別 配以 0,1,…, m q1 ，把這些符號(hào)的概率相加作為一個(gè)新 符號(hào)的概率，與其它符號(hào)一起重新排列。 單符號(hào)離散無(wú)記憶信源， 例 試對(duì)該信源編三進(jìn)制哈夫曼碼。 限失真信源編碼定理 ? 設(shè)離散無(wú)記憶信源 X 的信息率失真函數(shù)為 R (D) ， – 當(dāng)信息率 R ＞ R (D) 時(shí)，只要信源序列長(zhǎng)度 L 足 夠長(zhǎng)，一定存在一種編碼方法，其譯碼失真小 于或等于 D+ε， ε為任意小的正數(shù)； – 反之，若 R＜ R (D) ，則無(wú)論采用什么樣的編碼方 法，其譯碼失真必大于 D 。 在二元序列中，連 0 段稱為 0 游程，連 1 段稱為 1 游程 游程長(zhǎng)度序列 / 游程序列：用交替出現(xiàn)的 “ 0” 游程 和 “ 1” 游程長(zhǎng)度表示任意二元序列。 游程序列： 3113213 二元序列： 000101110010001 若已知二元序列以 0 起始，從游程序列很容易恢復(fù)成 原來(lái)的二元序列。 ? 編碼方法： – 首先測(cè)定 “ 0” 游程長(zhǎng)度和 “ 1” 游程長(zhǎng)度的概率 分布，即以游程長(zhǎng)度為元素，構(gòu)造一個(gè)新的 信源； – 對(duì)新的信源 ( 游程序列 ) 進(jìn)行哈夫曼編碼。 ? 算術(shù)編碼不同于哈夫曼碼，它是非分組 ( 非塊 ) 碼。 ? 算術(shù)編碼利用了累積概率的概念。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1