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

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

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

3、,的碼元個(gè)數(shù)（碼字長(zhǎng)度,碼,長(zhǎng),。碼字集合,C,稱為,碼,或,碼書(shū),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,若要實(shí)現(xiàn)無(wú)失真編碼，這種映射應(yīng)是,一一對(duì)應(yīng)的可逆,映射,編碼的形式化描述,從,信源符號(hào),到,碼符號(hào),的一種映射,或,1,二元碼與,r,元碼,2,元碼,碼符號(hào)集,X=0,1,如果將信源通過(guò)二元信道傳輸，必,須將

4、信源編成二元碼，這是最常用的一種碼,r,元碼,碼符號(hào)集有,r,個(gè)符號(hào)的編碼,2,等長(zhǎng)碼與變長(zhǎng)碼,等長(zhǎng)碼,一組碼中所有碼字的長(zhǎng)度都相同,變長(zhǎng)碼,一組碼中所有碼字的長(zhǎng)度各不相同,碼的分類(lèi)及定義,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,同價(jià)碼,同價(jià)碼,碼符號(hào)集,中每個(gè)碼符號(hào)所占的,傳輸時(shí)間,都相同,大多數(shù)情況,變長(zhǎng)碼中每個(gè)碼字的傳輸時(shí)間就不一定相同,摩爾斯電報(bào)碼,

5、點(diǎn),劃,所占傳輸時(shí)間不同,5,碼的,N,次擴(kuò)展,若某碼,C,它把信源,S,中的符號(hào),一一變換成碼,C,中的碼,字,則,碼,C,的,N,次擴(kuò)展碼,是所有,N,個(gè)碼字組成的碼字序列,的集合,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,擴(kuò)展,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,擴(kuò)展信源,擴(kuò)展碼,N,次擴(kuò)展,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,次擴(kuò)展,例,設(shè)信源,S,的概率空間為,若通過(guò),個(gè)二元信道進(jìn)行傳輸，須把信源符號(hào)變換成,0,1,符,號(hào)組成的碼符號(hào)序列,二元序列,采用如下二元碼,如下表所示,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,試求碼的二次擴(kuò)展碼,信源,S,的,二次擴(kuò)展信源,則,碼,的,二次擴(kuò)展碼,為,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)成的任意一串有限長(zhǎng)的,碼符號(hào)序列,只能被唯一的,譯成所對(duì)應(yīng)的,信源符

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

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

