1、普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著1第第5章信源編碼章信源編碼 編碼分為信源編碼和信道編碼，其中信源編碼分為信源編碼和信道編碼，其中信源編碼又分為編碼又分為無失真和限失真無失真和限失真。一般稱一般稱u無失真信源編碼定理無失真信源編碼定理為第一極限定理；為第一極限定理；u信道編碼定理信道編碼定理（包括離散和連續信道）稱為第（包括離散和連續信道）稱為第 二極限定理；二極限定理；u限失真信源編碼定理限失真信源編碼定理稱為第三極限定理。稱為第三極限定理。 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著2第第5章信源編碼章信源編碼由于信源符號之間存在分布由于信源符

2、號之間存在分布不均勻和相關不均勻和相關性性，使得信源存在，使得信源存在冗余度冗余度，信源編碼的主，信源編碼的主要任務就是減少冗余，提高編碼效率。要任務就是減少冗余，提高編碼效率。 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著3第第5章信源編碼章信源編碼信源編碼的基本途徑有兩個：信源編碼的基本途徑有兩個：n使序列中的各個符號盡可能地互相獨立，使序列中的各個符號盡可能地互相獨立，即解除相關性；即解除相關性；n使編碼中各個符號出現的概率盡可能地使編碼中各個符號出現的概率盡可能地相等，即概率均勻化。相等，即概率均勻化。 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著4第第

3、5章信源編碼章信源編碼信源編碼的基礎是信息論中的兩個編碼定理：信源編碼的基礎是信息論中的兩個編碼定理：n無失真編碼定理無失真編碼定理n限失真編碼定理限失真編碼定理 無失真編碼無失真編碼只適用于離散信源只適用于離散信源 對于連續信源，只能在失真受限制的情況下進對于連續信源，只能在失真受限制的情況下進行行限失真編碼限失真編碼 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著5第第5章信源編碼章信源編碼本章討論本章討論離散信源編碼離散信源編碼，首先從，首先從無失真編無失真編碼定理碼定理出發，重點討論以出發，重點討論以香農碼香農碼、費諾碼費諾碼和和霍夫曼碼霍夫曼碼為代表的最佳無失真碼。然后

4、為代表的最佳無失真碼。然后介紹了介紹了限失真編碼定理限失真編碼定理。最后簡單介紹了。最后簡單介紹了一些其它常用的信源編碼方法。一些其它常用的信源編碼方法。 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著65.1 編碼的定義編碼的定義信源信源編碼器編碼器信道信道碼表碼表圖圖5-1 信源編碼器示意圖信源編碼器示意圖普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著75.1 編碼的定義編碼的定義信源編碼信源編碼是指信源輸出符號經信源編碼器是指信源輸出符號經信源編碼器編碼后轉換成另外的壓縮符號編碼后轉換成另外的壓縮符號無失真信源編碼無失真信源編碼：可精確無失真地復制信：可精確無

5、失真地復制信源輸出地消息源輸出地消息普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著85.1 編碼的定義編碼的定義將信源消息分成若干組，即符號序列將信源消息分成若干組，即符號序列xi， xi(xi1xi2xilxiL)， xil A=a1，a2，ai，an每個符號序列每個符號序列xi依照固定碼表映射成一個碼字依照固定碼表映射成一個碼字yi， yi(yi1yi2yilyiL)， yil B=b1，b2，bi，bm這樣的碼稱為這樣的碼稱為分組碼分組碼，有時也叫塊碼。只有，有時也叫塊碼。只有分組碼才有對分組碼才有對應的碼表應的碼表，而非分組碼中則不存在碼表。，而非分組碼中則不存在碼表。

