信息論與編碼課件第四章

信息論與編碼課件第四章第1頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月第四章作業(yè)

教材第116頁(yè)~117頁(yè)

4.2， 4.8(1)(3)第2頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月編碼器S=（s1，s2，…，sq）

C=（W1，W2，…，Wq）

X=（x1，x2，…，xr

）信源符號(hào)碼字碼符號(hào)編碼器第3頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月碼：特定的符號(hào)集合。編碼：建立在源符號(hào)與碼符號(hào)或碼符號(hào)組之間的變換。

3547——>011101100111信源編碼：從信源輸出符號(hào)序列到碼符號(hào)序列的一種映射，其逆映射稱譯碼。信源編碼的目的：適合于信道傳輸，提高輸出效率編碼器第4頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月編碼器同價(jià)碼

非同價(jià)碼非奇異碼奇異碼不等長(zhǎng)碼等長(zhǎng)碼信源符號(hào)si

出現(xiàn)概率pi

碼A碼B碼Cs1p10000s2p20101s3p310100s4p4111011第5頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月等長(zhǎng)編碼及其定理唯一可譯碼：一個(gè)碼的任意一串有限長(zhǎng)的碼符號(hào)序列只能被唯一地譯成所對(duì)應(yīng)的信源符號(hào)序列。akp(ak)碼A碼Ba10.50000a20.250101a30.1251000a40.1251110等長(zhǎng)非奇異碼一定是唯一可譯碼第6頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月對(duì)信源S的N次擴(kuò)展信源SN進(jìn)行等長(zhǎng)編碼若S={s1,s2,…,sq}，則N次擴(kuò)展信源SN={a1,a2,…,aqN}，共有qN個(gè)符號(hào)序列。設(shè)碼符號(hào)集為X={x1,x2,…,xr}，長(zhǎng)度為l的碼符號(hào)序列Wi=(xi1xi2…xil),xi1,xi2,…,xil∈X。若要求編得的等長(zhǎng)碼是唯一可譯碼則必須滿足

qN≤rl等長(zhǎng)編碼及其定理第7頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月對(duì)qN≤rl兩邊取對(duì)數(shù)，則得Nlogq≤llogr

或例如英文電報(bào)有32個(gè)符號(hào)（26個(gè)英文字母加上6個(gè)字符），即q=32。若r=2，N=1(即對(duì)信源的逐個(gè)符號(hào)進(jìn)行二進(jìn)制編碼)，則等長(zhǎng)編碼及其定理第8頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月定理4.1（等長(zhǎng)信源編碼定理）

對(duì)于上述編碼，對(duì)于任意，只要N充分大，且滿足不等式則譯碼錯(cuò)誤概率任意小（可以進(jìn)行無失真編碼）。反之，若則不可能進(jìn)行無失真編碼，且N充分大時(shí)，譯碼錯(cuò)誤概率近似等于1。第9頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月實(shí)現(xiàn)無失真編碼存在問題：N充分大使存儲(chǔ)和處理難度大。解決辦法：采用變長(zhǎng)編碼。等長(zhǎng)信源編碼定理的意義：

信源的信息熵是（信源冗余度的可壓縮性）無失真數(shù)據(jù)壓縮的理論極限。壓縮到小于這個(gè)極限值，則無失真做不到。等長(zhǎng)編碼定理第10頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月不等長(zhǎng)編碼及其定理不等長(zhǎng)編碼的基本思想——“量體裁衣”出現(xiàn)概率大的信源符號(hào)用較短碼字表示，出現(xiàn)概率小的信源符號(hào)用較長(zhǎng)碼字表示。這樣平均每個(gè)信源符號(hào)所需的碼符號(hào)數(shù)降低，提高編碼效率。唯一可譯碼：一個(gè)碼的任意一串有限長(zhǎng)的碼符號(hào)序列只能被唯一地譯成所對(duì)應(yīng)的信源符號(hào)序列。即時(shí)碼：唯一可譯碼，譯碼時(shí)無需參考后續(xù)的碼符號(hào)就能立即作出譯碼判斷。異前綴碼：碼中沒有碼字是任意其他碼字的前綴?？梢栽跓o延時(shí)的情況下解碼。異前綴碼等價(jià)于即時(shí)碼第11頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月不等長(zhǎng)編碼及其定理第12頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月例：

