第五章 無(wú)失真信源編碼 北京郵電大學(xué) 信息工程學(xué)院 一、 概 述 二、定長(zhǎng)碼 三、變長(zhǎng)碼 四、哈夫曼編碼 主要內(nèi)容 本章主要介紹無(wú)失真信源編碼定理與一些重要的無(wú)失真信源編碼方法 五、幾種實(shí)用的信源編碼方法 信源編碼： 將信源符號(hào)序列按一定的數(shù)學(xué)規(guī)律映射成由碼符號(hào)組成的碼序列的過(guò)程。 信源譯碼： 根據(jù)碼序列恢復(fù)信源序列的過(guò)程。 無(wú)失真信源編碼： 即信源符號(hào)可以通過(guò)編碼序列無(wú)差錯(cuò)地恢復(fù)。 （適用于離散信源的編碼） 限失真信源編碼： 信源符號(hào)不能通過(guò)編碼序列無(wú)差錯(cuò)地恢復(fù)。 （可以把差錯(cuò)限制在某一個(gè)限度內(nèi)） 信源編碼的目的：提高傳輸有效性，即用盡可能短的碼符號(hào)序列來(lái)代表信源符號(hào)。 無(wú)失真信源編碼定理證明，如果對(duì)信源序列進(jìn)行編碼，當(dāng)序列長(zhǎng)度足夠長(zhǎng)時(shí) ，存在無(wú)失真編碼使得傳送每信源符號(hào)所需的比特?cái)?shù)接近信源的熵。因此，采用有效的信源編碼會(huì)使信息傳輸效率得到提高。 概述 本節(jié)主要內(nèi)容 一、 信源 編碼 器 二、 信源 編碼 的分 類 三、分組碼 源編碼器 分組碼單符號(hào)信源編碼器 1 , , , 信源序列 碼符號(hào)集 碼字集合 符號(hào)集 A 1 , , 為信源譯碼器 分組碼單符號(hào)譯碼器 1 , , , 信源序列 碼符號(hào)集 碼字集合 1 , , 信源編碼器 （ 1） 信源符號(hào) 英文字母 碼符號(hào)集 點(diǎn)、劃、字母間隔、單詞間隔 信道基本符號(hào) 0， 1 簡(jiǎn)單信源編碼器 信源編碼器 （ 2） 二進(jìn)信道 將英文字母變成摩爾斯電碼 將摩爾斯電碼變成二進(jìn)碼 符號(hào) 點(diǎn) 劃 字母間隔 單詞間隔 電平 + - + - - - - - - - - - 二進(jìn)代碼 1 0 1110 000 00000 摩爾斯信源編碼器 原信源的 將 當(dāng)于對(duì)原信源的 例 信源 X=0,1的二次擴(kuò)展源 00,01,10,11。對(duì) 為原信源 源編碼的分類 概率匹配編碼 ：信源符號(hào)的概率已知。 通用編碼 ：信源符號(hào)的概率未知。 分組碼：先分組再編碼。在分組碼中，每一個(gè)碼字僅與當(dāng)前輸入的信源符號(hào)組有關(guān)，與其他信源符號(hào)無(wú)關(guān)。 包括：定長(zhǎng)碼、變長(zhǎng)碼（ 諾編碼 ） 非分組碼：碼序列中的符號(hào)與信源序列中的符號(hào)無(wú)確定的對(duì)應(yīng)關(guān)系。例如算術(shù)編碼。 信源編碼 分組碼 非分組碼 按信源序列和編碼器輸出的關(guān)系 先分組再編碼 定長(zhǎng)碼 變長(zhǎng)碼 每一個(gè)碼字 僅與 當(dāng)前輸入的信源符號(hào)組有關(guān) 編碼器 信源序列 編碼序列 例如算術(shù)編碼就是非分組碼 無(wú)確定的對(duì)應(yīng)關(guān)系 組碼 與非分組碼的顯著區(qū)別：分組碼中包含 碼字 各碼字 都不相同？ Y N 非奇異碼 奇異碼 唯一可譯 不同的消息序列不會(huì)生成相同的碼序列 無(wú)失真編碼 必要條件 即時(shí)碼與非即時(shí)碼 只要接收到 每個(gè)碼字的 最后一個(gè)符 號(hào)可立即將 該碼字譯出？ Y 即時(shí)碼 N 非即時(shí)碼 優(yōu)點(diǎn)：譯碼延遲小 異前置碼 設(shè) 為長(zhǎng)度為 的碼字，即 ， 稱 為 的前置。 一個(gè)碼中無(wú)任何碼字是其他碼字的前置 異前置碼是唯一可譯碼 異前置碼與即時(shí)碼是等價(jià)的 逗號(hào)碼 用一個(gè)特定的碼符號(hào)表示所有碼字的結(jié)尾 逗號(hào)碼是唯一可譯碼 k 1 ,x x)1(21 j 例 設(shè)信源符號(hào)集為 a,b,c,d, 采用 6種分組編碼如下表，分析每一個(gè)碼的唯一可譯性 號(hào) 碼 A 碼 B 碼 C 碼 D 碼 E 碼 F a 0 0 00 0 1 0 b 0 1 01 10 01 01 c 1 10 10 110 001 011 d 10 11 11 111 0001 0111 非奇異 唯一可譯 10 ba c 等長(zhǎng) 異前置碼 逗號(hào)碼 0表示開頭 即時(shí)碼 一些結(jié)論 變長(zhǎng)碼 定長(zhǎng)碼 只要非奇異，就唯一可譯 非奇異且異前置就唯一可譯 速率變化 設(shè)置緩沖器 速率恒定 不需緩沖器 受誤碼影響大 ,逗號(hào)碼除外 碼長(zhǎng)已知 容易同步 容易產(chǎn)生差錯(cuò)傳播 無(wú)差錯(cuò)傳播 碼樹 碼樹是表示信源編碼碼字的重要工具之一 葉子 根節(jié)點(diǎn) 例 一個(gè)碼 個(gè)碼字： 1,01,000,001, 試用碼樹來(lái)表示 用二進(jìn)制碼樹 解： R 1 0 0 0 1 1 （ 1） （ 01） （ 001） （ 000） 一些結(jié)論 非奇異碼字總能與碼樹建立一一對(duì)應(yīng)的關(guān)系 在碼樹中， ： 2進(jìn)碼樹中， 長(zhǎng)碼 本節(jié)主要內(nèi)容 一、 無(wú)失真編碼條件 二、 信源序列分 組 定理 三、 定 長(zhǎng)碼 信源 編碼 定理 失真編碼條件 對(duì)于定長(zhǎng)碼 , 只要非奇異就唯一可譯。這就要求 碼字的數(shù)目不少于被編碼的信源序列的個(gè)數(shù) 設(shè)信源 符號(hào)集包含的符號(hào)數(shù)為 r 單信源符號(hào)編碼： 碼長(zhǎng) 平均每個(gè)信源符號(hào)所需碼符號(hào)數(shù) lN l o gl o g 或例 英文字母 26個(gè)加 1個(gè)空格可看成共 27個(gè)符號(hào)的信源。 如對(duì)單符號(hào)進(jìn)行編碼： l，l 取但是，如果采用適當(dāng)?shù)男旁淳幋a，理論上每信源符號(hào)所需二進(jìn)碼符號(hào)數(shù)可以遠(yuǎn)小于上面的值， 節(jié)就是從理論上證明這種壓縮是可以實(shí)現(xiàn)的。 源序列分組定理 定理 離散無(wú)記憶信源 00 ，任意給定都可以分成兩組的信源序列長(zhǎng)度為 00 所有符號(hào)序列出現(xiàn)概率之和小于 序列 出現(xiàn)的概率 滿足： x )( )()(l o ) 證： 我們先證明（ 5. 2. 3）式。 設(shè)信源符號(hào)集 為 ， 各符號(hào)出現(xiàn)的概率分別為 ， 為長(zhǎng)度為 的序列， 為 中符號(hào) 出現(xiàn)的次數(shù)。 將信源序列按下列原則分成兩 ： 、 ，其中， ： （ 5. ： 其它 根據(jù)大數(shù)定律，當(dāng)序列足夠長(zhǎng)時(shí)，信源符號(hào) 出現(xiàn)的次數(shù)接近 。因此， 中的序列的符號(hào)出 現(xiàn)的次數(shù)符合大數(shù)定律，稱典型序列。 12 , , qA a a a x x x x :x , 1 , , p i 2G :5. 2. 4）中可以看出， 隨 的不同而改變。 設(shè) ，則對(duì)于 中的信源符號(hào) ，有 或 ，其中 由于信源是無(wú)記憶的，所以 的概率為 ， 的自信息負(fù)值為： 1G 1xGx 1 ,i iN p i 1ix )(xp11 xo g)(l o g 1( ) l o i p p1( ) l o X N p 所以 選擇 ，使得 （ 5. 2. 5） 則式（ 5. 2. 3）成立。 1l o g ( ) ( ) l o X 11l o g ( )( ) l o g l o i p 1l o 下面證明定理的后半部分。設(shè) ， 根據(jù)（ 5. 2. 3）式，有 （ 5. 因?yàn)樾旁词菬o(wú)記憶的，所以 ， 得到 （ 5. 2. 7） 將（ 5. 2. 7）代入（ 5. 2. 6），得 （ 5. 2. 8） 2l o g ( ) ()()()( 1 l o g)(l o g 11l o g ( ) ( )x H 令 , 可得 , 所以 根據(jù) ，其中 為隨機(jī)變量；這樣就得到： （ 5. 2. 9） 其中 ， ， 所以， （ 5. 2. 10） l o g ( )p x ( ) ( )iE z H X1111l o g ( ) ( ) ( )p x E z H 2()V a 2211:z z 12( , , )Nz z z z11() 2 ()iV a r z 22l o g ( ): ( )x H 其中，自信息的方差 （ 5. 2. 11） 取 ，則當(dāng) ， )(l o g2 a r2 2 2 21l o g ( ) ( ) l o g ( )qi i p x H X p p H X 220N 0時(shí)22220有總結(jié) ,1 ,: 對(duì)離散無(wú)記憶信源，給定 ，令 取 ；那么對(duì)長(zhǎng)度為 足下式的為典型序列，否則為非典型序列。 0, 220 定理說(shuō)明，當(dāng) 型序列 的 的值接近信源的熵 (lo g對(duì)于有記憶的馬氏源，定理 漸進(jìn)均分特性 典型序列的概率估計(jì) 1設(shè) )()(l o g ()(l o g)( ()( 2)(2 為底 簡(jiǎn)記為 : )(2)( 足夠小時(shí)，每個(gè)典型序列的概率 接近， 其偏差不大于 ； 此時(shí)序列的長(zhǎng)度需要很大 )(2 設(shè) 為 中序列的個(gè)數(shù) 利用概率估計(jì)的下界 1)(m i )( ( ) )2 N H 再估計(jì)下界： 利用概率估計(jì)的上界 )(2)(m ( ) ( 1 ) 2 N H ( ) ( ) ( 1 ) 2 2N H X N H 漸近均分特性 當(dāng) 取值很小時(shí)（ 對(duì)于典型序列 ，)(2 )(2)( 含意： 當(dāng)長(zhǎng)度 典型序列接近等概率 ，數(shù)目近似于 非典型序列出現(xiàn)的概率接近為零 （以概率收斂） )(2 )(2 l o g ( ) ( )p x H 結(jié)論 設(shè)信源序列數(shù)為 ，編碼序列數(shù)為 。如果每個(gè)信源序列都至少要有一個(gè)碼字，即需要 。但是，隨著信源序列長(zhǎng)度的增加，基本上是典型序列出現(xiàn)，這樣我們僅考慮對(duì)典型序列的編碼，所以實(shí)際需要 個(gè)碼字。而當(dāng)信源的熵小于 時(shí)，就會(huì)使得碼字的長(zhǎng)度減小。 Nq )(2 2l o g q 長(zhǎng)碼信源編碼定理 定理 離散無(wú)記憶信源的熵為 H(X)，碼符號(hào)集的符號(hào)數(shù)為 r，將長(zhǎng)度為 要滿足： )(l o g 足夠大時(shí)，譯碼差錯(cuò)可以任意小 ( ）；若上述不等式不滿足，肯定會(huì)出現(xiàn)譯碼差錯(cuò)。 證明思路 )(l o g 以使所有典型序列都有對(duì)應(yīng)的碼字，而最壞的情況是所有的非典型序列無(wú)對(duì)應(yīng)的碼字。 典型序列的個(gè)數(shù)小于 ( ) 2 N H X ( ) 2l N H 正定理 證明思路 若不滿足上式 逆定理 )(lo g );( XI l o g)()()/()( )()( 0l o g)()/( 已知編碼序列條件下信源序列的不確定性，如果無(wú)差錯(cuò)譯碼 ,該不確定性為零。 相關(guān)定義 定長(zhǎng)碼編碼速率 )/( l o g 信源符號(hào)比特 它表示編碼后，一個(gè)信源符號(hào)平均所攜帶的最大信息量，也可以理解為傳送一個(gè)信源符號(hào)平均所需的比特?cái)?shù)。 壓縮碼率實(shí)際就是減小編碼速率。 編碼效率 ( X )g)( )表示 l 由定理 可以接近 1 由漸近均分特性，當(dāng) 減小時(shí)， 增加。 壓縮碼率和提高編碼效率是同樣的含義。 R 信息傳輸速率：每個(gè)傳輸符號(hào)所含信息量 )/( )( 碼符號(hào)比特 對(duì)于二進(jìn)編碼，編碼效率與信息傳輸速率數(shù)值相同。 g相關(guān)結(jié)論 無(wú)失真信源信源編碼的另一種表述 如果編碼速率 ，則存在無(wú)失真編碼。 反之，肯定有失真。 )( 編碼效率與熵的關(guān)系 )()1( 22222 信源給定后，若要求編碼效率越高， N 越大，要求譯碼差錯(cuò)越低， () ( ) ( )() X H )(1 例 離散無(wú)記憶信源的模型如下，要求用二元編碼，已知 ，試估計(jì)信源序列的最小長(zhǎng)度 N。 510 , 信源的熵 解： 8 108 71 o o 222 )()1( 222224/14/3)(21 要達(dá)到一定誤碼要求，信源序列長(zhǎng)度需很長(zhǎng)，所以編碼器難于實(shí)現(xiàn)。 長(zhǎng)碼 本節(jié)主要內(nèi)容 一、 異前置碼的性質(zhì) 二、 變長(zhǎng)碼 信源 編碼 定理 前置碼的性質(zhì) R 1 0 0 0 1 1 （ 1） （ 01） （ 001） （ 000） 變長(zhǎng)碼可用 非全碼樹 來(lái)描述。下圖就是一個(gè)異前置碼的碼樹。 只有端點(diǎn)（樹葉）對(duì)應(yīng)碼字。 對(duì)應(yīng)碼字的端點(diǎn)與根之間不能有其它的節(jié)點(diǎn)作為碼字 端點(diǎn)不能向上延伸再構(gòu)成新碼字 定理 ( )( K r af t 11不等式q，碼符號(hào)數(shù)為 r，對(duì)信源符號(hào)進(jìn)行編碼，相應(yīng)碼長(zhǎng)度為 ，則異前置碼存在的 充要條件 是： , 21 M 證明思路 充分性： 做一個(gè) 階全樹，樹葉總數(shù) 取 階的任一節(jié)點(diǎn)作為第一個(gè)碼字，去掉的樹葉 1211() l l ll l l r rr r r r r r 必要性： 構(gòu)造一個(gè)碼全樹，最高階為碼字最大長(zhǎng)度 對(duì)于階為 的節(jié)點(diǎn)，占用的樹葉數(shù)為 11M K M K l l l r r r當(dāng)碼滿足 等式時(shí)，未必就是異前置碼 異前置碼并不唯一，例如 0,1 交換。 例 表列出了 3種變長(zhǎng)碼的編碼，并給出了對(duì)應(yīng)每個(gè)碼的所有的碼長(zhǎng) 和具有同一碼長(zhǎng)的碼字的個(gè)數(shù)，其中碼符號(hào)集為 0,1,2,3。試問(wèn)對(duì)每個(gè)碼是否存在相應(yīng)的異前置碼？ 碼字 碼 個(gè)數(shù) 碼 長(zhǎng) 碼 1 碼 2 碼 3 1 3 2 1 2 3 7 7 3 3 3 3 4 3 3 7 5 4 5 4 解： 利用 等式來(lái)驗(yàn)證。 對(duì)于碼 1： 54321 4443434343 2 3 4 5 51 1 1 1 1 13 ( ) ( ) ( ) ( ) ( )4 4 4 4 4 41 存在相應(yīng)的異前置碼 同理： 碼 2不存在相應(yīng)的異前置碼；碼 3存在相應(yīng)的異前置碼。 實(shí)際上，可以用碼樹來(lái)驗(yàn)證，方法更簡(jiǎn)單。 定理 1若一個(gè)碼是唯一可譯碼且碼字長(zhǎng)為 則必滿足 ： , 21 q： 信源符號(hào)數(shù) r：碼符號(hào)數(shù) 推論 意唯一可譯碼都可用異前置碼代替，而不改變碼字的任一長(zhǎng)度。 結(jié)論 滿足 一定唯一可譯 ，因?yàn)槠娈惔a可能滿足 長(zhǎng)碼信源編碼定理 單信源符號(hào)編碼的 平均碼長(zhǎng) ： 對(duì)于 信源符號(hào)平均碼長(zhǎng)為 單符號(hào)信源變長(zhǎng)碼編碼定理 1l o g)(l o g)( (X)的離散無(wú)記憶信源 X，用 則存在唯一可譯碼，其平均碼長(zhǎng)滿足： (1)證明不等式前半部 l o gl o gl o g)(111l o g ( 1 ) l o g( l o g ) ( ) 0p ep r p re r p 證明思路 1 10等式成立條件 即 (2)證明不等式后半部 證明思路 111ii o g ( 1 / )i r l o g ( 1 / )i r 1ii l o g ( 1 / )i r 11ii 1111l o g l o i i p 11( l o ) ( ) ( 1 ) l o i p p l l r 1l o g)(l o g)1()( 有限序列信源變長(zhǎng)碼編碼定理 l o g)(l o g)( 證明略 若對(duì)長(zhǎng)度為 存在唯一可譯碼，且使每信源符號(hào)平均碼長(zhǎng)滿足 ： 且對(duì)任何唯一可譯碼左邊不等式都要滿足。 定理 l o g)(l o g)( 證明略 對(duì)于離散平穩(wěn)遍歷馬氏源，有 ： 定理 仙農(nóng)第一定理 證明思路： 若對(duì)任意信源 次擴(kuò)展源 進(jìn)行編碼，當(dāng) 能找到唯一可譯的 得 XH 不等式，就可得到定理的結(jié)果 相關(guān)定義 編碼速率： 編碼效率： 信息傳輸速率： 編碼剩余度： lo g ( 1g)()( 對(duì)所有唯一可譯碼都要滿足 無(wú)需一定滿足，但存在這種關(guān)系，通常希望越小越好 一些結(jié)論 平均碼長(zhǎng)的上、下界 1lo g )( ，此時(shí)： g)( 1 各信源符號(hào)出現(xiàn)概率為 每碼元平均所帶信息量為 ,碼元符號(hào)獨(dú)立且等概 ( 1 / ) ) l o 例 例 i) 對(duì)單信源符號(hào) 進(jìn)行二元編碼，即 ，求平均碼長(zhǎng)和編碼效率； 成 2次擴(kuò)展碼，信源序列與碼序列的映射關(guān)系為： 求平均碼長(zhǎng)和編碼效率。 1201，1 1 1 2 2 1 2 20 , 1 0 , 1 1 0 , 1 1 1s s s s s s s s 解： 1) ()1 0 . 8 1 1l ，11( ) ( 3 / 4 ) ( 3 / 4 ) 9 / 1 6p s s 12( ) ( 3 / 4 ) ( 1 / 4 ) 3 / 1 6p s s 21( ) ( 1 / 4 ) ( 3 / 4 ) 3 / 1 6p s s 22( ) ( 1 / 4 ) ( 1 / 4 ) 1 / 1 6p s s 信源序列的概率： 2) 2 7 / 3 2() 0 . 8 1 1 / ( 2 7 / 3 2 ) 0 . 9 6 1 且： 與例 以看出， 為得到同樣編碼效率所用的比定長(zhǎng)碼小得多 。 因此容易達(dá)到高的編碼效率，是變長(zhǎng)碼的顯著優(yōu)點(diǎn)。 2/)16/1316/3316/3216/91( l 夫曼編碼 本節(jié)主要內(nèi)容 一、二 元哈夫曼編碼 二、 多元哈夫曼 編碼 三、 馬氏源的編碼 定理 意對(duì)于一個(gè)含 在最優(yōu)的二進(jìn)制碼，其中有兩個(gè)最長(zhǎng)的碼字有相同的長(zhǎng)度且僅最后一個(gè)碼位有別，即其中一個(gè)的最末尾是 0，而另一個(gè)的最末尾是 1（或者相反） 若一個(gè)唯一可譯碼的平均碼長(zhǎng)小于所有其它唯一可譯碼，則稱該碼為 最優(yōu)碼 (或緊致碼 )。 應(yīng)注意：最優(yōu)是唯一可譯碼之間的比較，因此它的平均碼長(zhǎng) 未必達(dá)到編碼定理的下界 。 元哈夫曼編碼 證明思路： 首先證明對(duì)于最優(yōu)碼，概率小的符號(hào)對(duì)應(yīng)長(zhǎng)度長(zhǎng)的碼字。 證明最長(zhǎng)的碼字有兩個(gè)長(zhǎng)度相同，且只有最后一位不同。 一個(gè)最優(yōu)碼唯一可譯 滿足 存在與其同樣碼長(zhǎng)的異前置碼 二元最優(yōu)異前置碼的構(gòu)造方法 設(shè)信源 ，對(duì)應(yīng)的碼字為 )(. . .)( 1 ,.,1將概率最小的兩個(gè)碼符號(hào) 合并，從而產(chǎn)生新的信源 S 1 ,1 , . . . , 11 , . . . , 設(shè) ，對(duì)應(yīng)的碼字為 。對(duì)新信源編碼后，按下面的關(guān)系就可恢復(fù)原來(lái)信源的碼字： 1 22 1, , . . . , qx x x 1 , . . . , 2x i q ，111 0 1 證明思路： 設(shè) 若 對(duì)信源 是最優(yōu)的異前置碼，則 對(duì)信源 也是最優(yōu)的異前置碼 SS11 , ,1 1 ,121 ,1 21111111121)(對(duì) S，有 一些結(jié)論 我們可以采用合并兩個(gè)最小概率符號(hào)的方法，逐步地按這樣的路線去編碼： 最后將 2字母信源分配 0、 1符號(hào)；然后可 逐步反推 到原信源 S，從而得到信源的最優(yōu)編碼。這種編碼稱做 二元 . . . 2S S S 字母信源例 信源 = ， 概率分別為： 對(duì)信源符號(hào)進(jìn)行二元 解： 依次做信源 SSS，最后將 0、 1符號(hào)分配 給 S，如下圖： 54321 , a)a)a)a)a)1a)2a)3a)4a)1a)2a)31a)2a 3a 4a 5碼字 00 01 10 110 111 將信源概率分布按大小依遞減次序排列；合并 兩概率最小者，得到信新源；并分配 0,1 符號(hào) 新信源若包含兩個(gè)以上符號(hào)返回（ 1）， 否則 到（ 3） 從最后一級(jí)向前按順序?qū)懗雒啃旁捶?hào)所對(duì)應(yīng) 的碼字 例 信源 = ， 概率分別為： 對(duì)信源符號(hào)進(jìn)行二元 并計(jì)算平均碼長(zhǎng)和編碼效率 解： 54321 , a)a)a)a)1 10 110 111 1a 2a 3a 4a ( o 2)o o 緊致碼），是異前置碼 編碼結(jié)果并不唯一，例如 0、 1可換，相同概率符號(hào)碼字可換，但平均碼長(zhǎng)不變 不一定達(dá)到編碼定理下界，達(dá)下界條件為 2通常適用于多元信源，對(duì)于二元信源，必須采用合并符號(hào)的方法，才能得到較高的編碼效率 例 例 )a)a)a)a)0 110 1110 1111 1a 2a 3a 4a 5a)/2 . 2 (源符號(hào)碼元22222222222222221 但碼長(zhǎng)的方差改變了 一些結(jié)論 當(dāng)碼長(zhǎng)的方差小時(shí)，編碼器所需緩沖器容量小。因此要盡量減小碼長(zhǎng)的方差 。 方法是：在編碼 時(shí)， 應(yīng)使合并后的信源符號(hào)位于縮減信源符號(hào)盡可能高的位置上（減少合并次數(shù)）。 否則，就利用上式計(jì)算出大于 s。然后給信源增補(bǔ)零概率符號(hào)，使增補(bǔ)后的信源符號(hào)總數(shù)為 s。編碼后，去掉這些零概率符號(hào)所對(duì)應(yīng)的碼字，其余碼字為所需碼字 通過(guò)觀察可知，要使編碼的 平均碼長(zhǎng)最短 ，對(duì)應(yīng)的碼樹要構(gòu)成滿樹是必要條件。對(duì)于 第 個(gè)節(jié)點(diǎn)到 n+1階節(jié)點(diǎn)，增加的數(shù)目為 此，達(dá)到滿樹時(shí)，總的樹葉數(shù)為： 多 元哈夫曼編碼 ( 1 )s r r m 非負(fù)整數(shù) 例 信源 = 概率分別為： 試對(duì)信源符號(hào)進(jìn)行 3元 哈夫曼編碼 ，并計(jì)算平均碼長(zhǎng)和編碼效率 解： 87654321 , r8q3 源要增加 1個(gè)零概率符號(hào) 9 3 o o g)( (源符號(hào)碼元5 2 a)a)a)a)a)a)a)(a)a)a)a)a)a)a)如果有 率分別為 用某種測(cè)試方法分步對(duì)所選擇的目標(biāo)事件進(jìn)行識(shí)別，要求具有最小的決策平均次數(shù)，相當(dāng)于對(duì)這些事件進(jìn)行 應(yīng)用 決策樹舉例 例如，甲手中有 4張紙牌，點(diǎn)數(shù)分別為 1、 2、 3、 4，要求乙猜：乙可以向甲提問(wèn)題，甲只能用是否來(lái)回答。求乙平均最少問(wèn)幾個(gè)問(wèn)題可以猜到紙牌的點(diǎn)數(shù)和相應(yīng)的策略。 (1)1、 2、 3、 4的概率均為 1/4的決策樹； (2)1、 2、 3、 4的概率分別為 1/2、 1/4、 1/8、 1/8的決策樹 . 首先 決策的設(shè)計(jì)：每步?jīng)Q策結(jié)果應(yīng)該與節(jié)點(diǎn)分支的概率匹配。 第 (1)問(wèn) 第 (2)問(wèn) 按狀態(tài)編碼 根據(jù)馬氏源的特性，當(dāng)前發(fā)出的符號(hào)所含信息量取決于當(dāng)前的狀態(tài)。這個(gè)信息量可能很大也可能很小。例如，一個(gè)馬氏源包含 3個(gè)狀態(tài) a， b，c，每個(gè)狀態(tài)代表一個(gè)輸出符號(hào)，狀態(tài)轉(zhuǎn)移矩陣如下： 馬氏源可以采用按狀態(tài)編碼和多個(gè)符號(hào)合并編碼 馬氏源的編碼 0 1 / 2 1 / 21 / 4 1 / 2 1 / 40 1 0下一個(gè)字母 概 包含的信息量 最大 下一個(gè)字母 必然出現(xiàn) b 包含的信息量 為 0 ,根據(jù)轉(zhuǎn)移概率 進(jìn)行最優(yōu)編碼，例如 為對(duì)應(yīng)的碼表 ,其中規(guī)定 信源符號(hào) 和碼字 的對(duì)應(yīng)關(guān)系，記為 0 | ) , 0 , 1 , . . . , 1ip a s j i q )1,.,1,0( ( , )jj i iC a 編碼過(guò)程 ，設(shè)初始狀態(tài) 碼表，查出 對(duì)應(yīng)的碼字 作為編碼器輸出，同時(shí)根據(jù) 得到下一個(gè)狀態(tài) 到處理完最后一個(gè)信源符號(hào) )()()( , . . . , 1100nx x x 00 )( 00碼器初始狀態(tài) ， 用 碼表查出其中的碼字與序列 的前綴的相同部分 ,設(shè) ，則 對(duì)應(yīng)的 為譯碼器的輸出 和 確定下一個(gè)狀態(tài)，設(shè)為 ，則找到 碼表中的碼字與序列 中的前綴相同的部分，設(shè) ，則 對(duì)應(yīng)的 為譯碼器的輸出 到最后一個(gè)序列符號(hào)處理完。 0.10000. )( 00.0 )(2111100. . . )( 11狀態(tài)轉(zhuǎn)移矩陣 如下 的馬氏源進(jìn)行 哈夫曼編碼，并計(jì)算編碼效率。 解： 在