9、,信源的,N,次擴(kuò)展信源,進(jìn)行編碼，必須滿足,N,l,q,r,lo,g,lo,g,l,q,N,r,表示平均,每個(gè)信源符號(hào),所需的,碼符號(hào)個(gè)數(shù),l,N,即,為了使等長(zhǎng)碼為非奇異碼（唯一可譯碼），那么,例證：根據(jù)依賴關(guān)系，信源符號(hào)平均所需碼符號(hào)數(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,若不考慮符號(hào)間的依賴關(guān)系，可得每符號(hào)碼長(zhǎng),l,2,2,若考慮符號(hào)間的,二元依賴關(guān)系,

10、可作二次擴(kuò)展信源進(jìn)行,分析。根據(jù)條件概率僅有,4,項(xiàng)的概率不為零，可得擴(kuò)展信源,的碼長(zhǎng),l=2,而每個(gè)信源符號(hào)的,平均碼長(zhǎng),為,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,等長(zhǎng)信源編碼定理,給出了等長(zhǎng)信源編碼所需,碼長(zhǎng)的極限值,定理,等長(zhǎng)信源編碼定理,一熵為,H(S,的,離散無(wú)記憶信源,若對(duì)其,N,次擴(kuò)展信源,進(jìn),行等長(zhǎng),r,元編碼，碼長(zhǎng)為,l,對(duì)于任意,大于,0,只要滿足,

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

12、編碼后，平均每個(gè)信源,符號(hào)承載的信息量,S,H,R,最佳編碼效率,由定理知,H,S,H,S,R,H,S,1,H,S,log,H,S,H,S,l,R,r,N,編碼效率,移項(xiàng)后,0,1,l,o,g,l,r,H,S,N,當(dāng)信源符號(hào)自信息量的方差,和,確定時(shí)，只,要,N,足夠大，就可以實(shí)現(xiàn)允許錯(cuò)誤概率,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í)要求序列長(zhǎng)度滿足,任意一正數(shù),信源序列長(zhǎng)度,N,一般情況下，在已知信源熵的情況下，信源序列長(zhǎng)度,N,的選擇，與,最佳編碼效率,和,允許錯(cuò)誤概率,有關(guān)。可以證明,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,若采用,等長(zhǎng)二元編碼,要求編碼效率,允許,錯(cuò)誤率,0.96,5,1,0,則,7,4,1,3,1,0,N,例,設(shè)離散無(wú)記憶信源,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,唯一可譯變長(zhǎng)碼,5.5,變長(zhǎng)碼,優(yōu)勢(shì),容易實(shí)現(xiàn)效率很高的編碼,變長(zhǎng)碼也必須是,唯一可譯碼,才能實(shí)現(xiàn),無(wú)失真編碼,碼,1,是一個(gè),奇異碼,故不是唯一可譯碼,

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

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

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

17、,譯碼，則不一定是,即時(shí)碼,所有的碼,非奇異碼,唯一可譯碼,即時(shí)碼（非延長(zhǎng)碼,2,即時(shí)碼（非延時(shí)碼）的樹(shù)圖構(gòu)造法,對(duì)于給定碼字集合,C,可用,碼樹(shù),來(lái)描述,同時(shí)，樹(shù)圖法可構(gòu)造,即時(shí)碼,0,1,0,0,1,1,1,1,01,001,0001,碼,4,的樹(shù)圖描述,在每個(gè)節(jié)點(diǎn)上都有,r,個(gè)分枝的樹(shù)稱為,整樹(shù)（滿樹(shù),否則稱為,非整（滿）樹(shù),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,等長(zhǎng)碼二元碼樹(shù),整樹(shù),樹(shù)根,碼字的起點(diǎn),樹(shù)枝數(shù),碼符號(hào)數(shù),終端節(jié)點(diǎn),碼字,階數(shù),碼長(zhǎng),中間節(jié)點(diǎn),0 1 2,0 1 2 0 1 2 0 1 2,0

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

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

20、1,i,q,l,i,r,可以證明，對(duì)于,唯一可譯碼,也須滿足,Kraft,不等式,1,2,q,C,W,W,W,1,2,r,X,x,x,x,這說(shuō)明，其他唯一可譯碼并不比即時(shí)碼占優(yōu),而即時(shí)碼很容易用,樹(shù)圖法構(gòu)造,所以在討論唯一可譯碼,時(shí),只需要討論即時(shí)碼就可以了,定理,若存在一個(gè)碼長(zhǎng)為,的,唯一可譯碼,則一定,存在一個(gè)同樣長(zhǎng)度的,即時(shí)碼,1,2,q,l,l,l,L,例,設(shè)二進(jìn)制碼樹(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,的唯一可譯碼,如果將各碼字長(zhǎng)度改成,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,碼樹(shù),111,0,0,0,1,1,0,10,110,設(shè)信源,編碼后的碼字為,1,2,q,W,W,W,碼長(zhǎng)為,1,2,q,l,l,l,碼的,平均長(zhǎng)度（平均碼長(zhǎng),為,1,q,i,i,i,L,P,S,l,5.6,變長(zhǎng)信源編碼定理,碼符號(hào),信源符號(hào),3,2,1,3,2,1,q,q,s,P,s,P,s,P,s,P,s,s,s,s,x,P,X,碼的平均長(zhǎng)度,信息傳輸率（碼率,平均每個(gè),碼元

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

23、H,r,r,即,說(shuō)明,下界,平均碼長(zhǎng)不能小于極限,H(s)/logr,否則唯一可譯碼不存在,上界,給出了平均碼長(zhǎng)的上界。但并不是說(shuō)大于這個(gè)上界就不能,構(gòu)成唯一可譯碼。而是說(shuō),在上界范圍內(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,令,因總可找到一種唯一可譯碼，其碼長(zhǎng),滿足,Craft,不等式,所以,則證得,由,Craft,不等式，此等式成立的充要條件,即,2,1,log,log,log,q,i,s,P,r,s,P,l,i,r

24、,i,i,可見(jiàn)，只有當(dāng)能夠選擇每個(gè)碼長(zhǎng)滿足上述等式時(shí)候，平均碼,長(zhǎng)才能夠,達(dá)到,這個(gè)下界值,由于,l,i,必須為正整數(shù)，所以,也必須,為,正整數(shù),那么，當(dāng)該等式成立時(shí)，每個(gè),信源符號(hào)的概率分布,必,須呈現(xiàn)如下形式,log,i,r,i,s,P,l,1,為正整數(shù),i,i,i,r,s,P,如果這個(gè)條件滿足，則只要選擇,q,i,l,i,i,2,1,根據(jù)這些碼長(zhǎng)，按照,樹(shù)圖法,構(gòu)造出一種,唯一可譯碼,所得,的碼一定是,緊致碼,2,上界證明,只需證明存在,一種唯一可譯碼滿足,r,S,H,L,log,1,即可。令,2,1,log,q,i,s,P,i,r,i,則，選取每個(gè)碼字的長(zhǎng)度的原則是,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,不等式；因此,用這樣選擇的碼長(zhǎng),滿足,Craft,不等式,故,可構(gòu)造唯一可譯碼,但不一定是緊致碼,兩邊對(duì),i,求和，則有,1,1,i,q,l,i,r,由于,右邊的不等式兩邊進(jìn)行如下處理,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,平均碼長(zhǎng),因此，平均碼長(zhǎng),小于上界,的,唯一可譯碼存在,兩邊乘以,P,s,i,后，求和,另外由于,無(wú)失真變長(zhǎng)信源編碼定理（香農(nóng)第一定理,離散無(wú)記憶信源,S,的,N,次擴(kuò)展信源,其熵,為,且編碼器碼元符號(hào)集為,對(duì)信源,進(jìn),行編碼，總可以找到一種編碼方法，構(gòu)成唯一可譯碼，使信源,S,中,每個(gè)信源符號(hào),s,i,所需要的平均碼長(zhǎng),滿足,N,H,S,N,S,當(dāng),則得,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,即,對(duì)應(yīng)的碼字長(zhǎng)度,為符號(hào),的平均碼長(zhǎng),為擴(kuò)展

27、信源中每個(gè)符號(hào),其中,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è)離散無(wú)記憶信源,X,的數(shù)學(xué)模型,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,次擴(kuò)展,由于無(wú)記憶性，有,而,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,顯,然,由前述定理，有,定理含義,要做到無(wú)失真信源編碼，變換每個(gè)信源符號(hào)平均所,需最少的,r,元碼元數(shù)是信源的熵值,若編碼的平均碼長(zhǎng)小于信源的熵，則唯一可譯碼不,存在，在譯碼時(shí)必然帶來(lái)失真或差錯(cuò),同時(shí)，通過(guò)對(duì)擴(kuò)展信源進(jìn)行變長(zhǎng)編碼，當(dāng)擴(kuò)展長(zhǎng)度,N,足夠大時(shí)，平均碼長(zhǎng)可達(dá)到此極限值,信源的熵是無(wú)失真信源壓縮的極限值,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)有記憶信源,和,馬爾科夫信源,如果將定理中的下式改寫(xiě),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,為編碼后平均每個(gè)信源符號(hào)所能承載的最大信息量，即變長(zhǎng),編碼,后信源,的,信息傳輸率（編碼信息率,這樣，香農(nóng)第一定理也可表述為,若,R=H(S,就存在唯一可譯變長(zhǎng)編碼；若,R H(S,唯一,可譯邊長(zhǎng)碼不存在，不能實(shí)現(xiàn)無(wú)失真德信源編碼,log,l,R,r,N,則定義,等長(zhǎng)編碼,從,信道角度,看，編碼后,信道的信息傳輸率,碼符號(hào),比特,L,S,H,R,由此可見(jiàn)，此時(shí)信道的信息傳輸率等于,無(wú)噪無(wú)損信道,的信道容,量,C,信息傳輸率最高,因此，無(wú)失真信源編碼的實(shí)質(zhì)是,對(duì)離散信源進(jìn)行適當(dāng)編碼,使變換后新的碼符號(hào)信源（信道的輸入信源）盡可能等概率分布,以使新信源的每個(gè)碼符號(hào)平均所含的信息量達(dá)到最大，從而使信道,的信息傳輸率,R,達(dá)到信道容量,C,實(shí)現(xiàn)信源與信