《信源編碼》PPT課件

《《信源編碼》PPT課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《《信源編碼》PPT課件（61頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、HUST - Basis for Information Theory 1 信 源 編 碼 （ 主 要 內(nèi) 容 ） HUST - Basis for Information Theory 2 o 特 點(diǎn) ：n 在 符 號(hào) 序 列 長(zhǎng) 度 L不 很 大 時(shí) ， 能 達(dá) 到 較 高 的 編 碼效 率 。o 要 求 ：n 變 長(zhǎng) 碼 要 滿 足 唯 一 可 譯 碼 條 件 ， 則 它 必 須 是 非奇 異 碼 ， 而 且 任 意 有 限 長(zhǎng) L次 擴(kuò) 展 碼 也 應(yīng) 該 是 非奇 異 碼 。n 為 了 能 夠 即 時(shí) 譯 碼 ， 變 長(zhǎng) 碼 還 必 須 是 即 時(shí) 碼 。變 長(zhǎng) 編 碼 HUST -

2、 Basis for Information Theory 3 1、 克 拉 夫 特 不 等 式o 信 源 符 號(hào) 數(shù) 、 碼 符 號(hào) 數(shù) 和 碼 字 長(zhǎng) 度 之 間 應(yīng) 滿足 什 么 條 件 ， 才 能 構(gòu) 成 HUST - Basis for Information Theory 4 2、 麥 克 米 倫 不 等 式o 將 克 拉 夫 特 不 等 式 推 廣 到 的 情 況o 定 理 在 前 一 定 理 所 給 定 的 條 件 下 ， 唯 一 可譯 碼 存 在 的 充 要 條 件 是1 1其 中 ， m為 碼 符 號(hào) 個(gè) 數(shù) ， k為 碼 字 長(zhǎng) 度 ， n為 信 源 符 號(hào) 數(shù) iin

3、ki m HUST - Basis for Information Theory 5 說 明o 如 果 碼 字 長(zhǎng) 度 和 碼 符 號(hào) 數(shù) 滿 足 克 拉 夫 特 （ 或麥 克 米 倫 ） 不 等 式 ， 則 一 定 可 以 構(gòu) 造 出 即 時(shí)碼 （ 或 唯 一 可 譯 碼 ） ， 否 則 不 能 構(gòu) 造 出 即 時(shí)碼 （ 或 唯 一 可 譯 碼 ） 。o 但 是 該 定 理 并 不 能 作 為 判 斷 一 種 碼 是 否 為 即時(shí) 碼 （ 或 唯 一 可 譯 碼 ） 的 依 據(jù) 。n 例 如 ： 碼 中 ， 有 兩 個(gè) 碼 字 長(zhǎng) 度 相 同 ， 則 這 兩 個(gè) 碼字 無 論 是 否 相 同

4、 ， 都 可 能 使 不 等 式 成 立 。 但 是 ，兩 個(gè) 碼 字 相 同 時(shí) 顯 然 不 可 能 是 唯 一 可 譯 碼 。 HUST - Basis for Information Theory 6 3、 平 均 碼 長(zhǎng)o 定 義 設(shè) 信 源 o 編 碼 后 的 碼 字 分 別 為 W1 ， W2， ， Wn， 相 應(yīng)的 碼 長(zhǎng) 分 別 為 k1， k2， ， kn。 因 為 是 唯 一 可譯 碼 ， 信 源 符 號(hào) xi和 碼 字 Wi一 一 對(duì) 應(yīng) ， 則 平 均碼 長(zhǎng) 為 1 21 2 nnx x xX p x p x p xP 1= ( )n i iiK p x k HUST

5、- Basis for Information Theory 7K 4、 信 息 傳 輸 率 與 信 息 傳 輸 速 率 HUST - Basis for Information Theory 8 變 長(zhǎng) 無 失 真 信 源 編 碼 定 理o 即 香 農(nóng) 第 一 定 理o 定 理 設(shè) 離 散 無 記 憶 信 源 為1 21 2 1 21 2 1 2.( ) ( ) ( )( ) .( ) ( ) ( )( ) ( , ,., )L Ln nL nnL mX x x xP p x p x p xH X LX p p pP H X Y y y y 其 信 源 熵 為 ； 它 的 次 擴(kuò) 展 信 源

6、 為其 熵 為 ； 碼 符 號(hào) 集 HUST - Basis for Information Theory 9 變 長(zhǎng) 無 失 真 信 源 編 碼 定 理 （ 續(xù) ） HUST - Basis for Information Theory 10 變 長(zhǎng) 無 失 真 信 源 編 碼 定 理 理 解 HUST - Basis for Information Theory 11 推 廣 到 普 通 信 源o 變 長(zhǎng) 無 失 真 信 源 編 碼 定 理 可 以 推 廣 到 平 穩(wěn) 遍歷 的 有 記 憶 信 源 ， 一 般 離 散 信 源 或 馬 爾 可 夫信 源 ， 有 其 中 ， H 為 有 記 憶

