信息論與編碼5信源編碼

第5章信源編碼

編碼分為信源編碼和信道編碼，其中信源編碼又分為無(wú)失真和限失真。一般稱無(wú)失真信源編碼定理為第一極限定理；信道編碼定理（包括離散和連續(xù)信道）稱為第二極限定理；限失真信源編碼定理稱為第三極限定理。

1普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著第5章信源編碼由于信源符號(hào)之間存在分布不均勻和相關(guān)性，使得信源存在冗余度，信源編碼的主要任務(wù)就是減少冗余，提高編碼效率。

2普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著第5章信源編碼信源編碼的基本途徑有兩個(gè)：使序列中的各個(gè)符號(hào)盡可能地互相獨(dú)立，即解除相關(guān)性；使編碼中各個(gè)符號(hào)出現(xiàn)的概率盡可能地相等，即概率均勻化。3普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著第5章信源編碼信源編碼的基礎(chǔ)是信息論中的兩個(gè)編碼定理：無(wú)失真編碼定理限失真編碼定理

無(wú)失真編碼只適用于離散信源

對(duì)于連續(xù)信源，只能在失真受限制的情況下進(jìn)行限失真編碼

4普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著第5章信源編碼本章討論離散信源編碼，首先從無(wú)失真編碼定理出發(fā)，重點(diǎn)討論以香農(nóng)碼、費(fèi)諾碼和霍夫曼碼為代表的最佳無(wú)失真碼。然后介紹了限失真編碼定理。最后簡(jiǎn)單介紹了一些其它常用的信源編碼方法。5普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.1編碼的定義

信源編碼器信道碼表圖5-1信源編碼器示意圖6普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.1編碼的定義信源編碼是指信源輸出符號(hào)經(jīng)信源編碼器編碼后轉(zhuǎn)換成另外的壓縮符號(hào)無(wú)失真信源編碼：可精確無(wú)失真地復(fù)制信源輸出地消息7普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.1編碼的定義將信源消息分成若干組，即符號(hào)序列xi，xi＝(xi1xi2…xil…xiL)，xilA={a1，a2，…，ai，…，an}每個(gè)符號(hào)序列xi依照固定碼表映射成一個(gè)碼字yi，yi＝(yi1yi2…yil…yiL)，yilB={b1，b2，…，bi，…，bm}這樣的碼稱為分組碼，有時(shí)也叫塊碼。只有分組碼才有對(duì)應(yīng)的碼表，而非分組碼中則不存在碼表。

8普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.1編碼的定義如圖5-1所示，如果信源輸出符號(hào)序列長(zhǎng)度L＝1，信源符號(hào)集A(a1，a2，…，an)信源概率空間為若將信源X通過(guò)二元信道傳輸，就必須把信源符號(hào)ai變換成由0，1符號(hào)組成的碼符號(hào)序列，這個(gè)過(guò)程就是信源編碼9普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.1編碼的定義碼可分為兩類：一、固定長(zhǎng)度的碼，碼中所有碼字的長(zhǎng)度都相同，如表5-1中的碼1就是定長(zhǎng)碼二、可變長(zhǎng)度碼，碼中的碼字長(zhǎng)短不一，如表中碼2就是變長(zhǎng)碼。

10普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.1編碼的定義不同的碼符號(hào)序列，如表5-1所示。

表5-1變長(zhǎng)碼與定長(zhǎng)碼信源符號(hào)ai信源符號(hào)出現(xiàn)概率p(ai)碼表碼1碼2a1p(a1)000a2p(a2)0101a3p(a3)10001a4p(a4)1111111普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.1編碼的定義（1）奇異碼和非奇異碼

若信源符號(hào)和碼字是一一對(duì)應(yīng)的，則該碼為非奇異碼。反之為奇異碼。如表5-2中的碼1是奇異碼，碼2是非奇異碼。

12普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.1編碼的定義表5-2碼的不同屬性信源符號(hào)ai符號(hào)出現(xiàn)概率p(ai)碼1碼2碼3碼4a11/20011a21/411101001a31/80000100001a41/811011000000113普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.1編碼的定義（2）唯一可譯碼

