第7講-離散無記憶信源不等長編碼2014

離散無記憶信源

不等長編碼第7講消息集碼字集等長編碼無失真幾乎無失真對典型序列無誤編碼Review擲硬幣：正面出現(xiàn)p=0.25，這時信源熵H(U)=0.811比特。（1）若采用等長二元無錯編碼時，（2）若采用只對典型序列編碼，要求譯碼錯誤概率，求L由可得又可得例題要求長度達到2580萬以上，難以實現(xiàn)。Review出路：不等長編碼Morse電碼

特點：經(jīng)常出現(xiàn)的字母變換為較短的數(shù)字序列，不經(jīng)常出現(xiàn)的字母變換為較長的數(shù)字序列。ABCDEFGHI·

––

·

·

·

–

·

–

·–

·

···

·

–

·

–

–

·

·

·

·

·

·

·JKLMNOPQR·

–

–

––

·

–·

–

·

·

–

–

–

·

–

–

–

·

–

–

·

–

–

·

–

·

–

·

STUVWXYZ·

·

·

–·

·

–·

·

·

–·

–

–

–

·

·

–

–

·

–

–

–

–

·

·

設(shè)信源隨機變量U的概率分布為若事件ak對應(yīng)的碼字長度為nk，則平均碼字長度為平均碼長

希望小。解決方案：概率大的事件用短碼字。

1）每個消息都至少有一個碼字與之對應(yīng)，且不同的消息對應(yīng)不同的碼字；

2）對于一個碼，如果存在一種譯碼方法，使任意若干個碼字所組成的字母串只能唯一地被翻譯成這幾個碼字所對應(yīng)的事件序列，即碼字的分點唯一確定。不等長編碼的唯一可譯性解決方案：適當(dāng)?shù)鼐幋a，使得每個碼字都具有識別標(biāo)記。事件概率碼A碼B碼C碼Da10.50000a20.25011001a30.125100110011a40.12510111110111不等長碼實例碼C：異字頭碼碼D：逗點碼碼C的平均碼長小于碼D的平均碼長若①事件與碼字一一對應(yīng)；②每個碼字都不是另一個碼字的開頭部分（字頭）。

則稱此碼為異字頭碼。唯一可譯的兩種解決方法逗點碼若①事件與碼字一一對應(yīng)；②每個碼字的開頭部分都是一個相同的字母串；③這個字母串僅僅出現(xiàn)在碼字的開頭，不出現(xiàn)在碼字的其它部位。則稱這個字母串為逗號，稱此碼為逗點碼。異字頭碼見到逗號就識別為一個碼字的開始。見到一個碼字就立即識別。事件概率碼A碼B碼C碼Da10.50000a20.25011001a30.125100110011a40.12510111110111不等長碼實例碼C的平均碼長為

1×0.5+2×0.25+3×0.125+3×0.125=1.75碼D的平均碼長為

1×0.5+2×0.25+3×0.125+4×0.125=1.875異字頭碼異字頭碼可用樹圖表示。異字頭碼是唯一可譯的。異字頭碼具有即時性。A01000000000000011111111111二進制碼樹樹根—碼字的起點分成D個樹枝—碼的進制數(shù)端節(jié)點—碼字1101中間節(jié)點—碼字的一部分節(jié)數(shù)—碼長碼樹滿樹：端節(jié)點均為N節(jié)節(jié)點——等長碼，碼長為N端節(jié)點數(shù)目非滿樹：?01200112222三進制碼樹全樹：每個節(jié)點上都有D個分枝的樹D元全樹的端節(jié)點數(shù)目為D+m(D-1)，m為非負整數(shù)。0001112碼樹異字頭碼（譯碼）異字頭碼的樹圖表示。異字頭碼是唯一可譯的。異字頭碼具有即時性事件概率碼Ca10.50a20.2510a30.125110a40.125111異字頭碼（譯碼）異字頭碼的樹圖表示。異字頭碼是唯一可譯的。異字頭碼具有即時性。事件概率碼Ca10.50a20.2510a30.125110a40.125111000111a1a2a3a4111100a4a2a100001110101101110（2）當(dāng)碼字長度給定，異字頭碼不是唯一的。任意給定的n1,n2,…,nK和D，是否總能存在滿足條件的D元異字頭碼？

（1）若選定某一節(jié)點表示消息，則該節(jié)點不再延伸。這是為了保證異字頭條件。11111000100100010（3）若要構(gòu)造有K個碼字的D元異字頭碼，其碼長分別為n1,n2,…,nK，則只需畫出一個有K個端節(jié)點分別處于n1,n2,…,nK級的D元樹圖即可。

異字頭碼（編碼）Kraft不等式定理

任一長度為n1，n2，…，nK的D-元異字頭碼必滿足Kraft不等式反之，若給定滿足Kraft不等式的一組碼字長度，則可以構(gòu)造出具有同樣長度的異字頭碼。Kraft不等式必須注意：Kraft不等式只是用來說明唯一可譯碼是否存在，并不能作為唯一可譯碼的判據(jù)；如碼字{0，10，010，111}雖然滿足Kraft不等式，但它不是唯一可譯碼。010可譯碼為010，或0,10不妨設(shè)n1≤n2≤…≤nK，則n1級節(jié)點中的任何一個作端點即占去了滿樹中所有可能nK級節(jié)點的

