【正文】 和信號(hào)設(shè)計(jì)有杰出的貢獻(xiàn)。 ?哈夫曼碼的編碼方法保證了概率大的符號(hào)對(duì)應(yīng)于短碼 ， 概率小的符號(hào)對(duì)應(yīng)于長(zhǎng)碼 ， 充分利用了短碼； ?縮減信源的最后二個(gè)碼字總是最后一位不同 ， 從而保證了 哈夫曼碼是即時(shí)碼 。 77 無失真信源編碼 例 設(shè)有離散無記憶信源 ? ? ???????54321 aaaaaPX78 無失真信源編碼 信源符號(hào)ai 概率 p(ai) 碼字 Wi1 碼長(zhǎng) Ki1 碼字 Wi2 碼長(zhǎng) K’i2 a1 1 1 00 2 a2 01 2 10 2 a3 000 3 11 2 a4 0010 4 010 3 a5 0011 4 011 3 79 無失真信源編碼 0 1 0 1 0 1 0 1 01 01 01 0 1 80 無失真信源編碼 )(71?? ??iii KapK 碼元 /符號(hào) )( ??KXH?81 無失真信源編碼 進(jìn)行哈夫曼編碼時(shí) ， 為得到 碼方差 最小的碼 ，應(yīng)使合并的信源符號(hào)位于縮減信源序列 盡可能高的位置 上 ， 以減少再次合并的次數(shù) ， 充分利用短碼 。 76 無失真信源編碼 ? 對(duì)信源進(jìn)行縮減時(shí) ， 兩個(gè)概率最小的符號(hào)合并后的概率與其它信源符號(hào)的概率相同時(shí) ， 這兩者在縮減信源中進(jìn)行概率排序 ， 其位置放置次序是可以任意的 ，故會(huì)得到不同的哈夫曼碼 。 (5)從最后一級(jí)開始 ， 向前返回得到各個(gè)信源符號(hào)所對(duì)應(yīng)的碼元序列 ， 即相應(yīng)的碼字 。 nppp ??? ?2170 無失真信源編碼 (3)對(duì)重排后的兩個(gè)概率最小符號(hào)重復(fù)步驟 (2)的過程 。 67 無失真信源編碼 例 對(duì)以下信源進(jìn)行費(fèi)諾編碼 。 (4)如此重復(fù)，直至每個(gè)組只剩下一個(gè)信源符號(hào)為止。 (2)將依次排列的信源符號(hào)按概率值分為兩大組 ， 使兩個(gè)組的概率之和近于相同 ，并對(duì)各組賦予一個(gè)二進(jìn)制碼元 “ 0”和“ 1”。 ? ?????11ikki apP62 63 無失真信源編碼 例 設(shè)信源共 7個(gè)符號(hào)消息，其概率和累加概率如下表所示。 nppp ??? ?21? ? ? ? 1l o gl o g 22 ???? iii pKp－61 無失真信源編碼 3. 為了編成唯一可譯碼，計(jì)算第 i個(gè)消息的累加概率 4. 將累加概率 Pi變換成二進(jìn)制數(shù)。 平均碼長(zhǎng) ＝ 1二元碼符號(hào) /信源符號(hào) 1,0 21 ?? aaK52 無失真信源編碼 編碼效率為 )( ??KXH?輸出的信息效率為 R＝ /二元碼符號(hào) 53 無失真信源編碼 長(zhǎng)度為 2的信源序列進(jìn)行 變長(zhǎng)編碼 （編碼方法后面介紹），其即時(shí)碼如下表 ai p(ai) 即時(shí)碼 a1a1 9/16 0 a1a2 3/16 10 a2a1 3/16 110 a2a2 1/16 111 54 無失真信源編碼 322722 ?? KK162731613163216311692＝＋＋＋ ?????K二元碼符號(hào) /信源序列 二元碼符號(hào) /信源符號(hào) 55 無失真信源編碼 272 ????編碼效率 信息效率 R2＝ /二元碼符號(hào) 56 無失真信源編碼 L＝ 3 R3＝ /二元碼符號(hào) L＝ 4 R4＝ /二元碼符號(hào) ?? ??57 無失真信源編碼 定長(zhǎng)二元碼編碼，要求編碼效率達(dá)到 96％時(shí)，允許譯碼錯(cuò)誤概率 510 －??222122)()]([)( lo g)(b itXHppXiii??? ???75222 )()8 1 (4 7 1 ???? ＝－L58 無失真信源編碼 最佳變長(zhǎng)編碼 凡是能載荷一定的信息量 ， 且碼字的平均長(zhǎng)度最短 ， 可分離的變長(zhǎng)碼的碼字集合稱為 最佳變長(zhǎng)碼 。 49 無失真信源編碼 編碼效率總是小于 1， 可以用它來衡量各種編碼方法的優(yōu)劣 。（ 統(tǒng)計(jì)匹配 ） 46 無失真信源編碼 單個(gè)符號(hào) 變長(zhǎng)編碼定理：若離散無記憶信源的符號(hào)熵為 H(X)， 每個(gè)信源符號(hào)用 m進(jìn)制碼元進(jìn)行變長(zhǎng)編碼 ， 一定存在一種無失真編碼方法 ， 其碼字平均長(zhǎng)度滿足下列不等式 1l o g)(l o g)( ???mXHKmXH47 無失真信源編碼 離散平穩(wěn)無記憶序列 變長(zhǎng)編碼定理：對(duì)于平均符號(hào)熵為 HL(X)的離散平穩(wěn)無記憶信源 ， 必存在一種無失真編碼方法 ， 使平均信息率滿足不等式 其中 ?為任意小正數(shù) 。 40 無失真信源編碼 編碼效率 定義 為 編碼效率 ， 即信源的平均符號(hào)熵為 H(X)，采用平均符號(hào)碼長(zhǎng)為 來編碼 ， 所得的效率 。 當(dāng) 和 均為定值時(shí) ， 只要 L足夠大 ， Pe可以小于任一正數(shù) ?。 時(shí)，則為臨界狀態(tài)，可能無失真，也可能有失真。 對(duì)任意 ?0， ?0， 只要 則當(dāng) L足夠大時(shí) ， 必可使譯碼差錯(cuò)小于 ?； 反之 ， 當(dāng) 時(shí) ， 譯碼差錯(cuò)一 定是有限值 ， 而 L足夠大時(shí) ， 譯碼幾乎必定出錯(cuò) ??? )(log XLL HmLK?2)(log ?? XLL HmLK34 無失真信源編碼 定長(zhǎng)編碼定理說明， )()(l o g XX HLHmK LL ??碼字所能攜帶的信息量 大于 信源序列輸出的信息量，則可以使傳輸幾乎無失真，條件是 L足夠大 。 要求能夠 無失真或無差錯(cuò) 地譯碼，同時(shí)傳送 Y時(shí)所需要的 信息率最小 30 無失真信源編碼 Yk平均每個(gè)符號(hào) 的最大信息量為 log m KL長(zhǎng)碼字的最大信息量為 KLlog m 則傳送一個(gè)信源符號(hào)需要的信息率平均為 MLmLKK L lo g1lo g ?? LKmM ?31 無失真信源編碼 所謂 信息率最小 ， 就是找到一種編碼方式使 最小 ?？梢姡?A集中“ 10”和“ 0”都是碼字，故碼 C不是惟一可譯碼。觀察碼字“ 10”，它是碼字“ 1011”的前綴，所以有 尾隨后綴。又圖知，該碼是非異前置碼，所以還無法判斷是否是惟一可譯碼。 ?解法一（根據(jù)異前置碼是惟一可譯碼）： 首先碼字 C是非奇異碼，又由題知，信源符號(hào)數(shù)為q=6，輸出信源的碼符號(hào)數(shù)為 r=2，根據(jù) kraft不等式得， 滿足 kraft不等式。由此得到碼 C的所有可能的尾隨后綴組成的集合 A。這樣，首先獲得由最短的碼字能引起的所有尾隨后綴。而這些尾隨后綴又可能是某些碼字的前綴，再將由這些尾隨后綴產(chǎn)生的新的尾隨后綴列出。 ?集合 A的構(gòu)造： ? 首先觀察碼 C中最短的碼字是否是其它碼字的前綴。 ?24 編碼的定義 a1=1 0 1 0 1 0 1 a2=01 a3=011 a4=000 {1， 01， 001， 000} 惟一可譯碼； {1， 01， 101， 000} 不是惟一可譯碼； 均滿足克勞夫特不等式 122222 332141????? ???