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

1、第 5 章 信 源 編 碼 5.1 編 碼 的 定 義 5.2 無 失 真 信 源 編 碼 5.3 限 失 真 信 源 編 碼 定 理 5.4 常 用 信 源 編 碼 方 法 簡 介 編 碼 通 信 的 實(shí) 質(zhì) 是 傳 輸 信 息 ， 通 信 系 統(tǒng) 的 性 能 指 標(biāo) 主 要 有 有 效 性 、 可 靠 性 、 安 全 性 等 ， 這 些 指 標(biāo) 正 是 信 息 論 研 究 的 對(duì) 象 。 編 碼 的 目 的 是 為 了 優(yōu) 化 通 信 系 統(tǒng) ， 就 是 使 這 些 指 標(biāo) 達(dá) 到 最 佳 。 按 不 同 的 編 碼 目 的 ， 編 碼 分 為 三 類 ： 信 源 編 碼 信 道 編 碼

2、安 全 編 碼 /密 碼 信 源 編 碼 信 源 編 碼 是 以 提 高 通 信 的 有 效 性 為 目 的 編 碼 。 通 常 通 過 壓 縮 信 源 的 冗 余 度 來 實(shí) 現(xiàn) 。 采 用 的 一 般 方 法 是 壓 縮 每 個(gè) 信 源 符 號(hào) 的 平 均 比 特 數(shù) 或 信 源 的 碼 率 。 同 樣 多 的 信 息 用 較 少 的 碼 率 來 傳 送 ， 使 單 位 時(shí) 間 內(nèi) 傳 送 的 平 均 信 息 量 增 加 ， 從 而 提 高 通 信 的 有 效 性 。 在 不 失 真 或 允 許 失 真 的 條 件 下 ， 用 盡 可 能 少 的 符 號(hào) 傳 送 信 源 信 息 。 信 道

3、 編 碼 ： 是 以 提 高 信 息 傳 輸 的 可 靠 性 為 目 的 的 編 碼 。 通 常 通 過 增 加 信 源 的 冗 余 度 來 實(shí) 現(xiàn) 。 采 用 的 一 般 方 法 是 增 大 碼 率 /帶 寬 。 在 信 道 受 干 擾 的 情 況 下 增 加 信 號(hào) 的 抗 干 擾 能 力 ， 同 時(shí) 又 使 得 信 息 傳 輸 率 最 大 。 密 碼 ： 是 以 提 高 通 信 系 統(tǒng) 的 安 全 性 為 目 的 的 編 碼 。 通 常 通 過 加 密 和 解 密 來 實(shí) 現(xiàn) 。 無 失 真 編 碼 無 失 真 信 源 編 碼 定 理 信 源 編 碼 限 失 真 編 碼 限 失 真 信

4、源 編 碼 定 理 無 失 真 ( 冗 余 度 壓 縮 編 碼 ) ： 僅 對(duì) 信 源 的 冗 余 度 進(jìn) 行 壓 縮 ， 不 改 變 信 源 的 熵 。 無 失 真 編 碼 是 可 逆 的 ， 即 當(dāng) 信 源 符 號(hào) 變 換 成 代 碼 后 ， 可 從 代 碼 無 失 真 地 恢 復(fù) 出 原 信 源 符 號(hào) 。 只 適 用 于 離 散 信 源 。 限 失 真 ( 熵 壓 縮 編 碼 ) ： 在 失 真 受 限 的 情 況 下 進(jìn) 行 限 失 真 編 碼 。 在 連 續(xù) 信 源 的 情 況 下 ， 由 于 信 源 的 信 息 量 趨 于 無 限 ， 顯 然 不 能 用 離 散 符 號(hào) 序 列

5、來 完 成 無 失 真 編 碼 ， 而 只 能 進(jìn) 行 限 失 真 編 碼 。 離 散 信 源 無 失 真 信 源 編 碼 定 理 稱 為 第 一 極 限 定 理 離 散 和 連 續(xù) 信 道 信 道 編 碼 定 理 稱 為 第 二 極 限 定 理 限 失 真 信 源 編 碼 定 理 稱 為 第 三 極 限 定 理 連 續(xù) 信 源 信 源 編 碼 的 主 要 任 務(wù) 符 號(hào) 變 換 ： 使 信 源 輸 出 符 號(hào) 與 信 道 輸 入 符 號(hào) 匹 配 。 減 少 冗 余 ， 提 高 編 碼 效 率 。 針 對(duì) 信 源 輸 出 符 號(hào) 序 列 的 統(tǒng) 計(jì) 特 性 ， 尋 找 一 定 的 方 法 把

6、信 源 輸 出 符 號(hào) 序 列 變 換 為 最 短 的 碼 字 序 列 。 信 源 編 碼 的 基 本 途 徑 使 序 列 中 的 各 個(gè) 符 號(hào) 盡 可 能 地 互 相 獨(dú) 立 ， 即 解 除 相 關(guān) 性 ， 去 冗 余 ； 使 編 碼 中 各 個(gè) 符 號(hào) 出 現(xiàn) 的 概 率 盡 可 能 地 相 等 ， 即 概 率 均 勻 化 。 本 章 討 論 離 散 信 源 編 碼 。 首 先 從 無 失 真 編 碼 定 理 出 發(fā) ， 重 點(diǎn) 討 論 以 香 農(nóng) 碼 、 費(fèi) 諾 碼 和 霍 夫 曼 碼 為 代 表 的 最 佳 無 失 真 碼 。 5.1 編 碼 的 定 義 信 源 編 碼 ： 信 源