6、普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著95.1 編碼的定義編碼的定義如圖如圖5-1所示，如果信源輸出符號序列長度所示，如果信源輸出符號序列長度L1，信源符號集信源符號集A(a1，a2，an)信源概率空間為信源概率空間為 )()()(2121nnapapapaaaPX若將信源若將信源X通過二元信道傳輸，就必須把信源符通過二元信道傳輸，就必須把信源符號號ai變換成由變換成由0，1符號組成的碼符號序列，這個符號組成的碼符號序列，這個過程就是信源編碼過程就是信源編碼 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著105.1 編碼的定義編碼的定義碼可分為兩類：碼可分為

7、兩類：一、固定長度的碼，碼中所有碼字的長度一、固定長度的碼，碼中所有碼字的長度 都相同，如表都相同，如表5-1中的碼中的碼1就是就是定長碼定長碼二、可變長度碼，碼中的碼字長短不一，二、可變長度碼，碼中的碼字長短不一，如表中碼如表中碼2就是就是變長碼變長碼。 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著115.1 編碼的定義編碼的定義不同的碼符號序列，如表不同的碼符號序列，如表5-1所示。所示。 表表5-1 變長碼與定長碼變長碼與定長碼信源信源符號符號ai信源符號出信源符號出現概率現概率p(ai)碼表碼表碼碼1碼碼2a1p(a1)000a2p(a2)0101a3p(a3)1000

8、1a4p(a4)11111普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著125.1 編碼的定義編碼的定義（1）奇異碼和非奇異碼）奇異碼和非奇異碼 若信源符號和碼字是若信源符號和碼字是一一對應一一對應的，則該的，則該碼為碼為非奇異碼非奇異碼。反之為奇異碼。反之為奇異碼。 如表如表5-2中的碼中的碼1是奇異碼，碼是奇異碼，碼2是非奇異是非奇異碼。碼。 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著135.1 編碼的定義編碼的定義表表5-2 碼的不同屬性碼的不同屬性信源符號信源符號ai符號出現概率符號出現概率p(ai)碼碼1碼碼2碼碼3碼碼4a11/20011a21/41

9、1101001a31/80000100001a41/8110110000001普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著145.1 編碼的定義編碼的定義（2）唯一可譯碼唯一可譯碼 任意有限長的碼元序列，只能被唯一地任意有限長的碼元序列，只能被唯一地分割成一個個的碼字，便稱為唯一可譯分割成一個個的碼字，便稱為唯一可譯碼碼 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著155.1 編碼的定義編碼的定義唯一可譯碼中又分為唯一可譯碼中又分為非即時碼非即時碼和和即時碼即時碼：如果接收端收到一個完整的碼字后，不能如果接收端收到一個完整的碼字后，不能立即譯碼，還需等下一個碼字

10、開始接收后立即譯碼，還需等下一個碼字開始接收后才能判斷是否可以譯碼，這樣的碼叫做才能判斷是否可以譯碼，這樣的碼叫做非非即時碼。即時碼。普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著165.1 編碼的定義編碼的定義即時碼即時碼：只要收到符號就表示該碼字已完：只要收到符號就表示該碼字已完整，可以立即譯碼。整，可以立即譯碼。即時碼又稱為即時碼又稱為非延長碼非延長碼，任意一個碼字都，任意一個碼字都不是其它碼字的前綴部分，有時叫做不是其它碼字的前綴部分，有時叫做異前異前綴碼綴碼。 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著175.1 編碼的定義編碼的定義碼碼奇異碼奇異碼非

11、分組碼非分組碼分組碼分組碼非奇異碼非奇異碼非唯一可譯碼非唯一可譯碼非即時碼非即時碼即時碼即時碼(非延長碼非延長碼)唯一可譯碼唯一可譯碼普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著185.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 0 1二進制碼樹二進制碼樹普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著195.1 編碼的定義編碼的定義 0 1 2 0 1 2 0 1 2 0 1 20 1 20 1 2三進制碼樹三進

12、制碼樹普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著205.1 編碼的定義編碼的定義唯一可譯碼唯一可譯碼存在存在的充分和必要條件的充分和必要條件 各碼字的長度各碼字的長度Ki 應符合應符合克勞夫特不等式克勞夫特不等式： 11niKim普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著215.1 編碼的定義編碼的定義例例：設二進制碼樹中設二進制碼樹中X (a1， a2 ， a3 ， a4 )，K11，K22，K32，K43，應用上述判斷定理：應用上述判斷定理： 18922222322141iKi因此不存在滿足這種因此不存在滿足這種Ki的唯一可譯碼的唯一可譯碼。 普通高等教

13、育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著225.1 編碼的定義編碼的定義a1=1 0 1 0 1 0 1a2=01a3=011a4=0001，01，001，000 惟一可譯碼；惟一可譯碼；1，01，101，000 不是惟一可譯碼；不是惟一可譯碼；均滿足克勞夫特不等式均滿足克勞夫特不等式122222332141iKi普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著235.1 編碼的定義編碼的定義克勞夫特不等式克勞夫特不等式只是用來說明唯一可譯碼只是用來說明唯一可譯碼是否是否存存在，并不能作為唯一可譯碼的判據。在，并不能作為唯一可譯碼的判據。 普通高等教育“十五”國家級規劃教

14、材信息論與編碼 曹雪虹等編著245.2 5.2 無失真信源編碼無失真信源編碼信源輸出信源輸出X(X1X2XlXL)，Xl a1，a2，ai，an編碼為編碼為Y(Y1Y2Yk YkL)，Yk b1，b2，bj，bm。要求能夠要求能夠無失真或無差錯無失真或無差錯地譯碼，同時傳地譯碼，同時傳送送Y時所需要的時所需要的信息率最小信息率最小 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著255.2 5.2 無失真信源編碼無失真信源編碼Yk平均每個符號平均每個符號的最大信息量為的最大信息量為log mKL長碼字的最大信息量為長碼字的最大信息量為KLlog m則傳送一個信源符號需要的信息率平均

15、為則傳送一個信源符號需要的信息率平均為 MLmLKKLlog1logLKmM 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著265.2 5.2 無失真信源編碼無失真信源編碼所謂所謂信息率最小信息率最小，就是找到一種編碼方，就是找到一種編碼方式使式使 最小。最小。無失真信源編碼無失真信源編碼定理研究的內容定理研究的內容: :最小信息率為多少時，才能得到無失真最小信息率為多少時，才能得到無失真的譯碼？若小于這個信息率是否還能無的譯碼？若小于這個信息率是否還能無失真地譯碼失真地譯碼 K普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著275.2 5.2 無失真信源編碼無失真信

16、源編碼無失真的信源編碼定理無失真的信源編碼定理n定長定長編碼定理編碼定理n變長變長編碼定理編碼定理 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著285.2 5.2 無失真信源編碼無失真信源編碼n定長定長編碼定理編碼定理K是定值是定值 且惟一可譯碼且惟一可譯碼普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著295.2 5.2 無失真信源編碼無失真信源編碼由由L個符號組成的、每個符號的熵為個符號組成的、每個符號的熵為HL(X)的無記的無記憶平穩信源符號序列憶平穩信源符號序列X1X2XlXL，可用，可用KL個符個符號號Y1，Y2，Yk，（每個符號有，（每個符號有m種可能種

17、可能值）進行值）進行定長編碼定長編碼。對任意。對任意 0， 0，只要，只要則當則當L足夠大時，必可使譯碼差錯小于足夠大時，必可使譯碼差錯小于 ；反之，當反之，當 時，譯碼差錯一時，譯碼差錯一定是有限值，而定是有限值，而L足夠大時，譯碼幾乎必定出錯足夠大時，譯碼幾乎必定出錯 )(logXLLHmLK2)(logXLLHmLK普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著305.2 5.2 無失真信源編碼無失真信源編碼定長編碼定理說明，定長編碼定理說明，)()(logXXHLHmKLL碼字所能攜帶的信息量碼字所能攜帶的信息量大于大于信源序列輸出信源序列輸出的信息量，則可以使傳輸幾乎無

18、失真，當的信息量，則可以使傳輸幾乎無失真，當然條件是然條件是L L足夠大足夠大。 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著315.2 5.2 無失真信源編碼無失真信源編碼反之，當反之，當 時，不可能構成無失時，不可能構成無失真的編碼，也就是不可能做一種編碼器，真的編碼，也就是不可能做一種編碼器，能使收端譯碼時差錯概率趨于零。能使收端譯碼時差錯概率趨于零。 時，則為臨界狀態，可能無失真，時，則為臨界狀態，可能無失真，也可能有失真。也可能有失真。)(XLHK )(XLHK 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著325.2 5.2 無失真信源編碼無失真信源編

19、碼式中式中 為自信息方差為自信息方差 為一正數。當為一正數。當 和和 均為定值時，只要均為定值時，只要L足夠大，足夠大，Pe可以小于任一正數可以小于任一正數 。即，。即， 22)(LPeX)()()(22XxXHIEi)(2X222)(LX普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著335.2 5.2 無失真信源編碼無失真信源編碼當信源序列長度當信源序列長度L滿足滿足 時，時，能達到差錯率要求能達到差錯率要求 22)(XL22)(LPeX普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著345.2 5.2 無失真信源編碼無失真信源編碼在在連續信源連續信源的情況下，由于

20、信源的的情況下，由于信源的信息量信息量趨于無限趨于無限，顯然不能用離散符號序列，顯然不能用離散符號序列Y來來完成無失真編碼，而只能進行完成無失真編碼，而只能進行限失真編碼限失真編碼。普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著355.2 5.2 無失真信源編碼無失真信源編碼定義定義為為編碼效率編碼效率，即信源的平均符號熵為，即信源的平均符號熵為H(X)，采用平均符號碼長為采用平均符號碼長為 來編碼，所得的效來編碼，所得的效率。率。編碼效率總是小于編碼效率總是小于1，且最佳編碼效率為，且最佳編碼效率為 KHL)(XK0,)()(XXLLHH普通高等教育“十五”國家級規劃教材信息論

21、與編碼 曹雪虹等編著365.2 5.2 無失真信源編碼無失真信源編碼編碼定理從理論上闡明了編碼效率接近編碼定理從理論上闡明了編碼效率接近1的理想編碼器的存在性，它使輸出符號的的理想編碼器的存在性，它使輸出符號的信息率與信源熵之比接近于信息率與信源熵之比接近于1，即，即 L取無限長取無限長1log)(mLKHLLX普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著375.2 5.2 無失真信源編碼無失真信源編碼例例設離散無記憶信源概率空間為設離散無記憶信源概率空間為 比特比特/符號符號 04. 005. 006. 007. 01 . 01 . 018. 04 . 087654321aa

22、aaaaaaPX55. 2log)(81iiippXH普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著385.2 5.2 無失真信源編碼無失真信源編碼對信源符號采用對信源符號采用定長定長二元編碼，要求編碼二元編碼，要求編碼效率為效率為 90，若取，若取L1，則可算出，則可算出2.55 90%=2.8比特比特/符號符號Pe0.04 太大太大K普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著395.2 5.2 無失真信源編碼無失真信源編碼28. 0,90. 0)()(XHXH228122)(82. 7)()(log)()(bitXHppxIDXiiii若要求譯碼錯誤概率若要

23、求譯碼錯誤概率 61087622210108 . 91028. 082. 7)(XL普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著405.2 5.2 無失真信源編碼無失真信源編碼變長變長編碼定理編碼定理在變長編碼中，碼長在變長編碼中，碼長K是變化的是變化的根據信源各個符號的統計特性，如根據信源各個符號的統計特性，如概率大概率大的符號用短碼，概率小的用較長的碼的符號用短碼，概率小的用較長的碼，使，使得編碼后平均碼長降低，從而提高編碼效得編碼后平均碼長降低，從而提高編碼效率。（統計匹配）率。（統計匹配）普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著415.2 5.2 無

24、失真信源編碼無失真信源編碼單個符號單個符號變長編碼定理：若離散無記憶信變長編碼定理：若離散無記憶信源的符號熵為源的符號熵為H(X)，每個信源符號用，每個信源符號用m進進制碼元進行變長編碼，一定存在一種無失制碼元進行變長編碼，一定存在一種無失真編碼方法，其碼字平均長度滿足下列不真編碼方法，其碼字平均長度滿足下列不等式等式1log)(log)(mXHKmXH普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著425.2 5.2 無失真信源編碼無失真信源編碼 離散平穩無記憶序列離散平穩無記憶序列變長編碼定理：對于變長編碼定理：對于平均符號熵為平均符號熵為HL(X)的離散平穩無記憶信源，的離散

25、平穩無記憶信源，必存在一種無失真編碼方法，使平均信息必存在一種無失真編碼方法，使平均信息率滿足不等式率滿足不等式其中其中 為任意小正數。為任意小正數。)()(XXLLHKH普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著435.2 5.2 無失真信源編碼無失真信源編碼用變長編碼來達到相當高的編碼效率，一用變長編碼來達到相當高的編碼效率，一般所要求的符號長度般所要求的符號長度L可以比定長編碼小可以比定長編碼小得多。得多。 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著445.2 5.2 無失真信源編碼無失真信源編碼編碼效率總是小于編碼效率總是小于1 1，可以用它來衡量各

26、種，可以用它來衡量各種編碼方法的優劣。編碼方法的優劣。為了衡量各種編碼方法與為了衡量各種編碼方法與最佳碼最佳碼的差距，的差距，定義碼的剩余度為定義碼的剩余度為 KXHmLKXHLLL)(1log)(11普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著455.2 5.2 無失真信源編碼無失真信源編碼例例設離散無記憶信源的概率空間為設離散無記憶信源的概率空間為414321aaPX普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著465.2 5.2 無失真信源編碼無失真信源編碼符號/811. 034log434log41)(bitXH若用二元定長編碼若用二元定長編碼(0，1)來

27、構造一個即來構造一個即時碼：時碼： 。平均碼長平均碼長 1二元碼符號二元碼符號/信源符號信源符號1,021aaK普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著475.2 5.2 無失真信源編碼無失真信源編碼編碼效率為編碼效率為811. 0)(KXH輸出的信息效率為輸出的信息效率為R0.811比特比特/二元碼符號二元碼符號普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著485.2 5.2 無失真信源編碼無失真信源編碼長度為長度為2的信源序列進行的信源序列進行變長編碼變長編碼（編碼方（編碼方法后面介紹），其即時碼如下表法后面介紹），其即時碼如下表 aip(ai)即時碼a1

28、a19/160a1a23/1610a2a13/16110a2a21/16111普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著495.2 5.2 無失真信源編碼無失真信源編碼322722KK162731613163216311692K二元碼符號二元碼符號/信源序列信源序列二元碼符號二元碼符號/信源符號信源符號普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著505.2 5.2 無失真信源編碼無失真信源編碼961. 027811. 0322編碼效率編碼效率信息效率信息效率R20.961比特比特/二元碼符號二元碼符號 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編

29、著515.2 5.2 無失真信源編碼無失真信源編碼L3 R30.985比特比特/二元碼符號二元碼符號 L4 R40.991比特比特/二元碼符號二元碼符號 985. 03991. 04普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著525.2 5.2 無失真信源編碼無失真信源編碼定長二元碼編碼，要求編碼效率達到定長二元碼編碼，要求編碼效率達到96時，允許譯碼錯誤概率時，允許譯碼錯誤概率 510222122)(4715. 0)()(log)(bitXHppXiii752221013. 41004. 0)96. 0()811. 0(4715. 0L普通高等教育“十五”國家級規劃教材信息論

30、與編碼 曹雪虹等編著535.2 5.2 無失真信源編碼無失真信源編碼最佳變長編碼最佳變長編碼 凡是能載荷一定的信息量，且碼字的平均凡是能載荷一定的信息量，且碼字的平均長度最短，可分離的變長碼的碼字集合稱長度最短，可分離的變長碼的碼字集合稱為為最佳變長碼最佳變長碼。 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著545.2 5.2 無失真信源編碼無失真信源編碼能能獲得最佳碼的編碼方法主要有：獲得最佳碼的編碼方法主要有：n香農（香農（Shannon）n費諾（費諾（Fano）n哈夫曼（哈夫曼（Huffman）等）等 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著555.2

31、 5.2 無失真信源編碼無失真信源編碼香農香農（Shannon）編碼）編碼n將信源消息符號按其出現的概率大小依將信源消息符號按其出現的概率大小依次排列次排列n確定滿足下列不等式的整數碼長確定滿足下列不等式的整數碼長Ki。nppp211loglog22iiipKp普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著565.2 5.2 無失真信源編碼無失真信源編碼n為了編成唯一可譯碼，計算第為了編成唯一可譯碼，計算第i個消息個消息的累加概率的累加概率n將累加概率將累加概率Pi變換成二進制數。變換成二進制數。n取取Pi二進數的小數點后二進數的小數點后Ki位即為該消息位即為該消息符號的二進制碼

32、字。符號的二進制碼字。 11ikkiapP普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著575.2 5.2 無失真信源編碼無失真信源編碼例例 設信源共設信源共7個符號消息，其概率和累加個符號消息，其概率和累加概率如下表所示。概率如下表所示。 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著585.2 5.2 無失真信源編碼無失真信源編碼信源消息信源消息符號符號ai符號概符號概率率(ai)累加概累加概率率Pi-log p(ai)碼字長碼字長度度Ki碼字碼字a10.2002.323000a20.190.22.393001a30.180.392.473011a40.170.

33、572.563100a50.150.742.743101a60.100.893.3241110a70.010.996.6471111110普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著59十進制小數二進制小數 方法：“乘2取整”對十進制小數乘2得到的整數部分和小數部分,整數部分既是相應的二進制數碼,再用2乘小數部分(之前乘后得到新的小數部分),又得到整數和小數部分.如此不斷重復,直到小數部分為0或達到精度要求為止.第一次所得到為最高位,最后一次得到為最低位如:0.25的二進制0.25*2=0.5 取整是00.5*2=1.0 取整是1即0.25的二進制為 0.01 ( 第一次所得到

34、為最高位,最后一次得到為最低位)0.8125的二進制0.8125*2=1.625 取整是10.625*2=1.25 取整是10.25*2=0.5 取整是00.5*2=1.0 取整是1即0.8125的二進制是0.1101（第一次所得到為最高位,最后一次得到為最低位）普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著605.2 5.2 無失真信源編碼無失真信源編碼14. 3)(71iiiKapK碼元碼元/符號符號831. 014. 361. 2)(KXHR比特比特/碼元碼元 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著615.2 5.2 無失真信源編碼無失真信源編碼費諾費

35、諾編碼方法編碼方法費諾編碼屬于概率匹配編碼費諾編碼屬于概率匹配編碼(1)將信源消息符號按其出現的概率大小依將信源消息符號按其出現的概率大小依次排列：次排列： 。(2)將依次排列的信源符號按概率值分為兩將依次排列的信源符號按概率值分為兩大組，使兩個組的概率之和近于相同，大組，使兩個組的概率之和近于相同，并對各組賦予一個二進制碼元并對各組賦予一個二進制碼元“0”和和“1”。nppp21普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著625.2 5.2 無失真信源編碼無失真信源編碼(3)將每一大組的信源符號進一步再分成兩將每一大組的信源符號進一步再分成兩組，使劃分后的兩個組的概率之和近于

36、組，使劃分后的兩個組的概率之和近于相同，并又賦予兩個組一個二進制符號相同，并又賦予兩個組一個二進制符號“0”和和“1”。(4)如此重復，直至每個組只剩下一個信源如此重復，直至每個組只剩下一個信源符號為止。符號為止。(5)信源符號所對應的碼字即為費諾碼。信源符號所對應的碼字即為費諾碼。普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著635.2 5.2 無失真信源編碼無失真信源編碼例例 對以下信源進行費諾編碼對以下信源進行費諾編碼。 消息符消息符號號ai各 個 消各 個 消息概率息概率 p(ai)第一次第一次分組分組第二次第二次分組分組第三次第三次分組分組第四次第四次分組分組二元二元碼

37、字碼字碼長碼長Kia10.2000002a20.19100103a30.1810113a40.1710102a50.15101103a60.101011104a70.01111114普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著645.2 5.2 無失真信源編碼無失真信源編碼74. 2)(71iiiKapK953. 074. 261. 2)(KXHR 碼元碼元/符號符號 bit/符號符號 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著655.2 5.2 無失真信源編碼無失真信源編碼 哈夫曼哈夫曼編碼方法編碼方法(1)將信源消息符號按其出現的概率大小依將信源消息符號按

38、其出現的概率大小依次排列，次排列，(2)取兩個概率最小的字母分別配以取兩個概率最小的字母分別配以0和和1兩兩個碼元，并將這兩個概率相加作為一個個碼元，并將這兩個概率相加作為一個新字母的概率，與未分配的二進符號的新字母的概率，與未分配的二進符號的字母重新排隊。字母重新排隊。nppp21普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著665.2 5.2 無失真信源編碼無失真信源編碼(3)對重排后的兩個概率最小符號重復步驟對重排后的兩個概率最小符號重復步驟(2)的過程。的過程。(4)不斷繼續上述過程，直到最后兩個符號不斷繼續上述過程，直到最后兩個符號配以配以0和和1為止。為止。(5)從最

39、后一級開始，向前返回得到各個信從最后一級開始，向前返回得到各個信源符號所對應的碼元序列，即相應的碼源符號所對應的碼元序列，即相應的碼字。字。2022年5月2日星期一67例 1-3-1考慮離散信源DMS具有發生的概率如圖(1-3-4)說明的七個可能的符號x1,x2,x7我們安排信源符號的次序以符號發生概率遞降為序 p(x1)p(x2),p(x7)2022年5月2日星期一68從最后二個可能符號x6、x7開始討論他的編碼過程這二個符號如圖所示索搏在一起，上邊支路為“0”，下邊支路為“1”。 字符概率自信息碼x10.351.514600 x20.301.737001x30.202.321910 x40

40、.103.3219110 x50.044.64391110 x60.0057.643911110 x70.0057.643911111H(x)=2.11 R 221.普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著695.2 5.2 無失真信源編碼無失真信源編碼例例 對以下信源進行哈夫曼編碼對以下信源進行哈夫曼編碼 信源符號信源符號ai概率概率p(ai) 碼字碼字Wi碼長碼長Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104a70.0101114普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著705

41、.2 5.2 無失真信源編碼無失真信源編碼0.20 0.20 0.26 0.35 0.39 0.61 1.00.19 0.19 0.20 0.26 0.35 0.390.18 0.18 0.19 0.20 0.260.17 0.17 0.18 0.190.15 0.15 0.170.10 0.110.01010101010101普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著715.2 5.2 無失真信源編碼無失真信源編碼 碼元碼元/符號符號 bit/符號符號 72. 2)(71iiiKapK96. 072. 261. 2)(KXHR普通高等教育“十五”國家級規劃教材信息論與編碼

42、曹雪虹等編著725.2 5.2 無失真信源編碼無失真信源編碼哈夫曼編碼方法得到的碼并非唯一的哈夫曼編碼方法得到的碼并非唯一的n每次對信源縮減時，賦予信源最后兩個每次對信源縮減時，賦予信源最后兩個概率最小的符號，用概率最小的符號，用0和和1是可以任意的，是可以任意的，所以可以得到不同的哈夫曼碼，但不會所以可以得到不同的哈夫曼碼，但不會影響碼字的長度。影響碼字的長度。普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著735.2 5.2 無失真信源編碼無失真信源編碼n對信源進行縮減時，兩個概率最小的符對信源進行縮減時，兩個概率最小的符號合并后的概率與其它信源符號的概率號合并后的概率與其它信

43、源符號的概率相同時，這兩者在縮減信源中進行概率相同時，這兩者在縮減信源中進行概率排序，其位置放置次序是可以任意的，排序，其位置放置次序是可以任意的，故會得到不同的哈夫曼碼。此時將影響故會得到不同的哈夫曼碼。此時將影響碼字的長度，一般將碼字的長度，一般將合并的概率放在上合并的概率放在上面面，這樣可獲得，這樣可獲得較小的碼方差較小的碼方差。普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著745.2 5.2 無失真信源編碼無失真信源編碼例例 設有離散無記憶信源設有離散無記憶信源1 . 01 . 02 . 02 . 04 . 054321aaaaaPX普通高等教育“十五”國家級規劃教材信息

44、論與編碼 曹雪虹等編著755.2 5.2 無失真信源編碼無失真信源編碼信源符號信源符號ai概率概率p(ai)碼字碼字Wi1碼長碼長Ki1碼字碼字Wi2碼長碼長Ki2a10.411002a20.2012102a30.20003112a40.1001040103a50.1001140113普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著765.2 5.2 無失真信源編碼無失真信源編碼0.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.40.2 0.2 0.20.1 0.2 0.10.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.40.2 0.2 0.2

45、0.1 0.20.10101010101010101普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著775.2 5.2 無失真信源編碼無失真信源編碼2 . 2)(71iiiKapK 碼元碼元/符號符號 965. 0)(KXH普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著785.2 5.2 無失真信源編碼無失真信源編碼qiiiilKkapKkE1222)(36. 121l16. 022l普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著795.2 5.2 無失真信源編碼無失真信源編碼 進行哈夫曼編碼時，為得到進行哈夫曼編碼時，為得到碼方差碼方差最小的最小的碼，

46、應使合并的信源符號位于縮減信源序碼，應使合并的信源符號位于縮減信源序列列盡可能高的位置盡可能高的位置上，以減少再次合并的上，以減少再次合并的次數，充分利用短碼。次數，充分利用短碼。 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著805.2 5.2 無失真信源編碼無失真信源編碼哈夫曼碼是用哈夫曼碼是用概率匹配概率匹配方法進行信源編碼。方法進行信源編碼。n哈夫曼碼的編碼方法保證了概率大的符哈夫曼碼的編碼方法保證了概率大的符號對應于短碼，概率小的符號對應于長號對應于短碼，概率小的符號對應于長碼，充分利用了短碼；碼，充分利用了短碼；n縮減信源的最后二個碼字總是最后一位縮減信源的最后二個碼

47、字總是最后一位不同，從而保證了不同，從而保證了哈夫曼碼是即時碼哈夫曼碼是即時碼。普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著815.3 限失真信源編碼定理限失真信源編碼定理 信息率失真函數給出了失真小于D時所必須具有的最小信息率R(D)；只要信息率大于R(D)，一定可以找到一種編碼，使譯碼后的失真小于D。 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著825.3 限失真信源編碼定理限失真信源編碼定理限失真信源編碼定理：設離散無記憶信源X的信息率失真函數R(D)，則當信息率RR(D)，只要信源序列長度L足夠長，一定存在一種編碼方法，其譯碼失真小于或等于D，為任意小的

48、正數。反之，若RR(D)，則無論采用什么樣的編碼方法，其譯碼失真必大于D。普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著835.3 限失真信源編碼定理限失真信源編碼定理如果是二元信源，對于任意小的，每一個信源符號的平均碼長滿足如下公式 )()(DRKDR普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著845.3 限失真信源編碼定理限失真信源編碼定理在失真限度內使信息率任意接近R(D)的編碼方法存在。然而，要使信息率小于R(D)，平均失真一定會超過失真限度D。對于連續平穩無記憶信源，無法進行無失真編碼，在限失真情況下，有與上述定理一樣的編碼定理。普通高等教育“十五”國家

49、級規劃教材信息論與編碼 曹雪虹等編著855.3 限失真信源編碼定理限失真信源編碼定理限失真信源編碼定理只能說明最佳編碼是存在的，而具體構造編碼方法卻一無所知。因而就不能象無損編碼那樣從證明過程中引出概率匹配的編碼方法。一般只能從優化的思路去求最佳編碼。實際上迄今尚無合適的可實現的編碼方法可接近R(D)這個界。 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著865.4 常用信源編碼方法簡介常用信源編碼方法簡介n游程編碼 在二元序列中，連0段稱為0游程 連1段稱為1游程000101110010001 可變換成下列游程序列：3113213 普通高等教育“十五”國家級規劃教材信息論與編碼

50、 曹雪虹等編著875.4 常用信源編碼方法簡介常用信源編碼方法簡介若已知二元序列以0起始，從游程序列很容易恢復成原來的二元序列 游程序列是多元序列，各長度可按霍夫曼編碼或其它方法處理以達到壓縮碼率的目的。 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著885.4 常用信源編碼方法簡介常用信源編碼方法簡介n多元序列也存在相應的游程序列 n多元序列變換成游程序列再進行壓縮編碼沒有多大意義 n游程編碼只適用于二元序列，對于多元信源，一般不能直接利用游程編碼 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著895.4 常用信源編碼方法簡介常用信源編碼方法簡介n冗余位編碼，游程

51、編碼在多元信源的應用普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著905.4 常用信源編碼方法簡介常用信源編碼方法簡介如下多元序列x1，x2，xm1，y，y，y，x m1+1，xm1+2，x m2，y，y， 可以用下面序列表示 111，100，000111，111000 x1，x2，xm1，x m1+1，x m1+2x 2， 1表示信息位，0表示冗余位 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著915.4 常用信源編碼方法簡介常用信源編碼方法簡介n算術編碼 非分組碼的編碼方法之一算術碼普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著925.4 常用信

52、源編碼方法簡介常用信源編碼方法簡介符號概率與積累概率的遞推關系0)()() 1 ,()()0 ,(1 , 0,)()(),(PSpSPSPSPSPrPSpSPrSPr普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著935.4 常用信源編碼方法簡介常用信源編碼方法簡介采用累積概率P(S)表示碼字C(S)，符號概率p(S)表示狀態區間A(S) rrpSASrAPSASCSrC)()()()()(普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著945.4 常用信源編碼方法簡介常用信源編碼方法簡介P(S)把區間0，1)分割成許多小區間，每個小區間的長度等于各序列的概率p(S)，小區間內的任一點可用來代表這序列 0(P1) P2 P3 P4 P5 1 p1 p2 p3 p4 普通高等教育“十五”國家級規劃教材信息論與編碼 曹雪虹等編著955.4 常用信源編碼方法簡介常用信源編碼方法簡介 0(P1) P2 P3 P4 P5 1 p1 p2 p3 p4 )(