任意有限長(zhǎng)的碼元序列，只能被唯一地分割成一個(gè)個(gè)的碼字，便稱為唯一可譯碼14普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.1編碼的定義唯一可譯碼中又分為非即時(shí)碼和即時(shí)碼：如果接收端收到一個(gè)完整的碼字后，不能立即譯碼，還需等下一個(gè)碼字開(kāi)始接收后才能判斷是否可以譯碼，這樣的碼叫做非即時(shí)碼。15普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.1編碼的定義即時(shí)碼：只要收到符號(hào)就表示該碼字已完整，可以立即譯碼。即時(shí)碼又稱為非延長(zhǎng)碼，任意一個(gè)碼字都不是其它碼字的前綴部分，有時(shí)叫做異前綴碼。16普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.1編碼的定義碼奇異碼非分組碼分組碼非奇異碼非唯一可譯碼非即時(shí)碼即時(shí)碼(非延長(zhǎng)碼)唯一可譯碼17普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.1編碼的定義通?？捎么a樹(shù)來(lái)表示各碼字的構(gòu)成

01

01

01

01010101

0101010101010101二進(jìn)制碼樹(shù)18普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.1編碼的定義012012012012012012三進(jìn)制碼樹(shù)19普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.1編碼的定義唯一可譯碼存在的充分和必要條件各碼字的長(zhǎng)度Ki應(yīng)符合克勞夫特不等式：

20普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.1編碼的定義例：設(shè)二進(jìn)制碼樹(shù)中X(a1，a2，a3，a4)，K1＝1，K2＝2，K3＝2，K4＝3，應(yīng)用上述判斷定理：

因此不存在滿足這種Ki的唯一可譯碼。

21普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.1編碼的定義a1=1

01

01

01a2=01a3=011a4=000{1，01，001，000}惟一可譯碼；{1，01，101，000}不是惟一可譯碼；均滿足克勞夫特不等式22普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.1編碼的定義克勞夫特不等式只是用來(lái)說(shuō)明唯一可譯碼是否存在，并不能作為唯一可譯碼的判據(jù)。23普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼

信源輸出X＝(X1X2…Xl…XL)，Xl{a1，a2，…，ai，…，an}編碼為Y＝(Y1Y2…Yk…YkL)，Yk{b1，b2，…，bj，…，bm}。要求能夠無(wú)失真或無(wú)差錯(cuò)地譯碼，同時(shí)傳送Y時(shí)所需要的信息率最小

24普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼Yk平均每個(gè)符號(hào)的最大信息量為logmKL長(zhǎng)碼字的最大信息量為KLlogm則傳送一個(gè)信源符號(hào)需要的信息率平均為

25普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼所謂信息率最小，就是找到一種編碼方式使最小。無(wú)失真信源編碼定理研究的內(nèi)容:最小信息率為多少時(shí)，才能得到無(wú)失真的譯碼？若小于這個(gè)信息率是否還能無(wú)失真地譯碼26普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼無(wú)失真的信源編碼定理定長(zhǎng)編碼定理變長(zhǎng)編碼定理27普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼定長(zhǎng)編碼定理 K是定值

且惟一可譯碼28普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼由L個(gè)符號(hào)組成的、每個(gè)符號(hào)的熵為HL(X)的無(wú)記憶平穩(wěn)信源符號(hào)序列X1X2…Xl…XL，可用KL個(gè)符號(hào)Y1，Y2，…，Yk，…，（每個(gè)符號(hào)有m種可能值）進(jìn)行定長(zhǎng)編碼。對(duì)任意>0，>0，只要 則當(dāng)L足夠大時(shí)，必可使譯碼差錯(cuò)小于；反之，當(dāng)時(shí)，譯碼差錯(cuò)一定是有限值，而L足夠大時(shí)，譯碼幾乎必定出錯(cuò)

29普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼定長(zhǎng)編碼定理說(shuō)明，碼字所能攜帶的信息量大于信源序列輸出的信息量，則可以使傳輸幾乎無(wú)失真，當(dāng)然條件是L足夠大。

30普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼反之，當(dāng)時(shí)，不可能構(gòu)成無(wú)失真的編碼，也就是不可能做一種編碼器，能使收端譯碼時(shí)差錯(cuò)概率趨于零。時(shí)，則為臨界狀態(tài)，可能無(wú)失真，也可能有失真。31普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼式中為自信息方差為一正數(shù)。當(dāng)和均為定值時(shí)，只要L足夠大，Pe可以小于任一正數(shù)。即，

32普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼當(dāng)信源序列長(zhǎng)度L滿足時(shí)，能達(dá)到差錯(cuò)率要求

33普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼在連續(xù)信源的情況下，由于信源的信息量趨于無(wú)限，顯然不能用離散符號(hào)序列Y來(lái)完成無(wú)失真編碼，而只能進(jìn)行限失真編碼。34普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼定義

為編碼效率，即信源的平均符號(hào)熵為H(X)，采用平均符號(hào)碼長(zhǎng)為來(lái)編碼，所得的效率。編碼效率總是小于1，且最佳編碼效率為

