信息論與編碼課件第四章

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

教材第116頁~117頁

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

C=（W1，W2，…，Wq）

X=（x1，x2，…，xr

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

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

非同價碼非奇異碼奇異碼不等長碼等長碼信源符號si

出現(xiàn)概率pi

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

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

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

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

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

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

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

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

定理給出了碼字長度的下界的限制。第15頁，課件共35頁，創(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頁，課件共35頁，創(chuàng)作于2023年2月信源編碼有關(guān)概念（1）平均碼長單位：碼符號/信源符號意義：每個源符號平均需要的碼符號數(shù)。編碼后每個信源符號平均用個碼符號表示。（2）信息傳輸率（平均每個碼符號攜帶的信息量）

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

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

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

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

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

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

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

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

費諾（Fano）碼Fano碼不一定是最佳碼，但有時也可能是最佳碼。

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

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

0011

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

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

q=θ(r–1)

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