7、輸 出 符 號(hào) 經(jīng) 信 源 編 碼 器 編 碼 后 轉(zhuǎn) 換 成 另 外 的 壓 縮 符 號(hào) 無 失 真 信 源 編 碼 ： 可 精 確 無 失 真 地 復(fù) 制 信 源 輸 出 的 消 息 編 碼 器 的 作 用 將 信 源 符 號(hào) 集 X 中 的 符 號(hào) 變 換 成 由 碼 符 號(hào) 集 y 中 的 碼 元 組 成 的 長 度 為 Ki 的 一 一 對(duì) 應(yīng) 的 碼 字 。 碼 字 集 合 叫 做 代 碼 組 Y； 碼 字 所 含 碼 元 的 個(gè) 數(shù) 稱 為 該 碼 字 的 碼 長 ， 記 為 Ki 。 分 組 碼 將 信 源 消 息 分 成 若 干 組 ， 即 符 號(hào) 序 列 ， 每 個(gè) 符 號(hào)

8、 序 列 依 照 固 定 碼 表 映 射 成 一 個(gè) 碼 字 ， 這 樣 的 碼 稱 為 分 組 碼 ， 有 時(shí) 也 叫 塊 碼 。 只 有 分 組 碼 才 有 對(duì) 應(yīng) 的 碼 表 ， 而 非 分 組 碼 中 則 不 存 在 碼 表 。 例 ： 若 將 信 源 X 通 過 二 元 信 道 傳 輸 ， 就 必 須 把 信 源 符 號(hào) a i 變 換 成 由 0 、 1符 號(hào) 組 成 的 碼 符 號(hào) 序 列 ， 這 個(gè) 過 程 就 是 信 源 編 碼 。 定 長 碼 固 定 長 度 的 碼 ， 碼 中 所 有 碼 字 的 長 度 都 相 同 。 變 長 碼 可 變 長 度 碼 ， 碼 中 的 碼

9、字長 短 不 一 。 定 長 碼 變 長 碼 若 0 、 01 都 是 碼 字 ， 譯 碼 時(shí) 如 何 分 離 ？ 分 組 碼 / 塊 碼 將 信 源 符 號(hào) 集 中 的 每 個(gè) 符 號(hào) 映 射 成 一 個(gè) 固 定 的 碼 字 。 分 組 碼 必 須 具 有 某 些 屬 性 ， 才 能 保 證 在 接 收 端 能 夠 迅 速 可 靠 地 譯 碼 。 碼 的 不 同 屬 性 碼 表 信 源 符 號(hào) 信 源 出 現(xiàn) 概 率 p(ai) 符 號(hào) ai 碼 1 碼 2 碼 3 碼 4 a 1 1/2 0 0 1 1 a 2 1/4 11 10 10 01 a 3 1/8 00 00 100 001 a

10、 4 1/8 11 01 1000 0001 奇 異 碼 奇 異 碼 和 非 奇 異 碼 1 若 信 源 符 號(hào) 和 碼 字 是 一 一 對(duì) 應(yīng) 的 ， 則 該 碼 為 非 奇 異 碼 。 反 之 為 奇 異 碼 。 唯 一 可 譯 碼 2 任 意 有 限 長 的 碼 元 序 列 ， 只 能 被 唯 一 地 分 割 成 一 個(gè) 個(gè) 碼 字 。 例 ： 0,10,11 是 一 種 唯 一 可 譯 碼 。 任 意 一 串 有 限 長 碼 序 列 ， 如 100111000 ， 只 能 被 分 割 成 10、 0、 11、 10 、 0、 0 。 任 何 其 他 分 割 法 都 會(huì) 產(chǎn) 生 一 些

11、非 定 義 的 碼 字 。 奇 異 碼 不 是 唯 一 可 譯 碼 非 唯 一 可 譯 碼 碼 2 ， 可 譯 成 a 1a1或 a3 非 奇 異 碼 唯 一 可 譯 碼 碼 3 ， 但 譯 碼 有 延 時(shí) 非 即 時(shí) 碼 唯 一 可 譯 碼 即 時(shí) 碼 非 即 時(shí) 碼 接 收 端 收 到 一 個(gè) 完 整 的 碼 字 后 ， 不 能 立 即 譯 碼 ， 還 需 等 下 一 個(gè) 碼 字 開 始 接 收 后 才 能 判 斷 是 否 可 以 譯 碼 。 碼 3 即 時(shí) 碼 ( 非 延 長 碼 ) ( 異 前 綴 碼 ) 在 譯 碼 時(shí) 無 需 參 考 后 續(xù) 的 碼 符 號(hào) 就 能 立 即 作 出

12、判 斷 ， 譯 成 對(duì) 應(yīng) 的 信 源 符 號(hào) 。 碼 4 任 意 一 個(gè) 碼 字 都 不 是 其 它 碼 字 的 前 綴 部 分 碼 1 碼 2 碼 3 碼 4 ai a1 0 0 1 1 a2 11 10 10 01 a3 00 00 100 001 a4 11 01 1000 0001 即 時(shí) 碼 奇 異 碼 非 唯 一 可 譯 碼 非 即 時(shí) 碼 用 碼 樹 來 構(gòu) 造 碼 字 碼 樹 從 樹 根 開 始 向 下 長 出 m 個(gè) 樹 枝 ， 成 為 m 進(jìn)制 碼 樹 ， 樹 枝 代 表 碼 元 ， 樹 枝 與 樹 枝 的 交 點(diǎn) 叫 做 節(jié) 點(diǎn) 。 經(jīng) 過 r 個(gè) 樹 枝 才 能 到

