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

1、第第5 5章章 無失真信源編碼定理無失真信源編碼定理 5.1 5.1 編碼器編碼器5.2 5.2 等長碼等長碼5.6 5.6 變長信源編碼定理變長信源編碼定理5.4 5.4 等長信源編碼定理等長信源編碼定理5.5 5.5 變長碼變長碼 信息通過信道傳輸?shù)叫潘薜倪^程。要做到既不失真又快速信息通過信道傳輸?shù)叫潘薜倪^程。要做到既不失真又快速地通信，需要解決兩個(gè)問題：地通信，需要解決兩個(gè)問題：n信源編碼信源編碼: : 在不失真或允許一定失真條件下，提高在不失真或允許一定失真條件下，提高信息傳輸率信息傳輸率. .n信道編碼信道編碼: : 在信道受到干擾的情況下，增加信號的在信道受到干擾的情況下，增加信號

2、的抗干擾能力抗干擾能力，同時(shí)又，同時(shí)又使得信息傳輸率最大使得信息傳輸率最大. .n最佳編碼：最佳編碼： 一般來說，一般來說，抗干擾能抗干擾能與與信息傳輸率信息傳輸率二者相互矛盾。而編碼二者相互矛盾。而編碼定理理論上證明，至少存在某種定理理論上證明，至少存在某種最佳最佳的編碼能夠解決上述矛盾，的編碼能夠解決上述矛盾，做到做到既可靠又有效既可靠又有效地傳輸信息。地傳輸信息。n信源編碼：信源編碼： 信源雖然多種多樣，但無論是哪種類型的信源，信源符號信源雖然多種多樣，但無論是哪種類型的信源，信源符號之間總存在相關(guān)性和分布的不均勻性，使得信源存在冗余度。之間總存在相關(guān)性和分布的不均勻性，使得信源存在冗余

3、度。信源編碼的目的就是要減少冗余，提高編碼效率。信源編碼的目的就是要減少冗余，提高編碼效率。 引引 言言n研究方法研究方法研究研究信源編碼信源編碼時(shí)，將信道編碼與譯碼看成是時(shí)，將信道編碼與譯碼看成是信道信道的一部分，的一部分，從而突出信源編碼；從而突出信源編碼；研究研究信道編碼信道編碼時(shí)，將信源編碼與譯碼看成是時(shí)，將信源編碼與譯碼看成是信源與信宿信源與信宿的的一部分，從而突出信道編碼。一部分，從而突出信道編碼。12 ,.,qSS SS5.1 5.1 編碼器編碼器n編碼器：編碼器： 對信源的符號按一定的數(shù)學(xué)規(guī)則進(jìn)行的變換。對信源的符號按一定的數(shù)學(xué)規(guī)則進(jìn)行的變換。 它可以看作這樣一個(gè)系統(tǒng)，它的輸入

4、端為原始信源它可以看作這樣一個(gè)系統(tǒng)，它的輸入端為原始信源S S，其符，其符號集為號集為 而信道所能傳輸?shù)姆柤癁槎诺浪軅鬏數(shù)姆柤癁?12 ,.,rXx xx 編碼器功能：編碼器功能：用符號集用符號集X X中的元素，將原始信源的符中的元素，將原始信源的符號號 變換為相應(yīng)的碼字符號變換為相應(yīng)的碼字符號 ，編碼器輸出符號集為，編碼器輸出符號集為 ( (碼或碼書碼或碼書) 稱為稱為碼字碼字，l li i 為碼字為碼字 的碼元個(gè)數(shù)（碼字長度，的碼元個(gè)數(shù)（碼字長度，碼碼長長）。碼字集合）。碼字集合C C稱為稱為碼碼或或碼書碼書。 12:,.,qCW WWiwiwiwis),.2 , 1( ,),.(

5、),.,2 , 1(iiiiiiilkXxxxxWqiskil21 ),.2 , 1();,.2 , 1( ,),.().(2121iiiixiiiiiilkXxNkSsxxxWssskkilN 若要實(shí)現(xiàn)無失真編碼，這種映射應(yīng)是若要實(shí)現(xiàn)無失真編碼，這種映射應(yīng)是一一對應(yīng)的可逆一一對應(yīng)的可逆映射。映射。n編碼的形式化描述：編碼的形式化描述： 從從信源符號信源符號到到碼符號碼符號的一種映射的一種映射或：或：1 1、二元碼與二元碼與r r元碼元碼 2 2元碼元碼: : 碼符號集碼符號集X=0,1. X=0,1. 如果將信源通過二元信道傳輸，必如果將信源通過二元信道傳輸，必須將信源編成二元碼，這是最常用

6、的一種碼。須將信源編成二元碼，這是最常用的一種碼。 r r元碼元碼: : 碼符號集有碼符號集有r r個(gè)符號的編碼。個(gè)符號的編碼。2 2、等長碼與變長碼等長碼與變長碼 等長碼等長碼: : 一組碼中所有碼字的長度都相同。一組碼中所有碼字的長度都相同。 變長碼變長碼: : 一組碼中所有碼字的長度各不相同。一組碼中所有碼字的長度各不相同。n 碼的分類及定義碼的分類及定義信源符號信源符號si si符號出現(xiàn)概率符號出現(xiàn)概率p p(si)(si)編碼編碼1 1編碼編碼2 2s1s1p p(s1)(s1)00000 0s2s2p p (s2) (s2)01010101s3s3p p (s3) (s3)1010

7、001001s4s4p p (s4) (s4)11111011013 3、非奇異碼與奇異碼非奇異碼與奇異碼 非奇異碼非奇異碼: : 一組碼中所有碼字都不相同。一組碼中所有碼字都不相同。 奇異碼奇異碼: : 一組碼中有相同的碼字。一組碼中有相同的碼字。CWWSssWWssjijijiji,;CWWSssWWssjijijiji,;信源符號信源符號 編碼編碼1 1編碼編碼2 21/21/200000 01/41/401010 01/81/810101 11/81/8111110101a2a3a4a()ip a4 4、同價(jià)碼同價(jià)碼 同價(jià)碼同價(jià)碼: : 碼符號集碼符號集 中每個(gè)碼符號所占的中每個(gè)碼符號

8、所占的傳輸時(shí)間傳輸時(shí)間都相同都相同( (大多數(shù)情況大多數(shù)情況) )。 變長碼中每個(gè)碼字的傳輸時(shí)間就不一定相同。變長碼中每個(gè)碼字的傳輸時(shí)間就不一定相同。 （摩爾斯電報(bào)碼，（摩爾斯電報(bào)碼，點(diǎn)點(diǎn)- -劃劃 所占傳輸時(shí)間不同）所占傳輸時(shí)間不同）5 5、碼的碼的N N次擴(kuò)展次擴(kuò)展 若某碼若某碼 C C，它把信源，它把信源S S中的符號中的符號 一一變換成碼一一變換成碼C C中的碼中的碼字字 ，則，則碼碼C C的的N N次擴(kuò)展碼次擴(kuò)展碼是所有是所有N N個(gè)碼字組成的碼字序列個(gè)碼字組成的碼字序列的集合的集合B:B:12:,.,qCW WW12:(.)iiiiNB BWWWiw12 ,.,rXx xxisS擴(kuò)

9、展擴(kuò)展),.,2 , 1( ).().( ).(212121NiiiiiiiiiiiiiqiWWWBsssxxxWsNNil碼碼C C碼碼B B擴(kuò)展信源擴(kuò)展信源擴(kuò)展碼擴(kuò)展碼N N次擴(kuò)展次擴(kuò)展12,qCW WW 12(,), ,NlNiiiiiiiBW WWSWC N N次擴(kuò)展次擴(kuò)展 例例 設(shè)信源設(shè)信源S S的概率空間為：的概率空間為： 若通過若通過個(gè)二元信道進(jìn)行傳輸，須把信源符號變換成個(gè)二元信道進(jìn)行傳輸，須把信源符號變換成 0 0，1 1 符符號組成的碼符號序列號組成的碼符號序列( (二元序列二元序列) )。采用如下二元碼，。采用如下二元碼， 如下表所示如下表所示（q=4q=4）：）： )()

