信源編碼等長(zhǎng)碼

主講：肖竹第三章

離散信源無(wú)失真編碼第三章

PartI編碼的基本概念唯一可譯碼等長(zhǎng)碼與等長(zhǎng)信源編碼原理編碼實(shí)質(zhì)上是對(duì)信源的原始符號(hào)按一定的數(shù)學(xué)規(guī)則進(jìn)行一種變換。由于無(wú)失真信源編碼可以不考慮抗干擾問(wèn)題，所以它的數(shù)學(xué)描述比較簡(jiǎn)單。如圖所示,就是一個(gè)編碼器。編碼器S(消息、信源符號(hào)集){S1,S2,…,Sq}W(碼字符號(hào)集){w1,w2,…,wq}碼/信道符號(hào)集{X1,X2,…,Xr}圖3.1無(wú)失真信源編碼器3.1編碼的基本概念適合信道傳輸輸入信源符號(hào)S={S1,S2,…,Sq}。同時(shí)存在另一符號(hào)X={x1,x2,…,xr}，一般元素xj是適合信道傳輸?shù)?，稱為碼符號(hào)(或者碼元)。編碼器是將信源符號(hào)集中的符號(hào)Si(或者長(zhǎng)為N的信源符號(hào)序列)變換成由xj(j=1,2,…,r)組成的長(zhǎng)度為L(zhǎng)i的一一對(duì)應(yīng)的碼符號(hào)序列Wi的序列，稱為碼字。即Si(i=1,…,q)?Wi=(xi1xi2…xiLi),xi1∈X(k=1,…,Li)Si={Si1,Si2,…,SiN}?Wi=(xi1xi2…xiLi),SiK∈S(k=1,…,Li)長(zhǎng)度Li稱為碼字長(zhǎng)度或簡(jiǎn)稱碼長(zhǎng)。所有這些碼字的集合C稱為碼。映射：一一對(duì)應(yīng)，無(wú)壓縮編碼多對(duì)一，壓縮編碼[舉例]待發(fā)消息：陰晴雨雪信源符號(hào)集：{a1,a2,a3,a4}用二進(jìn)制信道：{0,1}，4個(gè)消息轉(zhuǎn)化為4個(gè)二進(jìn)制代碼：{a1:00,a2:01,a3:10,a4:11},碼長(zhǎng)為2漢字電報(bào)：10000個(gè)常用字?10000個(gè)4位十進(jìn)制數(shù)

每個(gè)十進(jìn)制數(shù)字?5位二進(jìn)制等重代碼組u1

?0000?01101011010110101101u2

?0001?01101011010110101011…u10000

?9999?10011100111001110011信源消息信源符號(hào)集：0,1,2，…,9碼符號(hào)集：0，1碼序列

碼的定義

1.二元碼

若碼符號(hào)集為X={0,1},所得碼字都是一些二元序列,則稱為二元碼。二元碼是數(shù)字通信和計(jì)算機(jī)系統(tǒng)中最常用的一種碼。

2.等長(zhǎng)碼(或稱固定長(zhǎng)度碼)若一組碼中所有碼字的碼長(zhǎng)都相同,即

Li=L(i=1,2,…,q),則稱為等長(zhǎng)碼。

3.變長(zhǎng)碼若一組碼中所有碼字的碼長(zhǎng)各不相同,即任意碼字由不同長(zhǎng)度Li碼符號(hào)序列組成,則稱為變長(zhǎng)碼。

4.非奇異碼若一組碼中所有碼字都不相同,即所有信源符號(hào)映射到不同的碼符號(hào)序列，5.奇異碼

若一組碼中有相同的碼字,信源消息到碼字的映射不是一一對(duì)應(yīng)則稱碼C為奇異碼。---不具備唯一可譯性6.同價(jià)碼若碼符號(hào)集X:{x1,x2,…,xr}中每個(gè)碼符號(hào)xi所占的傳輸時(shí)間相同,則所得的碼C為同價(jià)碼。一般二元碼是同價(jià)碼。對(duì)同價(jià)碼來(lái)說(shuō)，等長(zhǎng)碼中每個(gè)碼字的傳輸時(shí)間都相同；而變長(zhǎng)碼中每個(gè)碼字的傳輸時(shí)間就不一定相同。電報(bào)中常用的莫爾斯碼是非同價(jià)碼，其碼符號(hào)點(diǎn)(?)和劃(—)所占的傳輸時(shí)間不相同。