13、達(dá) 的 節(jié) 點(diǎn) 稱 為 r 階 節(jié) 點(diǎn) 。 向 下 不長 出 樹 枝 的 節(jié) 點(diǎn) 稱 為 終 端 節(jié) 點(diǎn) 或 端 點(diǎn) 。 m 進(jìn) 制 碼 樹 各 節(jié) 點(diǎn) ( 包 括 樹 根 ) 向 下 長 出 的 樹 枝 不 會(huì) 超 過 m， 若 等 于 m稱 為 滿 樹 (整 樹 ) ， 否 則 稱 為 非 滿 樹 (非 整 樹 ) 。 碼 樹 上 任 一 節(jié) 點(diǎn) 都 對(duì) 應(yīng) 一 個(gè) 碼 字 ， 組 成 該 碼 字 的 碼 元 就 是 從 樹 根 開 始 到 該 節(jié) 點(diǎn) 所 經(jīng) 過 的 樹 枝 ( 碼 元 ) 。 若 一 個(gè) 碼 所 有 碼 字 均 處 于 終 端 節(jié) 點(diǎn) ， 則 該 碼 為 即 時(shí) 碼 。

14、 滿 樹 等 長 碼 節(jié) 數(shù) 碼 長 非 滿 樹 變 長 碼 樹 碼 ： 若 有 n 個(gè) 信 源 符 號(hào) ， 那 么 在 碼 樹 上 就 要 選 擇 n 個(gè) 終 端 節(jié) 點(diǎn) ， 用 相 應(yīng) 的 m 元 基 本 符 號(hào) 表 示 這 些 碼 字 。 任 一 即 時(shí) 碼 都 可 用 樹 圖 法 來 表 示 。 當(dāng) 碼 字 長 度 給 定 ， 即 時(shí) 碼 不 是 唯 一 的 。 該 碼 樹 從 根 到 終 端 節(jié) 點(diǎn) 所 經(jīng) 路 徑 上 ， 每 一 個(gè) 中 間 節(jié) 點(diǎn) 皆 為 碼 字 ， 因 此 碼 3 不 是 即 時(shí) 碼 ， 但 它 是 唯 一 可 譯 碼 。 唯 一 可 譯 碼 存 在 的 充 分

15、 和 必 要 條 件 各 碼 字 的 長 度 K i 應(yīng) 符 合 克 勞 夫 特 (Kraft) 不 等 式 ： m ： 碼 元 進(jìn) 制 數(shù) n ： 信 源 符 號(hào) 數(shù) Ki ： 各 個(gè) 碼 字 的 長 度 例 ： 設(shè) 二 進(jìn) 制 碼 樹 中 X ( a 1, a2, a3, a4)， K1 =1 ， K2 =2 ， K3 =2 ， K4 =3 。 應(yīng) 用 Kraft 不 等 式 ， 得 ：不 存 在 滿 足 這 種 K i 的 唯 一 可 譯 碼 要 形 成 滿 足 上 述 長 度的 碼 字 ， 必 須 在 中 間 節(jié) 點(diǎn) 放 置 碼 字 。 中 間 節(jié) 點(diǎn)如 果 將 各 碼 字 長 度 改

16、 成 ： 存 在 唯 一 可 譯 碼 K1 =1 ， K2 =2 ， K3 =2 ， K4 =3 。 K1 =1 , K2 =2 , K3 =3 , K4 =3 。 注 意 Kraft 不 等 式 只 是 用 來 說 明 唯 一 可 譯 碼 是 否 存 在 ， 并 不 能 作 為 唯 一 可 譯 碼 的 判 據(jù) 。 如 碼 字 0， 10， 010， 111 雖 然 滿 足 Kraft 不 等 式 ， 但 它 不 是 唯 一 可 譯 碼 。 K1 =1 , K2 =2 , K3 =3 , K4 =3 。 5.2 無 失 真 信 源 編 碼 要 求 能 夠 無 失 真 或 無 差 錯(cuò) 地 譯 碼

17、 ， 同 時(shí) 希 望 所 得 編 碼 的 平 均 碼 長 最 小 。 對(duì) 信 源 的 L 長 符 號(hào) 序 列 進(jìn) 行 m 進(jìn) 制 編 碼 ， 碼 長 KL 只 要 可 用 的 碼 字 數(shù) 不 少 于 擴(kuò) 展 信 源 的 符 號(hào) 數(shù) ：就 可 做 到 唯 一 譯 碼 編 碼 輸 出 碼 字 的 個(gè) 數(shù) KL/L 是 平 均 每 個(gè) 信 源 符 號(hào) 所 需 要 的 碼 元 符 號(hào) 個(gè) 數(shù) 編 碼 后 平 均 每 個(gè) 信 源 符 號(hào) 能 載 荷 的 最 大 信 息 量 為 ： 5.2.1 定 長 編 碼 定 理 在 定 長 編 碼 中 ， K=KL 是 定 值 ， 且 為 唯 一 可 譯 碼 。 編

18、 碼 的 目 的 是 尋 找 最 小 K 值 若 對(duì) 信 源 進(jìn) 行 定 長 編 碼 ， 必 須 滿 足 : 對(duì) 于 定 長 唯 一 可 譯 碼 ， 每 個(gè) 信 源 符 號(hào) 至 少 需 用 （ log n / log m ） 個(gè) 碼 符 號(hào) 來 變 換 。 例 : 英 文 電 報(bào) 符 號(hào) ， n =27 ， L =1 ， m =2( 二 元 編 碼 ) log 2 n K = log 2 27 5 每 個(gè) 英 文 電 報(bào) 符 號(hào) 至 少 log 2 m 要 用 5位 二 元 符 號(hào) 編 碼 實(shí) 際 英 文 電 報(bào) 符 號(hào) 信 源 ， 平 均 每 個(gè) 英 文 電 報(bào) 符 號(hào) 所 提 供 的 信

19、息 量 約 等 于 1.4 比 特 ， 大 大 小 于 5 比 特 。 定 長 編 碼 后 每 個(gè) 碼 字 (5個(gè) 二 元 符 號(hào) )只 攜 帶 約 1.4比 特 信 息 量 。 定 長 編 碼 的 信 息 傳 輸 效 率 極 低 當(dāng) 考 慮 信 源 符 號(hào) 出 現(xiàn) 的 概 率 及 符 號(hào) 間 的 依 賴 關(guān) 系 后 （ 考 慮 信 源 的 冗 余 度 ） ， 在 定 長 編 碼 中 每 個(gè) 信 源 符 號(hào) 平 均 所 需 的 碼 長 可 以 減 少 。 定 長 編 碼 定 理 給 出 了 信 源 進(jìn) 行 定 長 編 碼 所 需 碼 長 的 理 論 極 限 值 。 定 長 編 碼 定 理 編