7、 信 源 的 極 限 熵o 定 長(zhǎng) 編 碼 作 為 變 長(zhǎng) 編 碼 的 特 例 ， 可 統(tǒng) 一 到 香農(nóng) 第 一 定 理 之 中 。lim logL L HKL m HUST - Basis for Information Theory 12 變 長(zhǎng) 編 碼 的 編 碼 信 息 率 Ro 定 義 變 長(zhǎng) 編 碼 的 編 碼 信 息 率 為 它 表 示 編 碼 后 平 均 每 個(gè) 信 源 符 號(hào) 能 載 荷 的 最大 信 息 量 。o 香 農(nóng) 第 一 定 理 可 表 述 為 ：n 若 H(X)RH(X)+， 就 存 在 唯 一 可 譯 的 變 長(zhǎng)編 碼 。n 若 RH(X)， 則 不 存 在 唯

8、 一 可 譯 的 變 長(zhǎng) 編 碼 。不 能 實(shí) 現(xiàn) 無 失 真 的 信 源 編 碼 。= logLKR mL HUST - Basis for Information Theory 13 信 息 傳 輸 率 Ro 從 信 道 角 度 看 ， 信 道 的 信 息 傳 輸 率 ( ) lo/ ( g) / ( ),logL H XKK H XK LH mXR K R m 比 特 信 源 符 號(hào) 比 特 碼 符 號(hào)碼 符 號(hào) 信 源 符 號(hào)因 為 所 以 ( )log log H XmR mK R C ， 可 見 等 于 無 噪 無 當(dāng) 達(dá) 到 時(shí) ， 編 碼 后 的 信損 信 道 的 信 道 容

9、量 ，信 息 極 限 值傳 輸 息 傳 輸 率率 最 高 。 HUST - Basis for Information Theory 14 編 碼 效 率 和 剩 余 度定 義 碼 的 剩 余 度 為 1 K1 ( )mH X HUST - Basis for Information Theory 15 1 21 21 2 3/4 1/43 4 1( ) log log4 0.811 /4 3 40,10, 11 /( ) 0.811 0.811 / x xX p pPH X x xK H XK R 設(shè) 有 一 離 散 無 記 憶 信 源 ：其 熵 為 比 特 信 源 符 號(hào) 現(xiàn) 用 二 元

10、符 號(hào) ( )來 構(gòu) 造 一 個(gè) 即 時(shí) 碼 平 均 碼 長(zhǎng) 二 元 碼 符 號(hào) 信 源 符 號(hào) 編 碼 的 效 率 為得 信 道 的 信 息 傳 輸 率 為 比 特 二 元 碼 符 號(hào) 變 長(zhǎng) 編 碼 舉 例 HUST - Basis for Information Theory 16 進(jìn) 一 步 ， 我 們 對(duì) 信 源 X的 二 次 擴(kuò) 展 信 源 X2進(jìn) 行 編 碼 。 其 二 次 擴(kuò) 展 信 源 X2和 即 時(shí) 碼 如 下 表 所 列 i ( )ip 即 時(shí) 碼 1 1xx 9/16 0 1 2xx 3/16 10 2 1x x 3/16 110 2 2x x 1/16 111 變 長(zhǎng)

11、 編 碼 舉 例 續(xù) HUST - Basis for Information Theory 17 變 長(zhǎng) 編 碼 舉 例 續(xù) HUST - Basis for Information Theory 18 變 長(zhǎng) 編 碼 舉 例 續(xù)o 用 同 樣 方 法 可 進(jìn) 一 步 對(duì) 信 源 X的 三 次 和 四 次 擴(kuò) 展 信源 進(jìn) 行 編 碼 ， 并 求 出 其 編 碼 效 率 為 ：n 3=0.985比 特 /二 元 碼 符 號(hào)n 4=0.991比 特 /二 元 碼 符 號(hào)o 對(duì) 于 同 一 信 源 ， 要 求 編 碼 效 率 都 達(dá) 到 96 ， 比 較n 變 長(zhǎng) 碼 只 需 對(duì) 二 次 擴(kuò) 展

