信息論與編碼理論基礎(chǔ)(第3章)

1、第三章：第三章：信源編碼-離散信源無失真編碼3.1 信源及其分類信源及其分類3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼3.3 離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼3.4 最佳不等長(zhǎng)編碼最佳不等長(zhǎng)編碼3.1 信源及其分類信源及其分類信源的概念信源的概念 直觀地理解，信源就是信息的來源。但是這里必須要注意兩點(diǎn)：n在一個(gè)固定的時(shí)刻，信源發(fā)出的是一個(gè)隨機(jī)變量。在一個(gè)固定的時(shí)刻，信源發(fā)出的是一個(gè)隨機(jī)變量。n隨著時(shí)間的延續(xù)，信源發(fā)出一個(gè)又一個(gè)隨機(jī)變量，稱之為一隨著時(shí)間的延續(xù)，信源發(fā)出一個(gè)又一個(gè)隨機(jī)變量，稱之為一個(gè)隨機(jī)過程。個(gè)隨機(jī)過程。因此，一般

2、的信源種類太多，其統(tǒng)計(jì)性質(zhì)太復(fù)雜。怎樣做工程實(shí)用的簡(jiǎn)化？ 離散信源離散信源 信源每隔一個(gè)定長(zhǎng)時(shí)間段就發(fā)出一個(gè)隨機(jī)變量；隨著 時(shí)間的延續(xù)，信源發(fā)出的是隨機(jī)變量序列U-2U-1U0U1U2，其中 (1) Uk為第k個(gè)時(shí)間段發(fā)出的隨機(jī)變量； (2) 每個(gè)Uk都是一個(gè)離散型的隨機(jī)變量。離散無記憶信源離散無記憶信源 離散無記憶信源是這樣的離散信源：隨機(jī)變量、U-2、U-1、U0、U1、U2、相互獨(dú)立。離散無記憶簡(jiǎn)單信源離散無記憶簡(jiǎn)單信源 離散無記憶簡(jiǎn)單信源是這樣的離散無記憶信源：隨機(jī)變量、U-2、U-1、U0、U1、U2、具有相同的概率分布。 3.1 信源及其分類信源及其分類總結(jié)：離散無記憶簡(jiǎn)單信源離散

3、無記憶簡(jiǎn)單信源 就是時(shí)間離散、事件離散、各隨機(jī)變量獨(dú)立同分布的信源。本課程學(xué)習(xí)所面對(duì)的信源將主要是離散無記憶簡(jiǎn)單信源。一般的信源一般的信源 連續(xù)信源：有時(shí)間連續(xù)的信源，也有事件連續(xù)的信源；有記憶信源：信源在不同時(shí)刻發(fā)出的隨機(jī)變量相互依賴；有限記憶信源：在有限時(shí)間差內(nèi)的信源隨機(jī)變量相互依賴；非簡(jiǎn)單信源：信源在不同時(shí)刻發(fā)出的隨機(jī)變量具有不同的概率分布。馬爾可夫信源：信源隨機(jī)過程是馬爾可夫過程。 以下將順序地?cái)⑹鱿旅娴南嚓P(guān)概念：3.1 信源及其分類信源及其分類3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（1）設(shè)有一個(gè)離散無記憶簡(jiǎn)單信源，信源發(fā)出的隨機(jī)變量序 列為：U-2U

4、-1U0U1U2。 設(shè)信源隨機(jī)變量U1的事件有K個(gè)：a1, a2, , aK，則L維信源隨機(jī)向量(U1U2UL)的事件有KL個(gè)：(u1u2uL)|其中每個(gè)分量ul跑遍a1, a2, , aK。P(U1U2UL)=(u1u2uL)=P(U1=u1)P(U2=u2) P(UL=uL)=P(U1=u1)P(U1=u2) P(U1=uL)=q(u1)q(u2) q(uL)3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（2）設(shè)有一個(gè)含D個(gè)字母的字母表。對(duì)于(U1U2UL)的每一個(gè)事件(u1u2uL)，都用一個(gè)字母串(c1c2)來表示。這種表示方法稱為這種表示方法稱為D元編碼元編