7.碼的N次擴(kuò)展碼假設(shè)某碼C,它把信源S中的符號(hào)Si一一變換成碼C中的碼字Wi,則碼C的N次擴(kuò)展碼是所有N個(gè)碼字組成的碼字序列的集合。若碼C={W1,W2,…,Wq}其中則N次擴(kuò)展碼可見(jiàn),N次擴(kuò)展B中,每個(gè)碼字Bi(i=1,…,qN)與N次擴(kuò)展信源SN中每個(gè)信源符號(hào)序列Si={si1,si2,…,siN}一一對(duì)應(yīng)。舉例，設(shè)信源S的概率空間為若把它通過(guò)一個(gè)二元信道進(jìn)行傳輸，為使信源適合信道傳輸，就必須把信源符號(hào)Si變換成0,1符號(hào)組成的碼符號(hào)序列(二元序列)。我們可采用不同的二元序列其與信源符號(hào)Si一一對(duì)應(yīng)，這樣就可得到不同的二元碼，如表3.1所示。表3.1等長(zhǎng)非奇異碼變長(zhǎng)非奇異碼求碼的N次擴(kuò)展碼：

求碼2的二次擴(kuò)展碼:[s1=0；s2=01；s3=001;s4=111]信源S的二次擴(kuò)展信源

S2=[a1=s1s1,a2=s1s2,a3=s1s3,…,a16=s4s4]所以碼2的二次擴(kuò)展碼為

8.唯一可譯碼若碼的任意一串有限長(zhǎng)的碼符號(hào)序列只能被唯一地譯成所對(duì)應(yīng)的信源符號(hào)序列,則此碼稱為唯一可譯碼,或單義可譯碼。否則，就稱為非唯一可譯碼或非單義可譯碼。

例如,表3.1中碼1是唯一可譯碼,而碼2是非唯一可譯碼。因?yàn)閷?duì)于碼2，其有限長(zhǎng)的碼符號(hào)序列能譯成不同的信源符號(hào)序列。如碼符號(hào)序列為0010，可譯成s1s2s1或s3s1，就不唯一了。表3.1唯一可譯碼非唯一可譯碼唯一可譯碼[定義]若W中任一有限長(zhǎng)的碼字序列（即有限長(zhǎng)的一串W），可以被唯一地分割成一個(gè)一個(gè)碼字，就稱為是單義可譯或唯一可譯的，W也叫做單義代碼。從擴(kuò)展性定義：碼的任意N次擴(kuò)展碼都是非奇異碼，則唯一可譯[例]考慮以下幾種變長(zhǎng)碼：

信源字母概率碼A碼B碼C碼D碼E碼Fa1a2a3a41/21/41/81/80011001111110101101110010110111001011111010101111[例]考慮以下幾種變長(zhǎng)碼：

信源字母概率碼A碼B碼C碼D碼E碼Fa1a2a3a41/21/41/81/800110011111101011011100101101110010111110101011111、碼A不是一一對(duì)應(yīng)的（碼字0同時(shí)對(duì)應(yīng)a1與a2），奇異碼，故不是唯一可譯的（雖然它具有最小的碼長(zhǎng)L）；2、碼B是一一對(duì)應(yīng)的（非奇異碼），但由它所構(gòu)成的序列不能被唯一分割。比如碼字序列01110，可以分割成0,1,1,1,0;也可分割成0,1,11,0；0,11,1,0；或0,111,0等,因而也不是唯一可譯的。但它與碼A還有不同之處：只要在碼字之間留有空隙（例如像莫爾斯電報(bào)那樣）或者加個(gè)“逗號(hào)”，就可以正確譯碼。

碼D:0010110111

3、碼D正是在碼B各碼字（除了w1）之前加了起一個(gè)逗號(hào)作用的碼元“0”，從而成為唯一可譯的，但這就使平均碼長(zhǎng)增加了0.5bit；

