5.4等長信源編碼定理1

若一組碼中所有碼字的碼長都相同，即li=l（i=1，2，…，q），則稱為等長碼。2定理證明的基本思路是：把離散無記憶的N次擴展信源劃分成兩個互補的集合G和G'。一個集合包含的都是經常出現的信源序列，這個集合出現的概率接近于1。另一個集合雖包含的元素較多，但都不是經常出現的信源序列，總的出現的概率極小，趨于零。對高概率集G中的信源序列進行編碼，而將低概率集G'中的信源序列舍棄，不編碼。這樣，所需的平均碼長可以減少，而所引起的錯誤概率去很小。34

它是編碼后平均每個信源符號能載荷的最大信息量，稱R'為編碼后信息傳輸率。可見編碼后信源的信息傳輸率大于信源的熵，才能實現幾乎無失真編碼，為了衡量各種實際等長編碼方法的編碼效果，引進稱為編碼效率5.5變長碼5.5.1唯一可譯變長碼與即時碼

5

本節討論對信源進行邊長編碼的問題。變長碼往往在N（信源序列長度）不很大時就可編出效率很高而且無失真的碼。同樣，變長碼也必須是唯一可譯碼，才能實現無失真編碼。對于變長碼，要滿足唯一可譯性，不但碼本身必須是非奇異的，而且其任意有限長N次擴展碼也都必須是非奇異的。所以，唯一可譯變長碼的任意有限長N次擴展碼都是非奇異碼。信源符號符號出現概率碼1碼2碼3碼4S11/20011S21/411101001S31/80000100001S41/8110110000001

對于碼1，顯然它不是唯一可譯的，因為信源符號S2和S4對應于同一個碼字11，碼1本身是一個奇異碼。對于碼2，雖然它本身是一個非奇異碼，但是它仍然不是唯一可以碼。

因為當接收到一串碼符號序列時無法唯一地譯出對應的信源符號。

表5.4675.5.2即時碼的樹圖構造法即時碼的一種簡單構造方法是樹圖法。對于給定碼字的全體集合C={W1，W2，...,Wq}，可用碼樹來描述它。所謂樹，既有根、枝，又有節點。。1.圖中最上端A點為根，從根出發向下伸出樹枝，樹枝的數目等于碼符號的總數r。2.樹枝的盡頭為節點，從節點出發再伸出樹枝，每次每個節點伸出r枝，依次下去構成一棵樹88.4用碼樹表述表5.4中的碼41.在左圖中，當某一個節點被安排為碼字后，就不再繼續伸枝，此節點稱為終端節點（用粗黑點表示）。2.其他節點稱為中間節點，不安排為碼字（用空心圈表示），給每個節點所伸出的樹枝分別從左向右標上碼符號0，1，…，r。9任一即時碼都可用樹圖法來表示。當碼字長度給定時，即時碼不是唯一的。在每個節點上都有r個分枝的樹稱為整樹（滿樹），否則稱為非整樹（非滿樹）。當元節的碼樹的所有樹枝都被用上時，第階節點共有個終端節點，正好對應于長度為的等長碼，可見等長碼也是即時碼的一種。105.5.3克拉夫特（Kraft)不等式1112定理5.6若存在一個碼長為L1,L2,...,Lq的唯一可譯碼，則一定存在一個具有相同碼長的即時碼

不滿足克拉夫特不等式的碼，一定不是唯一可譯碼。碼長滿足克拉夫特不等式的碼，也不一定是唯一可譯碼。克拉夫特不等式只是說明唯一可譯碼是否存在，并不能作為一種碼制是否是唯一可譯碼的判斷依據。5.5.4唯一可譯變長碼的判斷法

根據唯一可譯碼的定義可知，當且僅當有限長的碼符號序列能譯成兩種不同的碼字序列，此碼一定不是唯一可譯變長碼。假設下圖中情況發生，13圖5.10有限長碼符號序列譯成兩種不同的碼字序列