5、碼；每一個(gè)事件每一個(gè)事件(u1u2uL)所對(duì)應(yīng)的字母串所對(duì)應(yīng)的字母串(c1c2)稱為一個(gè)稱為一個(gè)碼字碼字。 例例：離散無記憶簡(jiǎn)單信源發(fā)出的隨機(jī)變量序列為：U-2U-1U0U1U2。其中U1的事件有3個(gè)：晴, 云, 陰。(U1U2)有9個(gè)事件(晴晴), (晴云), (晴陰), (云晴), (云云), (云陰), (陰晴), (陰云), (陰陰)。用字母表0, 1對(duì)(U1U2)的事件進(jìn)行2元編碼如下：（晴晴）0000，（晴云）0001，（晴陰）0011，（云晴）0100，（云云）0101，（云陰）0111，（陰晴）1100，（陰云）1101，（陰陰）1111。3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編

6、碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（3）如果限定所有碼字的長(zhǎng)度都為N（即每個(gè)碼字都是一個(gè)長(zhǎng)度為N的字母串，或稱為N維向量），則稱此編碼為等長(zhǎng)編碼等長(zhǎng)編碼，能夠選擇的不同碼字的個(gè)數(shù)為DN。（4）如果限定每個(gè)碼字的長(zhǎng)度都N（即每個(gè)碼字都是一個(gè)長(zhǎng)度N的字母串），則稱此編碼為不等長(zhǎng)編碼不等長(zhǎng)編碼，能夠選擇的不同碼字的個(gè)數(shù)為D1+D2+DN=D(DN-1)/(D-1)。 （注意：在不等長(zhǎng)編碼中，并不能同時(shí)使用D(DN-1)/(D-1)個(gè)不同的碼字。一個(gè)長(zhǎng)度為2的字母串究竟是兩個(gè)長(zhǎng)度為1的碼字相連，還是一個(gè)長(zhǎng)度為2的碼字？無法識(shí)別。而在等長(zhǎng)編碼中不存在這樣的識(shí)別問題 ）3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)

7、編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（本節(jié)以下將專門討論等長(zhǎng)編碼）（5）編碼速率編碼速率 R=NlogD/L。（單位時(shí)間內(nèi)碼可以攜帶的信息量，反映了碼的能力） 關(guān)于編碼速率的說明： 實(shí)際的編碼速率的計(jì)算公式為R=NlogD/L，似乎可以人為地任 意設(shè)置N和L，因而可以人為地任意設(shè)置編碼速率。事實(shí)并非如此，存在著編碼設(shè)備的編碼速率R0，它是編碼設(shè)備的性能指標(biāo)。這就是說，選擇N和L，必須使得實(shí)際的編碼速率NlogD/L不能超過編碼設(shè)備的編碼速率R0 ：R=NlogD/LR0。3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（6）無錯(cuò)編碼無錯(cuò)編碼 (U1U2UL)的不同事件用

8、不同的碼字來表示。能夠?qū)崿F(xiàn)無錯(cuò)編碼的充要條件是DNKL。 （即編碼速率R=NlogD/LlogK）（7）有錯(cuò)編碼有錯(cuò)編碼 (U1U2UL)的有些不同事件用相同的碼字來表示。（8）有錯(cuò)編碼的譯碼方法與有錯(cuò)編碼的譯碼方法與 “譯碼錯(cuò)誤譯碼錯(cuò)誤”概率概率 當(dāng)使用有錯(cuò)編碼時(shí)，必須給出譯碼方法（即：一個(gè)碼字可能表示幾個(gè)不同的事件，究竟翻譯成哪個(gè)事件）?！白g碼錯(cuò)誤”的概率定義為pe= P(U1U2UL)=(u1u2uL)| (u1u2uL)的碼字在譯碼時(shí)并不譯為(u1u2uL)。3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（9）在無錯(cuò)編碼的前提下，編碼的最低代價(jià)在無錯(cuò)編碼的前提

9、下，編碼的最低代價(jià)n當(dāng)RlogK時(shí)，能夠?qū)崿F(xiàn)無錯(cuò)編碼。 （DNKL）n當(dāng)RH(U1)時(shí)，無論怎樣編碼都是有錯(cuò)編碼。這是因?yàn)镽H(U1)logK。 （DNKL） （如果H(U1)=logK，則以上兩種情形已經(jīng)概括了全部情形。但如果H(U1)RH(U1)時(shí)，雖然無論怎樣編碼都是有錯(cuò)編碼，但可以適當(dāng)?shù)鼐幋a和譯碼使譯碼錯(cuò)誤的概率pe任意小。這就是所謂“漸進(jìn)無錯(cuò)編碼”。3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（10）漸進(jìn)無錯(cuò)編碼漸進(jìn)無錯(cuò)編碼 （簡(jiǎn)單地說就是：當(dāng)RH(U1)時(shí)，可以適當(dāng)?shù)鼐幋a和譯碼使得譯碼錯(cuò)誤的概率pe任意小。嚴(yán)格地說就是：） 設(shè)給定了編碼設(shè)備的編碼速率設(shè)給