碼B:0111111

碼C:010110111

4、碼C是唯一可譯的,因?yàn)槿我淮邢揲L(zhǎng)的碼字w,如100111011010只能被分割成10，0，111，0，110，10任何其他分割方法都會(huì)產(chǎn)生一些不屬于代碼W的碼字（如1，001，11，011，010）；

碼E:001011111

a1a2a3a45、比較微妙的是碼E：當(dāng)收端收到“0”時(shí)，仍不能及時(shí)判決為a1，必須等到第二個(gè)碼元來(lái)時(shí)，也許才可做出判斷。例如，當(dāng)?shù)诙€(gè)碼元為“0”時(shí)，就可判斷前一個(gè)“0”對(duì)應(yīng)于a1；但若第二個(gè)碼元仍為“1”，則還無(wú)法做出判斷，因?yàn)槭莂2或a3的可能性都還存在。所以它的譯碼就要等待一段時(shí)間。特別是若遇到如下的碼字序列：011111111…11111其中只有第一個(gè)碼元為“0”，其余均為“1”，收端在開(kāi)始幾步就無(wú)法加以判決。因?yàn)閷㈤_(kāi)頭幾個(gè)碼元“01111”判決成“a11111”固然可以，但判決成“a2111”或“a311”也未嘗不行。因而最好的辦法就是待收到全部序列(如無(wú)第二個(gè)“0”出現(xiàn))后，再?gòu)奈查_(kāi)始進(jìn)行判決，才能正確地決定第一個(gè)消息是什么。這樣一來(lái)，就產(chǎn)生了時(shí)間上的延遲和存儲(chǔ)容量的增加。甚至可以說(shuō)，也許要有無(wú)限大的存儲(chǔ)容量才夠用.

5、對(duì)于碼F，即使從尾開(kāi)始判斷，也不是唯一可譯的，如對(duì)碼序列101111010既可譯成“a2，a4，a2，a2”，也可判決為“a3，a4，a1，a2”。碼F:010101111

a1，a2，a3，a4即時(shí)碼：對(duì)于變長(zhǎng)碼的定義：字頭（前綴）：c=c1c2…cn；c1c2…ci（i<n）是字頭異字頭碼（無(wú)前綴碼）：任一碼字都不是另一碼字的字頭，可以即時(shí)譯碼，即時(shí)碼非異字頭碼不能即時(shí)譯碼，稱為非即時(shí)碼即時(shí)碼唯一可譯，而唯一可譯碼不一定是即時(shí)碼信源符號(hào)碼C碼D碼E碼Fa1a2a3a40101101110010110111001011111010101111即時(shí)碼唯一可譯非即時(shí)碼唯一可譯非即時(shí)碼可譯非即時(shí)碼非唯一可譯[樹(shù)圖舉例]={0,10,110,111}.對(duì)于D進(jìn)制碼，從樹(shù)根開(kāi)始，每次引出D個(gè)分支，某一節(jié)點(diǎn)確定為碼字之后，不再引出分支●●●oooo010110111根111000碼字是從樹(shù)根節(jié)點(diǎn)出發(fā)到達(dá)終節(jié)點(diǎn)所對(duì)應(yīng)的碼符號(hào)序列即時(shí)碼可以通過(guò)樹(shù)圖來(lái)構(gòu)造：根節(jié)點(diǎn)到終結(jié)點(diǎn)對(duì)應(yīng)的碼符號(hào)序列碼的分類結(jié)構(gòu)圖奇異碼非奇異碼唯一可譯碼非唯一可譯碼等長(zhǎng)碼非等長(zhǎng)碼即時(shí)碼延時(shí)碼平均碼長(zhǎng)等長(zhǎng)碼：平均碼長(zhǎng)=每個(gè)碼字碼長(zhǎng)碼字長(zhǎng)度碼字Cm出現(xiàn)概率碼長(zhǎng)的概率加權(quán)平均變長(zhǎng)碼平均碼長(zhǎng)碼：{0,1,00,11}；{1,10,100,1000}，假定各消息概率：（0.4,0.2,0.2,0.2）N次擴(kuò)展碼平均碼長(zhǎng)問(wèn)題：怎么使得平均碼長(zhǎng)盡量短？概率大碼長(zhǎng)小概率小碼長(zhǎng)大原信源消息碼字長(zhǎng)度信息傳輸速率-----信道單位時(shí)間內(nèi)所傳輸?shù)膶?shí)際信息量非壓縮（無(wú)失真編碼）-----信源的熵率（時(shí)間熵）信息傳輸率定義：信源熵平均碼長(zhǎng)碼符號(hào)時(shí)間若以碼元時(shí)間為單位：[舉例]為提高傳輸效率使得平均碼長(zhǎng)盡可能短，進(jìn)行二進(jìn)制不等長(zhǎng)編碼：求信息傳輸速率。信源特殊分布，每個(gè)消息的概率2^(-h)緊致碼。二進(jìn)制符號(hào)最大信息量為1bit