20、碼 器 的 平 均 輸 出 信 息 率 對(duì) 于 二 進(jìn) 制 編 碼 ， 每 個(gè) 信 源 符 號(hào) 必 須 輸 出 的 碼 長 定 長 編 碼 定 理 說 明 ： 只 要 碼 字 所 能 攜 帶 的 信 息 量 大 于 信 源 序 列 輸 出 的 信 息 量 ， 則 可 以 使 傳 輸 幾 乎 無 失 真 ， 當(dāng) 然 條 件 是 L足 夠 大 。 當(dāng) 時(shí) ， 不 可 能 構(gòu) 成 無 失 真 的 編 碼 ， 也 就 是 不 可 能 做 一 種 編 碼 器 ， 能 使 收 端 譯 碼 時(shí) 差 錯(cuò) 概 率 趨 于 零 。 當(dāng) 時(shí) ， 則 為 臨 界 狀 態(tài) ， 可 能 無 失 真 ， 也 可 能 有 失

21、 真 。 差 錯(cuò) 概 率 設(shè) 差 錯(cuò) 概 率 用 Pe 表 示 ， 則 有 ： 為 一 正 數(shù) 為 信 源 序 列 的 自 信 息 方 差 當(dāng) 均 為 定 值 時(shí) ， 只 要 L 足 夠 大 ， Pe可 以 小 于 任 一 正 數(shù) 。 即 ：當(dāng) 信 源 序 列 長 度 L 滿 足能 達(dá) 到 差 錯(cuò) 率 要 求 ： 編 碼 效 率 編 碼 效 率 總 定 義 編 碼 效 率 為 ： 是 小 于 1 信 源 的 平 均 符 號(hào) 熵 為 H L (X) ， 采 用 平 均 符 號(hào) 碼 長 為 K 來 編 碼 后 所 得 的 效 率 。 最 佳 編 碼 效 率 ：編 碼 定 理 從 理 論 上 闡 明

22、 了 編 碼 效 率 接 近 1 的 理 想 編 碼 器 的 存 在 性 ， 它 使 輸 出 符 號(hào) 的 信 息 率 與 信 源 熵 之 比 接 近 于 1 ， 即 ： 若 要 實(shí) 現(xiàn) ， 取 無 限 長 L 的 信 源 符 號(hào) 進(jìn) 行 統(tǒng) 一 編 碼 。 例 ： 設(shè) 離 散 無 記 憶 信 源 概 率 空 間 為 信 源 熵 ： H ( X ) = - p ( xi ) log p ( xi ) = 2.55 bit / 符 號(hào) i = 1 對(duì) 信 源 符 號(hào) 采 用 定 長 二 元 編 碼 , 要 求 編 碼 效 率 為 90 若 取 L 1 ， 則即 每 個(gè) 符 號(hào) 用 2.83bit

23、進(jìn) 行 定 長 編 碼 ， 共 有 22.83 =7.11 種 可 能 ， 按 7 種 可 能 性 計(jì) 算 ， 信 源 符 號(hào) 中 就 有 一 種 符 號(hào) 沒 有 對(duì) 應(yīng) 的 碼 字 ， 取 概 率 最 小 的 a 8 ， 則 Pe=0.04 , 太 大 信 源 序 列 的 自 信 息 方 差 ： 若 要 求 譯 碼 錯(cuò) 誤 概 率 10-6 L 應(yīng) 滿 足 ：對(duì) 于 定 長 編 碼 ， 即 使 在 編 碼 效 率 和 譯 碼 錯(cuò) 誤 概 率 的 要 求 并 不 十 分 苛 刻 的 情 況 下 ， 就 需 要 10 8 個(gè) 信 源 符 號(hào) 一 起 進(jìn) 行 編 碼 。 這 顯 然 是 很 難 實(shí)

24、 現(xiàn) 的 。 5.2.2 變 長 編 碼 定 理 在 變 長 編 碼 中 ， 碼 長 KL是 變 化 的 。 根 據(jù) 信 源 各 個(gè) 符 號(hào) 的 統(tǒng) 計(jì) 特 性 ， 如 概 率 大 的 符 號(hào) 用 短 碼 ， 概 率 小 的 用 較 長 的 碼 ， 使 得 編 碼 后 平 均 碼 長 降 低 ， 從 而 提 高 編 碼 效 率 。 （ 統(tǒng) 計(jì) 匹 配 ） 編 碼 后 碼 字 Y 1 , Y 2 , , Y n 碼 長 分 別 為 K 1 , K 2 , , K n 碼 的 平 均 長 度 為 ：編 碼 后 的 信 息 傳 輸 率 為 ： 對(duì) 于 某 一 信 源 和 某 一 碼 符 號(hào) 集 ，

25、若 有 一 個(gè) 唯 一 可 譯 碼 ， 其 平 均 長 度 小 于 所 有 其 他 唯 一 可 譯 碼 的 平 均 長 度 ， 則 稱 該 碼 為 最 佳 碼 （ 緊 致 碼 ） 。 單 個(gè) 符 號(hào) 變 長 編 碼 定 理 若 離 散 無 記 憶 信 源 的 符 號(hào) 熵 為 H (X) ， 每 個(gè) 信 源 符 號(hào) 用 m 進(jìn) 制 碼 元 進(jìn) 行 變 長 編 碼 ， 一 定 存 在 一 種 無 失 真 編 碼 方 法 ， 其 碼 字 平 均 長 度 K 滿 足 下 列 不 等 式 ： H ( X ) H ( X ) K + 1 log m log m 離 散 平 穩(wěn) 無 記 憶 序 列 變 長

