無失真信源編碼定理

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

2、00001S41/8110110000001 對于碼對于碼1，顯然它不是唯一可譯的，因為信源符，顯然它不是唯一可譯的，因為信源符號號S2和和S4對應于同一個碼字對應于同一個碼字11，碼，碼1本身是一個奇本身是一個奇異碼。異碼。 對于碼對于碼2，雖然它本身是一個非奇異碼，但是它，雖然它本身是一個非奇異碼，但是它仍然不是唯一可以碼。仍然不是唯一可以碼。 因為當接收到一串碼符號序因為當接收到一串碼符號序列時無法唯一地譯出對應的信源符號。列時無法唯一地譯出對應的信源符號。 表表5.4671.圖中最上端圖中最上端A點為根，從點為根，從根出發(fā)向根出發(fā)向 下伸出樹枝，樹下伸出樹枝，樹枝的數(shù)目等于碼符號的總數(shù)

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

4、等式的碼，也不一定是唯一可譯碼。唯一可譯碼。 克拉夫特不等式只是說明唯一可譯碼是否存在，克拉夫特不等式只是說明唯一可譯碼是否存在，并不能作為一種碼制是否是唯一可譯碼的判斷依據(jù)。并不能作為一種碼制是否是唯一可譯碼的判斷依據(jù)。 根據(jù)唯一可譯碼的定義可知，當且僅當有限長的根據(jù)唯一可譯碼的定義可知，當且僅當有限長的碼符號序列能譯成兩種不同的碼字序列，此碼一定碼符號序列能譯成兩種不同的碼字序列，此碼一定不是唯一可譯變長碼。假設下圖中情況發(fā)生，不是唯一可譯變長碼。假設下圖中情況發(fā)生，131415 再將產生的尾隨后綴列出，依此下去，直到沒有再將產生的尾隨后綴列出，依此下去，直到沒有一個尾隨后綴是碼字的前綴為

5、止。這樣，首先獲一個尾隨后綴是碼字的前綴為止。這樣，首先獲得了由最短的碼字能引起的所有尾隨后綴，接著，得了由最短的碼字能引起的所有尾隨后綴，接著，按照上述步驟將次短碼字、按照上述步驟將次短碼字、.所有碼字可能產生所有碼字可能產生的尾隨后綴全部列出。由此得到由碼的尾隨后綴全部列出。由此得到由碼C的所有可能的所有可能的尾隨后綴的集合的尾隨后綴的集合F。16所以，集合所以，集合F=11,00,10,01,0,1,100,110,011,101，其中，其中“10”為碼字，故碼為碼字，故碼C不是唯一可譯碼。不是唯一可譯碼。17qWWW,.,21qiiilspL1)()(,),(,),(,2211qqsp

6、sspsspsPSqlll,.,21),.,2 , 1()()(qispWpii設信源為設信源為18LL)(SHLSHXHR)()(LtSHRt)(tR1920 碼字平均長度碼字平均長度 不能小于極限值不能小于極限值 ，否則唯一，否則唯一可譯碼不存在。定理給出平均碼長的上界，但并不是可譯碼不存在。定理給出平均碼長的上界，但并不是說大于上界不能構成唯一可譯碼，而是我們希望說大于上界不能構成唯一可譯碼，而是我們希望 盡盡可能短。定理給出緊致碼的最短平均碼長，并指出這可能短。定理給出緊致碼的最短平均碼長，并指出這個最短的平均碼長與信源熵是有關的。個最短的平均碼長與信源熵是有關的。LrSHlog)(L21222324811. 034log434log41)(22SH414321ssPS251L811. 0)(LSH符號/811. 0bitR 26?162731613163216311692L27aiP(ai)即時碼即時碼s1s29/160s1s23/1610s2s13/16110s2s21/16111?322722LL961. 027811. 0322二元碼符號/961. 02bitR 28985. 03991. 04二元碼符號/985. 03bitR