10、()()()(321321qqsPsPsPsPsssssPS1)(1qiisp信源符號信源符號s si i符號出現(xiàn)概率符號出現(xiàn)概率P(sP(si i) )碼碼s s1 1P(sP(s1 1) )0 0s s2 2P(sP(s2 2) )0101s s3 3P(sP(s3 3) )001001s s4 4P(sP(s4 4) )111111試求碼的二次擴(kuò)展碼。試求碼的二次擴(kuò)展碼。信信源源S S的的二次擴(kuò)展信源二次擴(kuò)展信源：則則碼碼的的二次擴(kuò)展碼二次擴(kuò)展碼為：為：,.,44163132121112ssssssssS信源信源符號符號碼字碼字信源信源符號符號碼字碼字信源信源符號符號碼字碼字 1 100

11、: W00: W1 1WW1 1=B=B1 1 5 5010:W010:W2 2WW1 1=B=B5 5： 2 2001:W001:W1 1WW2 2=B=B2 2： 3 30001:W0001:W1 1WW3 3=B=B3 3： 4 40111:W0111:W1 1WW4 4=B=B4 4： 1616111111:W111111:W4 4WW4 4=B=B16166 6、唯一可譯碼、唯一可譯碼( (單義可譯碼單義可譯碼） 由碼構(gòu)成的任意一串有限長的由碼構(gòu)成的任意一串有限長的碼符號序列碼符號序列只能被唯一的只能被唯一的譯成所對應(yīng)的譯成所對應(yīng)的信源符號序列信源符號序列。 否則否則, ,就為非惟一

12、可譯碼或非單義可譯碼。就為非惟一可譯碼或非單義可譯碼。 n例例：對于二元碼：對于二元碼 ，當(dāng)任意給定一串，當(dāng)任意給定一串碼字碼字序列序列，例如，例如1000110110001101只可唯一地劃分為只可唯一地劃分為1,00,01,1,011,00,01,1,01，因此是，因此是惟一可譯碼惟一可譯碼；n而對另一個(gè)二元碼而對另一個(gè)二元碼 ，當(dāng)碼字序列為，當(dāng)碼字序列為0100101001可劃分為可劃分為0,10,010,10,01或或01,0,0101,0,01，所以是，所以是非惟一可譯的非惟一可譯的。11,01,00C 20,10,01C n唯一可譯碼的條件唯一可譯碼的條件 1 1）不同的信源符號變

13、換成不同的碼字）不同的信源符號變換成不同的碼字( (非奇異碼非奇異碼) )； 2 2）任意有限長任意有限長的的信源序列信源序列所對應(yīng)的所對應(yīng)的碼元序列碼元序列各不相同各不相同. . 即即: : 碼的任意有限長碼的任意有限長N N次擴(kuò)展碼次擴(kuò)展碼都是都是非奇異碼非奇異碼。Or: 碼符號序列碼符號序列的的反變換反變換也唯一的（也唯一的（擴(kuò)展碼非奇異擴(kuò)展碼非奇異） 原因：原因： 若要使某一碼為惟一可譯碼，則對于任意有限長的若要使某一碼為惟一可譯碼，則對于任意有限長的碼碼符號序列符號序列，必須只能被，必須只能被惟一地分割惟一地分割成一個(gè)個(gè)的碼字，才成一個(gè)個(gè)的碼字，才能實(shí)現(xiàn)唯一的譯碼。能實(shí)現(xiàn)唯一的譯碼。

14、n無失真的編碼的一般條件無失真的編碼的一般條件 1 1）碼字與信源符號之間一一對應(yīng)（）碼字與信源符號之間一一對應(yīng)（非奇異碼非奇異碼）；）； 2 2）碼符號序列碼符號序列的的反變換反變換也唯一的（也唯一的（擴(kuò)展碼非奇異擴(kuò)展碼非奇異）。）。即即：編碼必須是：編碼必須是唯一可譯碼唯一可譯碼。否則，就會(huì)引起譯碼的錯(cuò)。否則，就會(huì)引起譯碼的錯(cuò)誤與失真。誤與失真。等長碼是唯一可譯碼的條件等長碼是唯一可譯碼的條件 若等長碼是若等長碼是非奇異碼非奇異碼，則它的任意有限長，則它的任意有限長N N次擴(kuò)展次擴(kuò)展碼碼一定也是非奇異碼。一定也是非奇異碼。 因此，因此，等長非奇異碼字等長非奇異碼字一定是一定是唯一可譯碼唯一

15、可譯碼, ,因?yàn)椴捎靡驗(yàn)椴捎霉潭ㄩL度劃分碼字序列固定長度劃分碼字序列. .5.2 5.2 等長碼等長碼 1 1）若對）若對每個(gè)信源符號每個(gè)信源符號進(jìn)行等長編碼，則必須滿足進(jìn)行等長編碼，則必須滿足: : 其中其中: l : l是碼長，是碼長，r r是碼符號集的碼元數(shù)，是碼符號集的碼元數(shù)，q q信源符號數(shù)。信源符號數(shù)。lqr 2 2）若對）若對信源的信源的N N次擴(kuò)展信源次擴(kuò)展信源進(jìn)行編碼，必須滿足進(jìn)行編碼，必須滿足: :NlqrlogloglqNr表示平均表示平均每個(gè)信源符號每個(gè)信源符號所需的所需的碼符號個(gè)數(shù)。碼符號個(gè)數(shù)。lN即即 為了使等長碼為非奇異碼（唯一可譯碼），那么為了使等長碼為非奇異碼

16、（唯一可譯碼），那么: :例證：根據(jù)依賴關(guān)系，信源符號平均所需碼符號數(shù)可減少。例證：根據(jù)依賴關(guān)系，信源符號平均所需碼符號數(shù)可減少。例例 設(shè)信源設(shè)信源31241234( )( )()( )()ssssSP sP sP sP sP s41( )1iiP s而其依賴關(guān)系為：而其依賴關(guān)系為：0)|(, 1)|()|()|()|(43342112ijssPssPssPssPssP 其余其余1 1）若不考慮符號間的依賴關(guān)系，可得每符號碼長）若不考慮符號間的依賴關(guān)系，可得每符號碼長l l2 2；2 2）若考慮符號間的）若考慮符號間的二元依賴關(guān)系二元依賴關(guān)系，可作二次擴(kuò)展信源進(jìn)行，可作二次擴(kuò)展信源進(jìn)行分析。根

17、據(jù)條件概率僅有分析。根據(jù)條件概率僅有4 4項(xiàng)的概率不為零，可得擴(kuò)展信源項(xiàng)的概率不為零，可得擴(kuò)展信源的碼長的碼長 l=2l=2，而每個(gè)信源符號的，而每個(gè)信源符號的平均碼長平均碼長為為 l/N=1l/N=1 。23 44 31 22 121 22 13 44 3()()()()()s ss ss ss sSP s sP s sP s sP s sP s()1ijijP s s)|()()(ijijissPsPssP5.4 5.4 等長信源編碼定理等長信源編碼定理給出了等長信源編碼所需給出了等長信源編碼所需碼長的極限值碼長的極限值。定理定理 等長信源編碼定理等長信源編碼定理 一熵為一熵為H(S)H(

18、S)的的離散無記憶信源離散無記憶信源，若對其，若對其N N次擴(kuò)展信源次擴(kuò)展信源進(jìn)行等長進(jìn)行等長 r r 元編碼，碼長為元編碼，碼長為l l，對于任意，對于任意 大于大于0 0，只要滿，只要滿足足( )loglH SNr當(dāng)當(dāng)N N足夠大時(shí)，則可以實(shí)現(xiàn)幾乎無失真編碼，反之，若：足夠大時(shí)，則可以實(shí)現(xiàn)幾乎無失真編碼，反之，若：( )2loglH SNr則不可能實(shí)現(xiàn)無失真編碼，當(dāng)則不可能實(shí)現(xiàn)無失真編碼，當(dāng)N N趨向于無窮大時(shí)，譯碼錯(cuò)誤趨向于無窮大時(shí)，譯碼錯(cuò)誤率接近于率接近于1 1。分析分析：定理中的條件式可寫成：定理中的條件式可寫成log( )lrNH S 左邊左邊: : 長為長為 l l 的的碼符號（

19、碼字）碼符號（碼字）所能載荷的所能載荷的最大信息量最大信息量； 右邊右邊: : 長為長為N N的的信源符號序列信源符號序列平均攜帶的信息量。平均攜帶的信息量。 因此，定理說明了：只要因此，定理說明了：只要碼字傳輸?shù)淖畲笮畔⒘看a字傳輸?shù)淖畲笮畔⒘看笥诖笥谛旁葱蛐旁葱蛄袛y帶的信息量列攜帶的信息量，則可以實(shí)現(xiàn)無失真編碼，則可以實(shí)現(xiàn)無失真編碼 。 n編碼后信源的信息傳輸率編碼后信源的信息傳輸率 log( )lrH SN令：令：loglRrN可見，只有可見，只有編碼后信息傳輸率編碼后信息傳輸率 ，才能實(shí)現(xiàn)無失真編碼。才能實(shí)現(xiàn)無失真編碼。)(SHR ( (編碼后，平均每個(gè)信源編碼后，平均每個(gè)信源符號承載的

20、信息量符號承載的信息量) )(SHR 最佳編碼效率：最佳編碼效率： 由定理知，由定理知，( )( )( )H SH SRH S1( )H S( )( )logH SH SlRrNn編碼效率編碼效率移項(xiàng)后，移項(xiàng)后，)0( 1 log( )lrH SN當(dāng)信源符號自信息量的方差當(dāng)信源符號自信息量的方差 和和 確定時(shí)，只確定時(shí)，只要要N N足夠大，就可以實(shí)現(xiàn)允許錯(cuò)誤概率：足夠大，就可以實(shí)現(xiàn)允許錯(cuò)誤概率：2222)1 ()()()(SHsIDsIDNiiEP0)(isID0這時(shí)要求序列長度滿足：這時(shí)要求序列長度滿足：（任意一正數(shù)）（任意一正數(shù)）n信源序列長度信源序列長度N N 一般情況下，在已知信源熵的

21、情況下，信源序列長度一般情況下，在已知信源熵的情況下，信源序列長度N N的選擇，與的選擇，與最佳編碼效率最佳編碼效率和和允許錯(cuò)誤概率允許錯(cuò)誤概率有關(guān)?？梢宰C明：有關(guān)?？梢宰C明：1( )H S134()log 4log0.811443HS2222221134 ( )(log ) ( )(log4)(log )0.8110.4715443iiiiDI sppH S若采用若采用等長二元編碼等長二元編碼，要求編碼效率，要求編碼效率 ，允許，允許錯(cuò)誤率錯(cuò)誤率0.96510則：則：74.1310N 例例：設(shè)離散無記憶信源：設(shè)離散無記憶信源：1231( )44ssSP s811. 0)()(logSHNlS

22、HrNlR1 1、唯一可譯變長碼、唯一可譯變長碼信源符號信源符號出現(xiàn)概率出現(xiàn)概率碼碼1 1碼碼2 2碼碼3 3碼碼4 4s1s1s2s2s3s3s4s41/21/21/41/41/81/81/81/80 01111000011110 01010000001011 11010100100100010001 10101001001000100015.5 5.5 變長碼變長碼優(yōu)勢優(yōu)勢：容易實(shí)現(xiàn)效率很高的編碼。：容易實(shí)現(xiàn)效率很高的編碼。變長碼也必須是變長碼也必須是唯一可譯碼唯一可譯碼，才能實(shí)現(xiàn)，才能實(shí)現(xiàn)無失真編碼無失真編碼。碼碼1 1是一個(gè)是一個(gè)奇異碼奇異碼，故不是唯一可譯碼；，故不是唯一可譯碼；碼碼

23、2 2也不是唯一可譯碼，因?yàn)槭盏揭淮蛄?，無法唯一譯出對應(yīng)的也不是唯一可譯碼，因?yàn)槭盏揭淮蛄?，無法唯一譯出對應(yīng)的原符號序列，如原符號序列，如0100001000，即可譯作，即可譯作s4s3s1,s4s3s1,也可譯作也可譯作s4s1s3,s1s2s3s4s1s3,s1s2s3或或s1s2s1s1s1s2s1s1；碼碼2 2本身不是奇異碼，但從有限長的碼符號序列是奇異碼。本身不是奇異碼，但從有限長的碼符號序列是奇異碼。 如果把碼如果把碼2 2的的2 2次擴(kuò)展碼寫出，則會(huì)發(fā)現(xiàn)：次擴(kuò)展碼寫出，則會(huì)發(fā)現(xiàn)： S1S3S1S3的的擴(kuò)展碼字?jǐn)U展碼字為：為：000 000 ； S3S1S3S1的的擴(kuò)展碼字?jǐn)U