p(ak)碼A碼B碼C碼Da10.50000a20.250100110a30.125100011110a40.125100101111110

碼A：奇異，非唯一；碼B：非奇異，非唯一；碼C：唯一，非異前綴；碼D：唯一，異前綴，即時(shí)碼。不等長(zhǎng)編碼及其定理第13頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月異前綴碼是唯一可譯碼中的一類子碼，易于構(gòu)造。異前綴碼等價(jià)于即時(shí)碼。即任何一種唯一可譯碼都可找到相應(yīng)、同樣有效的異前綴碼。不等長(zhǎng)編碼及其定理樹圖法是構(gòu)造即時(shí)碼（異前綴碼）的一種簡(jiǎn)單方法。

22022122210111220210一級(jí)節(jié)點(diǎn)二級(jí)節(jié)點(diǎn)三級(jí)節(jié)點(diǎn)120樹根中間節(jié)點(diǎn)不能作為碼字的終點(diǎn)第14頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月定理4.2設(shè)信源S={s1,s2,…,sq}，碼符號(hào)集X={x1,x2,…,xr}，又設(shè)碼字為（W1，W2，…，Wq），其分別對(duì)應(yīng)的碼長(zhǎng)為l1，l2，…，lq，則存在唯一可譯碼的充要條件為Kraft不等式

定理給出了碼字長(zhǎng)度的下界的限制。第15頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月例：

p(ak)碼A碼B碼C碼Da10.50011a20.2511101101a30.1250000100001a40.125110110100001r＝2，碼A，碼B：l1=1,l2=l3=l4=2,這樣碼A，碼B不可能是唯一可譯碼。r＝2，碼C，碼D：l1=1,l2=2,l3=3,l4=4,碼C不是唯一可譯碼，碼D是唯一可譯碼。第16頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月信源編碼有關(guān)概念（1）平均碼長(zhǎng)單位：碼符號(hào)/信源符號(hào)意義：每個(gè)源符號(hào)平均需要的碼符號(hào)數(shù)。編碼后每個(gè)信源符號(hào)平均用個(gè)碼符號(hào)表示。（2）信息傳輸率（平均每個(gè)碼符號(hào)攜帶的信息量）

越短，信息傳輸率就越高。第17頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月（3）最佳碼（緊致碼）最佳碼：對(duì)于某一信源和某一碼符號(hào)集，若有一唯一可譯碼，其平均碼長(zhǎng)小于等于所有其他唯一可譯碼的平均碼長(zhǎng)，則該碼稱為最佳碼。（最短唯一可譯碼）

無失真信源編碼的基本問題就是找到最佳碼，最佳碼的平均碼長(zhǎng)為理論極限。

理論極限是多少呢？第18頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月定理4.3（單符號(hào)信源的變長(zhǎng)編碼定理）若有一離散無記憶信源S具有熵H（S），并有r個(gè)碼符號(hào)的符號(hào)集X={x1,x2,…,xr}，則總可以找到一種無失真編碼方法，構(gòu)成唯一可譯碼，使其平均碼長(zhǎng)滿足證明：第19頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月第20頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月定理4.4（變長(zhǎng)無失真信源編碼定理----

香農(nóng)第一定理）離散無記憶信源S的N次擴(kuò)展信源SN={a1,a2,…,aqN

}，共有qN個(gè)符號(hào)序列，具有熵H（SN），并有r個(gè)碼符號(hào)的符號(hào)集X={x1,x2,…,xr}。若對(duì)信源SN（即信源輸出的是N長(zhǎng)的符號(hào)序列）進(jìn)行編碼，總可以找到一種編碼方法，構(gòu)成唯一可譯碼，使信源S中每個(gè)信源符號(hào)所需的碼字平均長(zhǎng)度滿足香農(nóng)第一定理第21頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月由香農(nóng)第一定理得到平均碼長(zhǎng)的理論極限：H(S)/logr香農(nóng)第一定理第22頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月由香農(nóng)第一定理得到平均碼長(zhǎng)的理論極限：H(S)/logr香農(nóng)第一定理的物理意義R等于無噪無損信道的信道容量C。無失真信源編碼的實(shí)質(zhì)：對(duì)離散信源進(jìn)行適當(dāng)?shù)淖儞Q，使變換后新的碼符號(hào)信源（信道的輸入信源）盡可能等概率分布，以使新信源的每個(gè)碼符號(hào)平均所含的信息量達(dá)到最大，從而使信息傳輸率R達(dá)到信道容量C，實(shí)現(xiàn)信源與信道理想的統(tǒng)計(jì)匹配。