12、 信 源 （ L = 2） 進(jìn) 行 編 碼 ；n 而 等 長(zhǎng) 碼 則 要 求 L大 于 4.13X10 7 .o 變 長(zhǎng) 碼 編 碼 效 率 更 高 ， L不 需 很 大 就 可 以 達(dá) 到 比 較高 的 編 碼 效 率 ， 而 且 可 實(shí) 現(xiàn) 無 失 真 編 碼 。 HUST - Basis for Information Theory 19 小 結(jié)o 介 紹 了 變 長(zhǎng) 碼 基 本 特 征 和 平 均 碼 長(zhǎng) 的 概 念 ；o 通 過 克 拉 夫 特 不 等 式 和 麥 克 米 倫 不 等 式 ， 給出 了 構(gòu) 成 即 時(shí) 碼 和 唯 一 可 譯 碼 時(shí) ， 信 源 符 號(hào)數(shù) 和 碼 字

13、長(zhǎng) 度 之 間 應(yīng) 滿 足 的 條 件 ；o 討 論 了 香 農(nóng) 第 一 定 理 ： 變 長(zhǎng) 編 碼 定 理 ； HUST - Basis for Information Theory 20 信 源 編 碼 （ 主 要 內(nèi) 容 ） HUST - Basis for Information Theory 21 1 2.( ) 0( ) ( )( )( ) LX X X XR DDR R DL CD C DR R DD C D ， ， 設(shè) 一 離 散 平 穩(wěn) 無 記 憶 信 源 的 輸 出 為若 該 信 源 的 信 息 率 失 真 函 數(shù) 為 ， 并 選 定 有 限 的 失 真 函 數(shù) 。對(duì) 于

14、任 意 允 許 平 均 失 真 度 和 任 意 ， 則 當(dāng) 只 要 信 源 序 列 長(zhǎng) 度 足 夠 長(zhǎng) ， 則 一 定 存 在 一 種 編 碼 方 式 ， 使譯 碼 后 的 平 均 失 真 度反 之 ， 若 ， 則 無 論 用 編 碼 信 息什 么 編 碼 方 式 ， 必 有 即 譯 碼 平 均 失 真 率大 于 允 許 失 該 定 理 可 推 廣 到 連 續(xù) 平 穩(wěn) 無 記真 。 （憶 信 源證 明 ： 略 ）的 情 況 。 限 失 真 信 源 編 碼 定 理 HUST - Basis for Information Theory 22 對(duì) 信 源 編 碼 定 理 的 統(tǒng) 一 理 解o 定

15、長(zhǎng) 信 源 無 失 真 編 碼 定 理o 變 長(zhǎng) 信 源 無 失 真 編 碼 定 理 （ 香 農(nóng) 第 一 定 理 ）o 保 真 度 準(zhǔn) 則 下 的 信 源 編 碼 定 理 （ 香 農(nóng) 第 三 定 理 ）o 從 編 碼 信 息 率 的 角 度 ， 當(dāng) 時(shí) ， 則 信 源 編 碼 無 失 真 或 失 真 可 控 。( )log log ( )KRK H XL Hm m XL lo( )l (g g )o LL KRK H m HLXL m X ( )R R D ( ) ( )R H X R R D 或 HUST - Basis for Information Theory 23 信 源 編 碼 （

16、 主 要 內(nèi) 容 ） HUST - Basis for Information Theory 24 常 見 的 方 法 ：o 香 農(nóng) 編 碼o 費(fèi) 諾 編 碼o 霍 夫 曼 編 碼o 游 程 編 碼o 冗 余 位 編 碼變 長(zhǎng) 碼 的 編 碼 方 法 HUST - Basis for Information Theory 25 1、 香 農(nóng) 編 碼 HUST - Basis for Information Theory 26 香 農(nóng) 編 碼 舉 例 HUST - Basis for Information Theory 27 香 農(nóng) 編 碼 舉 例 （ 續(xù) ） HUST - Basis for

17、 Information Theory 28 香 農(nóng) 編 碼 舉 例 （ 續(xù) ）o 由 上 表 可 以 看 出 ， 一 共 有 5個(gè) 三 位 的 代 碼 組 ， 各 代 碼 組之 間 至 少 有 一 位 數(shù) 字 不 相 同 ， 故 是 唯 一 可 譯 碼 。 還 可 以判 斷 出 ， 這 7個(gè) 代 碼 組 都 屬 于 即 時(shí) 碼 。o 平 均 碼 長(zhǎng) 、 信 息 傳 輸 率 、 編 碼 信 息 率 和 編 碼 效 率 1 K ( ) 3.14( ) 2.61 0.831 /3.14 log 3.14 / 83.1%n i ii Lp x kH XR KKR mLH(X)= R 碼 元 /信 源