26、編 碼 定 理 對(duì) 于 平 均 符 號(hào) 熵 為 H L(X) 的 離 散 平 穩(wěn) 無 記 憶 信 源 ， 必 存 在 一 種 無 失 真 編 碼 方 法 ， 使 平 均 信 息 率 R 滿 足 不 等 式 ： 其 中 為 任 意 小 正 數(shù) 。 無 失 真 變 長 信 源 編 碼 定 理 （ 香 農(nóng) 第 一 定 理 ） 對(duì) 于 平 均 符 號(hào) 熵 為 H L(X) 的 離 散 平 穩(wěn) 無 記 憶 信 源 （ 離 散 無 記 憶 信 源 X 的 L 次 擴(kuò) 展 信 源對(duì) 其 進(jìn) 行 m 元 編 碼 ， 必 存 在 一 種 無 失 真 編 碼 方 法 ， 構(gòu) 成 唯 一 可 譯 碼 ， 使 信 源

27、 X 中 每 個(gè) 信 源 符 號(hào) 所 需 的 平 均 碼 長 滿 足 ： 用 變 長 編 碼 可 達(dá) 到 相 當(dāng) 高 的 編 碼 效 率 ， 一 般 所 要 求 的 符 號(hào) 長 度 L 可 以 比 定 長 編 碼 小 得 多 。 編 碼 效 率 的 下 界 為 了 衡 量 各 種 編 碼 方 法 與 最 佳 碼 的 差 距 ， 定 義 碼 的 剩 余 度 為 ： 同 前 例 ： 設(shè) 離 散 無 記 憶 信 源 概 率 空 間 為 信 源 熵 ： H ( X ) = 2 . 55 bit / 符 號(hào) 要 求 編 碼 效 率 為 90 用 二 進(jìn) 制 變 長 編 碼 ， m 2 例 ： 設(shè) 離 散

28、 無 記 憶 信 源 概 率 空 間 為 信 源 熵 ： H ( X ) = 1/4 log4 +3/4 log3/4 = 0. 811 bit / 信 源 符 號(hào) 若 用 二 元 定 長 編 碼 (0,1) 來 構(gòu) 造 一 個(gè) 即 時(shí) 碼 ： 平 均 碼 長 ： 二 元 碼 符 號(hào) / 信 源 符 號(hào) 編 碼 效 率 ： 輸 出 的 信 息 傳 輸 率 ： 再 對(duì) 長 度 L 為 2 的 信 源 序 列 進(jìn) 行 變 長 編 碼 ， 其 即 時(shí) 碼 如 表 ： 碼 字 平 均 長 度 ： 單 個(gè) 符 號(hào) 的 平 均 碼 長 編 碼 效 率 輸 出 的 信 息 傳 輸 率 ： R 2 0.961

29、bit/ 二 元 碼 符 號(hào) 信 源 序 列 的 長 度 增 加 : 編 碼 復(fù) 雜 一 些 ， 但 信 息 傳 輸 率 有 了 提 高 變 長 編 碼 ： L 2 ， 2 = 0.961 定 長 編 碼 ： 要 求 編 碼 效 率 達(dá) 到 96 時(shí) ， 允 許 譯 碼 錯(cuò) 誤 概 率 10 5 說 明 (1) 定 長 碼 需 要 的 信 源 序 列 長 ， 使 碼 表 很 大 ， 且 總 存 在 譯 碼 差 錯(cuò) 。 而 用 變 長 碼 編 碼 時(shí) ， L 不 需 要 很 大 就 可 達(dá) 到 相 當(dāng) 高 的 編 碼 效 率 ， 而 且 可 實(shí) 現(xiàn) 無 失 真 編 碼 。 (2) 隨 著 信 源

30、 序 列 長 度 的 增 加 ， 編 碼 的 效 率 越 來 越 接 近 于 1 。 編 碼 后 的 傳 輸 率 R 也 越 來 越 接 近 于 無 噪 無損 二 元 對(duì) 稱 信 道 的 信 道 容 量 (1bit/ 二 元 碼 符 號(hào) ) ， 達(dá) 到信 源 與 信 道 的 匹 配 。 最 佳 變 長 編 碼 5.2.3 凡 是 能 載 荷 一 定 的 信 息 量 ， 且 碼 字 的 平 均 長 度 最 短 ， 可 分 離 的 變 長 碼 的 碼 字 集 合 稱 為 最 佳 變 長 碼 。 編 碼 主 要 方 法 有 ： 香 農(nóng) 編 碼 、 費(fèi) 諾 編 碼 、 哈 夫 曼 編 碼 等 。 僅

31、哈 夫 曼 編 碼 是 真 正 意 義 下 的 最 佳 編 碼 哈 夫 曼 編 碼 效 率 最 高 ， 費(fèi) 諾 編 碼 效 率 次 之 ， 香 農(nóng) 編 碼 效 率 最 低 ， 甚 至 低 于 定 長 編 碼 的 效 率 。 因 此 ， 香 農(nóng) 編 碼 的 實(shí) 用 價(jià) 值 不 大 ， 但 卻 有 深 遠(yuǎn) 的 理 論 意 義 ， 因 為 按 香 農(nóng) 的 方 法 對(duì) 信 源 序 列 編 碼 ， 當(dāng) 序 列 長 度 趨 于 無 窮 時(shí) ， 平 均 碼 長 會(huì) 趨 于 信 源 的 熵 。 香 農(nóng) （ Shannon ） 編 碼 方 法 1 香 農(nóng) 第 一 定 理 指 出 了 平 均 碼 長 與 信 源

