信息論基礎(chǔ)理論與應(yīng)用第三版傅祖蕓講義課堂

1、第,5,章,無失真信源編碼定理,5.1,編碼器,5.2,等長碼,5.6,變長信源編碼定理,5.4,等長信源編碼定理,5.5,變長碼,信息通過信道傳輸?shù)叫潘薜倪^程。要做到既不失真又快速地,通信，需要解決兩個問題,信源編碼,在不失真或允許一定失真條件下，提高,信息傳輸率,信道編碼,在信道受到干擾的情況下，增加信號的,抗干擾能力,同時又,使得信息傳輸率最大,最佳編碼,一般來說,抗干擾能,與,信息傳輸率,二者相互矛盾。而編碼,定理理論上證明，至少存在某種,最佳,的編碼能夠解決上述矛盾,做到,既可靠又有效,地傳輸信息,信源編碼,信源雖然多種多樣，但無論是哪種類型的信源，信源符號,之間總存在相關(guān)性和分布的

2、不均勻性，使得信源存在冗余度,信源編碼的目的就是要減少冗余，提高編碼效率,引,言,研究方法,研究,信源編碼,時，將信道編碼與譯碼看成是,信道,的一部分,從而突出信源編碼,研究,信道編碼,時，將信源編碼與譯碼看成是,信源與信宿,的,一部分，從而突出信道編碼,1,2,q,S,S,S,S,5.1,編碼器,編碼器,對信源的符號按一定的數(shù)學規(guī)則進行的變換,它可以看作這樣一個系統(tǒng)，它的輸入端為原始信源,S,其符,號集為,而信道所能傳輸?shù)姆柤癁?1,2,r,X,x,x,x,編碼器功能,用符號集,X,中的元素，將原始信源的符,號,變換為相應(yīng)的碼字符號,編碼器輸出符號集為,碼或碼書,稱為,碼字,l,i,為碼字

3、,的碼元個數(shù)（碼字長度,碼,長,。碼字集合,C,稱為,碼,或,碼書,1,2,q,C,W,W,W,i,w,i,w,i,w,i,s,2,1,2,1,i,i,i,i,i,i,i,l,k,X,x,x,x,x,W,q,i,s,k,i,l,2,1,2,1,2,1,2,1,2,1,i,i,i,i,x,i,i,i,i,i,i,l,k,X,x,N,k,S,s,x,x,x,W,s,s,s,k,k,i,l,N,若要實現(xiàn)無失真編碼，這種映射應(yīng)是,一一對應(yīng)的可逆,映射,編碼的形式化描述,從,信源符號,到,碼符號,的一種映射,或,1,二元碼與,r,元碼,2,元碼,碼符號集,X=0,1,如果將信源通過二元信道傳輸，必,須將

4、信源編成二元碼，這是最常用的一種碼,r,元碼,碼符號集有,r,個符號的編碼,2,等長碼與變長碼,等長碼,一組碼中所有碼字的長度都相同,變長碼,一組碼中所有碼字的長度各不相同,碼的分類及定義,3,非奇異碼與奇異碼,非奇異碼,一組碼中所有碼字都不相同,奇異碼,一組碼中有相同的碼字,C,W,W,S,s,s,W,W,s,s,j,i,j,i,j,i,j,i,C,W,W,S,s,s,W,W,s,s,j,i,j,i,j,i,j,i,1,a,2,a,3,a,4,a,i,p,a,4,同價碼,同價碼,碼符號集,中每個碼符號所占的,傳輸時間,都相同,大多數(shù)情況,變長碼中每個碼字的傳輸時間就不一定相同,摩爾斯電報碼,

5、點,劃,所占傳輸時間不同,5,碼的,N,次擴展,若某碼,C,它把信源,S,中的符號,一一變換成碼,C,中的碼,字,則,碼,C,的,N,次擴展碼,是所有,N,個碼字組成的碼字序列,的集合,B,1,2,q,C,W,W,W,1,2,i,i,i,i,N,BB,W,W,W,i,w,1,2,r,X,x,x,x,i,s,S,擴展,2,1,2,1,2,1,2,1,N,i,i,i,i,i,i,i,i,i,i,i,i,i,q,i,W,W,W,B,s,s,s,x,x,x,W,s,N,N,i,l,碼,C,碼,B,擴展信源,擴展碼,N,次擴展,1,2,q,C,W,W,W,L,1,2,N,l,N,i,i,i,i,i,i,