24、展碼字也為：也為：000000 所以，當(dāng)出現(xiàn)所以，當(dāng)出現(xiàn)000000序列時(shí)候，不能唯一地確定信源符號。序列時(shí)候，不能唯一地確定信源符號。碼碼3 3和和碼碼4 4都是唯一可譯的，但碼都是唯一可譯的，但碼3 3和碼和碼4 4也不太一樣。也不太一樣。 碼碼4 4稱作稱作逗點(diǎn)碼逗點(diǎn)碼，只要收到，只要收到1 1，就可以立即作出，就可以立即作出譯碼譯碼； 而而碼碼3 3不同，當(dāng)收到一個(gè)或幾個(gè)碼時(shí)，必須參考后面的不同，當(dāng)收到一個(gè)或幾個(gè)碼時(shí)，必須參考后面的碼才能作出判斷。碼才能作出判斷。 1 10000001 100001010 n即時(shí)碼即時(shí)碼 接收端收到一個(gè)完整的碼字后，就能接收端收到一個(gè)完整的碼字后，就能

25、立即進(jìn)行譯碼立即進(jìn)行譯碼，無須參考后面的碼字無須參考后面的碼字就可以作出唯一判斷就可以作出唯一判斷（譯碼）（譯碼）。n對于對于非即時(shí)碼，非即時(shí)碼，接收端收到一個(gè)完整的碼字后，還接收端收到一個(gè)完整的碼字后，還需等后續(xù)碼元接收后才能判斷是否可以唯一譯碼。需等后續(xù)碼元接收后才能判斷是否可以唯一譯碼。 n非延長碼（前綴條件碼）非延長碼（前綴條件碼） 若碼若碼C C中，沒有任何完整的碼字是其他碼字的前綴，中，沒有任何完整的碼字是其他碼字的前綴，即設(shè)即設(shè) 是碼是碼C C中的任意碼字，而它不是其他中的任意碼字，而它不是其他碼字碼字 （jmjm）的前綴，則此碼為的前綴，則此碼為非延長碼非延長碼（或（或前綴條件