10、定了編碼設(shè)備的編碼速率R0，R0H(U1)，則對(duì)任意的，則對(duì)任意的0，總存在一個(gè)總存在一個(gè)L0，使得對(duì)任意的，使得對(duì)任意的LL0，都有對(duì)，都有對(duì)(U1U2UL)的等長(zhǎng)的等長(zhǎng)編碼和對(duì)應(yīng)的譯碼方法，滿足編碼和對(duì)應(yīng)的譯碼方法，滿足 實(shí)際的編碼速率實(shí)際的編碼速率R=NlogD/LR0， 譯碼錯(cuò)誤的概率譯碼錯(cuò)誤的概率pe。（11）漸進(jìn)無錯(cuò)編碼的原理漸進(jìn)無錯(cuò)編碼的原理 大數(shù)定律。隨著L的增加，(U1U2UL)的所有事件中，某些事件所占的比例越來越?。?），其發(fā)生的概率卻越來越大（1）。 3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（12）不能漸進(jìn)無錯(cuò)的編碼不能漸進(jìn)無錯(cuò)的編碼 （

11、簡(jiǎn)單地說就是：當(dāng)RH(U1)時(shí)，無論怎樣編碼和譯碼都不能使譯碼錯(cuò)誤的概率pe任意小。嚴(yán)格地說就是： ）設(shè)給定了編碼設(shè)備的編碼速率R0，R00有P(U1U2UL)=(u1u2uL)| H(U1)-ILH(U1)+LllLVLI11)(111UHEVLEILllL1121111DVLDVLVLDDILllLllL211LDV3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼取定L0使得則當(dāng)LL0時(shí)總有因此當(dāng)LL0時(shí)總有P(U1U2UL)=(u1u2uL)| H(U1)-ILH(U1)+1-。 201LDV21LDV3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源

12、的等長(zhǎng)編碼定義定義3.2.1(p57) 定義TU(L, )=(u1u2uL)|H(U1)-ILH(U1)+，稱TU(L, )為-典型序列集。稱TU(L, )的補(bǔ)集為非-典型序列集。 （綜上所述有）定理定理3.2.1(信源劃分定理，p58) 對(duì)任意0，取L0使得則當(dāng)LL0時(shí)總有P(U1U2UL)TU(L, )1-。 201LDV3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（簡(jiǎn)記H(U)=H(U1)。設(shè)以下的對(duì)數(shù)都是以2為底的。）系系3.2.1(特定典型序列出現(xiàn)的概率，p58) 若一個(gè)特定的事件(u1u2uL)TU(L, )，則2-L(H(U)+)P(U1U2UL)=(

13、u1u2uL)2-L(H(U)-)。 證明 設(shè)(u1u2uL)TU(L, )。注意到此時(shí) H(U)-ILH(U)+，111log()LLlllILP Uu3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼112211log() ()()LLLP Uu P UuP Uu121 211log()()LLLP UUUuuu所以)()()(1log1)(2121UHuuuUUUPLUHLL)()()(log)(2121UHLuuuUUUPUHLLL)(2121)(2)()(2UHLLLUHLuuuUUUP3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼系系

14、3.2.2(典型序列的數(shù)量，p58) (1-)2L(H(U)-)|TU(L, )|2L(H(U)+)。證明 一方面，121()( , )LUP U UUTL3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼1 21212()( , )()()LULLu uuTLP U UUu uu()( , )2L H UUTL因此，()2( , )L H UUTL1 2()()( , )21LUL H Uu uuTL（由系 ）另一方面，121()( , )(3.2.1)LUP U UUTL由定理3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼1 21212()(

15、 , )()()LULLu uuTLP U UUu uu1 2()()( , )2(1)LUL H Uu uuTL由系()2( , )L H UUTL()( , )12L H UUTL因此，（）（如果采用2元編碼，且對(duì)數(shù)都是以2為底的，則編碼速率為R=NlogD/L=N/L。）補(bǔ)充引理補(bǔ)充引理 設(shè)給定一個(gè)R0H(U)。對(duì)每個(gè)正整數(shù)L，對(duì)應(yīng)地取整數(shù)N=R0L（R0L的下取整）。則N/LR0，limL+N/L=R0。 進(jìn)而，任取正數(shù)(R0 -H(U)/2，存在正整數(shù)L0，當(dāng)LL0時(shí)（1）N/LR0-(R0 -H(U)/2=H(U)+(R0-H(U)/2H(U)+。（2）P(U1U2UL)TU(L,

16、 )1-。 （由定理3.2.1） 3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼定理定理3.2.2(無錯(cuò)編碼正定理，無錯(cuò)編碼正定理，p60) 給定編碼設(shè)備的編碼速率給定編碼設(shè)備的編碼速率R0，R0H(U)。則對(duì)任意的。則對(duì)任意的0，總存在一個(gè)，總存在一個(gè)L0，使得對(duì)任意的，使得對(duì)任意的LL0，都有對(duì)都有對(duì)(U1U2UL)的的2元等長(zhǎng)編碼方法和對(duì)應(yīng)的譯碼方法，元等長(zhǎng)編碼方法和對(duì)應(yīng)的譯碼方法，實(shí)際的編碼速率實(shí)際的編碼速率R滿足滿足 R0RH(U)，“譯碼錯(cuò)誤譯碼錯(cuò)誤”的概率的概率pe L0，取N=LR0，令R=N/L，即N=LR， 則由補(bǔ)充引理的(1)可得 RH(U)+

17、， 從而，2N =2LR 2L(H(U)+) 再由系3.2.2， |TU(L, )|2L(H(U)+) 2LR=2N ，3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼 這就是說， 典型序列集TU(L, )中的事件的個(gè)數(shù)不超過長(zhǎng)度為N的2元碼字的數(shù)量2N。 因此，做如下的編碼：將TU(L, )中的事件用不同的N長(zhǎng)2元碼字來表示，而將TU(L, )以外的事件用一個(gè)固定的N長(zhǎng)2元碼字來表示，這個(gè)固定的N長(zhǎng)2元碼字已經(jīng)用來表示了TU(L, )中的某個(gè)事件。3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼 對(duì)應(yīng)的譯碼：所有的碼字均譯為它所表示的TU(L,

18、 )中的事件。結(jié)論：實(shí)際的編碼速率R滿足R0RH(U)； “譯碼錯(cuò)誤”的概率pe=P(U1U2UL)不屬于TU(L, )=1-P(U1U2UL)TU(L, )H(U)；給定一個(gè)任意小的正數(shù)0；要求：選擇合適的L，N，對(duì)(U1U2UL)進(jìn)行合適的2元N長(zhǎng)編碼，使得 實(shí)際的編碼速率R=N/L滿足RR0； “譯碼錯(cuò)誤”的概率pe。3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼漸進(jìn)無錯(cuò)編碼的步驟漸進(jìn)無錯(cuò)編碼的步驟由U1的概率分布計(jì)算取L滿足 。取整數(shù)N=R0L（R0L下取整）。取典型序列集2111331, ( , )DVDVLDV一般來說，所以KkkkKkkkUHaqaqDV

19、aqaqUH1212111)()(1log)(;)(1log)()()()(1log1)(| )(),(11121UHuqLUHuuuLTLllLU3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼漸進(jìn)無錯(cuò)編碼的步驟漸進(jìn)無錯(cuò)編碼的步驟將TU(L, )中的事件用不同的N長(zhǎng)2元碼字來表示，而將TU(L, )以外的事件用一個(gè)固定的N長(zhǎng)2元碼字來表示，這個(gè)固定的N長(zhǎng)2元碼字已經(jīng)用來表示了TU(L, )中的某個(gè)事件。譯碼時(shí)，所有的碼字均譯為它所表示的TU(L, )中的事件。注解：顯然滿足RR0；| TU(L, ) | 2N，因此碼字足夠用；譯碼錯(cuò)誤的概率為 pe=P(U1U2UL)

20、=(u1u2uL)| (u1u2uL)不屬于TU(L, )0.037587148=H(U1)。希望： 2元編碼的實(shí)際編碼速率RR0； 譯碼錯(cuò)誤的概率不超過。 取=0.1, 找L使得43496.25231DVL3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼 取L=253即可，再取N=R0L=126。 將TU(L, )中的事件用不同的N長(zhǎng)2元碼字來表示，而將TU(L, )以外的事件用一個(gè)固定的N長(zhǎng)2元碼字來表示，這個(gè)固定的N長(zhǎng)2元碼字已經(jīng)用來表示了TU(L, )中的某個(gè)事件。 譯碼時(shí)，所有的碼字均譯為它所表示的TU(L, )中的事件。3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編

21、碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼 注：在本題中， TU(L, )中的事件有更加簡(jiǎn)單的表達(dá)方式。 當(dāng)事件(u1u2uL)中a1的個(gè)數(shù)為k，a2的個(gè)數(shù)為L(zhǎng)-k時(shí)，111log7.9657840.005747( ) 7.9600370.005747LllkLkLq uLLkL031840148. 0960037. 7)()(1log111LkUHuqLLll3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼事件(u1u2uL)屬于典型序列集TU(L, 0.1)；0.17.9600370.0318401480.1；kL0.008562760.01656276 ；LkL00.01

22、656276 ；kL401656276. 00Lk3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)當(dāng)事件(u1u2u253)中a1的個(gè)數(shù)不超過4時(shí)， (u1u2u253)TU(253, 0.1)；否則(u1u2u253)不屬于TU(253, 0.1)。(u1u2u253)TU(253, 0.1)的概率不小于0.9；(u1u2u253)TU(253, 0.1)的個(gè)數(shù)為6 .219253355557444.33355557444.33)1 . 0)(4025322/222占全部事件的比例為；UHLkkC3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼

23、離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼對(duì)L=253，對(duì)應(yīng)地取整數(shù)N=R0L=126。則N/LR0，這就是說2元編碼的實(shí)際編碼速率并未超出編碼設(shè)備的編碼速率。2元編碼的編碼方法： 將TU(253, 0.1)中的事件用不同的126長(zhǎng)碼字表示；將TU(253, 0.1)外的事件用同一個(gè)126長(zhǎng)碼字表示，該碼字已經(jīng)用于表示了TU(253, 0.1)中的一個(gè)事件。 由于|TU(253, 0.1)|233.3555574442126，碼字足夠用。2元編碼的譯碼方法： 將碼字譯為它所表示的TU(253, 0.1)中的事件(u1u2u253) 。于是，譯碼錯(cuò)誤的概率為P(u1u2u253)不屬于TU(253, 0.

24、1)=0.1。3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼取=0.05。找L使得即L=2020。有P(U1U2UL)=(u1u2uL)| -0.05IL-H(U) 0.050.95。另一方面，當(dāng)事件(u1u2uL)中a1的個(gè)數(shù)為k，a2的個(gè)數(shù)為L(zhǎng)-k時(shí)，47968.201931DVL005747. 0960037. 7005747. 0965784. 7LkLkLLkIL031840148. 0960037. 7)(LkUHIL3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼事件(u1u2uL)屬于典型序列集TU(L, 0.05)；當(dāng)且僅當(dāng)

25、-0.05IL-H(U) 0.05；0.057.9600370.0318401480.05；kL0.002281370.01028137 ；LkLLk01028137. 003.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)設(shè)L=2020。此時(shí)0.01028137L=20.7683674。當(dāng)事件(u1u2u2020)中a1的個(gè)數(shù)不超過20時(shí)， (u1u2u2020)TU(2020, 0.05)；否則(u1u2u2020)不屬于TU(2020, 0.05)。(u1u2u2020)TU(2020, 0.05)的概率不小于0.95；(u1u2u2020)

26、TU(2020, 0.05)的個(gè)數(shù)為07.1843202092603896176)01. 0)(200202022/222占全部事件的比例為；UHLkkC3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼對(duì)L=2020，對(duì)應(yīng)地取整數(shù)N=R0L=1010。則N/L=R0，這就是說2元編碼的實(shí)際編碼速率等于編碼設(shè)備的編碼速率。2元編碼的編碼方法： 將TU(2020, 0.05)中的事件用不同的1010長(zhǎng)碼字表示；將TU(2020, 0.05)外的事件用同一個(gè)1010長(zhǎng)碼字表示，該

27、碼字已經(jīng)用于表示了TU(2020, 0.05)中的一個(gè)事件。由于|TU(2020, 0.05)|2176.9260389621010，碼字足夠用。2元編碼的譯碼方法： 將碼字譯為它所表示的TU(2020, 0.05)中的事件(u1u2u2020) 。于是，譯碼錯(cuò)誤的概率為P(u1u2u2020)不屬于TU(2020, 0.05)=0.05。3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼取=0.01。找L使得即L=252435。有P(U1U2UL)=(u1u2uL)| -0.01IL-H(U) 0.010.99。另一方面，當(dāng)事件(u1u2uL)中a1的個(gè)數(shù)為k，a2的個(gè)

28、數(shù)為L(zhǎng)-k時(shí)，96.25243431DVL005747. 0960037. 7005747. 0965784. 7LkLkLLkIL031840148. 0960037. 7)(LkUHIL3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼事件(u1u2uL)屬于典型序列集TU(L, 0.01), 當(dāng)且僅當(dāng)-0.01IL-H(U) 0.01；0.017.9600370.0318401480.01；kLLkL00525628. 000274372. 0當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)692.610961326.8690k3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源

