第2章信源熵.ppt

1 第2章信源熵 2 1單符號(hào)離散信源2 2多符號(hào)離散平穩(wěn)信源2 3連續(xù)信源2 4離散無(wú)失真信源編碼定理 2 第2章信源熵 2 1單符號(hào)離散信源單符號(hào)信源 信源每次輸出一個(gè)符號(hào) 用離散隨機(jī)變量描述多符號(hào)信源 信源每次輸出多個(gè)符號(hào) 符號(hào)序列 用離散隨機(jī)矢量描述離散信源 信源符號(hào)取值離散連續(xù)信源 信源符號(hào)取值連續(xù) 用隨機(jī)過程描述 結(jié)論 從概率 隨機(jī)變量 過程 來(lái)研究信息信息 對(duì)事物狀態(tài) 存在方式 不確定性的描述 3 2 1 1單符號(hào)離散信源的數(shù)學(xué)模型 X取值于集合 x1 x2 xi xn n I p xi X取值xi的概率 0 p xi 1 p xi 1 4 2 1 2自信息和信源熵 復(fù)習(xí) 設(shè)X取值 x1 x2 xi xn Y取值 y1 y2 yj ym 則 聯(lián)合概率p xiyj X取值xi Y取值yj同時(shí)成立的概率 條件概率p yj xi X取值xi條件下 Y取值yj的概率 條件概率p xi yj Y取值yj條件下 X取值xi的概率 性質(zhì) 5 2 1 2自信息和信源熵 續(xù) 一 信息量1 自信息 I xi log2p xi bit nat Hart 含義 信源X發(fā)xi后所帶來(lái)的信息量 特例 等概二進(jìn)制信源發(fā)出的每個(gè)碼元均包含1bit信息量 性質(zhì) 非負(fù) 單調(diào)遞減 當(dāng)p xi 0時(shí) I xi 不可能事件當(dāng)p xi 1時(shí) I xi 0 確定事件 6 2 1 2自信息和信源熵 續(xù) 2 聯(lián)合自信息I xiyj log2p xiyj 含義 X xi Y yj同時(shí)發(fā)生時(shí) 帶來(lái)的信息量 特例 若X Y獨(dú)立 則I xiyj I xi I yj 3 條件自信息 I xi yj log2p xi yj Y yj條件下 發(fā)生X xi所帶來(lái)的信息量 I yj xi log2p yj xi X xi條件下 發(fā)生Y yj所帶來(lái)的信息量 說明 I xiyj I xi yj I yj xi 亦有 非負(fù) 單調(diào)遞減性 關(guān)系 I xiyj I xi I yj xi I xiyj I yj I xi yj 7 2 1 2自信息和信源熵 續(xù) 4 補(bǔ) 不確定度 不肯定程度 8 2 1 2自信息和信源熵 續(xù) 4 補(bǔ) 不確定度 不肯定程度 續(xù) 例 8只燈泡串聯(lián) 損壞概率相等 有一只壞了 用表查 每只損壞概率1 8 每只損壞的不確定度為3bit 中分法 查一次 知壞燈泡在那4只中 不確定度為2bit 獲信息1bit 以此類推 結(jié)論 獲得的信息量 不確定度的減少量 9 2 1 2自信息和信源熵 續(xù) 二 互信息和條件互信息 10 2 1 2自信息和信源熵 續(xù) 二 互信息和條件互信息1 互信息 1 yj對(duì)xi的互信息I xi yj 即 I xi yj I xi I xi yj 2 1 8 p xi 先驗(yàn)概率 信源發(fā)xi的概率p xi yj 后驗(yàn)概率 信宿收到y(tǒng)j后 推測(cè)信源發(fā)xi的概率 含義 互信息I xi yj 自信息I xi 條件自信息I xi yj I xi 信宿收到y(tǒng)j之前 對(duì)信源發(fā)xi的不確定度 I xi yj 信宿收到y(tǒng)j之后 對(duì)信源發(fā)xi的不確定度 I xi yj 收到y(tǒng)j而得到 關(guān)于xi 的互信息 不確定度的減少量 11 2 1 2自信息和信源熵 續(xù) 二 互信息和條件互信息1 互信息 2 xi對(duì)yj的互信息I yj xi 含義 信源發(fā)xi前 后 信宿收到y(tǒng)j的不確定度的減少 3 I xi yj I xi I yj I xiyj 2 1 10 注意 I xi yj 與I xiyj 不同 12 2 1 2自信息和信源熵 續(xù) 2 互信息的性質(zhì) 1 對(duì)稱性 I xi yj I yj xi 2 X與Y獨(dú)立時(shí) I xi yj 0 3 I xi yj 可為正 負(fù) 03 條件互信息給定zk條件下 xi與yj間互信息 13 2 1 2自信息和信源熵 續(xù) I xi yj 可為正 負(fù) 0的舉例設(shè)yj代表 閃電 則當(dāng)xi代表 打雷 時(shí) I xi yj 0 I xi yj I xi 0當(dāng)xi代表 下雨 時(shí) I xi yj I xi I xi yj 0當(dāng)xi代表 霧天 時(shí) I xi yj I xi I xi yj 0當(dāng)xi代表 飛機(jī)正點(diǎn)起飛 時(shí) I xi yj I xi I xi yj 0 14 2 1 2自信息和信源熵 續(xù) 三 信源熵1 信源熵H X E I xi p xi log2p xi 單位 bit 信源 符號(hào) 定義 各離散消息xi自信息量I xi 的數(shù)學(xué)期望 平均不確定度的度量 體現(xiàn) 總體平均 含義 反映 變量X的隨機(jī)性 表示 信源發(fā)送前 信源具有的平均不確定度 表示 信源發(fā)送后 每個(gè)消息 xi 提供的平均信息量 15 2 1 2自信息和信源熵 續(xù) 2 條件熵 定義 在XY聯(lián)合集上 條件自信息的數(shù)學(xué)期望H X Y 信宿收到Y(jié)后 信源X仍存在的不確定度由于信道噪聲所致 故稱信道疑義度 損失熵3 聯(lián)合熵 定義 在XY聯(lián)合集上 聯(lián)合自信息的數(shù)學(xué)期望 16 2 1 3信源熵基本性質(zhì) 1 非負(fù)性2 對(duì)稱性 各p xi 次序可換3 最大熵 等概時(shí)H X max log2n 附 若n 2 則H X plog2p 1 p log2 1 p H p 重要公式 17 2 1 3信源熵基本性質(zhì) 續(xù) 4 擴(kuò)展性 信源含有的新增消息為小概率時(shí) 熵不變5 確定性 某消息取值概率為1時(shí) 熵為06 可加性 H XY H X H Y X H Y H X Y 7 極值性 含義 p xi 對(duì)其他分布 p yi 的自信息量取數(shù)學(xué)期望必大于其自身熵 18 2 1 3信源熵基本性質(zhì) 續(xù) 定理 條件熵不大于信源熵 無(wú)條件熵 H X Y H X H Y X H Y 8 上凸性 含義 熵H P P 概率分布p xi 間為上凸曲線 意義 上凸曲線有最大值 結(jié)論 H X max log2n 等概 19 2 1 4加權(quán)熵 對(duì)香農(nóng)熵引入主觀因素 效用權(quán)重系數(shù) 重量 一 定義 設(shè)信源X則加權(quán)熵Hw X 含義 消息xi的權(quán)重wi對(duì)I xi 的加權(quán)平均二 性質(zhì) 略 20 2 1 5平均互信息 一 定義1 Y對(duì)X 2 1 43 2 X對(duì)Y 2 1 44 3 合寫 2 1 45 含義 信道中流通信息量的整體測(cè)度 附 貝葉斯公式 p xiyj p xi p yj xi p yj p xi yj 21 2 1 5平均互信息 續(xù) 二 物理意義1 由 2 1 43 I X Y H X H X Y 1 H X 信源熵 X的不確定度H X Y 已知Y時(shí) 對(duì)X仍剩的不確定度 結(jié)論 Y已知 使得對(duì)X的不確定度減小了 即獲得了I X Y 的信息量 2 H X 信源含有的平均信息量 總 有用 I X Y 信宿收到的平均信息量 有用部分 結(jié)論 H X Y 因信道有擾而丟失的平均信息量 故稱損失熵 22 2 1 5平均互信息 續(xù) 二 物理意義2 由 2 1 44 I Y X H Y H Y X I X Y 1 H Y 信宿收到的平均信息量I X Y 信道傳輸?shù)钠骄畔⒘?結(jié)論 H Y X 因信道有擾而產(chǎn)生的假平均信息量 稱噪聲熵 散布度 2 H Y Y的先驗(yàn)不定度H Y X 發(fā)出X后 關(guān)于Y的后驗(yàn)不定度 結(jié)論 I Y X 發(fā)X前后 Y不定度的減少量 23 2 1 5平均互信息 續(xù) 3 由 2 1 45 I X Y H X H Y H XY H X H Y 通信前 整個(gè)系統(tǒng)的先驗(yàn)不定度H XY 通信后 整個(gè)系統(tǒng)仍剩的不定度I X Y 通信前后 整個(gè)系統(tǒng)不確定度的減少量 即傳輸?shù)幕バ畔?結(jié)論 I X Y 平均每傳送一個(gè)信源符號(hào)時(shí) 流經(jīng)信道的平均 有用 信息量 24 2 1 5平均互信息 續(xù) 三 平均互信息的性質(zhì)1 非負(fù)性 I X Y 0 盡管I xi yj 的某些元素可為負(fù)2 對(duì)稱性 I X Y I Y X 3 極值性 I X Y H X I X Y H Y 特例 I X Y H X H X Y 當(dāng)H X Y 0時(shí) I X Y H X 信道無(wú)噪 X Y一一對(duì)應(yīng) 當(dāng)I X Y 0時(shí) H X Y H X 信道中斷 X Y獨(dú)立 25 2 1 5平均互信息 續(xù) 4 凸函數(shù)性 1 I X Y 是信源概率分布P X 的上凸函數(shù) 最大值 信道容量的基礎(chǔ) 2 I X Y 是信道轉(zhuǎn)移概率P Y X 的下凸函數(shù) 最小值 率失真函數(shù)的基礎(chǔ) 26 例2 1 6 二進(jìn)制對(duì)稱信道q不變時(shí) I X Y 為上凸曲線 p 0 5時(shí)有最大值p不變時(shí) I X Y 為下凸曲線 q 0 5時(shí)有最小值 2 1 5平均互信息 續(xù) 27 2 1 5平均互信息 續(xù) 5 數(shù)據(jù)處理定理I X Z I X Y I X Z I Y Z 意義 信息不增原理 每經(jīng)一次處理 可能丟失一部分信息 28 2 1 6文氏圖 I X Y H X H X Y H Y H Y X H XY H X H Y X H Y H X Y H XY I X Y H X H Y H X Y H Y X H Y H X I X Y H XY 29 2 2多符號(hào)離散平穩(wěn)信源 多符號(hào)信源 序列信源 每次發(fā)送一個(gè)符號(hào)序列 用隨機(jī)矢量描述 平穩(wěn)信源 信源所發(fā)送符號(hào)序列的概率分布與時(shí)間起點(diǎn)無(wú)關(guān) 無(wú)記憶信源 信源所發(fā)送符號(hào)序列的各符號(hào)之間統(tǒng)計(jì)無(wú)關(guān) 有記憶信源 信源所發(fā)送符號(hào)序列的各符號(hào)之間統(tǒng)計(jì)有關(guān) 2 2 1離散平穩(wěn) 序列 信源 定義 若一離散序列信源的各維聯(lián)合概率均與時(shí)間起點(diǎn)無(wú)關(guān) 則為離散平穩(wěn) 序列 信源 30 2 2 2離散平穩(wěn)無(wú)記憶信源 擴(kuò)展信源 一 定義 若單符號(hào)離散信源X 則X的N次擴(kuò)展信源XN 說明 XN信源集中 共有q nN個(gè)元素 序列種類 每個(gè)元素ai 由N個(gè)xi組成的某一序列 兩者 i 不等 無(wú)記憶 故p ai p xi1 p xi2 p xiN 31 2 2 2離散平穩(wěn)無(wú)記憶信源 擴(kuò)展信源 續(xù) 二 熵H XN NH X 2 2 5 例2 2 1 法一 先構(gòu)造二次擴(kuò)展信源 表2 2 1 再求H X2 法二 先求單符號(hào)信源熵 H X 1 5bit 符號(hào)再由式 2 2 5 求 H X2 2H X 3bit 符號(hào)序列 32 2 2 3離散平穩(wěn)有記憶信源 有記憶信源 用信源發(fā)送一個(gè)符號(hào)序列的聯(lián)合概率描述馬爾可夫鏈 用信源發(fā)送一個(gè)符號(hào)序列中各符號(hào)間條件概率 狀態(tài)轉(zhuǎn)移概率 描述一 二維有記憶信源X X1X2二維 每組 符號(hào)序列 包含2個(gè)符號(hào)有記憶 每組內(nèi) 后一符號(hào)與前一符號(hào)相關(guān)平穩(wěn) 上述 相關(guān)性與時(shí)間起點(diǎn)無(wú)關(guān)假設(shè) 組間統(tǒng)計(jì)獨(dú)立 33 2 2 3離散平穩(wěn)有記憶信源 續(xù) 1 分析設(shè)X1 X2 x1 x2 xn 則X x1x1 x1xn x2x1 x2xn xnx1 xnxn 令ai xi1xi2 i1 i2 1 2 n 則i 1 2 n2 于是 34 2 2 3離散平穩(wěn)有記憶信源 續(xù) 2 結(jié)果3 說明對(duì)無(wú)記憶信源 X1 X2相互獨(dú)立 H X H X1 H X2 由于H X2 X1 H X2 因此 H X2X1 H X1 H X2 2 當(dāng)X1 X2取自同一集合X時(shí) H X 2H X H X2 為二次擴(kuò)展信源 35 2 2 3離散平穩(wěn)有記憶信源 續(xù) 例2 2 2 給定信源概率 條件概率 求得 1 原始 信源熵H X 1 542bit 符號(hào) 2 條件熵H X2 X1 0 870bit 符號(hào) 3 聯(lián)合熵H X H X1X2 2 412bit 符號(hào)序列 4 平均符號(hào)熵H2 X 0 5H X 1 206bit 符號(hào) 說明 H X2 X1 H X 條件熵 無(wú)條件熵 H2 X H X 解釋 X2與X1相關(guān) 使熵值減小 36 2 2 3離散平穩(wěn)有記憶信源 續(xù) 二 N維有記憶信源1 聯(lián)合熵H X H X H X1X2 XN H X1 H X2 X1 H X3 X1X2 H XN X1X2 XN 1 bit 符號(hào)序列 2 條件熵H XN X1X2 XN 1 是N的不增函數(shù)H XN X1X2 XN 1 H XN 1 X1X2 XN 2 H X3 X1X2 H X2 X1 H X1 37 2 2 3離散平穩(wěn)有記憶信源 續(xù) 二 N維有記憶信源3 平均符號(hào)熵HN X HN X 1 N H X 1 N H X1X2 XN bit 符號(hào)4 極限熵 1 意義 實(shí)際工作時(shí) 信源不斷發(fā)送符號(hào) 2 對(duì)平穩(wěn)信源 38 2 2 4馬爾可夫信源 一 概述有一類信源 其輸出符號(hào)只與此前已輸出的若干個(gè)符號(hào)有關(guān) 如 若把前已輸出的符號(hào)視為狀態(tài) 則有 1 輸出符號(hào)概率 在l時(shí)刻 信源處于狀態(tài)ei時(shí) 輸出符號(hào)xk的概率 P Xe Xk Sl ei pl xk ei 2 狀態(tài)轉(zhuǎn)移概率 在l時(shí)刻 信源處于狀態(tài)ei 而在l 1時(shí)刻轉(zhuǎn)移到ej的概率P Sl 1 ej Sl ei pl ej ei 又稱一步轉(zhuǎn)移概率時(shí)齊 齊次 若上述兩概率與時(shí)刻l無(wú)關(guān) 即pl xk ei p xk ei pl ej ei p ej ei 39 2 2 4馬爾可夫信源 續(xù) 二 馬爾可夫信源1 定義 若一信源滿足下列兩點(diǎn) 即為馬爾可夫信源 1 輸出符號(hào)只與當(dāng)前狀態(tài)有關(guān) p xk ei 2 當(dāng)前狀態(tài)和輸出決定了下一狀態(tài) p ej ei 描述 狀態(tài)轉(zhuǎn)移圖 例2 2 3 給定狀態(tài)轉(zhuǎn)移圖 圖2 2 1 可得 符號(hào)條件概率p xk ei 矩陣 2 2 40 每行和為1一步轉(zhuǎn)移概率p ej ei 矩陣 2 2 42 每行和為1 40 2 2 4馬爾可夫信源 續(xù) 2 m階馬爾可夫信源 1 m階 輸出符號(hào)概率只與前m個(gè)符號(hào)有關(guān) 若每符號(hào)取值n種 則共有nm種狀態(tài) 每種狀態(tài)對(duì)應(yīng)一個(gè)m長(zhǎng) n進(jìn)制 序列 2 極限熵 41 2 2 4馬爾可夫信源 續(xù) 2 m階馬爾可夫信源 3 有限齊次馬爾可夫鏈的各態(tài)歷經(jīng)定理 定理 對(duì)每個(gè)j 都存在與i無(wú)關(guān)的極限且p ej 由式 2 2 48 決定 42 2 2 4馬爾可夫信源 續(xù) 例2 2 4 二元二階馬爾可夫信源 信源符號(hào)集X 0 1 解 nm 4 狀態(tài)空間集E e1 00 e2 01 e3 10 e4 11 狀態(tài)圖 圖2 2 2由狀態(tài)圖得狀態(tài)矩陣 由 2 2 48 得 43 2 2 4馬爾可夫信源 續(xù) 由 2 2 46 解得 H 0 8bit 符號(hào) 結(jié)論 該信源在穩(wěn)定后發(fā)00 11的概率為5 14發(fā)01 10概率為2 14平均每符號(hào) 0 1 包含0 8bit信息量 44 2 2 4馬爾可夫信源 續(xù) 小結(jié) 兩種有記記憶信源比較 45 2 2 5信源冗余度及信息變差 實(shí)際信源以馬氏源近似 對(duì)馬氏源 m Hm 即 H0 log2n H1 H2 Hm H 2 2 54 H0 最大熵H 實(shí)際熵 1 相對(duì)熵率 H H0 2 冗余度 1 I0 H0 3 信息變差I(lǐng)0 H0 H 46 2 2 5信源冗余度及信息變差 續(xù) 例 英語(yǔ)26字母加空格共27個(gè)符號(hào) 概率分布見表2 2 2 可得 H0 4 76bit 符號(hào) H1 4 03bit 符號(hào) H2 3 32bit 符號(hào) H3 3 10bit 符號(hào)H 1 40bit 符號(hào) 且 0 29 0 71 I0 3 36bit 符號(hào) 說明 若按最大熵 等概 相互獨(dú)立 設(shè)計(jì) 每符號(hào)需多傳3 36bit 英文中 有71 冗余度 是由語(yǔ)言結(jié)構(gòu)決定的 該部分無(wú)需傳輸 可壓縮 于是 冗余度 信源可壓縮程度 47 2 3連續(xù)信源 概念 連續(xù)信源 輸出在時(shí)間 取值上都連續(xù) 屬隨機(jī)過程 x t 以概率密度描述平穩(wěn)過程 統(tǒng)計(jì)特性與時(shí)間起點(diǎn)無(wú)關(guān)遍歷過程 集平均 時(shí)間平均的平穩(wěn)過程 48 2 3 1連續(xù)信源的熵 熵計(jì)算兩法 法一 連續(xù)消息 離散消息再用離散信源方法計(jì)算 法二 連續(xù)消息抽樣 時(shí)間離散的連續(xù)消息分析時(shí)先量化 再令 0 49 2 3 1連續(xù)信源的熵 續(xù) 分類 單變量信源 無(wú)記憶信源 與單符號(hào)離散源相似 隨機(jī)過程中取一個(gè)時(shí)間t1多變量信源 有記憶信源 與多符號(hào)離散源相似 隨機(jī)過程中取多個(gè)時(shí)間ti 說明 對(duì)單變量信源 可研究 數(shù)學(xué)期望 方差對(duì)兩變量信源 可研究 自相關(guān)函數(shù) 50 2 3 1連續(xù)信源的熵 續(xù) 一 單變量連續(xù)信源數(shù)學(xué)模型R 連續(xù)變量X的取值范圍二 連續(xù)信源的熵由法二得 圖2 3 1 上式中第2項(xiàng)為 即連續(xù)信源熵值無(wú)窮大 取值可能性無(wú)限多 舍第2項(xiàng)得定義 相對(duì)熵 51 2 3 1連續(xù)信源的熵 續(xù) 二 連續(xù)信源的熵 兩個(gè)連續(xù)變量 聯(lián)合熵條件熵 52 2 3 2幾種特殊連續(xù)信源的熵和最大熵定理 一 均勻分布信源 Hc X log2 b a 結(jié)論 熵值只與均勻分布間隔 b a 有關(guān) 若b a 1 則Hc X 為負(fù) 53 2 3 2幾種特殊連續(xù)信源的熵和最大熵定理 續(xù) 二 高斯分布信源 結(jié)論 熵值只與方差有關(guān) 與m無(wú)關(guān) 54 2 3 2幾種特殊連續(xù)信源的熵和最大熵定理 續(xù) 三 指數(shù)分布信源m 數(shù)學(xué)期望 結(jié)論 熵值只與數(shù)學(xué)期望m有關(guān) 55 2 3 2幾種特殊連續(xù)信源的熵和最大熵定理 續(xù) 四 最大熵定理限峰值功率的最大熵定理 均勻分布的連續(xù)信源具最大熵2 限平均功率的最大熵定理 高斯分布的連續(xù)信源具最大熵3 限均值的最大熵定理 指數(shù)分布的連續(xù)信源具最大熵 結(jié)論 連續(xù)信源的最大熵因條件而異 離散信源的最大熵出現(xiàn)于等概之時(shí) 56 2 3 3連續(xù)熵的性質(zhì) 1 連續(xù)熵可為負(fù)值 與離散熵不同 2 可加性Hc XY Hc X Hc Y X Hc Y Hc X Y Hc X1X2 XN Hc X1 Hc X2 X1 Hc X3 X1X2 Hc XN X1X2 XN 1 57 2 3 3連續(xù)熵的性質(zhì) 續(xù) 3 平均互信息的非負(fù)性Ic X Y Hc X Hc X Y Ic Y X Hc Y Hc Y X 對(duì)稱性 Ic X Y Ic Y X 非負(fù)性 Ic X Y 0 Ic Y X 0條件熵不大于無(wú)條件熵Hc X Y Hc X Hc Y X Hc Y 58 2 3 4熵功率 1 信息變差I(lǐng)p q Hc p x X Hc q x X 2 3 49 Hc p x X 最大熵 對(duì)應(yīng)分布p x Hc q x X 實(shí)際熵 對(duì)應(yīng)分布q x 說明 式 2 3 49 與I0 H0 H 相對(duì)應(yīng)且有 實(shí)際熵Hc q x X Hc p x X Ip q 最大熵 最大的平均不確定度實(shí)際熵 測(cè)定q x 后還剩下的不定度于是 獲得的信息量Ip q 不確定度的減少量 59 2 3 4熵功率 續(xù) 2 熵功率對(duì)零均值 平均功率 P 受限的信源 高斯分布p x 具最大值 m 0 P 2 對(duì)實(shí)際信源 分布為q x 也可寫為 結(jié)論 冗余度 信息變差取決于限定功率與熵功率之比 60 2 4離散無(wú)失真信源編碼定理 一 引言1 通信根本問題 信源輸出的信息 在接收端精確 近似重現(xiàn) 需解決 信源輸出的描述 信息量計(jì)算 熵 信源輸出的表示 信源編碼2 信源編碼 1 含義 信源符號(hào) 碼符號(hào) 以適合信道傳輸?shù)囊环N映射 變換 61 2 4離散無(wú)失真信源編碼定理 續(xù) 2 要求 無(wú)失真 可逆 唯一 有效 所編碼字盡量短 提高編碼效率 減小信息率 3 實(shí)質(zhì) 壓縮信源輸出中的冗余度 消息概率分布的非平均 H0 X H1 X 消息間相關(guān)性 H1 X H2 X H3 X 對(duì)無(wú)記憶信源 利用 對(duì)有記憶信源 利用 主要是 4 編碼 62 2 4離散無(wú)失真信源編碼定理 續(xù) 二 定長(zhǎng)編碼定理1 目的 在保證一一對(duì)應(yīng) 變換唯一前提下 使K盡量小 63 2 4離散無(wú)失真信源編碼定理 續(xù) 2 定理 由L個(gè)符號(hào)組成的 每符號(hào)熵為H x 的平穩(wěn)無(wú)記憶符號(hào)序列X可用由K個(gè)碼符號(hào) 每個(gè)有m種取值 組成的碼序列作定長(zhǎng)編碼 對(duì)任意 0 0 有 1 正定理 只要?jiǎng)t當(dāng)L足夠大時(shí) 譯碼差錯(cuò)必小于 2 逆定理 當(dāng)時(shí)譯碼差錯(cuò)必為有限值 且當(dāng)L足夠大時(shí) 譯碼幾乎必定出錯(cuò) 64 2 4離散無(wú)失真信源編碼定理 續(xù) 3 說明 1 術(shù)語(yǔ) 信息率 編碼速率 R K L log2mbit 信源符號(hào)log2m 每個(gè)碼符號(hào)的最大熵 bit 碼符號(hào) Klog2m 每個(gè)碼符號(hào)序列最大熵 bit 碼序列 K L log2m 編碼后 平均每個(gè)信源符號(hào)所能載荷的最大信息量 65 2 4離散無(wú)失真信源編碼定理 續(xù) 編碼效率H X 編碼前 平均每個(gè)信源符號(hào)包含的信息量R 編碼后 平均每個(gè)信源符號(hào)所能傳送的最大信息量若在正定理中取等號(hào) R H X 于是 66 2 4離散無(wú)失真信源編碼定理 續(xù) 2 正定理指出 當(dāng)信息率R 單符號(hào)熵H X 時(shí)可做到幾乎無(wú)失真譯碼 條件是L大只要 譯碼差錯(cuò)率必小于 信源序列自信息方差 67 2 4離散無(wú)失真信源編碼定理 續(xù) 3 逆定理指出 若R比H X 小一個(gè) 時(shí) 譯碼差錯(cuò)未必超過 若R比H X 小兩個(gè) 時(shí) 譯碼差錯(cuò)必定大于 L 時(shí)必失真 4 結(jié)論 單符號(hào) 信源熵H X 實(shí)為一個(gè)界限當(dāng)R H X 時(shí) 無(wú)失真譯碼當(dāng)R H X 時(shí) 有失真譯碼 68 2 4離散無(wú)失真信源編碼定理 續(xù) 例2 4 1 給定信源模型 8種符號(hào)和概率算得 H X 2 55bit 信源符號(hào) 2 X 1 323 若要求 編碼效率 90 由得 0 28 若要求 譯碼差錯(cuò)率 10 6 則L太大此外 相對(duì)熵率不高 69 2 4離散無(wú)失真信源編碼定理 續(xù) 三 變長(zhǎng)編碼定理1 基礎(chǔ) 1 碼的分類 70 2 4離散無(wú)失真信源編碼定理 續(xù) 例2 4 2 A 奇異碼 信源符號(hào) 碼字并非一一對(duì)