唯一可譯碼的判斷方法：將碼C中所有可能的尾隨后綴組成一個集合F，當且僅當集合F中沒有包含任一碼字，則可判斷此碼C為唯一可譯碼。如何構成集合F,可以按如下步驟進行。首先，觀察碼C中最短的碼字是否是其它碼字的前綴。若是，將其所有可能的尾隨后綴排列出。而這些尾隨后綴又有可能是某些碼字的前綴，再將這些尾隨后綴產生的新的尾隨后綴列出，然后再觀察這些新的尾隨后綴是否是某些碼字的前綴，1415

再將產生的尾隨后綴列出，依此下去，直到沒有一個尾隨后綴是碼字的前綴為止。這樣，首先獲得了由最短的碼字能引起的所有尾隨后綴，接著，按照上述步驟將次短碼字、…...所有碼字可能產生的尾隨后綴全部列出。由此得到由碼C的所有可能的尾隨后綴的集合F。

【例5.2】現設碼C={0，10，1100，1110，1011，1101}，根據上述測試方法，判斷是否是唯一可譯碼。解：先看最短的碼字：“0”，它不是其他碼字前綴，所以沒有尾隨后綴。再觀察碼字“10”，它是碼字“1011”的前綴，因此有尾隨后綴：16C={0，10，1100，1110，1011，1101}所以，集合F={11,00,10,01,0,1,100,110,011,101}，其中“10”為碼字，故碼C不是唯一可譯碼。5.6變長信源編碼定理

由上一節討論可知，對于已知信源S可用碼符號X進行變長編碼，而且對同一信源編成同一碼符號的即時碼或唯一可譯碼可有許多種。究竟哪一種最好呢？從高效率傳輸信息的觀點來考慮，當然希望選擇由短的碼符號組成的碼字，就是用碼長作為選擇準則，為此我們引入碼的平均長度。17編碼后的碼字為對應的碼長分布為因為對唯一可譯碼來說，信源符號與碼字是一一對應的，所以有則這個碼的平均長度為它是每個信源符號平均需用的碼元數。設信源為18

當信源給定時，信源的熵就確定（為比特/信源符號），而編碼后每個信源符號平均用個碼元來變換。那么平均每個碼元攜帶的信息量即編碼后信道的信息傳輸率（碼率）為（比特/碼符號）若傳輸一個碼符號平均需要t秒鐘，則編碼后信道每秒鐘傳輸的信息量為（比特/秒）可見，越短，越大，信息傳輸效率就越高。19

對某一信源來說，若有一個唯一可譯碼，其平均長度小于所有其它的唯一可譯碼的平均長度，則該碼稱為緊致碼，或稱最佳碼。無失真變長信源編碼的基本問題就是要找最佳碼。20

碼字平均長度不能小于極限值，否則唯一可譯碼不存在。定理給出平均碼長的上界，但并不是說大于上界不能構成唯一可譯碼，而是我們希望盡可能短。定理給出緊致碼的最短平均碼長，并指出這個最短的平均碼長與信源熵是有關的。2122為了衡量各種編碼，定義變長碼的編碼效率。對于平穩有記憶信源對于無記憶信源則有式中

23

一定是小于或等于1的數。對同一信源來說，若碼的平均碼長越短，越接近極限值，信道的信息傳輸率就越高，也越接近于1，所以用碼的效率來衡量各種編碼的優劣。為了衡量各種編碼與最佳碼的差距，定義碼的剩余度為編碼效率越高，碼剩余度越接近零。24【例5.4】

有一離散無記憶信源其熵為（比特/信源符號）25

若用二元碼符號(0，1)來構造一個即時碼:s1→0，s2→1，這時平均碼長為（二元碼符號/信源符號）編碼效率為輸出的信息率為26

為提高傳輸效率，再對信源S的二次擴展信源進行編碼，其即時碼如下表所示：這個碼的平均長度為（二元碼符號/信源符號）27aiP(ai)即時碼s1s29/160s1s23/1610s2s13/16110s2s21/16111信源S中每一單個符號的平均碼長為

（二元碼符號/信源符號）其編碼效率為編碼復雜了，但信息傳輸率和效率有了提高。28

同樣可以求得信源序列長度增加到3和4時