3.2等長(zhǎng)碼及等長(zhǎng)編碼定理

簡(jiǎn)單信源S:信源符號(hào)集包含K個(gè)符號(hào)，碼符號(hào)集包含D個(gè)符號(hào)，碼字長(zhǎng)度為n，碼字個(gè)數(shù)為對(duì)S進(jìn)行

等長(zhǎng)無(wú)差錯(cuò)編碼，得到碼集C是唯一可譯，必須滿足：

信源消息概率碼1碼2u1u2u3u41/21/41/81/80011101100011011唯一可譯不是唯一可譯必要非充分碼1，碼2K=4，D=2，n=2簡(jiǎn)單信源S的L次擴(kuò)展信源進(jìn)行等長(zhǎng)編碼，擴(kuò)展信源包含個(gè)消息，得到長(zhǎng)為n的唯一可譯碼，需滿足：這里K是信源符號(hào)集的元素個(gè)數(shù)，D是碼符號(hào)集，n是碼長(zhǎng)。對(duì)上式兩邊取對(duì)數(shù)并整理：信源序列中平均每個(gè)信源符號(hào)至少所需要的碼符號(hào)數(shù)（3-5）（3-6）[例]英文27個(gè)英文字符(字母+空格)進(jìn)行等長(zhǎng)二進(jìn)制編碼，即K=27，L=1，D=2，根據(jù)（3-6），為得到唯一可譯碼，應(yīng)滿足碼長(zhǎng)：實(shí)際碼長(zhǎng)取整數(shù)5每個(gè)英文字符需要5位二進(jìn)制碼，最大信息量5bit（等概條件）。實(shí)際中，英文字符出現(xiàn)概率不同，再考慮字符間關(guān)聯(lián)性（T+h,r，in+g）,已知東西多，得到信息少。收到5位二進(jìn)制數(shù)的信息量遠(yuǎn)小于5bit，傳輸效率低若對(duì)極少出現(xiàn)的字符不進(jìn)行編碼，可以降低平均碼長(zhǎng)，進(jìn)而提高傳輸率：會(huì)引起失真。但當(dāng)滿足一定條件，可以使失真趨于零定理3.1等長(zhǎng)編碼定理：設(shè)離散無(wú)記憶信源的熵為H(X),S的L維擴(kuò)展信源為，

對(duì)信源輸出的L長(zhǎng)序列進(jìn)行等長(zhǎng)編碼，碼字是長(zhǎng)度為n的D進(jìn)制字符串，若滿足：則當(dāng)可使譯碼差錯(cuò)無(wú)窮小量反之，若不可能實(shí)現(xiàn)無(wú)差錯(cuò)編碼比較定理3.1和（3-6）的下界H(X)是單符號(hào)信源的熵,根據(jù)極大離散熵定理，信源等概分布時(shí)熵值最大，最大值為logK，即H(X)≤logK.因此定理3.1給出了更緊的下界對(duì)n/L的要求更低。[例]英文27個(gè)英文字符(字母+空格)進(jìn)行等長(zhǎng)二進(jìn)制編碼，即K=27，L=1，D=2，根據(jù)（3-6），為得到唯一可譯碼，應(yīng)滿足碼長(zhǎng)：若根據(jù)定理3.1：編