18、 符 號(hào)比 特 碼 元比 特 信 源 符 號(hào) HUST - Basis for Information Theory 29 2、 霍 夫 曼 編 碼 -方 法 HUST - Basis for Information Theory 30 霍 夫 曼 編 碼 舉 例 HUST - Basis for Information Theory 31 霍 夫 曼 編 碼 舉 例 （ 續(xù) ）o 該 霍 夫 曼 碼 的 平 均 碼 長(zhǎng)o 從 編 碼 表 可 以 看 出 ， 霍 夫 曼 是 即時(shí) 碼 ， 從 右 圖 的 碼 樹 中 也 可 以 清楚 看 出 。51 ( ) 0.4 1 0.2 2 0.2 30

19、.1 4 0.1 42.2 /( ) 0.965i ii mK p s lH SK 碼 元 信 源 符 號(hào)其 編 碼 效 率 HUST - Basis for Information Theory 32 霍 夫 曼 編 碼 并 不 唯 一霍 夫 曼 編 碼 方 法 非 唯 一 ， 原 因 ：o 每 次 對(duì) 信 源 縮 減 時(shí) ， 賦 予 信 源 最 后 兩 個(gè) 概 率最 小 的 符 號(hào) ， 用 0和 1是 可 以 任 意 的 ；o 對(duì) 信 源 進(jìn) 行 縮 減 時(shí) ， 兩 個(gè) 概 率 最 小 的 符 號(hào) 合并 后 的 概 率 與 其 它 信 源 符 號(hào) 的 概 率 相 同 時(shí) ，這 兩 者 在

20、縮 減 信 源 中 進(jìn) 行 概 率 排 序 時(shí) ， 其 位置 放 置 次 序 可 以 任 意 。 HUST - Basis for Information Theory 33 另 一 種 霍 夫 曼 編 碼o 合 并 后 的 概 率 與 其 它 信 源 符 號(hào) 的 概 率 相 同 時(shí) ，改 變 這 兩 者 在 縮 減 信 源 中 的 排 序 ， 可 以 得 到 另一 種 霍 夫 曼 編 碼 。 HUST - Basis for Information Theory 34 另 一 種 霍 夫 曼 編 碼 （ 續(xù) ）o 該 霍 夫 曼 碼 的 平 均 碼 長(zhǎng)o 編 碼 效 率 與 前 一 種 霍

21、夫 曼 碼 的 效 率 相 同 。o 但 后 一 種 編 碼 的 碼 長(zhǎng) 方 差 o 方 差 比 第 一 種 方 法 小 ， 即 碼 長(zhǎng) 變 化 小 ， 簡(jiǎn) 單 ， 易 實(shí) 現(xiàn) 。 故 在 霍 夫 曼 編 碼 過 程 中 ， 對(duì) 縮 減 信 源 符 號(hào) 以 概 率 重 新 排 列 時(shí) ， 應(yīng) 使 合 并 符 號(hào) 盡 量 靠前 ， 可 使 合 并 符 號(hào) 重 復(fù) 編 碼 次 數(shù) 減 少 ， 使 短 碼 得 到 充 分 利 用 。51 0.4 2 0.2 20.2 2 0.1 3 0.1 32.2 ( ) 0.965( ) mi ii H SKK p s lK 碼 元 /信 源 符 號(hào)其 編 碼

22、效 率 ：2 21( ) ( )( )n i iik p x k K HUST - Basis for Information Theory 35 r元 霍 夫 曼 碼o 二 進(jìn) 制 霍 夫 曼 碼 的 編 碼 方 法 可 以 很 容 易 推 廣 到 r進(jìn)制 的 情 況 。 只 是 編 碼 過 程 中 構(gòu) 成 縮 減 信 源 時(shí) ， 每 次都 是 將 r個(gè) 概 率 最 小 的 符 號(hào) 合 并 ， 并 分 別 用 0, 1, , (r-1)碼 符 號(hào) 表 示 。o 例 設(shè) 有 離 散 無 記 憶 信 源 碼 符 號(hào) 集 X (0,1,2)， 試 構(gòu) 造 一 種 三 進(jìn) 制 霍 夫 曼 碼 。 1

23、 2 3 4 5 6 7 80.4 0.2 0.1 0.1 0.05 0.05 0.05 0.05 s s s s s s s sSP HUST - Basis for Information Theory 36 r元 霍 夫 曼 碼 舉 例o 編 碼 過 程 見 下 表 ， 其 中 信 源 s9是 增 補(bǔ) 的 ， 令 其 概 率 為 零 . HUST - Basis for Information Theory 37 r元 霍 夫 曼 碼 舉 例 （ 續(xù) ） r3元 霍 夫 曼 編 碼 810.4 1 0.2 2 0.1 2 0.1 2 0.05 20.05 2 0.05 3 1.7其 平