35普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼編碼定理從理論上闡明了編碼效率接近1的理想編碼器的存在性，它使輸出符號(hào)的信息率與信源熵之比接近于1，即L取無(wú)限長(zhǎng)36普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼例

設(shè)離散無(wú)記憶信源概率空間為比特/符號(hào)

37普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼對(duì)信源符號(hào)采用定長(zhǎng)二元編碼，要求編碼效率為90％，若取L＝1，則可算出 ＝2.5590%=2.8比特/符號(hào)Pe＝0.04太大38普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼若要求譯碼錯(cuò)誤概率

39普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼變長(zhǎng)編碼定理在變長(zhǎng)編碼中，碼長(zhǎng)K是變化的根據(jù)信源各個(gè)符號(hào)的統(tǒng)計(jì)特性，如概率大的符號(hào)用短碼，概率小的用較長(zhǎng)的碼，使得編碼后平均碼長(zhǎng)降低，從而提高編碼效率。（統(tǒng)計(jì)匹配）40普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼單個(gè)符號(hào)變長(zhǎng)編碼定理：若離散無(wú)記憶信源的符號(hào)熵為H(X)，每個(gè)信源符號(hào)用m進(jìn)制碼元進(jìn)行變長(zhǎng)編碼，一定存在一種無(wú)失真編碼方法，其碼字平均長(zhǎng)度滿足下列不等式41普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼

離散平穩(wěn)無(wú)記憶序列變長(zhǎng)編碼定理：對(duì)于平均符號(hào)熵為HL(X)的離散平穩(wěn)無(wú)記憶信源，必存在一種無(wú)失真編碼方法，使平均信息率滿足不等式其中為任意小正數(shù)。42普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼用變長(zhǎng)編碼來(lái)達(dá)到相當(dāng)高的編碼效率，一般所要求的符號(hào)長(zhǎng)度L可以比定長(zhǎng)編碼小得多。43普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼編碼效率總是小于1，可以用它來(lái)衡量各種編碼方法的優(yōu)劣。為了衡量各種編碼方法與最佳碼的差距，定義碼的剩余度為

44普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼例 設(shè)離散無(wú)記憶信源的概率空間為45普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼若用二元定長(zhǎng)編碼(0，1)來(lái)構(gòu)造一個(gè)即時(shí)碼：。平均碼長(zhǎng)＝1二元碼符號(hào)/信源符號(hào)46普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼編碼效率為輸出的信息效率為R＝0.811比特/二元碼符號(hào)47普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼長(zhǎng)度為2的信源序列進(jìn)行變長(zhǎng)編碼（編碼方法后面介紹），其即時(shí)碼如下表aip(ai)即時(shí)碼a1a19/160a1a23/1610a2a13/16110a2a21/1611148普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼二元碼符號(hào)/信源序列二元碼符號(hào)/信源符號(hào)49普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼編碼效率信息效率R2＝0.961比特/二元碼符號(hào)50普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼L＝3R3＝0.985比特/二元碼符號(hào)

L＝4R4＝0.991比特/二元碼符號(hào)

51普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼定長(zhǎng)二元碼編碼，要求編碼效率達(dá)到96％時(shí)，允許譯碼錯(cuò)誤概率

52普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼最佳變長(zhǎng)編碼

凡是能載荷一定的信息量，且碼字的平均長(zhǎng)度最短，可分離的變長(zhǎng)碼的碼字集合稱為最佳變長(zhǎng)碼。

53普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼能獲得最佳碼的編碼方法主要有：香農(nóng)（Shannon）費(fèi)諾（Fano）哈夫曼（Huffman）等

54普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼香農(nóng)（Shannon）編碼將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列確定滿足下列不等式的整數(shù)碼長(zhǎng)Ki。55普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼為了編成唯一可譯碼，計(jì)算第i個(gè)消息的累加概率將累加概率Pi變換成二進(jìn)制數(shù)。取Pi二進(jìn)數(shù)的小數(shù)點(diǎn)后Ki位即為該消息符號(hào)的二進(jìn)制碼字。56普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼例設(shè)信源共7個(gè)符號(hào)消息，其概率和累加概率如下表所示。

57普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼信源消息符號(hào)ai符號(hào)概率(ai)累加概率Pi-logp(ai)碼字長(zhǎng)度Ki碼字a10.2002.323000a20.190.22.393001a30.180.392.473011a40.170.572.563100a50.150.742.743101a60.100.893.3241110a70.010.996.647111111058普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼碼元/符號(hào)比特/碼元