6、i,B,W,W,W,S,W,C,v,v,L,N,次擴展,例,設(shè)信源,S,的概率空間為,若通過,個二元信道進行傳輸，須把信源符號變換成,0,1,符,號組成的碼符號序列,二元序列,采用如下二元碼,如下表所示,q=4,3,2,1,3,2,1,q,q,s,P,s,P,s,P,s,P,s,s,s,s,s,P,S,1,1,q,i,i,s,p,試求碼的二次擴展碼,信源,S,的,二次擴展信源,則,碼,的,二次擴展碼,為,4,4,16,3,1,3,2,1,2,1,1,1,2,s,s,s,s,s,s,s,s,S,6,唯一可譯碼,單義可譯碼,由碼構(gòu)成的任意一串有限長的,碼符號序列,只能被唯一的,譯成所對應(yīng)的,信源符

7、號序列,否則,就為非惟一可譯碼或非單義可譯碼,例,對于二元碼,當任意給定一串,碼字,序列,例如,10001101,只可唯一地劃分為,1,00,01,1,01,因此是,惟一可譯碼,而對另一個二元碼,當碼字序列為,01001,可劃分為,0,10,01,或,01,0,01,所以是,非惟一可譯的,1,1,0,1,0,0,C,2,0,1,0,0,1,C,唯一可譯碼的條件,1,不同的信源符號變換成不同的碼字,非奇異碼,2,任意有限長,的,信源序列,所對應(yīng)的,碼元序列,各不相同,即,碼的任意有限長,N,次擴展碼,都是,非奇異碼,Or,碼符號序列,的,反變換,也唯一的,擴展碼非奇異,原因,若要使某一碼為惟一可

8、譯碼，則對于任意有限長的,碼,符號序列,必須只能被,惟一地分割,成一個個的碼字，才能,實現(xiàn)唯一的譯碼,無失真的編碼的一般條件,1,碼字與信源符號之間一一對應(yīng),非奇異碼,2,碼符號序列,的,反變換,也唯一的,擴展碼非奇異,即,編碼必須是,唯一可譯碼,否則，就會引起譯碼的錯,誤與失真,等長碼是唯一可譯碼的條件,若等長碼是,非奇異碼,則它的任意有限長,N,次擴展,碼,一定也是非奇異碼,因此,等長非奇異碼字,一定是,唯一可譯碼,因為采用,固定長度劃分碼字序列,5.2,等長碼,1,若對,每個信源符號,進行等長編碼，則必須滿足,其中,l,是碼長,r,是碼符號集的碼元數(shù),q,信源符號數(shù),l,q,r,2,若對

9、,信源的,N,次擴展信源,進行編碼，必須滿足,N,l,q,r,lo,g,lo,g,l,q,N,r,表示平均,每個信源符號,所需的,碼符號個數(shù),l,N,即,為了使等長碼為非奇異碼（唯一可譯碼），那么,例證：根據(jù)依賴關(guān)系，信源符號平均所需碼符號數(shù)可減少,例,設(shè)信源,3,1,2,4,1,2,3,4,s,s,s,s,S,P,s,P,s,P,s,P,s,P,s,4,1,1,i,i,P,s,而其依賴關(guān)系為,0,1,4,3,3,4,2,1,1,2,i,j,s,s,P,s,s,P,s,s,P,s,s,P,s,s,P,其余,1,若不考慮符號間的依賴關(guān)系，可得每符號碼長,l,2,2,若考慮符號間的,二元依賴關(guān)系,