24、均 碼 長(zhǎng) i iiL p s l HUST - Basis for Information Theory 38 霍 夫 曼 編 碼 總 結(jié)o 1、 編 碼 方 法 保 證 了 概 率 大 的 符 號(hào) 對(duì) 應(yīng) 于 短碼 ， 概 率 小 的 符 號(hào) 對(duì) 應(yīng) 于 長(zhǎng) 碼 ， 充 分 利 用 了短 碼 ；o 2、 每 次 縮 減 信 源 的 最 后 二 個(gè) 碼 字 總 是 最 后一 位 不 同 ， 從 而 保 證 了 霍 夫 曼 碼 是 即 時(shí) 碼 。 HUST - Basis for Information Theory 39 3、 費(fèi) 諾 編 碼 HUST - Basis for Informa

25、tion Theory 40 費(fèi) 諾 編 碼 舉 例 HUST - Basis for Information Theory 41 費(fèi) 諾 編 碼 舉 例 （ 續(xù) ） HUST - Basis for Information Theory 42 4、 游 程 編 碼 與 游 程 變 換o 前 面 三 種 方 法 針 對(duì) 無 記 憶 信 源 ， 對(duì) 于 有 記 憶 信 源 的編 碼 效 率 不 高 ， 一 般 采 用 其 它 編 碼 。 如 ： 游 程 編 碼 。o 二 元 序 列 ： 000101110010001n “0”游 程 、 “ 1”游 程 ； 游 程 長(zhǎng) 度 L(0)、 L(1)

26、o 多 元 序 列 /游 程 長(zhǎng) 度 序 列 ： 31132131規(guī) 定 游 程 序 列 從 “ 0”開 始 ， 是 可 逆 變 換 。它 減 弱 了 二 元 序 列 的 相 關(guān) 性 。 對(duì) 變 換 后 的 多 元 序 列可 采 用 其 它 編 碼 方 法 ， 比 如 ： 哈 夫 曼 編 碼 。o 多 元 序 列 也 可 以 變 換 成 游 程 序 列 ， 但 是 需 要 增 加 標(biāo)志 位 ， 可 能 會(huì) 抵 消 壓 縮 編 碼 得 到 的 好 處 ， 意 義 不 大 。 HUST - Basis for Information Theory 43 游 程 序 列 的 概 率 特 性o 若 二

27、 元 序 列 的 概 率 特 性 已 知 ， 可 計(jì) 算 出 游 程序 列 的 概 率 特 性 。o 假 設(shè) 二 元 序 列 為 獨(dú) 立 序 列 ， 則n 0游 程 長(zhǎng) 度 概 率 ： pL(0)= p0 L(0)-1 p1 ;n 0游 程 長(zhǎng) 度 的 熵 ： H L(0)=H (p0 )/ p1 ; n 0游 程 序 列 的 平 均 長(zhǎng) 度 ： l0=EL(0)=1/ p1n pL(1)= p1 L(1)-1 p0 ; H L(1)=H (p0 )/ p0 ; l 1=EL(1)=1/ p0o p0和 p1分 別 為 二 元 序 列 中 “ 0”和 “ 1”的 概 率n H (X) = H

28、L(0)+ H L(1) / (l0+l1) = H (p0 ) = H (p1 ) HUST - Basis for Information Theory 44 0/ 1游 程 長(zhǎng) 度 的 概 率 ： pL(0)、 pL(1)2 10 0 01 1 1 (0) 1 12 1100(0) 0 11 0 1 00 10.1(1 ) 2(1 ) 3(1 ) . .(0) . . (0)1 01. 1 1 11 11 11.1(0 ) 2(0 ) 3(0 ) . .(1) .0 00 000 . . 0 0(1) 1 01 LLLL LLp L LLp Lz p p p ppp p pp p ppp

29、 pp 游 程 ：游 程 ： (0) 1 10 12 30 0 02 30 0 0 0 (1) 1 01 0(1) 1 (1)0(0) 1 (0) 1 100 1 (0) . 11 1 . 1 1; (1) 11 ;11L LL LL L ppp L p pp p L p pp p ppp p p p p z z p HUST - Basis for Information Theory 45 平 均 游 程 長(zhǎng) 度 ： EL(0)、 EL(1) 0 2 0 1 1(0) 1 12 20 0 0 0 0 2 20 1(0 ()0 1) 111 0(1) 1 (1) 1 00(0) 1 01 1