59普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼費(fèi)諾編碼方法費(fèi)諾編碼屬于概率匹配編碼(1)將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列：。(2)將依次排列的信源符號(hào)按概率值分為兩大組，使兩個(gè)組的概率之和近于相同，并對(duì)各組賦予一個(gè)二進(jìn)制碼元“0”和“1”。60普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼(3)將每一大組的信源符號(hào)進(jìn)一步再分成兩組，使劃分后的兩個(gè)組的概率之和近于相同，并又賦予兩個(gè)組一個(gè)二進(jìn)制符號(hào)“0”和“1”。(4)如此重復(fù)，直至每個(gè)組只剩下一個(gè)信源符號(hào)為止。(5)信源符號(hào)所對(duì)應(yīng)的碼字即為費(fèi)諾碼。61普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼例對(duì)以下信源進(jìn)行費(fèi)諾編碼。

消息符號(hào)ai各個(gè)消息概率p(ai)第一次分組第二次分組第三次分組第四次分組二元碼字碼長(zhǎng)Kia10.2000002a20.19100103a30.1810113a40.1710102a50.15101103a60.101011104a70.0111111462普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼

碼元/符號(hào)

bit/符號(hào)

63普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼

哈夫曼編碼方法(1)將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列，(2)取兩個(gè)概率最小的字母分別配以0和1兩個(gè)碼元，并將這兩個(gè)概率相加作為一個(gè)新字母的概率，與未分配的二進(jìn)符號(hào)的字母重新排隊(duì)。64普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼(3)對(duì)重排后的兩個(gè)概率最小符號(hào)重復(fù)步驟(2)的過(guò)程。(4)不斷繼續(xù)上述過(guò)程，直到最后兩個(gè)符號(hào)配以0和1為止。(5)從最后一級(jí)開(kāi)始，向前返回得到各個(gè)信源符號(hào)所對(duì)應(yīng)的碼元序列，即相應(yīng)的碼字。65普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼例對(duì)以下信源進(jìn)行哈夫曼編碼

信源符號(hào)ai概率p(ai)碼字Wi碼長(zhǎng)Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104a70.010111466普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼0.20 0.200.260.350.390.611.00.190.190.200.260.350.390.180.180.190.200.260.170.170.180.190.150.150.170.100.110.0101010101010167普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼

碼元/符號(hào)

bit/符號(hào)

68普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼哈夫曼編碼方法得到的碼并非唯一的每次對(duì)信源縮減時(shí)，賦予信源最后兩個(gè)概率最小的符號(hào)，用0和1是可以任意的，所以可以得到不同的哈夫曼碼，但不會(huì)影響碼字的長(zhǎng)度。69普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼對(duì)信源進(jìn)行縮減時(shí)，兩個(gè)概率最小的符號(hào)合并后的概率與其它信源符號(hào)的概率相同時(shí)，這兩者在縮減信源中進(jìn)行概率排序，其位置放置次序是可以任意的，故會(huì)得到不同的哈夫曼碼。此時(shí)將影響碼字的長(zhǎng)度，一般將合并的概率放在上面，這樣可獲得較小的碼方差。70普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼例設(shè)有離散無(wú)記憶信源71普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼信源符號(hào)ai概率p(ai)碼字Wi1碼長(zhǎng)Ki1碼字Wi2碼長(zhǎng)K’i2a10.411002a20.2012102a30.20003112a40.1001040103a50.100114011372普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼0.40.40.40.61.00.20.20.40.40.20.20.20.10.20.10.40.40.40.61.00.20.20.40.40.20.20.20.10.20.1010101010101010173普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼

碼元/符號(hào)

74普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼75普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼

進(jìn)行哈夫曼編碼時(shí)，為得到碼方差最小的碼，應(yīng)使合并的信源符號(hào)位于縮減信源序列盡可能高的位置上，以減少再次合并的次數(shù)，充分利用短碼。

76普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.2無(wú)失真信源編碼哈夫曼碼是用概率匹配方法進(jìn)行信源編碼。哈夫曼碼的編碼方法保證了概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的符號(hào)對(duì)應(yīng)于長(zhǎng)碼，充分利用了短碼；縮減信源的最后二個(gè)碼字總是最后一位不同，從而保證了哈夫曼碼是即時(shí)碼。77普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.3限失真信源編碼定理