26、碼前綴條件碼）。）。).(21imiiixxxW ).(21kjkmkkkxxxxW ！顯然：即時(shí)碼！顯然：即時(shí)碼等價(jià)于等價(jià)于前綴條件碼（非延長碼）前綴條件碼（非延長碼）。碼碼3 3：s1s1的碼字是的碼字是s2,s3,s4s2,s3,s4的碼字的的碼字的前前綴綴（詞頭）；（詞頭）；s2s2的碼字是的碼字是s3,s4s3,s4的碼字的前綴；的碼字的前綴；s3s3的碼字是的碼字是s4s4的碼字的前綴；的碼字的前綴；當(dāng)譯碼時(shí)，接受到一個(gè)完整碼字后，當(dāng)譯碼時(shí)，接受到一個(gè)完整碼字后，不能馬上譯碼不能馬上譯碼，還需考察，還需考察后續(xù)碼元后續(xù)碼元的情況才能進(jìn)行正確譯碼；的情況才能進(jìn)行正確譯碼；如：如：1

27、10000001 100001010 可譯碼為：可譯碼為： s4s3 s4s3 ？因此，碼因此，碼3 3不是即時(shí)碼；但確是唯一不是即時(shí)碼；但確是唯一可譯碼?？勺g碼。信源符號信源符號碼碼3 3s1s1s2s2s3s3s4s41 1101010010010001000信源符號信源符號碼碼4 4s1s1s2s2s3s3s4s41 1010100100100010001碼碼4 4：碼本中的任何一個(gè)碼字：碼本中的任何一個(gè)碼字都不是其他碼字的前綴。都不是其他碼字的前綴。當(dāng)譯碼時(shí)，接受到一個(gè)完整當(dāng)譯碼時(shí)，接受到一個(gè)完整碼字后，不需要等待后續(xù)碼碼字后，不需要等待后續(xù)碼元的情況即可正確譯碼；元的情況即可正確譯碼

28、；如：如：1 1000100010010010 0 可譯碼為：可譯碼為：s1 s4 s3 s1 s4 s3 因此，碼因此，碼4 4 是即時(shí)碼，也是唯是即時(shí)碼，也是唯一可譯碼。一可譯碼。因此，對于碼因此，對于碼C C：若其為唯一可譯碼，則必為若其為唯一可譯碼，則必為非奇異碼非奇異碼；若其為即時(shí)碼，則必是若其為即時(shí)碼，則必是唯一可譯碼唯一可譯碼；反之，作為唯一可；反之，作為唯一可譯碼，則不一定是譯碼，則不一定是即時(shí)碼即時(shí)碼。 所有的碼所有的碼非奇異碼非奇異碼唯一可譯碼唯一可譯碼即時(shí)碼（非延長碼）即時(shí)碼（非延長碼）信源符號信源符號碼碼4 4s1s1s2s2s3s3s4s41 101010010010

29、00100012 2、即時(shí)碼（非延時(shí)碼）的樹圖構(gòu)造法、即時(shí)碼（非延時(shí)碼）的樹圖構(gòu)造法 對于給定碼字集合對于給定碼字集合C C，可用，可用碼樹碼樹來描述。來描述。 同時(shí)，樹圖法可構(gòu)造同時(shí)，樹圖法可構(gòu)造即時(shí)碼。即時(shí)碼。01001111010010001碼碼4 4的樹圖描述的樹圖描述 在每個(gè)節(jié)點(diǎn)上都有在每個(gè)節(jié)點(diǎn)上都有r r個(gè)分枝的樹稱為個(gè)分枝的樹稱為整樹（滿樹），整樹（滿樹），否則稱為否則稱為非整（滿）樹。非整（滿）樹。 0 10 1 0 10 1 0 10 1 0 1 0 1 0 1 0 10 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 10 1 0 1

30、 0 1 0 1 0 1 0 1 0 1 0 1等長碼二元碼樹（等長碼二元碼樹（整樹整樹）樹根樹根碼字的起點(diǎn)碼字的起點(diǎn)樹枝數(shù)樹枝數(shù)碼符號數(shù)碼符號數(shù)終端節(jié)點(diǎn)終端節(jié)點(diǎn)碼字碼字階數(shù)階數(shù)碼長碼長中間節(jié)點(diǎn)中間節(jié)點(diǎn) 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 20 1 20 1 20 1 20 1 2三元碼樹三元碼樹（整樹）（整樹）滿樹滿樹變長碼變長碼01001111010010001非滿樹非滿樹非即時(shí)碼非即時(shí)碼的樹圖的樹圖中間節(jié)點(diǎn)安排為碼字中間節(jié)點(diǎn)安排為碼字1. 1.樹圖樹圖中間節(jié)點(diǎn)中間節(jié)點(diǎn)不作為碼字；不作為碼字；2. 2.一旦某節(jié)點(diǎn)作為碼字，則一旦某節(jié)點(diǎn)

31、作為碼字，則不再繼續(xù)進(jìn)行分枝不再繼續(xù)進(jìn)行分枝。 這樣可保證每個(gè)碼字不同，這樣可保證每個(gè)碼字不同，且滿足且滿足前綴條件碼前綴條件碼的條件。的條件。一般編碼方法一般編碼方法 選擇相應(yīng)節(jié)點(diǎn)作為碼字：選擇相應(yīng)節(jié)點(diǎn)作為碼字：不同的路徑上的分支，對應(yīng)了不同的路徑上的分支，對應(yīng)了相應(yīng)的碼元符號，則可得到所編碼字。相應(yīng)的碼元符號，則可得到所編碼字。10001101001000構(gòu)造構(gòu)造即時(shí)碼即時(shí)碼編碼舉例編碼舉例（即時(shí)碼，編碼方式不同）（即時(shí)碼，編碼方式不同）都為即時(shí)碼，但編碼方式不唯一都為即時(shí)碼，但編碼方式不唯一編碼舉例（多元即時(shí)碼）編碼舉例（多元即時(shí)碼）譯碼方法譯碼方法 因?yàn)槊恳淮a元對應(yīng)于一個(gè)的樹圖分枝路徑