30、(0) (0) (0)1 2 3 . 0 2 . 1 1(1 )1(1) (1) (1) ( 11 . 11(0) )L LL L LLE L L p L p p pt p p p p pt t p pE L L p L Ll p L t pp ppppl 同 理 ： HUST - Basis for Information Theory 46 0/ 1游 程 長(zhǎng) 度 的 熵 ： H L(0)/ H L(1) (0) 1 (0) 12 0 1 0 1(0) 1 (0) 1(0) 10 1 0) 1 (0) 12 1 0 1 2 0(0) 1 1 1 0 02 1( 1 0 0 1 (0) 1

31、( 000) 1 12 0 21 (0)log (0 () 0) loglog loglog loglog logl (o )g 1LL L LL LL LLL Lp L p L p p p pp p p pp p p p pp p p p pH L H pp pp pp 其 中 ： 0) 1(0) 1 2 2 3 3 (0) 1 (0) 10 0 0 0 0 0 0 2 02 3 (0) 10 0 0 0 0 0 0 00 0 0 02 (0) 20 0 0 210 log log log . log . 11 2 3 . .log 2 log 3 log . (0) 1 log .log

32、log. (0) 1 .(1)L L LL Lp p p p p p p pp p p p p p L p pp p p pp p L p pH L 同 理 ： 00( )H pp HUST - Basis for Information Theory 47 原 二 元 序 列 的 熵 H(X)o0游 程 序 列 的 熵 與 1游 程 序 列 的 熵 之 和 除 以 它們 的 平 均 游 程 長(zhǎng) 度 之 和 。n H (X) = H L(0)+ H L(1) / (l0+l1) = H (p0 ) /p1 + H (p0 ) /p0 / (1/ p1 +1/ p0 ) = H (p0 ) =

33、H (p1 ) o 游 程 變 換 后 符 號(hào) 熵 沒 有 變 。o 當(dāng) 0游 程 和 1游 程 的 編 碼 效 率 都 很 高 時(shí) ， 采 用游 程 編 碼 的 效 率 也 會(huì) 高 。 HUST - Basis for Information Theory 48 相 關(guān) 性 二 元 序 列 的 游 程 變 換o 若 原 二 元 序 列 是 二 階 馬 氏 鏈 ， 由 它 變 換 而 來 的 游 程序 列 將 也 是 獨(dú) 立 序 列 。n 0游 程 ： 10X； 1游 程 ： 01Xo 對(duì) 于 高 階 馬 氏 鏈 ， 若 階 數(shù) 大 于 2， 經(jīng) 變 換 的 游 程 序列 將 不 再 是 獨(dú)

34、立 序 列 。n 如 三 階 馬 氏 鏈 ： Y10X一 階 馬 氏 鏈n 一 般 k階 馬 氏 鏈 ， 由 之 變 換 而 來 的 游 程 序 列 將 為 k-2階 馬氏 鏈 。o 通 過 游 程 變 換 可 有 效 的 解 除 或 減 弱 二 元 序 列 的 相 關(guān)性 ， 再 對(duì) 游 程 長(zhǎng) 度 進(jìn) 行 編 碼 可 達(dá) 到 較 高 的 編 碼 效 率 。 HUST - Basis for Information Theory 49 游 程 長(zhǎng) 度 與 碼 字 之 間 的 o 取 適 當(dāng) 值 n， 游 程 長(zhǎng) 度 為 1, 2, , 2n-1, 2n， 所 有 大 于 2n者 ， 都 按 2

35、n處 理 。o 所 有 長(zhǎng) 度 大 于 等 于 2n的 游程 ， 只 有 一 個(gè) 碼 字 C， 需 要按 右 表 進(jìn) 一 步 區(qū) 分 。o 當(dāng) 游 程 長(zhǎng) 度 大 于 或 等 于 2n+1時(shí) ， 需 要 兩 個(gè) 或 兩 個(gè) 以 上的 C 。 概 率 小 ， 碼 字 長(zhǎng) 。o 0游 程 和 1游 程 應(yīng) 分 別 編 碼 ，建 立 各 自 的 碼 字 和 碼 表 。碼 字 可 重 復(fù) ， C必 須 不 同 。如 ： C 0 或 C1 游 程 長(zhǎng) 度 2n C之 后 為 一 個(gè) n位 的 自然 碼 （ C0 或 C1）2n C00002n+1 C0001 2n+1 -1 C11112n+1 C000

36、0 C00002 n+2 -1 C0000 C1111 HUST - Basis for Information Theory 50 冗 余 位 編 碼 （ Lynch-Davission）o 冗 余 位 ： 信 源 序 列 中 不 攜 帶 信 息 的 符 號(hào) ， 除 了 符 號(hào)數(shù) 目 或 所 占 時(shí) 長(zhǎng) 外 ， 可 不 必 傳 送 。n 語 音 中 的 話 語 間 歇 、 圖 像 的 單 一 背 景 部 分 。o 去 掉 部 分 冗 余 信 息 可 以 提 高 通 信 效 率 。o 設(shè) 有 多 元 信 源 序 列 ： x 為 信 息 位 ； y 冗 余 位n x 1 , x2 ,xm1 ,y