Kraft不等式充分性證明證明:依次進行下去，當(dāng)為第K個消息選擇碼字時，若有就能保證為第K個消息能夠選擇一個nK級端點作為碼字，從而構(gòu)造了異字頭碼。

設(shè)有一個異字頭碼存在，它的各碼字長度為n1≤n2≤…≤nK。Kraft不等式必要性證明證明：每個碼字對應(yīng)的節(jié)點占去碼樹的。根據(jù)異字頭條件，我們可以將K個碼字和樹中的某一級節(jié)點相對應(yīng)，即將碼字嵌入樹中。由異字頭條件知，這K個碼字至多覆蓋整個碼樹，因而有唯一可譯碼必要條件唯一可譯碼必滿足Kraft不等式定理：證明對任意的正整數(shù)r，有r長碼字序列總共個序列，對其進行重新組合表示含有i個碼元的序列總數(shù)則消息集碼字集唯一可譯碼必要條件唯一可譯碼必滿足Kraft不等式定理證明對任意的正整數(shù)r，有由碼的唯一可譯性，可知長度為i含r個碼字的序列必不相同，于是，則當(dāng)時，上式右邊指數(shù)項趨于0，因而右邊趨于1。由此得任一滿足Kraft不等式的非異字頭碼都可以找到一個碼字長度不變的異字頭碼。

任一唯一可譯的D元不等長碼總滿足存在唯一可譯的D元不等長碼滿足不等長編碼定理不等長編碼定理證明證明于是有Kraft不等式

選n1、n2、…、nK，使不等長編碼定理證明另外，對上式右邊求倒數(shù)取對數(shù)并進行概率加權(quán)得則有，所以必存在碼字長度為n1、n2、…、nK的唯一可譯D元不等長碼。于是有任一唯一可譯的D元不等長碼總滿足存在唯一可譯的D元不等長碼滿足不等長編碼定理推論若對L長消息符號序列進行編碼，相當(dāng)于對源中的元素進行編碼任一唯一可譯的D元不等長碼總滿足存在唯一可譯的D元不等長碼滿足Shannon第一編碼定理編碼速率與編碼效率——離散無記憶信源任一唯一可譯的D元不等長碼總滿足存在唯一可譯的D元不等長碼滿足Shannon第一編碼定理任一唯一可譯的D元不等長碼總滿足存在唯一可譯的D元不等長碼滿足——離散無記憶信源例題作二元編碼U概率碼字平均碼長Rηa13/401×3/4+1×1/4=1a21/41U2概率碼字平均碼長Rηa1a19/1601×9/16+2×3/16+3×3/16+3×1/16=27/1627/320.961a1a23/1610a2a13/16110a2a21/16111H(U)=0.8111

0.811Shannon-Fano-Elias編碼Shannon-Fano-Elias編碼方法采用信源符號的累積分布函數(shù)來分配碼字。設(shè)信源符號集，其相應(yīng)的概率分布為P(a

k)>0(k=1,2,…,K)。定義信源符號的累積分布函數(shù)為其中。又定義修正累積分布函數(shù)：

將區(qū)間分為了K個子區(qū)間，每個區(qū)間的寬度為P(ak)。修正累積分布函數(shù)值處于對應(yīng)ak臺階的中點。編碼方法？因為所有概率都大于0，所有當(dāng)問題：的數(shù)值取多少位能保證唯一可譯？一般為一實數(shù)，若用二進制數(shù)表示，可能為無限位數(shù)。二元編碼方法：消息ak的碼字為實數(shù)

的二元數(shù)字表示序列的截短，保留的截短序列長度nk是大于或等于I(ak)的最小整數(shù)加1。即如知道，就能確定處在累積分布函數(shù)圖中那個區(qū)間，就能確定信源符號。因此，可采用的數(shù)值作為符號的碼字?？勺C明：該碼是滿足異字頭碼條件，并且唯一可譯碼？若選取得可見，與它的近似值之差小于該臺階的一半。唯一可譯！根據(jù)二進制小數(shù)截去位數(shù)的影響，得異字頭碼？用對編碼，得的碼字為此碼字對應(yīng)的區(qū)間為。由和可知，此區(qū)間的下界處于累積分布函數(shù)臺階的中點以下，以上，而這區(qū)間的上界處于以下。也就是，每個碼字對應(yīng)的區(qū)間完全處于累積分布函數(shù)中該信源符號對應(yīng)的臺階寬度內(nèi)。所以，不同碼字對應(yīng)的區(qū)域是不同的，沒有重疊，該碼滿足異字頭條件。注意：在這種編碼方法中沒有要求信源符號的概率按照大小次序排列。習(xí)題3-7（Shannon編碼）

令離散無記憶信源，且。定義累積分布函數(shù):

而Ql=0。今按下述方法進行二元編碼：消息ak的碼字為實數(shù)Qk的二元數(shù)字表示序列的截短，保留的截短序列長度nk是大于或等于I(ak)的最小整數(shù),如有尾數(shù)進位。(a)證明這樣編得到的碼滿足異字頭條件，且平均碼長滿足Fano編碼為選出的碼集合的平均長度最小，自然想到:從每個節(jié)點出發(fā)的D種可能的分支出現(xiàn)的概率近于相等，這將給出一種近于最佳的編碼方法—Fano編碼。例：設(shè)信源U的9個消息a1，a2，…，a9的概率分別為1/3，1/9，1/9，1/9，1/9，1/9，1/27，1/27，1/27。為了使平均碼長盡可能地短，我們將消息劃分成近于等概的3個子集{a1