10、可作二次擴展信源進行,分析。根據(jù)條件概率僅有,4,項的概率不為零，可得擴展信源,的碼長,l=2,而每個信源符號的,平均碼長,為,l/N=1,2,3,4,4,3,1,2,2,1,2,1,2,2,1,3,4,4,3,s,s,s,s,s,s,s,s,S,P,s,s,P,s,s,P,s,s,P,s,s,P,s,1,i,j,ij,P,s,s,i,j,i,j,i,s,s,P,s,P,s,s,P,5.4,等長信源編碼定理,給出了等長信源編碼所需,碼長的極限值,定理,等長信源編碼定理,一熵為,H(S,的,離散無記憶信源,若對其,N,次擴展信源,進,行等長,r,元編碼，碼長為,l,對于任意,大于,0,只要滿足,

11、log,l,H,S,N,r,當,N,足夠大時，則可以實現(xiàn)幾乎無失真編碼，反之，若,2,log,l,H,S,N,r,則不可能實現(xiàn)無失真編碼，當,N,趨向于無窮大時，譯碼錯誤,率接近于,1,分析,定理中的條件式可寫成,l,o,g,l,r,N,H,S,左邊,長為,l,的,碼符號（碼字,所能載荷的,最大信息量,右邊,長為,N,的,信源符號序列,平均攜帶的信息量,因此，定理說明了：只要,碼字傳輸?shù)淖畲笮畔⒘?大于,信源序,列攜帶的信息量,則可以實現(xiàn)無失真編碼,編碼后信源的信息傳輸率,l,o,g,l,r,H,S,N,令,log,l,R,r,N,可見，只有,編碼后信息傳輸率,才能實現(xiàn)無失真編碼,S,H,R,

12、編碼后，平均每個信源,符號承載的信息量,S,H,R,最佳編碼效率,由定理知,H,S,H,S,R,H,S,1,H,S,log,H,S,H,S,l,R,r,N,編碼效率,移項后,0,1,l,o,g,l,r,H,S,N,當信源符號自信息量的方差,和,確定時，只,要,N,足夠大，就可以實現(xiàn)允許錯誤概率,2,2,2,2,1,S,H,s,I,D,s,I,D,N,i,i,E,P,0,i,s,I,D,0,這時要求序列長度滿足,任意一正數(shù),信源序列長度,N,一般情況下，在已知信源熵的情況下，信源序列長度,N,的選擇，與,最佳編碼效率,和,允許錯誤概率,有關(guān)?？梢宰C明,1,H,S,1,3,4,l,o,g,4,l,

13、o,g,0,8,1,1,4,4,3,H,S,2,2,2,2,2,2,1,1,3,4,l,o,g,l,o,g,4,l,o,g,0,8,1,1,0,4,7,1,5,4,4,3,i,i,i,i,D,I,s,ppH,S,若采用,等長二元編碼,要求編碼效率,允許,錯誤率,0.96,5,1,0,則,7,4,1,3,1,0,N,例,設(shè)離散無記憶信源,1,2,3,1,4,4,s,s,S,P,s,811,0,log,S,H,N,l,S,H,r,N,l,R,1,唯一可譯變長碼,5.5,變長碼,優(yōu)勢,容易實現(xiàn)效率很高的編碼,變長碼也必須是,唯一可譯碼,才能實現(xiàn),無失真編碼,碼,1,是一個,奇異碼,故不是唯一可譯碼,

14、碼,2,也不是唯一可譯碼，因為收到一串序列，無法唯一譯出對應(yīng)的,原符號序列，如,01000,即可譯作,s4s3s1,也可譯作,s4s1s3,s1s2s3,或,s1s2s1s1,碼,2,本身不是奇異碼，但從有限長的碼符號序列是奇異碼,如果把碼,2,的,2,次擴展碼寫出，則會發(fā)現(xiàn),S1S3,的,擴展碼字,為,000,S3S1,的,擴展碼字,也為,000,所以，當出現(xiàn),000,序列時候，不能唯一地確定信源符號,碼,3,和,碼,4,都是唯一可譯的，但碼,3,和碼,4,也不太一樣,碼,4,稱作,逗點碼,只要收到,1,就可以立即作出,譯碼,而,碼,3,不同，當收到一個或幾個碼時，必須參考后面的,碼才能作出

15、判斷,1,000,1,00,10,即時碼,接收端收到一個完整的碼字后，就能,立即進行譯碼,無須參考后面的碼字,就可以作出唯一判斷,譯碼,對于,非即時碼,接收端收到一個完整的碼字后，還,需等后續(xù)碼元接收后才能判斷是否可以唯一譯碼,非延長碼（前綴條件碼,若碼,C,中，沒有任何完整的碼字是其他碼字的前綴,即設(shè),是碼,C,中的任意碼字，而它不是其他,碼字,jm,的前綴，則此碼為,非延長碼,或,前綴條件碼,2,1,im,i,i,i,x,x,x,W,2,1,kj,km,k,k,k,x,x,x,x,W,顯然：即時碼,等價于,前綴條件碼（非延長碼,碼,3,s1,的碼字是,s2,s3,s4,的碼字的,前,綴,詞