37、,y,y, xm1+1 , xm1+2 , xm2 ,y,y, 可 用 下 面 兩 個(gè) 序 列 來 代 替 ：n 冗 余 位 序 列 ： 111,100,000111,111000n 信 息 位 序 列 ： x1 , x2 ,xm1 , xm1+1 , xm1+2 , xm2 , HUST - Basis for Information Theory 51 冗 余 位 編 碼 思 路分 解 ： 一 個(gè) 和 一 個(gè)。o 對(duì) 兩 個(gè) 序 列 分 別 編 碼 ， 有 效 壓 縮 信 源n 如 ： 對(duì) 二 元 序 列 進(jìn) 行 游 程 編 碼 ； 對(duì) 多 元 序 列 直接 采 用 哈 夫 曼 編 碼 。

38、o 要 求 同 時(shí) 傳 送 兩 個(gè) 序 列 ， 才 能 在 接 收 端 實(shí) 時(shí)恢 復(fù) 出 原 來 的 多 元 信 源 序 列 。n 實(shí) 際 應(yīng) 用 有 困 難 ， 通 常 采 用 分 幀 傳 送 的 方 式 。 HUST - Basis for Information Theory 52 分 幀 傳 送 冗 余 位 序 列 ： L-D編 碼o 在 中 取 N個(gè) 符 號(hào) 作 為 一 幀 ， 編 成一 個(gè) ， 其 后 就 把 本 幀 中 的 信 息 位 按 序 排列 ， 再 取 下 一 幀 作 同 樣 處 理 。 在 接 收 端 根 據(jù)這 些 碼 字 和 信 息 序 列 進(jìn) 行 譯 碼 。o 每

39、個(gè) 中 含 有 ： 和 11 1Q jjj Q nT jn jn n 其 中 是 幀 內(nèi) 第 個(gè) 信 息 位 的 位 置 序 號(hào) ，最 小 ， 最 大 。 HUST - Basis for Information Theory 53 L-D編 碼 的 譯 碼 過 程o 收 端 收 到 Q和 T后 ， 如 下 譯 碼 ：1 11 1 11 11 11QQ K KK TQ QKn K T T QL LL TQ Qn L n 尋 找 某 一 值 ， 若則 ， 再 令 ，再 找 某 一 值 ， 若則 ， 依 次 直 至 求 出 ， 從 而 確 定 所 有 位 置 信 息 。1 1K K KQ Q Q

40、這 種 譯 碼 的 唯 一 性 可 通 過 恒 等 式 來 證 明 。 HUST - Basis for Information Theory 54 編 碼 Q和 To Q可 以 取 0到 N的 各 種 值 ， 共 N+1種 ， 故 log 1log log 1 logQ N NQ QNT Q N XA N Q 表 達(dá) 值 需 要 比 特 ；值 確 定 后 ， 各 信 息 位 的 可 能 位 置 共 有 種 ，表 達(dá) 值 需 要 比 特 。 所 以 ， 共 需 要表 示 向 上 取 整 。比 特 HUST - Basis for Information Theory 55 例 ： 對(duì) 一 冗

41、余 位 序 列 編 L-D碼o 一 冗 余 位 序 列 ： 00 0000000 0000， N=15o 這 里 Q=2， n1=3， n2=11， 則 2 1 11 1 3 1 10 9 2 1+ =472 1 2 1 115 15 14 105, log105 7, log 15 1010111 42 2 14 7 001015 4 27 , 4711 13TNQ Q TL D N Q QT Tn n 分 別 用 位 和 位 二 進(jìn) 制 自 然 碼 表 示 和 ，即 得 編 碼 ：譯 碼 時(shí) ， 已 知 ， 前 位 必 為 值 ， 即 。后 位 必 為 為 。 由 前 面 譯 碼 過 程

42、可 算 出， ， 即 可 恢 復(fù) 出 原 冗 余 位 序 列 。 HUST - Basis for Information Theory 56 Q=2和 T=47的 譯 碼 過 程o 收 端 收 到 Q=2和 T=47后 ， 如 下 譯 碼 ：4710 1 1110 9 11 1010 45 552 2 212 29 9 1 109 8 10 99 36 452 2 2 22 1 2 111 111 1011 552 2 21 22 1 2 12K KKKK K KK KKK 尋 找 某 一 值 ， 若 2 12 12 11 61 10 1 1 2 11 62Qn K n 則 ， HUST -