32、，則因?yàn)槊恳淮a元對應(yīng)于一個(gè)的樹圖分枝路徑，則即時(shí)碼的即時(shí)碼的樹圖樹圖可以用來可以用來譯碼譯碼。譯碼器系統(tǒng)對一串符號序列譯碼過程：。譯碼器系統(tǒng)對一串符號序列譯碼過程：1 1）首先從）首先從樹根樹根出發(fā)，根據(jù)接收的出發(fā)，根據(jù)接收的第一個(gè)碼元符號第一個(gè)碼元符號來選擇應(yīng)走來選擇應(yīng)走的第一條路徑；的第一條路徑；2 2）若沿著所選路徑走到）若沿著所選路徑走到某中間節(jié)點(diǎn)某中間節(jié)點(diǎn)，再根據(jù)接收的，再根據(jù)接收的第二個(gè)碼第二個(gè)碼元符號元符號來選擇第二條路經(jīng)；來選擇第二條路經(jīng)；3 3）若又走到中間節(jié)點(diǎn)，再依次繼續(xù)選擇路徑，直到）若又走到中間節(jié)點(diǎn)，再依次繼續(xù)選擇路徑，直到終端節(jié)點(diǎn)終端節(jié)點(diǎn)為止。這時(shí)，可根據(jù)所經(jīng)歷的為止