16、頭,s2,的碼字是,s3,s4,的碼字的前綴,s3,的碼字是,s4,的碼字的前綴,當譯碼時，接受到一個完整碼字后,不能馬上譯碼,還需考察,后續(xù)碼元,的情況才能進行正確譯碼,如,1,000,1,00,10,可譯碼為,s4s3,因此，碼,3,不是即時碼；但確是唯一,可譯碼,碼,4,碼本中的任何一個碼字,都不是其他碼字的前綴,當譯碼時，接受到一個完整碼,字后，不需要等待后續(xù)碼元的,情況即可正確譯碼,如,1,0001,001,0,可譯碼為,s1 s4 s3,因此，碼,4,是即時碼，也是唯,一可譯碼,因此，對于碼,C,若其為唯一可譯碼，則必為,非奇異碼,若其為即時碼，則必是,唯一可譯碼,反之，作為唯一可

17、,譯碼，則不一定是,即時碼,所有的碼,非奇異碼,唯一可譯碼,即時碼（非延長碼,2,即時碼（非延時碼）的樹圖構(gòu)造法,對于給定碼字集合,C,可用,碼樹,來描述,同時，樹圖法可構(gòu)造,即時碼,0,1,0,0,1,1,1,1,01,001,0001,碼,4,的樹圖描述,在每個節(jié)點上都有,r,個分枝的樹稱為,整樹（滿樹,否則稱為,非整（滿）樹,0 1,0 1,0 1,0 1 0 1 0 1 0 1,0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1,等長碼二元碼樹,整樹,樹根,碼字的起點,樹枝數(shù),碼符號數(shù),終端節(jié)點,碼字,階數(shù),碼長,中間節(jié)點,0 1 2,0 1 2 0 1 2 0 1 2,0

18、 1 2,0 1 2,三元碼樹,整樹,滿樹,變長碼,0,1,0,0,1,1,1,1,01,001,0001,非滿樹,非即時碼,的樹圖,中間節(jié)點安排為碼字,1,樹圖,中間節(jié)點,不作為碼字,2,一旦某節(jié)點作為碼字，則,不再繼續(xù)進行分枝,這樣可保證每個碼字不同,且滿足,前綴條件碼,的條件,一般編碼方法,選擇相應(yīng)節(jié)點作為碼字,不同的路徑上的分支，對應(yīng)了,相應(yīng)的碼元符號，則可得到所編碼字,1,0,0,0,1,10,100,1000,構(gòu)造,即時碼,編碼舉例,即時碼，編碼方式不同,都為即時碼，但編碼方式不唯一,編碼舉例（多元即時碼,譯碼方法,因為每一碼元對應(yīng)于一個的樹圖分枝路徑，則,即時碼的,樹圖,可以用來

19、,譯碼,譯碼器系統(tǒng)對一串符號序列譯碼過程,1,首先從,樹根,出發(fā)，根據(jù)接收的,第一個碼元符號,來選擇應(yīng)走,的第一條路徑,2,若沿著所選路徑走到,某中間節(jié)點,再根據(jù)接收的,第二個碼,元符號,來選擇第二條路經(jīng),3,若又走到中間節(jié)點，再依次繼續(xù)選擇路徑，直到,終端節(jié)點,為止。這時，可根據(jù)所經(jīng)歷的,枝路,判斷出所接收的碼字,4,重新,返回樹根,再作下一個接收碼字的判斷,這樣，便可將接收到的一串碼符號序列譯成信源符號序列,3,克拉夫特,Kraft,不等式,定理,對于碼符號為,的任意,r,元,即時,碼,若所對應(yīng)的碼長,則必定滿足,反之，若碼長滿足上式，則一定存在這樣的,即時碼,1,2,q,l,l,l,1,