29、的等長(zhǎng)編碼設(shè)L=252435。此時(shí)0.00274372L=692.61096 ； 0.00525628L=1326.8690 。 當(dāng)事件(u1u2u252435)中a1的個(gè)數(shù)不超出閉區(qū)間693，1326內(nèi)時(shí)， (u1u2u252435)TU(252435, 0.01)；否則(u1u2u252435)不屬于TU(252435, 0.01)。(u1u2u252435) TU(252435, 0.01)的概率不小于0.99；(u1u2u252435) TU(252435, 0.01)的個(gè)數(shù)為34.2404222524356617.120126617.12012)01. 0)(132669325243

30、522/222占全部事件的比例為；UHLkkC3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼對(duì)L=252435，對(duì)應(yīng)地取整數(shù)N=R0L=126217。則N/LR0，這就是說2元編碼的實(shí)際編碼速率小于編碼設(shè)備的編碼速率。2元編碼的編碼方法： 將TU(252435, 0.01)中的事件用不同的126217長(zhǎng)碼字表示；將TU(252435, 0.01)外的事件用同一個(gè)126217長(zhǎng)碼字表示，該碼字已經(jīng)用于表示了TU(252435, 0.01)中的一個(gè)事件。由于|TU(252435, 0.01)|212012.66172126217，碼字足夠用。2元編碼的譯碼方法： 將碼字譯

31、為它所表示的TU(252435, 0.01)中的事件(u1u2u252435) 。于是，譯碼錯(cuò)誤的概率為P(u1u2u252435)不屬于TU(252435, 0.01)=0.01。漸進(jìn)無錯(cuò)編碼的步驟漸進(jìn)無錯(cuò)編碼的步驟由U1的概率分布計(jì)算對(duì)給定的錯(cuò)誤控制概率 取L滿足 取整數(shù)N=R0L（R0L下取整）。31DVL KkkkKkkkUHaqaqDVaqaqUH1212111)()(1log)(;)(1log)()(回顧回顧將TU(L, )中的事件用不同的N長(zhǎng)2元碼字來表示，而將TU(L, )以外的事件用一個(gè)固定的N長(zhǎng)2元碼字來表示，這個(gè)固定的N長(zhǎng)2元碼字已經(jīng)用來表示了TU(L, )中的某個(gè)事件。

32、譯碼時(shí)，所有的碼字均譯為它所表示的TU(L, )中的事件。注解：顯然滿足RR0；| TU(L, ) | 2N，因此碼字足夠用；譯碼錯(cuò)誤的概率為 pe=P(U1U2UL)=(u1u2uL)| (u1u2uL)不屬于TU(L, )；一般來說，越小，要求L越大，因此對(duì)應(yīng)的N越大。)()(1log1)(| )(),(11121UHuqLUHuuuLTLllLU取典型序列集練習(xí) 設(shè)以上是一個(gè)離散無記憶信源。若對(duì)其輸出的長(zhǎng)為100的事件序列中含有兩個(gè)和更少個(gè) 的序列提供不同的碼字。(a) 在等長(zhǎng)編碼下，求二元碼的最短碼長(zhǎng)N。(b) 求錯(cuò)誤概率(誤組率)。996. 0004. 021aaUl1an3.2 離

33、散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼3.2 離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼1010019910010029823100( ) 錯(cuò)誤概率為：長(zhǎng)為100的事件序列中 至少含有3個(gè) 的序列出現(xiàn)的概率， 10.9960.9960.004 0.9960.0047.75510ebaPCCC定理定理3.2.2(無錯(cuò)編碼反定理，p60) 設(shè)給定編碼設(shè)備的編碼速率R0，滿足R0qb，其碼字長(zhǎng)度也具有不等式nanb?，F(xiàn)在將事件a和b交換碼字，其它事件的碼字保持不變。此時(shí)2元異字頭碼S 變成新的2元異字頭碼T。3.4 最佳不等長(zhǎng)編碼最佳不等長(zhǎng)編碼（1）碼S

34、 中事件a和b的碼字對(duì)平均碼長(zhǎng)的貢獻(xiàn)為qana+qbnb；（2）碼T中事件a和b的碼字對(duì)平均碼長(zhǎng)的貢獻(xiàn)為qanb+qbna。(qana+qbnb)-(qanb+qbna)=(qa-qb)(na-nb)0。這就是說，碼S 的平均碼長(zhǎng)碼T 的平均碼長(zhǎng)。因而碼S 不是最佳2元異字頭碼。用反證法已經(jīng)證明了補(bǔ)充引理2。 3.4 最佳不等長(zhǎng)編碼最佳不等長(zhǎng)編碼補(bǔ)充引理補(bǔ)充引理2 設(shè)信源隨機(jī)變量U的最佳最佳2元異字頭碼元異字頭碼S ，則最長(zhǎng)的碼字最長(zhǎng)的碼字至少有兩個(gè)至少有兩個(gè)。證明 如果2元異字頭碼S 的最長(zhǎng)的碼字竟然只有一個(gè)。設(shè)這個(gè)碼字為c，是事件a的碼字?，F(xiàn)在將c的最后一位去掉，成為c，將c仍然作為事件a

35、的碼字。其它事件的碼字保持不變。此時(shí)2元異字頭碼S 變成新的2元碼T。注意到以下兩點(diǎn)：（1）碼T仍然是2元異字頭碼；（2）碼S 的平均碼長(zhǎng)碼T 的平均碼長(zhǎng)。因而碼S 不是最佳2元異字頭碼。用反證法已經(jīng)證明了補(bǔ)充引理3。3.4 最佳不等長(zhǎng)編碼最佳不等長(zhǎng)編碼補(bǔ)充引理補(bǔ)充引理3 最佳最佳2元異字頭碼元異字頭碼S可以滿足以下兩條：（1）概率最小的兩個(gè)事件碼字最長(zhǎng)，且長(zhǎng)度相等；）概率最小的兩個(gè)事件碼字最長(zhǎng)，且長(zhǎng)度相等；（2）它們的碼字僅僅最后一位不同。）它們的碼字僅僅最后一位不同。證明 取概率最小的事件a。在剩下的事件中取概率最小的事件b。根據(jù)補(bǔ)充引理1和補(bǔ)充引理2，事件a和事件b的碼字最長(zhǎng)，且長(zhǎng)度相等

36、。這就是說，最佳2元異字頭碼S顯然滿足第（1）條。3.4 最佳不等長(zhǎng)編碼最佳不等長(zhǎng)編碼關(guān)于第（2）條，分以下三種情形來討論：情形一 事件a和事件b的碼字僅僅最后一位不同。情形二 事件a和事件b的碼字不是僅僅最后一位不同，但有第三個(gè)事件c，其碼字與事件a的碼字僅僅最后一位不同。情形三 事件a和事件b的碼字不是僅僅最后一位不同，也沒有第三個(gè)事件c，其碼字與事件a的碼字僅僅最后一位不同。3.4 最佳不等長(zhǎng)編碼最佳不等長(zhǎng)編碼3.4 最佳不等長(zhǎng)編碼最佳不等長(zhǎng)編碼補(bǔ)充引理補(bǔ)充引理4 信源隨機(jī)變量的最佳2元異字頭碼，一定是該信源隨機(jī)變量的最佳2元不等長(zhǎng)碼。（換句話說，尋找最佳尋找最佳2元不等長(zhǎng)元不等長(zhǎng)碼，只

37、要尋找最佳碼，只要尋找最佳2元異字頭碼即可元異字頭碼即可）證明 設(shè)最佳2元異字頭碼的碼字長(zhǎng)度依次為設(shè)最佳2元不等長(zhǎng)碼的碼字長(zhǎng)度依次為12, ,.Knnn12, ,.Knnn首先有：11KKkkkkkkq nq n3.4 最佳不等長(zhǎng)編碼最佳不等長(zhǎng)編碼取碼字長(zhǎng)度依次為122221Kmmm其次，對(duì)于任意滿足Craft不等式的碼字長(zhǎng)度依次為m1、m2、mK的2元不等長(zhǎng)碼，總存在碼字長(zhǎng)度依次為m1、m2、mK的2元異字頭碼。1122, ,KKmnmnmn2元不等長(zhǎng)碼，3.4 最佳不等長(zhǎng)編碼最佳不等長(zhǎng)編碼則也存在具有相同碼字長(zhǎng)度的2元異字頭碼，1122, ,KKmnmnmn而12, ,Knnn是最佳的2元

38、異字頭碼的碼長(zhǎng)故有11KKkkkkkkq nq n引理得證。3.4 最佳不等長(zhǎng)編碼最佳不等長(zhǎng)編碼補(bǔ)充定理補(bǔ)充定理 設(shè)信源隨機(jī)變量U有K個(gè)事件， K3。(1) 取出兩個(gè)概率最小的事件：事件a和事件b。(2) 將事件a與事件b合并成一個(gè)事件e， e的概率為事件a與事件b的概率之和；而將信源隨機(jī)變量U的其它事件和其對(duì)應(yīng)的概率保持不變。這樣得到了新的信源隨機(jī)變量U。(3) 找到U的一個(gè)最佳2元異字頭碼R。(4) 將碼R中事件e的碼字后面分別添加0和1，分別作為事件a和事件b各自的碼字；而將碼R中其它事件的碼字保持不變。這樣得到 了U的2元碼R。則：碼R是U的最佳2元異字頭碼。3.4 最佳不等長(zhǎng)編碼最佳

39、不等長(zhǎng)編碼證明 首先說明， 碼R是U的2元異字頭碼。碼R中，事件a的碼字不是事件b的碼字的字頭，事件b的碼字也不是事件a的碼字的字頭. (兩個(gè)碼字長(zhǎng)度相同，僅僅最后一位不同)事件a的碼字或事件b的碼字不是任何其它碼字的字頭(因?yàn)榇aR中事件e的碼字不是任何其它碼字的字頭)任何其它碼字不是事件a的碼字或事件b的碼字的字頭。（因?yàn)槭录或事件b的碼字的字頭，要么是碼字本身，要么是碼R中事件e的碼字的字頭）綜上所述，碼R是U的2元異字頭碼。3.4 最佳不等長(zhǎng)編碼最佳不等長(zhǎng)編碼其次，任取U的2元異字頭碼S，要證明碼R的平均碼長(zhǎng)碼S的平均碼長(zhǎng)。對(duì)碼S逐步進(jìn)行如下的三次變換。3.4 最佳不等長(zhǎng)編碼最佳不等長(zhǎng)