33、。這時(shí)，可根據(jù)所經(jīng)歷的枝路枝路，判斷出所接收的碼字。，判斷出所接收的碼字。4 4）重新）重新返回樹根，返回樹根，再作下一個(gè)接收碼字的判斷。再作下一個(gè)接收碼字的判斷。 這樣，便可將接收到的一串碼符號序列譯成信源符號序列。這樣，便可將接收到的一串碼符號序列譯成信源符號序列。3 3、克拉夫特（、克拉夫特（KraftKraft）不等式）不等式定理定理 對于碼符號為對于碼符號為 的任意的任意r r元元即時(shí)即時(shí)碼碼 ，若所對應(yīng)的碼長，若所對應(yīng)的碼長 ，則必定滿足：則必定滿足：反之，若碼長滿足上式，則一定存在這樣的反之，若碼長滿足上式，則一定存在這樣的即時(shí)碼即時(shí)碼 。12, ,.,ql ll11iqlir

34、* *可以證明，對于可以證明，對于唯一可譯碼唯一可譯碼也須滿足也須滿足KraftKraft不等式。不等式。12:,.,qCW WW12 ,., rXx xx 這說明，其他唯一可譯碼并不比即時(shí)碼占優(yōu)。這說明，其他唯一可譯碼并不比即時(shí)碼占優(yōu)。 而即時(shí)碼很容易用而即時(shí)碼很容易用樹圖法構(gòu)造樹圖法構(gòu)造，所以在討論唯一可譯碼，所以在討論唯一可譯碼時(shí)，時(shí)，只需要討論即時(shí)碼就可以了。只需要討論即時(shí)碼就可以了。定理定理 若存在一個(gè)碼長為若存在一個(gè)碼長為 的的唯一可譯碼唯一可譯碼，則一，則一定存在一個(gè)同樣長度的定存在一個(gè)同樣長度的即時(shí)碼即時(shí)碼。12,qllln例例：設(shè)二進(jìn)制碼樹中設(shè)二進(jìn)制碼樹中S=(sS=(s1

35、1 , s , s2 2 , s, s3 3 , s , s4 4), L), L1 1=1, =1, L L2 2=2,L=2,L3 3=2,L=2,L4 4=3,=3,應(yīng)用應(yīng)用KraftKraft不等式不等式, ,得：得： 不存在滿足這種不存在滿足這種L Li i的唯一可譯碼的唯一可譯碼 n如果將各碼字長度改成如果將各碼字長度改成L L1 1=1,L=1,L2 2=2,L=2,L3 3=3,L=3,L4 4=3,=3,則則18922222322141 iKi122222332141iKi存在滿足這種存在滿足這種L Li i唯一可譯碼唯一可譯碼 000110 010101101101111碼