第23頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月〖例4.1〗有一離散無記憶信源其熵為H(S)=0.811

比特/信源符號(hào)，用二進(jìn)制符號(hào){0，1}來構(gòu)造一個(gè)即時(shí)碼。s1→0，s2→1。碼的效率為η1=0.811信息傳輸率為R1=0.811比特/二進(jìn)制符號(hào)。對(duì)信源S的長(zhǎng)為2、3、4的符號(hào)序列的符號(hào)序列（即N=2、3、4）分別進(jìn)行變長(zhǎng)編碼。η2=0.961 R2=0.961比特/二進(jìn)制符號(hào)η3=0.985 R3=0.985比特/二進(jìn)制符號(hào)η4=0.991 R4=0.991比特/二進(jìn)制符號(hào)可見編碼復(fù)雜一些，使信息傳輸率提高。第24頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月變長(zhǎng)碼的編碼方法霍夫曼(Huffman)

碼Huffman碼是異字頭碼，是一種最佳碼。1952年提出，應(yīng)用于數(shù)據(jù)壓縮，文件傳輸、語(yǔ)音處理、圖象處理。

費(fèi)諾（Fano）碼Fano碼不一定是最佳碼，但有時(shí)也可能是最佳碼。

第25頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月霍夫曼碼的編碼方法二進(jìn)制霍夫曼碼的的編碼方法，它的編碼步驟如下：（1）將q個(gè)信源符號(hào)按概率值的大小以遞減次序排列起來，設(shè)

p1≥p2≥…≥pq（2）用0和1碼符號(hào)分別代表概率最小的兩個(gè)信源符號(hào)，并將這兩個(gè)概率最小的信源符號(hào)合并一個(gè)符號(hào)，從而得到包含q－1個(gè)符號(hào)的新信源--------縮減信源S′。（3）把縮減信源S′的符號(hào)仍按概率值大小以遞減次序排列，再將其最后二個(gè)概率最小的符號(hào)合并成一個(gè)符號(hào)，并分別用0和1碼符號(hào)表示，這樣又得到q－2個(gè)符號(hào)的新縮減信源S〞。（4）依次繼續(xù)下去，直至信源最后只剩兩個(gè)符號(hào)為止。將這最后兩個(gè)信源符號(hào)分別用0和1碼符號(hào)表示。然后從最后一級(jí)縮減信源開始，向前返回，就得出各信源符號(hào)所對(duì)應(yīng)的碼符號(hào)序列，即得到對(duì)應(yīng)的碼字。第26頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月縮減信源（輔助信源）設(shè)信源S，取值于集合其概率分布滿足,碼為縮減信源S’碼為第27頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月例：對(duì)下列離散無記憶穩(wěn)恒信源進(jìn)行Huffman編碼源字母概率碼字編碼過程a10.4a20.2a30.2a40.1a50.1霍夫曼碼編碼舉例第28頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月霍夫曼碼編碼舉例0001001110101010110010

0011

01100010101010第29頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月霍夫曼碼說明：（1）如果出現(xiàn)相同概率的情況，合并后的概率盡量安排處于最高的位置，減少合并元素被重復(fù)編碼的次數(shù)，使短碼字充分利用。（2）不同編碼后，平均碼長(zhǎng)相等，取碼長(zhǎng)偏離平均碼長(zhǎng)的方差較小的，即

（3）縮減時(shí)源符號(hào)不夠時(shí)，補(bǔ)零（概率）后編碼。即：信源符號(hào)個(gè)數(shù)應(yīng)滿足

q=θ(r–1)

+r第30頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月例：對(duì)下列離散無記憶穩(wěn)恒信源進(jìn)行4進(jìn)制Huffman編碼源字母概率碼字編碼過程a10.22a20.20a30.18a40.15a50.10a60.08a70.05a80.02r進(jìn)制霍夫曼碼編碼舉例第31頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月霍夫曼碼的最佳性定理4.5對(duì)于給定信源，存在有最佳唯一可譯二元碼，其最小概率的兩個(gè)碼字Wq-1和