32、之 間 的 關(guān) 系 ， 同 時(shí) 也 指 出 了 可 以 通 過 編 碼 使 平 均 碼 長 達(dá) 到 極 限 值 。 香 農(nóng) 第 一 定 理 指 出 ， 選 擇 每 個(gè) 碼 字 的 長 度 K i 滿 足 下 式 ， 就 可 以 得 到 香 農(nóng) 碼 ： 二 進(jìn) 制 香 農(nóng) 碼 的 編 碼 步 驟 按 信 源 符 號(hào) 的 概 率 從 大 到 小 的 順 序 排 隊(duì) ， 不 妨 設(shè) ： 1 確 定 滿 足 下 列 不 等 式 的 整 數(shù) 碼 長 K i ： 2 令 p ( a0 )=0 ， 計(jì) 算 第 i 個(gè) 消 息 的 累 加 概 率 P i ： 3 將 累 加 概 率 P i 變 換 成 二 進(jìn)

33、 制 數(shù) ， 并 取 小 數(shù) 點(diǎn) 后 Ki 位 4 作 為 符 號(hào) ai的 編 碼 。 例 ： 有 一 單 符 號(hào) 離 散 無 記 憶 信 源 對(duì) 該 信 源 編 二 進(jìn) 制 香 農(nóng) 碼 。 香 農(nóng) 碼 的 平 均 碼 長 信 源 熵 編 碼 效 率 為 提 高 編 碼 效 率 ， 可 把 x 4 x 5 換 成 前 面 的節(jié) 點(diǎn) ， 可 減 小 平 均 碼 長 。 不 應(yīng) 先 規(guī) 定 碼 長 ， 而 是 由 碼 樹 來 規(guī) 定 碼 字 ， 可 得 更 好 的 結(jié) 果 。 例 ： 設(shè) 信 源 共 7 個(gè) 符 號(hào) 消 息 ， 其 概 率 如 表 所 示 ： 費(fèi) 諾 （ Fano ） 編 碼 方

34、法 概 率 匹 配 2 按 信 源 符 號(hào) 的 概 率 從 大 到 小 的 順 序 排 隊(duì) ， 不 妨 設(shè) ： p ( a 1 ) p ( a 2 ) p ( a n ) 按 編 碼 進(jìn) 制 數(shù) 將 概 率 分 組 ， 使 每 組 概 率 盡 可 能 接 近 或 相 等 。 如 編 二 進(jìn) 制 碼 就 分 成 兩 組 ， 編 m 進(jìn) 制 碼 就 分 成 m 組 。 給 每 一 組 分 配 一 位 碼 元 。 將 每 一 分 組 再 按 同 樣 原 則 劃 分 ， 重 復(fù) 步 驟 2 和 3 ， 直 至 概 率 不 再 可 分 為 止 。 信 源 符 號(hào) 對(duì) 應(yīng) 的 碼 字 即 為 費(fèi) 諾 碼

35、。 例 ： 對(duì) 前 例 信 源 進(jìn) 行 二 進(jìn) 制 費(fèi) 諾 編 碼 。 費(fèi) 諾 編 碼 的 基 本 特 點(diǎn): 1) 費(fèi) 諾 編 碼 在 構(gòu) 造 碼 樹 時(shí) ， 是 從 樹 根 開 始 到 終 端 節(jié) 點(diǎn) 結(jié) 束 ； 2) 由 于 賦 碼 元 時(shí) 的 任 意 性 ， 因 此 編 出 的 碼 字 不 唯 一 ； 3) 費(fèi) 諾 編 碼 雖 屬 于 概 率 匹 配 范 疇 ， 但 并 未 嚴(yán) 格 遵 守 匹 配 規(guī) 則 ， 有 時(shí) 出 現(xiàn) 概 率 小 的 碼 長 反 而 小 。 因 此 平 均 碼 長 一 般 不 會(huì) 最 小 。 費(fèi) 諾 碼 比 較 適 合 于 每 次 分 組 概 率 都 很 接 近

36、的 信 源 ， 特 別 是 對(duì) 每 次 分 組 概 率 都 相 等 的 信 源 進(jìn) 行 編 碼 時(shí) ， 可 達(dá) 到 理 想 的 編 碼 效 率 。 例 ： 對(duì) 該 信 源 進(jìn) 行 二 進(jìn) 制 費(fèi) 諾 編 碼 。 平 均 碼 長 ： 編 碼 效 率 ： 例 ： 二 進(jìn) 制 費(fèi) 諾 編 碼 信 源 符 號(hào) 概 率 編 碼 碼 字 碼 長 x 1 0.25 0 0 00 2 x 2 0.25 1 01 2 x 3 0.125 0 100 3 0 x 4 0.125 1 101 3 x 5 0.0625 0 1100 4 1 0 x 6 0.0625 1 1101 4 1 x 7 0.0625 0 1

37、110 4 1 x 8 0.0625 1 1111 4 平 均 碼 長 K = 2 . 75 碼 元 / 符 號(hào) 每 次 所 分 兩 組 的 信 源 熵 H ( X ) = 2 . 75 bit / 符 號(hào) 概 率 恰 好 相 等 。 H ( X ) 編 碼 效 率 = = 1 K log 2 樹 圖 ： 哈 夫 曼 （ H uffman ） 編 碼 方 法 3 將 信 源 符 號(hào) 按 概 率 由 大 到 小 順 序 排 隊(duì) 1 給 兩 個(gè) 概 率 最 小 的 符 號(hào) 各 分 配 一 個(gè) 碼 元 ， 將 其 概 率 2 相 加 后 合 并 作 為 一 個(gè) 新 的 符 號(hào) ， 與 剩 下 的 符