信息率失真函數(shù)給出了失真小于D時(shí)所必須具有的最小信息率R(D)；只要信息率大于R(D)，一定可以找到一種編碼，使譯碼后的失真小于D。78普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.3限失真信源編碼定理限失真信源編碼定理：設(shè)離散無(wú)記憶信源X的信息率失真函數(shù)R(D)，則當(dāng)信息率R>R(D)，只要信源序列長(zhǎng)度L足夠長(zhǎng)，一定存在一種編碼方法，其譯碼失真小于或等于D＋，為任意小的正數(shù)。反之，若R<R(D)，則無(wú)論采用什么樣的編碼方法，其譯碼失真必大于D。79普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.3限失真信源編碼定理如果是二元信源，對(duì)于任意小的，每一個(gè)信源符號(hào)的平均碼長(zhǎng)滿足如下公式

80普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.3限失真信源編碼定理在失真限度內(nèi)使信息率任意接近R(D)的編碼方法存在。然而，要使信息率小于R(D)，平均失真一定會(huì)超過(guò)失真限度D。對(duì)于連續(xù)平穩(wěn)無(wú)記憶信源，無(wú)法進(jìn)行無(wú)失真編碼，在限失真情況下，有與上述定理一樣的編碼定理。81普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.3限失真信源編碼定理限失真信源編碼定理只能說(shuō)明最佳編碼是存在的，而具體構(gòu)造編碼方法卻一無(wú)所知。因而就不能象無(wú)損編碼那樣從證明過(guò)程中引出概率匹配的編碼方法。一般只能從優(yōu)化的思路去求最佳編碼。實(shí)際上迄今尚無(wú)合適的可實(shí)現(xiàn)的編碼方法可接近R(D)這個(gè)界。82普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.4常用信源編碼方法簡(jiǎn)介游程編碼在二元序列中，連0段稱為0游程連1段稱為1游程000101110010001可變換成下列游程序列：311321383普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.4常用信源編碼方法簡(jiǎn)介若已知二元序列以0起始，從游程序列很容易恢復(fù)成原來(lái)的二元序列游程序列是多元序列，各長(zhǎng)度可按霍夫曼編碼或其它方法處理以達(dá)到壓縮碼率的目的。84普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.4常用信源編碼方法簡(jiǎn)介多元序列也存在相應(yīng)的游程序列多元序列變換成游程序列再進(jìn)行壓縮編碼沒(méi)有多大意義游程編碼只適用于二元序列，對(duì)于多元信源，一般不能直接利用游程編碼85普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.4常用信源編碼方法簡(jiǎn)介冗余位編碼，——游程編碼在多元信源的應(yīng)用86普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.4常用信源編碼方法簡(jiǎn)介如下多元序列x1，x2，…，xm1，y，y，…，y，x

m1+1，xm1+2，…x

m2，y，y，…可以用下面序列表示111，…，100，…，000111，…，111000x1，x2，…，xm1，x

m1+1，x

m1+2…x

2，…1表示信息位，0表示冗余位87普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.4常用信源編碼方法簡(jiǎn)介算術(shù)編碼非分組碼的編碼方法之一——算術(shù)碼88普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.4常用信源編碼方法簡(jiǎn)介符號(hào)概率與積累概率的遞推關(guān)系89普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.4常用信源編碼方法簡(jiǎn)介采用累積概率P(S)表示碼字C(S)，符號(hào)概率p(S)表示狀態(tài)區(qū)間A(S)90普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.4常用信源編碼方法簡(jiǎn)介P(S)把區(qū)間[0，1)分割成許多小區(qū)間，每個(gè)小區(qū)間的長(zhǎng)度等于各序列的概率p(S)，小區(qū)間內(nèi)的任一點(diǎn)可用來(lái)代表這序列0(P1)P2P3P4P5……1

……p1

p2p3p491普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.4常用信源編碼方法簡(jiǎn)介0(P1)P2P3P4P5……1

……p1

p2p3p4代表大于或等于的最小整數(shù)。把積累概率P(S)寫成二進(jìn)位的小數(shù)，取其前L位;如果有尾數(shù)，就進(jìn)位到第L位，這樣得到一個(gè)數(shù)C

92普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.4常用信源編碼方法簡(jiǎn)介例如P(S)＝0.10110001，p(S)=1/17，則L＝5， 得C＝0.10111這個(gè)C就可作為S的碼字編碼效率很高，當(dāng)序列很長(zhǎng)時(shí)，可達(dá)到概率匹配。平均代碼長(zhǎng)度接近S的熵值。可以唯一地譯碼

93普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材《信息論與編碼》曹雪虹等編著5.4常用信源編碼方法簡(jiǎn)介符號(hào)符號(hào)概率pi符號(hào)累積概率Pja0.100(1/2)0.000b0.010(1/4)0.100c0.001(1/8)0.110d0.001(1/8)0.111例有四個(gè)符