40、編碼3.4 最佳不等長(zhǎng)編碼最佳不等長(zhǎng)編碼容易看出，碼T、碼V、碼W也都是信源隨機(jī)變量U的2元異字頭碼。將碼W中事件a的碼字去掉最后一位，當(dāng)作合并事件e的碼字；將碼W中其它事件的碼字保持不變。這樣得到了合并信源U的2元碼W。容易看出碼W是U的2元異字頭碼，因此碼碼R的平均碼長(zhǎng)的平均碼長(zhǎng)碼碼W的平均碼長(zhǎng)。的平均碼長(zhǎng)。3.4 最佳不等長(zhǎng)編碼最佳不等長(zhǎng)編碼另一方面，碼碼R的平均碼長(zhǎng)的平均碼長(zhǎng)=碼碼R的平均碼長(zhǎng)的平均碼長(zhǎng)+事件事件a的概率的概率+事件事件b的概率；的概率；碼碼W的平均碼長(zhǎng)的平均碼長(zhǎng)=碼碼W的平均碼長(zhǎng)的平均碼長(zhǎng)+事件事件a的概率的概率+事件事件b的概率。的概率。所以: 碼R的平均碼長(zhǎng)碼W的

41、平均碼長(zhǎng)碼V的平均碼長(zhǎng)碼T的平均碼長(zhǎng)碼S的平均碼長(zhǎng)。補(bǔ)充定理得證。3.4 最佳不等長(zhǎng)編碼最佳不等長(zhǎng)編碼 補(bǔ)充定理給出了一種構(gòu)造信源隨機(jī)變量U的最佳2元異字頭碼的方法：(1) 取出兩個(gè)概率最小的事件a和事件b，分別標(biāo)號(hào)為0和1；(2) 然后將事件a和事件b合并成事件e，將信源隨機(jī)變量U合并成U；(3) 尋找U的最佳2元異字頭碼；(4) 然后將該碼中事件e的碼字后面分別添加事件a和事件b的標(biāo)號(hào) （0和1），分別成為事件a和事件b的碼字。這種構(gòu)造方法正是2元Huffman編碼。3.4 最佳不等長(zhǎng)編碼最佳不等長(zhǎng)編碼定理定理 對(duì)信源隨機(jī)變量對(duì)信源隨機(jī)變量U的的2元元Huffman編碼是最佳編碼是最佳2元異字頭碼，元異字頭碼，因而是在唯一可譯前提下的最佳因而是在唯一可譯前提下的最佳2元不等長(zhǎng)編碼。元不等長(zhǎng)編碼。