38、 號(hào) 一 起 ， 再 重 新 排 隊(duì) 給 縮 減 信 源 中 概 率 最 小 的 兩 個(gè) 符 號(hào) 各 分 配 一 個(gè) 碼 元 3 4 重 復(fù) 步 驟 2 、 3 直 至 概 率 和 為 1 從 最 后 一 級(jí) 開 始 ， 向 前 返 回 得 到 各 個(gè) 信 源 符 號(hào) 所 對(duì) 5 應(yīng) 的 碼 元 序 列 ， 即 相 應(yīng) 的 碼 字 。 例 ： 試 對(duì) 該 信 源 編 二 進(jìn) 制 哈 夫 曼 碼 。 讀 取 碼 字 的 時(shí) 候 ， 要 從 后 向 前 讀 ， 此 時(shí) 編 出 來 的 碼 字 是 可 分 離 的 即 時(shí) 碼 。 平 均 碼 長 信 源 熵 H (X) = H (0.2,0.19,0

39、.18,0.17,0.15,0.1,0.01)=2.61 bit/ 符 號(hào) 編 碼 效 率 哈 夫 曼 編 碼 的 基 本 特 點(diǎn) 1) 哈 夫 曼 編 碼 在 構(gòu) 造 碼 樹 時(shí) ， 是 從 端 點(diǎn) 開 始 直 到 樹 根 結(jié) 束 ； 2) 哈 夫 曼 編 碼 采 用 概 率 匹 配 方 法 來 決 定 各 碼 字 長 度 ， 概 率 大 的 符 號(hào) 對(duì) 應(yīng) 于 短 碼 ， 概 率 小 的 符 號(hào) 對(duì) 應(yīng) 與 長 碼 ， 充 分 利 用 了 短 碼 ， 從 而 使 平 均 碼 長 最 小 ； 3) 哈 夫 曼 編 碼 時(shí) ， 縮 減 信 源 的 最 后 二 個(gè) 碼 字 總 是 最 后 一 位

40、 不 同 ， 從 而 保 證 了 哈 夫 曼 碼 是 即 時(shí) 碼 。 費(fèi) 諾 碼 是 從 樹 根 開 始 ， 把 各 節(jié) 點(diǎn) 分 給 某 子 集 ， 若 子 集 已 是 單 點(diǎn) 集 ， 它 就 是 一 片 樹 葉 而 作 為 碼 字 。 哈 夫 曼 編 碼 是 先 給 每 一 符 號(hào) 一 片 樹 葉 ， 逐 步 合 并 成 節(jié) 點(diǎn) 直 到 樹 根 。 哈 夫 曼 的 編 法 并 不 惟 一 。 說 明 每 次 對(duì) 概 率 最 小 的 符 號(hào) 分 配 “ 0” 和 “ 1” 碼 元 是 任意 的 ， 所 以 可 得 到 不 同 的 碼 字 。 只 要 在 各 次 縮 減 信 源 中 保 持 碼

41、元 分 配 的 一 致 性 ， 即 能 得 到 可 分 離 碼 字 。 不 同 的 碼 元 分 配 ， 得 到 的 具 體 碼 字 不 同 ， 但 碼 長 K i 不 變 ， 平 均 碼 長 也 不 變 ， 所 以 沒 有 本 質(zhì) 區(qū) 別 。 縮 減 信 源 時(shí) ， 若 合 并 后 的 新 符 號(hào) 概 率 與 其 他 符 號(hào) 概 率 相 等 ， 從 編 碼 方 法 上 來 說 ， 這 幾 個(gè) 符 號(hào) 的 次 序 可 任 意 排 列 ， 編 出 的 碼 都 是 正 確 的 ， 但 得 到 的 碼 字 不 相 同 ， 不 同 的 編 法 得 到 的 碼 字 長 度 K i 也 不 盡 相 同 。

42、在 哈 夫 曼 編 碼 過 程 中 ， 對(duì) 縮 減 信 源 符 號(hào) 按 概 率 由 大 到 小 的 順 序 重 新 排 列 時(shí) ， 應(yīng) 使 合 并 后 的 新 符 號(hào) 盡 可 能 排 在 靠 前 的 位 置 ， 這 樣 可 使 合 并 后 的 新 符 號(hào) 重 復(fù) 編 碼 次 數(shù) 減 少 ， 使 短 碼 得 到 充 分 利 用 。 m 進(jìn) 制 哈 夫 曼 編 碼 在 編 m 進(jìn) 制 哈 夫 曼 碼 時(shí) ， 為 了 使 短 碼 得 到 充 分 利 用 ， 使 平 均 碼 長 最 短 ， 必 須 使 最 后 一 步 的 縮 減 信 源 有 m 個(gè) 信 源 符 號(hào) 。 縮 減 次 數(shù) 每 次 縮 減

43、所 減 少 的 信 源 符 號(hào) 個(gè) 數(shù) 信 源 符 號(hào) 數(shù) n 應(yīng) 滿 足 ：不 滿 足 時(shí) ： 設(shè) q個(gè) 概 率 為 0 的 信 源 符 號(hào) ， 使 q+n 滿 足 要 求 第 一 次 對(duì) 最 小 概 率 符 號(hào) 分 配 碼 元 時(shí) 只 取 (m-q) 個(gè) ， 分 別 配 以 0,1, m-q-1 ， 把 這 些 符 號(hào) 的 概 率 相 加 作 為 一 個(gè) 新 符 號(hào) 的 概 率 ， 與 其 它 符 號(hào) 一 起 重 新 排 列 。 以 后 每 次 取 m 個(gè) 符 號(hào) ， 分 別 配 以 0,1, m-1； 如 此 下 去 ， 直 至 所 有 概 率 相 加 得 1 為 止 ， 即 得 到 各