43、 Basis for Information Theory 57 Q=2和 T=47的 譯 碼 過 程 -續(xù)1 12 1 101 11 47 47 45 221 1 2 1 11 11 1 21 1 22 1 32 2 31 11 11 1 21 1Q Q Kn K n T T QL LL QQ QL TL LL QLn Q LQ Q ， 再時(shí) ， 令 ，再 找 某 一 值 ， 若時(shí)則 ， ， 122 1 11 1 2 1 33 11n L nnn n ， 求 出 ， 從 而 確 定 了 所 有 位 置 信 息 。即 ： ， HUST - Basis for Information Theor

44、y 58 對(duì) 例 題 的 說 明o 當(dāng) Q為 0或 N時(shí) ， 相 當(dāng) 于 全 0或 全 1序 列 ， 此時(shí) T值 為 0， 在 編 碼 時(shí) 只 需 編 Q值 ， 對(duì) 于N=15， 得 0000或 1111oL-D編 碼 與 哈 夫 曼 碼 不 同 ， 不 需 要 已 知 概 率特 性 。 也 就 是 編 成 的 碼 字 與 概 率 特 性 無 關(guān) ，而 與 一 幀 內(nèi) 的 信 息 位 的 數(shù) 目 有 關(guān) ， 即 碼 字 長(zhǎng)度 與 Q有 關(guān) 。 HUST - Basis for Information Theory 59 碼 字 長(zhǎng) 度 與 Q的 關(guān) 系 Q 0 1 2 3 4 5 6 715

45、14 13 12 11 10 9 8Log(15 Q ) 0 3.91 6.71 8.83 10.4 11.8 12.3 12.9T的 碼 字 長(zhǎng) 度 0 4 7 9 11 12 13 13碼 字 總 長(zhǎng) 度 4 8 11 13 15 16 17 17壓 縮 率 r 0.27 0.53 0.73 0.87 1 1.07 1.13 1.13o 概 率 未 知 ， 無 法 計(jì) 算 熵 ， 也 無 法 計(jì) 算 編 碼 效 率 ， 一 般 只 能 用壓 縮 率 來 表 達(dá) 編 碼 增 益 。o 當(dāng) Q接 近 N/2時(shí) ， L-D編 碼 是 無 效 的 ； 當(dāng) Q接 近 0或 N時(shí) ， 可得 很 小 的

46、 壓 縮 率 ， N很 大 時(shí) 更 有 效 。 HUST - Basis for Information Theory 60 編 碼 方 法 小 結(jié)o 介 紹 了 幾 種 變 長(zhǎng) 碼 的 編 碼 方 法 ：n 香 農(nóng) 編 碼 、 哈 夫 曼 編 碼 和 費(fèi) 諾 編 碼n 游 程 編 碼 和 冗 余 位 編 碼o 變 長(zhǎng) 碼 的 缺 點(diǎn) ：n 1.高 概 率 符 號(hào) 和 低 概 率 符 號(hào) 出 現(xiàn) 的 不 均 勻 與 信 源 符 號(hào) 恒 速 輸 出的 矛 盾 。 信 道 可 能 無 信 息 可 送 ， 或 信 息 溢 出 而 丟 失 。 （ 需 要 很大 的 緩 存 ）n 2.差 錯(cuò) 的 擴(kuò) 散

47、 。 因 為 它 采 用 異 前 置 碼 來 分 解 碼 字 ， 一 旦 傳 送 中出 現(xiàn) 誤 碼 ， 則 某 個(gè) 碼 字 的 前 置 部 分 可 能 成 為 另 一 個(gè) 碼 字 ， 因 而錯(cuò) 譯 為 另 一 個(gè) 符 號(hào) 。 （ 需 要 采 用 差 錯(cuò) 控 制 ） HUST - Basis for Information Theory 61 本 章 小 結(jié)o 介 紹 了 變 長(zhǎng) 碼 基 本 特 征 和 平 均 碼 長(zhǎng) 的 概 念 ；o 通 過 克 拉 夫 特 不 等 式 和 麥 克 米 倫 不 等 式 ， 給 出 了 為 構(gòu) 成唯 一 可 譯 碼 ， 信 源 符 號(hào) 數(shù) 和 碼 字 長(zhǎng) 度 之 間 應(yīng) 滿 足 的 條 件 ；o 給 出 了 一 種 唯 一 可 譯 碼 的 判 別 準(zhǔn) 則 ；o 討 論 了 香 農(nóng) 第 一 定 理 ： 變 長(zhǎng) 編 碼 定 理 ；o 學(xué) 習(xí) 了 幾 種 變 長(zhǎng) 碼 的 編 碼 方 法 ， 包 括 ： 香 農(nóng) 編 碼 、 費(fèi) 諾編 碼 和 霍 夫 曼 編 碼 。