信源編碼等長碼

主講：肖竹第三章

離散信源無失真編碼第三章

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

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

?0000?01101011010110101101u2

?0001?01101011010110101011…u10000

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

碼的定義

1.二元碼

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

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

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

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

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

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

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

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

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

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

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

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

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

碼D:0010110111

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

碼B:0111111

碼C:010110111

4、碼C是唯一可譯的,因為任一串有限長的碼字w,如100111011010只能被分割成10，0，111，0，110，10任何其他分割方法都會產(chǎn)生一些不屬于代碼W的碼字（如1，001，11，011，010）；

碼E:001011111

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

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

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

3.2等長碼及等長編碼定理

簡單信源S:信源符號集包含K個符號，碼符號集包含D個符號，碼字長度為n，碼字個數(shù)為對S進行

等長無差錯編碼，得到碼集C是唯一可譯，必須滿足：

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

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