20、1,i,q,l,i,r,可以證明，對于,唯一可譯碼,也須滿足,Kraft,不等式,1,2,q,C,W,W,W,1,2,r,X,x,x,x,這說明，其他唯一可譯碼并不比即時碼占優(yōu),而即時碼很容易用,樹圖法構(gòu)造,所以在討論唯一可譯碼,時,只需要討論即時碼就可以了,定理,若存在一個碼長為,的,唯一可譯碼,則一定,存在一個同樣長度的,即時碼,1,2,q,l,l,l,L,例,設(shè)二進制碼樹中,S=(s,1,s,2,s,3,s,4,L,1,1, L,2,2,L,3,2,L,4,3,應(yīng)用,Kraft,不等式,得,不存在滿足這種,L,i,的唯一可譯碼,如果將各碼字長度改成,L,1,1,L,2,2,L,3,3,L

21、,4,3,則,1,8,9,2,2,2,2,2,3,2,2,1,4,1,i,K,i,1,2,2,2,2,2,3,3,2,1,4,1,i,K,i,存在滿足這種,L,i,唯一可譯碼,0,0,0,1,1,0,10,110,11,碼樹,111,0,0,0,1,1,0,10,110,設(shè)信源,編碼后的碼字為,1,2,q,W,W,W,碼長為,1,2,q,l,l,l,碼的,平均長度（平均碼長,為,1,q,i,i,i,L,P,S,l,5.6,變長信源編碼定理,碼符號,信源符號,3,2,1,3,2,1,q,q,s,P,s,P,s,P,s,P,s,s,s,s,x,P,X,碼的平均長度,信息傳輸率（碼率,平均每個,碼元

22、攜帶的信息量,即,編碼后信道的信息傳輸,率,比特,碼符號,L,S,H,R,若信道傳輸一個碼符號平均需要,t,秒鐘，則編碼后信道的,每秒傳輸?shù)男畔⒘繛?比特,秒,L,t,S,H,t,R,R,t,由此可見,平均碼長越短，信息傳輸效率越高,緊致碼（最佳碼,對于某一信源和某一個碼符號集合，若有一個,唯一可譯,碼,它的平均碼長小于其他唯一可譯碼的長度,無失真信源編碼的,基本問題,就是尋找,緊致碼,定理,若對一熵為,H(S,的離散無記憶信源,S,進行,r,元編碼，則,總是可以找到一種無失真編碼方法構(gòu)成,唯一可譯碼,使其,平,均碼長,滿足,1,log,1,log,S,H,L,S,H,r,S,H,L,r,S,

23、H,r,r,即,說明,下界,平均碼長不能小于極限,H(s)/logr,否則唯一可譯碼不存在,上界,給出了平均碼長的上界。但并不是說大于這個上界就不能,構(gòu)成唯一可譯碼。而是說,在上界范圍內(nèi)，可找到唯一可譯碼,證明,1,下界證明,L,r,S,H,log,0,log,r,L,S,H,詹森不等式,lo,g,lo,g,i,i,i,l,i,i,i,i,i,i,i,s,P,p,s,P,r,x,x,p,x,p,i,令,因總可找到一種唯一可譯碼，其碼長,滿足,Craft,不等式,所以,則證得,由,Craft,不等式，此等式成立的充要條件,即,2,1,log,log,log,q,i,s,P,r,s,P,l,i,r

24、,i,i,可見，只有當能夠選擇每個碼長滿足上述等式時候，平均碼,長才能夠,達到,這個下界值,由于,l,i,必須為正整數(shù)，所以,也必須,為,正整數(shù),那么，當該等式成立時，每個,信源符號的概率分布,必,須呈現(xiàn)如下形式,log,i,r,i,s,P,l,1,為正整數(shù),i,i,i,r,s,P,如果這個條件滿足，則只要選擇,q,i,l,i,i,2,1,根據(jù)這些碼長，按照,樹圖法,構(gòu)造出一種,唯一可譯碼,所得,的碼一定是,緊致碼,2,上界證明,只需證明存在,一種唯一可譯碼滿足,r,S,H,L,log,1,即可。令,2,1,log,q,i,s,P,i,r,i,則，選取每個碼字的長度的原則是,2,1,log,q

25、,i,s,P,l,i,i,r,i,i,i,不為正整數(shù),為正整數(shù),1,i,i,i,l,的最小整數(shù),代表不小于,為天花板函數(shù),x,x,顯然知,2,1,log,log,q,i,r,s,P,l,r,s,P,l,i,l,i,i,i,i,i,i,即,即,即為,Craft,不等式；因此,用這樣選擇的碼長,滿足,Craft,不等式,故,可構(gòu)造唯一可譯碼,但不一定是緊致碼,兩邊對,i,求和，則有,1,1,i,q,l,i,r,由于,右邊的不等式兩邊進行如下處理,1,i,i,l,1,log,i,r,i,s,P,l,1,log,log,1,1,r,s,P,s,P,l,s,P,i,q,i,i,i,q,i,i,1,1,l

26、og,S,H,r,S,H,L,r,平均碼長,因此，平均碼長,小于上界,的,唯一可譯碼存在,兩邊乘以,P,s,i,后，求和,另外由于,無失真變長信源編碼定理（香農(nóng)第一定理,離散無記憶信源,S,的,N,次擴展信源,其熵,為,且編碼器碼元符號集為,對信源,進,行編碼，總可以找到一種編碼方法，構(gòu)成唯一可譯碼，使信源,S,中,每個信源符號,s,i,所需要的平均碼長,滿足,N,H,S,N,S,當,則得,N,N,q,N,S,2,1,r,x,x,x,X,2,1,1,log,1,log,S,H,N,N,L,S,H,r,S,H,N,N,L,r,S,H,r,N,r,N,即,對應(yīng)的碼字長度,為符號,的平均碼長,為擴展

27、信源中每個符號,其中,i,i,i,i,q,i,i,N,r,N,N,N,P,L,S,H,N,L,lim,1,N,L,L,N,證明,設(shè)離散無記憶信源,X,的數(shù)學模型,1,1,2,1,2,1,q,i,i,q,q,p,p,p,p,s,s,s,s,p,S,2,1,2,1,2,1,N,N,N,i,i,i,i,q,q,i,N,s,s,s,p,p,p,p,S,1,1,N,q,i,i,P,2,1,2,1,q,i,s,P,s,P,s,P,P,N,i,i,i,i,N,次擴展,由于無記憶性，有,而,1,S,NH,S,H,S,H,L,S,H,r,N,r,N,r,N,N,r,N,S,H,N,L,S,H,S,NH,L,S,

28、NH,r,N,r,r,N,r,1,1,即,r,S,H,S,H,N,L,r,N,N,log,lim,顯,然,由前述定理，有,定理含義,要做到無失真信源編碼，變換每個信源符號平均所,需最少的,r,元碼元數(shù)是信源的熵值,若編碼的平均碼長小于信源的熵，則唯一可譯碼不,存在，在譯碼時必然帶來失真或差錯,同時，通過對擴展信源進行變長編碼，當擴展長度,N,足夠大時，平均碼長可達到此極限值,信源的熵是無失真信源壓縮的極限值,r,H,H,S,S,S,H,N,N,L,N,r,N,S,S,S,H,N,L,r,N,S,S,S,H,S,S,S,H,L,S,S,S,H,r,N,N,N,N,N,N,N,N,r,N,N,r,

29、log,1,lim,lim,且,1,log,log,則,1,2,1,2,1,2,1,2,1,2,1,定理推廣,可以推廣到,平穩(wěn)有記憶信源,和,馬爾科夫信源,如果將定理中的下式改寫,r,S,H,N,N,L,r,S,H,N,log,1,log,log,log,S,H,S,H,N,r,r,N,L,S,H,N,r,N,L,R,N,log,為編碼后平均每個信源符號所能承載的最大信息量，即變長,編碼,后信源,的,信息傳輸率（編碼信息率,這樣，香農(nóng)第一定理也可表述為,若,R=H(S,就存在唯一可譯變長編碼；若,R H(S,唯一,可譯邊長碼不存在，不能實現(xiàn)無失真德信源編碼,log,l,R,r,N,則定義,等長編碼,從,信道角度,看，編碼后,信道的信息傳輸率,碼符號,比特,L,S,H,R,由此可見，此時信道的信息傳輸率等于,無噪無損信道,的信道容,量,C,信息傳輸率最高,因此，無失真信源編碼的實質(zhì)是,對離散信源進行適當編碼,使變換后新的碼符號信源（信道的輸入信源）盡可能等概率分布,以使新信源的每個碼符號平均所含的信息量達到最大，從而使信道,的信息傳輸率,R,達到信道容量,C,實現(xiàn)信源與信