無失真信源編碼定理

1、1 若一組碼中所有碼字的碼長都相同，即li=l（i=1， 2，q），則稱為等長碼。 2 3 4 rNLRlog)( )(logl/)(/ )(rnSHRSH? 稱為 5 本節(jié)討論對信源進行邊長編碼的問題。變長碼 往往在N（信源序列長度）不很大時就可編出效 率很高而且無失真的碼。 同樣，變長碼也必須是唯一可譯碼，才能實現(xiàn)無 失真編碼。對于變長碼，要滿足唯一可譯性，不 但碼本身必須是非奇異的，而且其任意有限長N 次擴展碼也都必須是非奇異的。所以，唯一可譯 變長碼的任意有限長N次擴展碼都是非奇異碼。 信源符號信源符號符號出現(xiàn)概率符號出現(xiàn)概率碼碼1碼碼2碼碼3碼碼4 S11/20011 S21/411

2、101001 S31/80000100001 S41/8110110000001 對于碼對于碼1，顯然它不是唯一可譯的，因為信源符，顯然它不是唯一可譯的，因為信源符 號號S2和和S4對應(yīng)于同一個碼字對應(yīng)于同一個碼字11，碼，碼1本身是一個奇本身是一個奇 異碼。異碼。 對于碼對于碼2，雖然它本身是一個非奇異碼，但是它，雖然它本身是一個非奇異碼，但是它 仍然不是唯一可以碼。仍然不是唯一可以碼。 因為當接收到一串碼符號序因為當接收到一串碼符號序 列時無法唯一地譯出對應(yīng)的信源符號。列時無法唯一地譯出對應(yīng)的信源符號。 表表5.4 6 7 1.圖中最上端圖中最上端A點為根，從點為根，從 根出發(fā)向根出發(fā)向

3、下伸出樹枝，樹下伸出樹枝，樹 枝的數(shù)目等于碼符號的總數(shù)枝的數(shù)目等于碼符號的總數(shù) r。 2.樹枝的盡頭為節(jié)點，從節(jié)樹枝的盡頭為節(jié)點，從節(jié) 點出發(fā)再伸出樹枝，每次每點出發(fā)再伸出樹枝，每次每 個節(jié)點伸出個節(jié)點伸出r枝，依次下去枝，依次下去 構(gòu)成一棵樹構(gòu)成一棵樹 9 當當 元元 節(jié)的碼樹的所有樹枝都被用上時，第節(jié)的碼樹的所有樹枝都被用上時，第 階節(jié)階節(jié) 點共有點共有 個終端節(jié)點，正好對應(yīng)于長度為個終端節(jié)點，正好對應(yīng)于長度為 的等長碼，的等長碼， 可見等長碼也是即時碼的一種?？梢姷乳L碼也是即時碼的一種。 rll l l r 10 11 12 不滿足克拉夫特不等式的碼，一定不是唯一可不滿足克拉夫特不等式的

4、碼，一定不是唯一可 譯碼。碼長滿足克拉夫特不等式的碼，也不一定是譯碼。碼長滿足克拉夫特不等式的碼，也不一定是 唯一可譯碼。唯一可譯碼。 克拉夫特不等式只是說明唯一可譯碼是否存在，克拉夫特不等式只是說明唯一可譯碼是否存在， 并不能作為一種碼制是否是唯一可譯碼的判斷依據(jù)。并不能作為一種碼制是否是唯一可譯碼的判斷依據(jù)。 根據(jù)唯一可譯碼的定義可知，當且僅當有限長的根據(jù)唯一可譯碼的定義可知，當且僅當有限長的 碼符號序列能譯成兩種不同的碼字序列，此碼一定碼符號序列能譯成兩種不同的碼字序列，此碼一定 不是唯一可譯變長碼。假設(shè)下圖中情況發(fā)生，不是唯一可譯變長碼。假設(shè)下圖中情況發(fā)生， 13 14 15 再將產(chǎn)生

5、的尾隨后綴列出，依此下去，直到?jīng)]有再將產(chǎn)生的尾隨后綴列出，依此下去，直到?jīng)]有 一個尾隨后綴是碼字的前綴為止。這樣，首先獲一個尾隨后綴是碼字的前綴為止。這樣，首先獲 得了由最短的碼字能引起的所有尾隨后綴，接著，得了由最短的碼字能引起的所有尾隨后綴，接著， 按照上述步驟將次短碼字、按照上述步驟將次短碼字、.所有碼字可能產(chǎn)生所有碼字可能產(chǎn)生 的尾隨后綴全部列出。由此得到由碼的尾隨后綴全部列出。由此得到由碼C的所有可能的所有可能 的尾隨后綴的集合的尾隨后綴的集合F。 16 所以，集合所以，集合F=11,00,10,01,0,1,100,110,011,101，其中，其中 “10”為碼字，故碼為碼字，故

6、碼C不是唯一可譯碼。不是唯一可譯碼。 17 q WWW,., 21 q i ii lspL 1 )( )(, , ),( , ),( , 2 2 1 1 q q sp s sp s sp s P S q lll,., 21 ),.,2 , 1()()(qispWp ii 設(shè)信源為設(shè)信源為 18 L L )(SH L SH XHR )( )( Lt SH Rt )( t R 19 20 碼字平均長度碼字平均長度 不能小于極限值不能小于極限值 ，否則唯一，否則唯一 可譯碼不存在。定理給出平均碼長的上界，但并不是可譯碼不存在。定理給出平均碼長的上界，但并不是 說大于上界不能構(gòu)成唯一可譯碼，而是我們希

7、望說大于上界不能構(gòu)成唯一可譯碼，而是我們希望 盡盡 可能短。定理給出緊致碼的最短平均碼長，并指出這可能短。定理給出緊致碼的最短平均碼長，并指出這 個最短的平均碼長與信源熵是有關(guān)的。個最短的平均碼長與信源熵是有關(guān)的。 L r SH log )( L 21 22 23 24 811. 0 3 4 log 4 3 4log 4 1 )( 22 SH 4 1 4 3 21 ss P S 25 1L 811. 0 )( L SH 符號/811. 0bitR 26 ? 16 27 3 16 1 3 16 3 2 16 3 1 16 9 2 L 27 aiP(ai)即時碼即時碼 s1s29/160 s1s23/1610 s2s13/16110 s2s21/16111 ? 32 27 2 2 L L 961. 0 27 811. 032 2 二元碼符號/961. 0 2 bitR 28 985. 0 3 991. 0 4 二元碼符號/985. 0 3 bitR 二元碼符號/991. 0 4 b