36、樹碼樹111111000110 01010110110設(shè)信源設(shè)信源編碼后的碼字為：編碼后的碼字為：12,.,qW WW碼長為：碼長為：12,.,ql ll碼的碼的平均長度（平均碼長）平均長度（平均碼長）為：為：1()qiiiLP S l5.6 5.6 變長信源編碼定理變長信源編碼定理（碼符號（碼符號/ /信源符號）信源符號）)(.)()()(.)(321321qqsPsPsPsPssssxPXn碼的平均長度碼的平均長度n信息傳輸率（碼率）：信息傳輸率（碼率）： 平均每個(gè)平均每個(gè)碼元攜帶的信息量碼元攜帶的信息量，即，即編碼后信道的信息傳輸編碼后信道的信息傳輸率率：（比特（比特/ /碼符號）碼符號

37、）LSHR)( 若信道傳輸一個(gè)碼符號平均需要若信道傳輸一個(gè)碼符號平均需要t t秒鐘，則編碼后信道的秒鐘，則編碼后信道的每秒傳輸?shù)男畔⒘繛椋好棵雮鬏數(shù)男畔⒘繛椋海ū忍兀ū忍? /秒）秒）LtSHtRRt)(/由此可見：由此可見： 平均碼長越短，信息傳輸效率越高。平均碼長越短，信息傳輸效率越高。n緊致碼（最佳碼）緊致碼（最佳碼） 對于某一信源和某一個(gè)碼符號集合，若有一個(gè)對于某一信源和某一個(gè)碼符號集合，若有一個(gè)唯一可譯唯一可譯碼，碼，它的平均碼長小于其他唯一可譯碼的長度。它的平均碼長小于其他唯一可譯碼的長度。 無失真信源編碼的無失真信源編碼的基本問題基本問題就是尋找就是尋找緊致碼緊致碼。定理定理 若

38、對一熵為若對一熵為H(S)H(S)的離散無記憶信源的離散無記憶信源 S S 進(jìn)行進(jìn)行r r 元編碼，則元編碼，則總是可以找到一種無失真編碼方法構(gòu)成總是可以找到一種無失真編碼方法構(gòu)成唯一可譯碼唯一可譯碼，使其，使其平平均碼長均碼長滿足：滿足： )(1)(,log)(1log)(SHLSHrSHLrSHrr即說明：說明： 下界下界：平均碼長不能小于極限：平均碼長不能小于極限H(s)/logr,H(s)/logr,否則唯一可譯碼不存在。否則唯一可譯碼不存在。 上界上界：給出了平均碼長的上界。但并不是說大于這個(gè)上界就不能：給出了平均碼長的上界。但并不是說大于這個(gè)上界就不能構(gòu)成唯一可譯碼。而是說構(gòu)成唯一

39、可譯碼。而是說在上界范圍內(nèi)，可找到唯一可譯碼在上界范圍內(nèi)，可找到唯一可譯碼。證明：證明： 1. 1.下界證明：下界證明：LrSHlog)(0log)(rLSH詹森不等式詹森不等式)(,)(,log)log(iiiliiiiiiisPpsPrxxpxpi令因總可找到一種唯一可譯碼，其碼長因總可找到一種唯一可譯碼，其碼長滿足滿足CraftCraft不等式不等式，所以，所以則證得：則證得：由由CraftCraft不等式，此等式成立的充要條件：不等式，此等式成立的充要條件：即：即：),.,2 , 1()(loglog)(logqisPrsPlirii可見，只有當(dāng)能夠選擇每個(gè)碼長滿足上述等式時(shí)候，平均碼

40、可見，只有當(dāng)能夠選擇每個(gè)碼長滿足上述等式時(shí)候，平均碼長才能夠長才能夠達(dá)到達(dá)到這個(gè)下界值。這個(gè)下界值。 由于由于l li i 必須為正整數(shù)，所以必須為正整數(shù)，所以 也必須也必須為為正整數(shù)正整數(shù)。 那么，當(dāng)該等式成立時(shí)，每個(gè)那么，當(dāng)該等式成立時(shí)，每個(gè)信源符號的概率分布信源符號的概率分布必必須呈現(xiàn)如下形式：須呈現(xiàn)如下形式：)(logirisPl)(/1)(為正整數(shù)iiirsP如果這個(gè)條件滿足，則只要選擇：如果這個(gè)條件滿足，則只要選擇：）（qilii,.,2 , 1根據(jù)這些碼長，按照根據(jù)這些碼長，按照樹圖法樹圖法構(gòu)造出一種構(gòu)造出一種唯一可譯碼唯一可譯碼，所得，所得的碼一定是的碼一定是緊致碼緊致碼。2.

41、 2.上界證明：上界證明：只需證明存在只需證明存在一種唯一可譯碼滿足一種唯一可譯碼滿足rSHLlog)(1即可。令即可。令),.,2 , 1()(logqisPiri則，選取每個(gè)碼字的長度的原則是：則，選取每個(gè)碼字的長度的原則是：),.,2 , 1(,)(logqisPliiriii不為正整數(shù)為正整數(shù)；，1iiil 的最小整數(shù)代表不小于為天花板函數(shù)，xx顯然知顯然知),.,2 , 1( ,)(log)(logqirsPlrsPliliiiiii即即即即，即為即為CraftCraft不等式；因此，不等式；因此，用這樣選擇的碼長用這樣選擇的碼長滿足滿足CraftCraft不等式不等式，故故可構(gòu)造唯

42、一可譯碼可構(gòu)造唯一可譯碼。但不一定是緊致碼。但不一定是緊致碼。兩邊對兩邊對i i求和，則有：求和，則有：11iqlir由于由于右邊的不等式兩邊進(jìn)行如下處理：右邊的不等式兩邊進(jìn)行如下處理：1iil1)(logirisPl1log)(log)()(11rsPsPlsPiqiiiqii1)(1log)(SHrSHLr平均碼長平均碼長因此，平均碼長因此，平均碼長小于上界小于上界的的唯一可譯碼存在唯一可譯碼存在。兩邊乘以兩邊乘以P(P(s si i) )后，求和。后，求和。另外由于另外由于無失真變長信源編碼定理（香農(nóng)第一定理）無失真變長信源編碼定理（香農(nóng)第一定理） 離散無記憶信源離散無記憶信源S S的的

43、N N次擴(kuò)展信源次擴(kuò)展信源 ，其熵，其熵為為 ，且編碼器碼元符號集為，且編碼器碼元符號集為 . . 對信源對信源 進(jìn)進(jìn)行編碼，總可以找到一種編碼方法，構(gòu)成唯一可譯碼，使信源行編碼，總可以找到一種編碼方法，構(gòu)成唯一可譯碼，使信源S S中中每個(gè)信源符號每個(gè)信源符號s si i所需要的平均碼長所需要的平均碼長 滿足滿足 ()NH SNS當(dāng)當(dāng) 則得：則得：N NqNS,.,21rxxxX,.,21)(1)(,log)(1log)(SHNNLSHrSHNNLrSHrNrN即對應(yīng)的碼字長度。對應(yīng)的碼字長度。為符號為符號的平均碼長；的平均碼長；為擴(kuò)展信源中每個(gè)符號為擴(kuò)展信源中每個(gè)符號，其中，其中，iiiiq

44、iiNrNNNPLSHNL.)()(lim1NLLN/證明證明：設(shè)離散無記憶信源：設(shè)離散無記憶信源X X的數(shù)學(xué)模型的數(shù)學(xué)模型1.)(12121qiiqqppppsssspS).(,)(.)()(.)(212121NNNiiiiqqiNsssppppS1()1NqiiP),.2 , 1( ,)().()()(21qisPsPsPPNiiiiN N次擴(kuò)展次擴(kuò)展由于無記憶性，有：由于無記憶性，有：)()(而, 1)()(SNHSHSHLSHrNrNrNNrNSHNLSHSNHLSNHrNrrNr/1)()(1)()(即：rSHSHNLrNNlog)()(lim 顯然：由前述定理，有：由前述定理，有：

45、定理含義：定理含義： 要做到無失真信源編碼，變換每個(gè)信源符號平均所要做到無失真信源編碼，變換每個(gè)信源符號平均所需最少的需最少的r r元碼元數(shù)是信源的熵值。元碼元數(shù)是信源的熵值。 若編碼的平均碼長小于信源的熵，則唯一可譯碼不若編碼的平均碼長小于信源的熵，則唯一可譯碼不存在，在譯碼時(shí)必然帶來失真或差錯(cuò)。存在，在譯碼時(shí)必然帶來失真或差錯(cuò)。 同時(shí)，通過對擴(kuò)展信源進(jìn)行變長編碼，當(dāng)擴(kuò)展長度同時(shí)，通過對擴(kuò)展信源進(jìn)行變長編碼，當(dāng)擴(kuò)展長度N N足夠大時(shí)，平均碼長可達(dá)到此極限值。足夠大時(shí)，平均碼長可達(dá)到此極限值。 信源的熵是無失真信源壓縮的極限值。信源的熵是無失真信源壓縮的極限值。rHHSSSHNNLNrNSSS

46、HNLrNSSSHSSSHLSSSHrNNNNNNNNrNNrlog)()().(1limlim 且：/1log).(log).(則：1).().(2121212121定理推廣：定理推廣： 可以推廣到可以推廣到平穩(wěn)有記憶信源平穩(wěn)有記憶信源和和馬爾科夫信源馬爾科夫信源： 如果將定理中的下式改寫：如果將定理中的下式改寫：rSHNNLrSHNlog)(1log)()()(loglog)(SHSHNrrNLSHNrNLRNlog為編碼后平均每個(gè)信源符號所能承載的最大信息量，即變長為編碼后平均每個(gè)信源符號所能承載的最大信息量，即變長編碼編碼后信源后信源的的信息傳輸率（編碼信息率）信息傳輸率（編碼信息率）

47、。 這樣，香農(nóng)第一定理也可表述為：這樣，香農(nóng)第一定理也可表述為： 若若R=H(S), R=H(S), 就存在唯一可譯變長編碼；若就存在唯一可譯變長編碼；若R H(S),R H(S),唯一唯一可譯邊長碼不存在，不能實(shí)現(xiàn)無失真德信源編碼?？勺g邊長碼不存在，不能實(shí)現(xiàn)無失真德信源編碼。loglRrN則定義：則定義：等長編碼等長編碼 從從信道角度信道角度看，編碼后看，編碼后信道的信息傳輸率信道的信息傳輸率：)/(/ )(碼符號比特LSHR 由此可見，此時(shí)信道的信息傳輸率等于由此可見，此時(shí)信道的信息傳輸率等于無噪無損信道無噪無損信道的信道容的信道容量量C C，信息傳輸率最高。，信息傳輸率最高。 因此，無失真信源編碼的實(shí)質(zhì)是：因此，無失真信源編碼的實(shí)質(zhì)是：對離散信源進(jìn)行適當(dāng)編碼，對離散信源進(jìn)行適當(dāng)編碼，使變換后新的碼符號信源（信道的輸入信源）盡可能等概率分布，使變換后新的碼符號信源（信道的輸入信源）盡可能等概率分布，以使新信源的每個(gè)碼符號平均所含的信息量達(dá)到最大，從而使信道以使新信源的每個(gè)碼符號平均所含的信息量達(dá)到最大，從而使信道的信息傳輸率的信息傳輸率R R達(dá)到信道容量達(dá)到信道容量C C，實(shí)現(xiàn)信源與信道的統(tǒng)計(jì)匹配。，實(shí)現(xiàn)信源與信道的統(tǒng)計(jì)匹配。 所以，無失真信源編碼實(shí)質(zhì)上就是所以，無失真信源編碼實(shí)質(zhì)上就是無噪信道編碼問題。無噪信道編碼問題。rSHNLLNlog/ )(/ 而而rLSHRlo