44、 符 號(hào) 的 m 進(jìn) 制 碼 字 。 單 符 號(hào) 離 散 無 記 憶 信 源 ， 例 試 對(duì) 該 信 源 編 三 進(jìn) 制 哈 夫 曼 碼 。 m =3 ， n =8 無 法 滿 足 n = s ( m -1) + m s =3 ， q =1 q + n = s ( m -1) + m 第 一 次 取 m - q =2 個(gè) 符 號(hào) 進(jìn) 行 編 碼 平 均 碼 長 信 息 傳 輸 率 編 碼 效 率 香 農(nóng) 碼 、 費(fèi) 諾 碼 、 哈 夫 曼 碼 都 考 慮 了 信 源 的 統(tǒng) 計(jì) 特 性 ， 使 經(jīng) 常 出 現(xiàn) 的 信 源 符 號(hào) 對(duì) 應(yīng) 較 短 的 碼 字 ， 使 平 均 碼 長 縮 短 ，

45、從 而 實(shí) 現(xiàn) 了 對(duì) 信 源 的 壓 縮 ； 香 農(nóng) 碼 有 系 統(tǒng) 的 、 惟 一 的 編 碼 方 法 ， 費(fèi) 諾 碼 和 哈 夫 曼 碼 的 編 碼 方 法 都 不 惟 一 ； 費(fèi) 諾 碼 比 較 適 合 于 對(duì) 分 組 概 率 相 等 或 接 近 的 信 源 編 碼 ， 費(fèi) 諾 碼 也 可 以 編 m 進(jìn) 制 碼 ， 但 m 越 大 ， 信 源 的符 號(hào) 數(shù) 越 多 ， 可 能 的 編 碼 方 案 就 越 多 ， 編 碼 過 程 就 越 復(fù) 雜 ， 有 時(shí) 短 碼 未 必 能 得 到 充 分 利 用 ； 哈 夫 曼 碼 對(duì) 信 源 的 統(tǒng) 計(jì) 特 性 沒 有 特 殊 要 求 ， 編 碼

46、 效 率 比 較 高 ， 對(duì) 編 碼 設(shè) 備 的 要 求 也 比 較 簡 單 ， 因 此 綜 合 性 能 優(yōu) 于 香 農(nóng) 碼 和 費(fèi) 諾 碼 。 5.3 限 失 真 信 源 編 碼 定 理 設(shè) 離 散 無 記 憶 信 源 X 的 信 息 率 失 真 函 數(shù) 為 R (D) ， 當(dāng) 信 息 率 R R (D) 時(shí) ， 只 要 信 源 序 列 長 度 L 足 夠 長 ， 一 定 存 在 一 種 編 碼 方 法 ， 其 譯 碼 失 真 小 于 或 等 于 D+， 為 任 意 小 的 正 數(shù) ； 反 之 ， 若 R R (D) ， 則 無 論 采 用 什 么 樣 的 編 碼方 法 ， 其 譯 碼 失

47、真 必 大 于 D 。 如 是 二 元 信 源 ， 則 對(duì) 于 任 意 小 的 0 ， 每 一 個(gè) 信 源 符 號(hào) 的 平 均 碼 長 滿 足 如 下 公 式 ： 5.4 常 用 信 源 編 碼 方 法 簡 介 5.4.1 游 程 編 碼 游 程 ： 數(shù) 字 序 列 中 連 續(xù) 出 現(xiàn) 相 同 符 號(hào) 的 一 段 。 在 二 元 序 列 中 ， 連 0 段 稱 為 0 游 程 ， 連 1 段 稱 為 1 游程 游 程 長 度 序 列 / 游 程 序 列 ： 用 交 替 出 現(xiàn) 的 “ 0” 游程 和 “ 1” 游 程 長 度 表 示 任 意 二 元 序 列 。 游 程 變 換 ： 是 一 種

48、一 一 對(duì) 應(yīng) 的 變 換 ， 也 是 可 逆 變 換 。 游 程 序 列 ： 3113213 二 元 序 列 ： 000101110010001 若 已 知 二 元 序 列 以 0 起 始 ， 從 游 程 序 列 很 容 易 恢 復(fù) 成 原 來 的 二 元 序 列 。 游 程 變 換 將 二 元 序 列 變 換 成 了 多 元 序 列 ； 這 樣 就 適 合 于 用 其 他 方 法 ， 如 哈 夫 曼 編 碼 ， 進(jìn) 一 步 壓 縮 信 源 ， 提 高 通 信 效 率 。 編 碼 方 法 ： 首 先 測 定 “ 0” 游 程 長 度 和 “ 1” 游 程 長 度 的 概率 分 布 ， 即 以

49、 游 程 長 度 為 元 素 ， 構(gòu) 造 一 個(gè) 新 的 信 源 ； 對(duì) 新 的 信 源 ( 游 程 序 列 ) 進(jìn) 行 哈 夫 曼 編 碼 。 5.4.2 算 術(shù) 編 碼 算 術(shù) 編 碼 是 近 十 多 年 來 發(fā) 展 迅 速 的 一 種 無 失 真 信 源 編 碼 ， 它 與 最 佳 的 哈 夫 曼 碼 相 比 ， 理 論 性 能 稍 加 遜 色 ， 而 實(shí) 際 壓 縮 率 和 編 碼 效 率 卻 往 往 還 優(yōu) 于 哈 夫 曼 碼 ， 且 實(shí) 現(xiàn) 簡 單 ， 故 很 受 工 程 上 的 重 視 。 算 術(shù) 編 碼 不 同 于 哈 夫 曼 碼 ， 它 是 非 分 組 ( 非 塊 ) 碼 。 它 從 全 序 列 出 發(fā) ， 考 慮 符 號(hào) 之 間 的 關(guān) 系 來 進(jìn) 行 編 碼 。 算 術(shù) 編 碼 利 用 了 累 積 概 率 的 概 念 。 算 術(shù) 碼 主 要 的 編 碼 方 法 是 計(jì) 算 輸 入 信 源 符 號(hào) 序 列 所 對(duì) 應(yīng) 的 區(qū) 間 。