信息論與編碼2016(第3章)

1、信息理論與編碼朱仁祥電子與信息工程學(xué)院12022-6-302第三章：第三章：信源編碼離散信源無失真編碼3.1 信源及其分類信源及其分類3.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼3.3 離散無記憶（簡單）信源的不等長編碼離散無記憶（簡單）信源的不等長編碼3.4 最佳不等長編碼最佳不等長編碼3n通信的根本問題是將信源的輸出在接收端精確地或近似地重新出來。n兩個問題： 1. 信源的輸出應(yīng)如何描述，即如何計算它產(chǎn)生的信息量。 2. 如何表示信源的輸出，即信源編碼問題。2022-6-304n無失真信源編碼無失真信源編碼 保證信源產(chǎn)生的全部信息無損地遞給信宿；n限定失真的信源

2、編碼限定失真的信源編碼 不要求完全精確地復(fù)制出信源的輸出，但要滿足一定的保真度準(zhǔn)則。53.1 信源及其分類信源及其分類信源的概念信源的概念 （直觀地理解，信源就是信息的來源。但是必須要注意兩點）：n在一個固定的時刻，信源發(fā)出的是一個隨機(jī)變量。在一個固定的時刻，信源發(fā)出的是一個隨機(jī)變量。n隨著時間的延續(xù)，信源發(fā)出一個又一個隨機(jī)變量，稱之為一隨著時間的延續(xù)，信源發(fā)出一個又一個隨機(jī)變量，稱之為一個隨機(jī)過程。個隨機(jī)過程。（因此，一般的信源種類太多，其統(tǒng)計性質(zhì)太復(fù)雜。怎樣做工程實用的簡化？） 63.1 信源及其分類信源及其分類離散信源離散信源 信源每隔一個定長時間段就發(fā)出一個隨機(jī)變量；隨著時間的延續(xù)，信

3、源發(fā)出的是隨機(jī)變量序列 U-2U-1U0U1U2其中nUk為第k個時間段發(fā)出的隨機(jī)變量；n每個Uk都是一個離散型的隨機(jī)變量。3.1 信源及其分類信源及其分類離散無記憶信源離散無記憶信源 離散無記憶信源是這樣的離散信源：隨機(jī)變量、U-2、U-1、U0、U1、U2、相互獨立。離散無記憶簡單信源離散無記憶簡單信源 離散無記憶簡單信源是這樣的離散無記憶信源：隨機(jī)變量、U-2、U-1、U0、U1、U2、具有相同的概率分布。 783.1 信源及其分類信源及其分類小 結(jié)離散無記憶簡單信源離散無記憶簡單信源 就是時間離散、事件離散、各隨機(jī)變量獨立同分布的信源. 課程學(xué)習(xí)所面對的信源將主要是離散無記憶簡單信源.

4、3.1 信源及其分類信源及其分類一般的信源一般的信源 連續(xù)信源：有時間連續(xù)的信源，也有事件連續(xù)的信源；有記憶信源：信源在不同時刻發(fā)出的隨機(jī)變量相互依賴；有限記憶信源：在有限時間差內(nèi)的信源隨機(jī)變量相互依賴；非簡單信源：信源在不同時刻發(fā)出的隨機(jī)變量具有不同的概率分布。馬爾可夫信源：信源隨機(jī)過程是馬爾可夫過程。 93.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼編碼編碼實質(zhì)上是對信源的原始符號信源的原始符號按一定的數(shù)學(xué)數(shù)學(xué)規(guī)則規(guī)則進(jìn)行的一種變換變換，映射成碼字碼字以適合信道傳適合信道傳輸輸。102022-6-30113.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信

5、源的等長編碼n設(shè)有一個離散無記憶簡單信源，信源發(fā)出的隨機(jī)變量序列為：U-2U-1U0U1U2。設(shè)信源隨機(jī)變量U1的事件有K個：a1, a2, , aK，則L維信源隨機(jī)向量(U1U2UL)的事件有KL個：(u1u2uL)|其中每個分量ul跑遍a1, a2, , aK。3.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼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)12133.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼n設(shè)有

6、一個含D個字母的字母表。對于(U1U2UL)的每一個事件(u1u2uL)，都用一個字母串(c1c2)來表示。這種表示方法稱為這種表示方法稱為D元編碼元編碼；每一個事件每一個事件(u1u2uL)所對應(yīng)的字母串所對應(yīng)的字母串(c1c2)稱稱為一個為一個碼字碼字。143.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼例例：離散無記憶簡單信源發(fā)出的隨機(jī)變量序列為：U-2U-1U0U1U2，其中U1的事件有3個：晴, 云, 陰. 將(U1U2)進(jìn)行2元編碼.3.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼(U1U2)有9個事件（晴晴），（晴云），（晴陰），（

7、云晴），（云云），（云陰），（陰晴），（陰云）， （陰陰）153.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼用字母表0, 1對(U1U2)的事件進(jìn)行2元編碼如下：（晴晴）0000，（晴云）0001，（晴陰）0011，（云晴）0100，（云云）0101，（云陰）0111，（陰晴）1100，（陰云）1101，（陰陰）1111。16173.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼n如果限定所有碼字的長度都為N（即每個碼字都是一個長度為N的字母串，或稱為N維向量），則稱此編碼為等長編碼等長編碼，能夠選擇的不同碼字的個數(shù)為DN。183.2 離散無記憶

8、（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼n如果限定每個碼字的長度都N（即每個碼字都是一個長度N的字母串），則稱此編碼為不等長編碼不等長編碼，能夠選擇的不同碼字的個數(shù)為D1+D2+DN=D(DN-1)/(D-1)。193.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼問題：在不等長編碼中，能否同時使用 D(DN-1)/(D-1)個不同的碼字？u一個長度為2的字母串究竟是兩個長度為1的碼字相連，還是一個長度為2的碼字？無法識別。u在等長編碼中不存在這樣的識別問題。203.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼對等長碼對等長碼n若對每

9、個消息都至少有一個碼字與之對應(yīng)，且不同的消息對應(yīng)不同的碼字，則稱這樣的碼為單義可譯碼或唯一可譯碼。n在無擾傳輸時，單義可譯碼的譯碼錯誤概率為0，又稱為無錯編碼。213.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼n無錯編碼無錯編碼 (U1U2UL)的不同事件用不同的碼字來表示。 消息集是消息集是 K元字母表元字母表 L長消息序長消息序列，編碼成列，編碼成 D元元 N長碼字長碼字。n能夠?qū)崿F(xiàn)無錯編碼的充要條件是DNKL 即 NlogD LlogK 或 NlogD/L logK (下界)等長碼基本問題 C2=000,001,100,101,111，K2=3 code/sig

10、C1=00,01,10,11,10，K1=2 code/sig等長碼特點：等長碼特點：Ki=K要求：要求：xiyj 高效高效問題：問題：K=? 12345x x x x xX例: 11111P 2481616等長編碼等長編碼: 要求要求:可能的碼字?jǐn)?shù)可能的碼字?jǐn)?shù)消息數(shù)消息數(shù)對基本信源編碼對基本信源編碼： xiX=( x1,x2,xn )-yj 碼字?jǐn)?shù)：碼字?jǐn)?shù)：mK m Kn (Klogmn) （對例（對例1，n=5, 要求：要求：2K5，即，即K 3）對對L長源編碼長源編碼： aiXL=(a1,a2,anL)yj m KnL (K/Llogmn)例（續(xù)）例（續(xù)）X的三次擴(kuò)展：的三次擴(kuò)展： X3

11、:a1=(x1 x1 x1),a53 =(x5 x5 x5) 則，則，nL=53=125種種128=27 K=7 code/3sigs 平均碼長：平均碼長：K/L=7/3=2.33 code/sig K2 結(jié)論結(jié)論: 等長碼碼長要求等長碼碼長要求K/L logmn(保證唯一可譯碼保證唯一可譯碼,無失真無失真) logmn為下限為下限 擴(kuò)展信源編碼的平均碼長擴(kuò)展信源編碼的平均碼長基本源編碼的平均碼長基本源編碼的平均碼長253.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼n編碼速率編碼速率 R=NlogD/Ln實現(xiàn)無錯編碼無錯編碼的充要條件是 編碼速率R=NlogD/Llo

12、gK263.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼 n有錯編碼有錯編碼 (U1U2UL)的有些不同事件用相同的碼字來表示。273.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼編碼速率的說明編碼速率的說明 實際的編碼速率的計算公式為R=NlogD/L，似乎可以人為地任意設(shè)置N和L，因而可以人為地任意設(shè)置編碼速率。? 3.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼 事實并非如此，存在著編碼設(shè)備的編碼速率R0，它是編碼設(shè)備的性能指標(biāo). 這就是說，選擇N和L，必須使得實際的編碼速率 NlogD/L 不能超過編碼設(shè)備的編碼速

13、率R0 ：R=NlogD/LR0 28293.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼n有錯編碼的譯碼方法與有錯編碼的譯碼方法與 “譯碼錯誤譯碼錯誤”概率概率 當(dāng)使用有錯編碼時，必須給出譯碼方法（即：一個碼字可能表示幾個不同的事件，究竟翻譯成哪個事件）。 “譯碼錯誤”的概率定義為 pe= P(U1U2UL)=(u1u2uL) | (u1u2uL)的碼字在譯碼時并不譯為(u1u2uL)。303.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼n在無錯編碼的前提下，編碼的最低代價在無錯編碼的前提下，編碼的最低代價p當(dāng)RlogK時，能夠?qū)崿F(xiàn)無錯編碼。

14、（DNKL）p當(dāng)RH(U1)時，無論怎樣編碼都是有錯編碼。 這是因為RH(U1)logK。 （DNKL） 如果H(U1)=logK，則以上兩種情形已經(jīng)概括了全部情形。但如果H(U1)RH(U1)時，雖然無論怎樣編碼都是有錯編碼，但可以適當(dāng)?shù)鼐幋a和譯碼使譯碼錯誤的概率pe任意小。這就是所謂“漸進(jìn)無錯編碼”。313.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼logKH(U1)RRR無錯編碼無錯編碼不能漸進(jìn)無錯編碼不能漸進(jìn)無錯編碼漸進(jìn)無錯編碼漸進(jìn)無錯編碼 323.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼n漸進(jìn)無錯編碼漸進(jìn)無錯編碼 簡單地說就是：當(dāng)

15、RH(U1)時，可以適當(dāng)?shù)鼐幋a和譯碼使得譯碼錯誤的概率pe任意小。333.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼n漸進(jìn)無錯編碼漸進(jìn)無錯編碼 嚴(yán)格地說就是： 設(shè)給定了編碼設(shè)備的編碼速率設(shè)給定了編碼設(shè)備的編碼速率R0，R0H(U1)。則對任意的則對任意的0，總存在一個，總存在一個L0，使得對任意，使得對任意的的LL0，都有對，都有對(U1U2UL)的等長編碼和對應(yīng)的等長編碼和對應(yīng)的譯碼方法，滿足的譯碼方法，滿足 實際的編碼速率實際的編碼速率R=NlogD/LR0， 譯碼錯誤的概率譯碼錯誤的概率pe。343.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等

16、長編碼n漸進(jìn)無錯編碼的原理漸進(jìn)無錯編碼的原理 大數(shù)定律。隨著L的增加，(U1U2UL)的所有事件中，某些事件所占的比例越來越?。?），其發(fā)生的概率卻越來越大（1）。353.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼n不能漸進(jìn)無錯的編碼不能漸進(jìn)無錯的編碼 簡單地說就是：當(dāng)RH(U1)時，無論怎樣編碼和譯碼都不能使譯碼錯誤的概率pe 任意小。 嚴(yán)格地說就是：設(shè)給定了編碼設(shè)備的編碼速率R0，R00有P(U1U2UL)=(u1u2uL)| H(U1)-ILH(U1)+LllLVLI11)(111UHEVLEILllL1121111DVLDVLVLDDILllLllL211LD

17、V383.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼取定L0使得則當(dāng)LL0時總有因此當(dāng)LL0時總有P(U1U2UL)=(u1u2uL)| H(U1)-ILH(U1)+1-。 201LDV21LDV393.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼定義定義3.2.1(p50) 定義TU(L, )=(u1u2uL)|H(U1)-ILH(U1)+，稱TU(L, )為-典型序列集。稱TU(L, )的補集為非-典型序列集。 （綜上所述有）定理定理3.2.1(信源劃分定理，p51) 對任意0，取L0使得則當(dāng)LL0時總有P(U1U2UL)TU(L, )1-

18、。 120DVL2022-6-30403.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼（簡記H(U)=H(U1)。設(shè)以下的對數(shù)都是以2為底的。）系系3.2.1(特定典型序列出現(xiàn)的概率，p51) 若一個特定的事件(u1u2uL)TU(L, )，則2-L(H(U)+)P(U1U2UL)=(u1u2uL)2-L(H(U)-)。 證明 設(shè)(u1u2uL)TU(L, )。注意到此時H(U)-ILH(U)+，)()(1log1)()()(1log1)(1log1212122111LLLLLlllLuuuUUUPLuUPuUPuUPLuUPLI413.2 離散無記憶（簡單）信源的等長

19、編碼離散無記憶（簡單）信源的等長編碼所以)()()(1log1)(2121UHuuuUUUPLUHLL)()()(log)(2121UHLuuuUUUPUHLLL)(2121)(2)()(2UHLLLUHLuuuUUUP423.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼系系3.2.2(典型序列的數(shù)量，p51) (1-)2L(H(U)-)|TU(L, )|2L(H(U)+)。證明 一方面，)()(),()()(),()(2121212),(),(212)()(),()(12121UHLUUUHLLTuuuUHLLTuuuLLULLTLTuuuUUUPLTUUUPULUL

20、因此，）（由系433.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼另一方面，)()(),()()(),()(21212121),(),(2) 1(2)()() 1 . 2 . 3(),()(12121UHLUUUHLLTuuuUHLLTuuuLLULLTLTuuuUUUPLTUUUPULUL）（因此，由系由定理443.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼（如果采用2元編碼，且對數(shù)都是以2為底的，則編碼速率為R=NlogD/L=N/L。）補充引理補充引理 設(shè)給定一個R0H(U)。對每個正整數(shù)L，對應(yīng)地取整數(shù)N=R0L（R0L的下取整）。則N

21、/LR0，limL+N/L=R0。任取正數(shù)(R0 -H(U)/2，存在正整數(shù)L0，當(dāng)LL0時（1）N/LR0-(R0 -H(U)/2=H(U)+(R0-H(U)/2H(U)+。（2）P(U1U2UL)TU(L, )1-。 （由定理3.2.1） 453.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼定理定理3.2.2(無錯編碼正定理，無錯編碼正定理，p53) 給定編碼設(shè)備的編碼速率給定編碼設(shè)備的編碼速率R0，R0H(U)。則對任意的則對任意的0，總存在一個，總存在一個L0，使得對任，使得對任意的意的LL0，都有對，都有對(U1U2UL)的的2元等長編元等長編碼方法和對應(yīng)的譯

22、碼方法，碼方法和對應(yīng)的譯碼方法，實際的編碼速率實際的編碼速率R滿足滿足R0RH(U)，“譯碼錯誤譯碼錯誤”的概率的概率peH(U)；“譯碼錯誤”的概率pe=P(U1U2UL)不屬于TU(L, )=1-P(U1U2UL)TU(L, )。得證。 定理定理3.2.2(無錯編碼反定理，p53) 設(shè)給定編碼設(shè)備的編碼速率R0，滿足R0H(U)；給定一個任意小的正數(shù)0；要求：選擇合適的L，N，對(U1U2UL)進(jìn)行合適的2元N長編碼，使得實際的編碼速率R=N/L滿足RR0；“譯碼錯誤”的概率pe。49漸進(jìn)無錯編碼的步驟漸進(jìn)無錯編碼的步驟由U1的概率分布計算取L滿足 。取整數(shù)N=R0L（R0L下取整）。取典

23、型序列集31DVL KkkkKkkkUHaqaqDVaqaqUH1212111)()(1log)(;)(1log)()()()(1log1)(| )(),(11121UHuqLUHuuuLTLllLU50漸進(jìn)無錯編碼的步驟漸進(jìn)無錯編碼的步驟將TU(L, )中的事件用不同的N長2元碼字來表示，而將TU(L, )以外的事件用一個固定的N長2元碼字來表示，這個固定的N長2元碼字已經(jīng)用來表示了TU(L, )中的某個事件。譯碼時，所有的碼字均譯為它所表示的TU(L, )中的事件。（注解：顯然滿足RR0；| TU(L, ) | 2N，因此碼字足夠用；譯碼錯誤的概率為pe=P(U1U2UL)=(u1u2uL

24、)| (u1u2uL)不屬于TU(L, )0.037587148=H(U1)。希望：2元編碼的實際編碼速率RR0；譯碼錯誤的概率不超過。其中取=0.1。找L使得43496.25231DVL2022-6-30533.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼取L=253即可。再取N=R0L=126。將TU(L, )中的事件用不同的N長2元碼字來表示，而將TU(L, )以外的事件用一個固定的N長2元碼字來表示，這個固定的N長2元碼字已經(jīng)用來表示了TU(L, )中的某個事件。譯碼時，所有的碼字均譯為它所表示的TU(L, )中的事件。另一方面， TU(L, )中的事件有更加簡

25、單的表達(dá)方式。當(dāng)事件(u1u2uL)中a1的個數(shù)為k，a2的個數(shù)為L-k時，005747. 0960037. 7005747. 0965784. 7)(1log11LkLkLLkuqLLll031840148. 0960037. 7)()(1log111LkUHuqLLll543.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼事件(u1u2uL)屬于典型序列集TU(L, 0.1)；當(dāng)且僅當(dāng)；當(dāng)且僅當(dāng)1 . 0031840148. 0960037. 71 . 0Lk；當(dāng)且僅當(dāng)LkL01656276. 000856276. 0；當(dāng)且僅當(dāng)Lk01656276. 00401656

26、276. 00Lk553.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼當(dāng)事件(u1u2u253)中a1的個數(shù)不超過4時， (u1u2u253)TU(253, 0.1)；否則(u1u2u253)不屬于TU(253, 0.1)。(u1u2u253)TU(253, 0.1)的概率不小于0.9；(u1u2u253)TU(253, 0.1)的個數(shù)為6 .219253355557444.33355557444.33)1 . 0)(4025322/222占全部事件的比例為；UHLkkC563.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼對L=253，對應(yīng)地取整

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

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

29、當(dāng)05. 0031840148. 0960037. 705. 0Lk；當(dāng)且僅當(dāng)LkL01028137. 000228137. 0Lk01028137. 00593.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼設(shè)L=2020。此時0.01028137L=20.7683674。當(dāng)事件(u1u2u2020)中a1的個數(shù)不超過20時， (u1u2u2020)TU(2020, 0.05)；否則(u1u2u2020)不屬于TU(2020, 0.05)。(u1u2u2020)TU(2020, 0.05)的概率不小于0.95；(u1u2u2020)TU(2020, 0.05)的個數(shù)為2

30、0() 0.01)176.9260389620200176.9260389620201843.07222/22kL H UkC；占全部事件的比例 603.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼對L=2020，對應(yīng)地取整數(shù)N=R0L=1010。則N/L=R0，這就是說2元編碼的實際編碼速率等于編碼設(shè)備的編碼速率。2元編碼的編碼方法： 將TU(2020, 0.05)中的事件用不同的1010長碼字表示；將TU(2020, 0.05)外的事件用同一個1010長碼字表示，該碼字已經(jīng)用于表示了TU(2020, 0.05)中的一個事件。由于|TU(2020, 0.05)|217

31、6.9260389621010，碼字足夠用。2元編碼的譯碼方法： 將碼字譯為它所表示的TU(2020, 0.05)中的事件(u1u2u2020) 。于是，譯碼錯誤的概率為P(u1u2u2020)不屬于TU(2020, 0.05)=0.05。613.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼取=0.01。找L使得即L=252435。有P(U1U2UL)=(u1u2uL)| -0.01IL-H(U) 0.010.99。另一方面，當(dāng)事件(u1u2uL)中a1的個數(shù)為k，a2的個數(shù)為L-k時，96.25243431DVL005747. 0960037. 7005747. 09

32、65784. 7LkLkLLkIL031840148. 0960037. 7)(LkUHIL623.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼事件(u1u2uL)屬于典型序列集TU(L, 0.01)；當(dāng)且僅當(dāng)-0.01IL-H(U) 0.01；當(dāng)且僅當(dāng)；當(dāng)且僅當(dāng)01. 0031840148. 0960037. 701. 0LkLkL00525628. 000274372. 02022-6-30633.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源的等長編碼設(shè)L=252435。此時0.00274372L=692.61096 ； 0.00525628L=132

33、6.8690 。 當(dāng)事件(u1u2u252435)中a1的個數(shù)不超出閉區(qū)間693，1326內(nèi)時， (u1u2u252435)TU(252435, 0.01)；否則(u1u2u252435)不屬于TU(252435, 0.01)。(u1u2u252435) TU(252435, 0.01)的概率不小于0.99；(u1u2u252435) TU(252435, 0.01)的個數(shù)為34.2404222524356617.120126617.12012)01. 0)(132669325243522/222占全部事件的比例為；UHLkkC643.2 離散無記憶（簡單）信源的等長編碼離散無記憶（簡單）信源

34、的等長編碼對L=252435，對應(yīng)地取整數(shù)N=R0L=126217。則N/LR0，這就是說2元編碼的實際編碼速率小于編碼設(shè)備的編碼速率。2元編碼的編碼方法： 將TU(252435, 0.01)中的事件用不同的126217長碼字表示；將TU(252435, 0.01)外的事件用同一個126217長碼字表示，該碼字已經(jīng)用于表示了TU(252435, 0.01)中的一個事件。由于|TU(252435, 0.01)|212012.6617=1-epsilon） +非典型序列集（低概率集）；2. 將典型序列集中的信源序列一一編碼（無錯編碼），而將非典型序列集中的信源序列編碼成剛才的一個碼字；3. 典型序

35、列集勢約為2LH(U)，占KL少, 非典型序列集勢占多。lbmLKH(X)KH(X)RH(X)Le e2 22 22 22 2p p) )( (1 1( (X X) )H HL L22i)()( )DI(xiixIExIE2n1i2ii2H(X)lbp(xp(x注意注意: 適用于適用于DMS及無記憶平穩(wěn)信源及無記憶平穩(wěn)信源 平均碼長下限：平均碼長下限： 基本方法：基本方法：L長源、等長編碼長源、等長編碼 對等長編碼對等長編碼,若要實現(xiàn)幾乎無失真編碼若要實現(xiàn)幾乎無失真編碼,則信源長度必滿足則信源長度必滿足:LPe則，一定，若要求、已知,H(X)其中其中:)(_XHKL,eP 2 22 2( (1

36、 1 - - ) )H H( (X X) )L L當(dāng)當(dāng)Pe10-5則有：則有： =0.5 得得L71687 =0.8 得得L1146990 =0.9 得得L5806641 =0.96 得得L41291672 進(jìn)進(jìn)行行等等長長編編碼碼 41 43x xPX DMS 例3.21解：解：H(X)=0.811 bit/sig 信源方差信源方差DI(xi)=EI2(xi)EI(xi)2=0.4715n等長碼的缺點：平均碼長太長等長碼的缺點：平均碼長太長L無法實現(xiàn)無法實現(xiàn)變長碼的特點：每個碼字長度可不同變長碼的特點：每個碼字長度可不同要求：惟一可譯要求：惟一可譯693.3 離散無記憶（簡單）信源的不等長編

37、碼離散無記憶（簡單）信源的不等長編碼（順序地敘述以下的概念）（1）不等長編碼的優(yōu)越性不等長編碼的優(yōu)越性 總體上減少碼字的長度。（2）不等長編碼的特殊問題不等長編碼的特殊問題 唯一可譯性，或者叫做可識別性。對于一個碼，如果存在一種譯碼方法，使任意若干個碼字所組成的字母串只能唯一地被翻譯成這幾個碼字所對應(yīng)的事件序列。這個碼就被稱為是唯一可譯的。解決方案：適當(dāng)?shù)鼐幋a，使得每個碼字都具有識別標(biāo)記。（注解：一個唯一可譯的、碼字長度不超過N的D元碼，其碼字個數(shù)小于D(DN-1)/(D-1)個。這是因為兩個碼字c(1)和c(2) 連接成的字母串c(1)c(2) 不能是碼字）703.3 離散無記憶（簡單）信源

38、的不等長編碼離散無記憶（簡單）信源的不等長編碼平均碼字長度。設(shè)信源隨機(jī)變量U的概率分布為ak, q(ak), k=1K，事件ak對應(yīng)的碼字長度為nk，則平均碼字長度為希望 小。解決方案：概率大的事件用短碼字。實時譯碼和容量限制。Kkkkaqnn1)(n713.3 離散無記憶（簡單）信源的不等長編碼離散無記憶（簡單）信源的不等長編碼唯一可譯性的兩種解決方法唯一可譯性的兩種解決方法定義定義3.3.2(p55) 若事件與碼字一一對應(yīng)；每個碼字的開頭部分都是一個相同的字母串；這個字母串僅僅出現(xiàn)在碼字的開頭，不出現(xiàn)在碼字的其它部位，也不出現(xiàn)在兩個碼字的結(jié)合部。則稱這個字母串為逗號，稱此碼為逗點碼逗點碼。

39、定義定義3.3.4(p55) 若事件與碼字一一對應(yīng)；每個碼字都不是另一個碼字的開頭部分（字頭）。則稱此碼為異字頭碼異字頭碼。723.3 離散無記憶（簡單）信源的不等長編碼離散無記憶（簡單）信源的不等長編碼注解注解逗點碼顯然是唯一可譯的，識別碼字的方法為：見到逗號就識別為一個碼字的開始見到逗號就識別為一個碼字的開始。異字頭碼也是唯一可譯的，識別碼字的方法為：見到一個碼字就識別為一個碼字見到一個碼字就識別為一個碼字。（許多具體的異字頭碼有更加簡便的識別碼字的方法）按譯碼的按譯碼的即時即時性分類性分類n非即時碼非即時碼：接收端收到一個：接收端收到一個完整的碼字完整的碼字后后,不能立即譯碼；不能立即譯

40、碼； 還需要等到下一個碼字開始接收后才能判斷是還需要等到下一個碼字開始接收后才能判斷是 否 可 以 譯 碼否 可 以 譯 碼 ; 非 即 時 碼非 即 時 碼 , 又 名 延 長 碼又 名 延 長 碼 , 一 碼 字 是一 碼 字 是 其他碼字的延長。其他碼字的延長。n即時碼即時碼：接收端收到一個：接收端收到一個完整的碼字完整的碼字后，就能立即譯碼；后，就能立即譯碼； 即時碼又稱為即時碼又稱為非延長碼非延長碼或或非前綴碼非前綴碼，任何一個碼任何一個碼 不能是其他碼的前綴不能是其他碼的前綴。 例：例：非即時碼非即時碼碼流碼流 01001100 x10 x201 x311 譯碼為譯碼為 x2, x

41、1, x1, x3, x1, ? 即時碼即時碼碼流碼流 01001100 x10 x210 x311 譯碼為譯碼為 x1, x2, x1, x3, x1, x1 記憶記憶 非前綴碼必定是即時碼，即時碼必定是唯一可譯碼非前綴碼必定是即時碼，即時碼必定是唯一可譯碼, 但唯一可譯碼不一定是即時碼。但唯一可譯碼不一定是即時碼。有實用價值的分組碼有實用價值的分組碼 是是非奇異碼、唯一可譯碼、即時碼非奇異碼、唯一可譯碼、即時碼743.3 離散無記憶（簡單）信源的不等長編碼離散無記憶（簡單）信源的不等長編碼例例 觀察表3.3.1(p55)。事件概率碼A碼B碼C碼Da10.50000a20.25011001a

42、30.125100110011a40.12510111110111753.3 離散無記憶（簡單）信源的不等長編碼離散無記憶（簡單）信源的不等長編碼碼A不是唯一可譯的。碼B不是唯一可譯的。碼C是唯一可譯的，識別碼字的方法為：見“0”或“111”就是一個碼字的結(jié)束。實際上，碼C是異字頭碼。碼D是唯一可譯的，識別碼字的方法為：見“0”就是一個碼字的開始。實際上，碼D是逗點碼，其中“0”是逗號。碼C不是逗點碼。碼D不是異字頭碼。碼C的平均碼長比碼D的平均碼長小：碼C的平均碼長為10.5+20.25+30.125+30.125=1.75；碼D的平均碼長為10.5+20.25+30.125+40.125=

43、1.875。基本術(shù)語基本術(shù)語 n終端節(jié)點終端節(jié)點 后面不再分支的節(jié)點后面不再分支的節(jié)點 。 n中間節(jié)點中間節(jié)點 除樹根、終端節(jié)點外的節(jié)點。除樹根、終端節(jié)點外的節(jié)點。n聯(lián)枝聯(lián)枝 串聯(lián)的樹枝串聯(lián)的樹枝n碼字碼字 從從樹根出發(fā)，到達(dá)樹根出發(fā)，到達(dá)某一終端節(jié)點的某一終端節(jié)點的聯(lián)枝聯(lián)枝n即時碼即時碼 每個碼字都到達(dá)終端節(jié)點每個碼字都到達(dá)終端節(jié)點n滿樹滿樹 每個每個碼字的聯(lián)枝數(shù)均相同時碼字的聯(lián)枝數(shù)均相同時(定長碼定長碼)n非滿樹非滿樹 當(dāng)碼字的聯(lián)枝數(shù)不同時當(dāng)碼字的聯(lián)枝數(shù)不同時(變長碼變長碼) n全全 樹樹 每個中間節(jié)點的后續(xù)分支數(shù)均為每個中間節(jié)點的后續(xù)分支數(shù)均為m n非全樹非全樹 有些中間節(jié)點的后續(xù)分支數(shù)

44、不足有些中間節(jié)點的后續(xù)分支數(shù)不足m碼樹法碼樹法滿樹滿樹全樹，非滿樹全樹，非滿樹非全樹非全樹二進(jìn)制碼樹、滿樹、全樹二進(jìn)制碼樹、滿樹、全樹012000001111122222三進(jìn)制碼樹、非滿樹、全樹三進(jìn)制碼樹、非滿樹、全樹A01000000000000011111111111(1)規(guī)則規(guī)則n樹根樹根=碼字的起點碼字的起點n樹的度樹的度=碼元數(shù)碼元數(shù)n分支結(jié)點分支結(jié)點=碼的符號的一部分碼的符號的一部分n終端結(jié)點終端結(jié)點=待編碼符號待編碼符號(2)碼樹畫法碼樹畫法(m進(jìn)制進(jìn)制)從樹根出發(fā)，畫從樹根出發(fā)，畫m條分支，分支端點稱為節(jié)。條分支，分支端點稱為節(jié)。第一節(jié)有第一節(jié)有m個端點，每端點對應(yīng)一個碼字個端

45、點，每端點對應(yīng)一個碼字從第一節(jié)每個端點出發(fā)，再畫從第一節(jié)每個端點出發(fā)，再畫m條分支，得第二條分支，得第二節(jié)。第二節(jié)有節(jié)。第二節(jié)有m2個端點個端點以此類推以此類推(3)編碼方法：編碼方法：將待編碼的字符作為終端結(jié)點，構(gòu)造碼樹；將待編碼的字符作為終端結(jié)點，構(gòu)造碼樹；按一定規(guī)則給每個樹枝分配一個標(biāo)記；按一定規(guī)則給每個樹枝分配一個標(biāo)記；將從根到終端結(jié)點的路徑上的編號依次相連，作將從根到終端結(jié)點的路徑上的編號依次相連，作為該終端結(jié)點所表示的字符的編碼。為該終端結(jié)點所表示的字符的編碼。(4)譯碼方法：譯碼方法：從樹根出發(fā)從樹根出發(fā), 根據(jù)接收到的第一個碼字符號來選擇根據(jù)接收到的第一個碼字符號來選擇應(yīng)走的第

46、一條路徑應(yīng)走的第一條路徑沿所選路徑走到分支結(jié)點沿所選路徑走到分支結(jié)點,再根據(jù)收到的第二個碼再根據(jù)收到的第二個碼字選擇應(yīng)走的第二條路徑字選擇應(yīng)走的第二條路徑, 直至走到終端結(jié)點為止直至走到終端結(jié)點為止根據(jù)所走路徑根據(jù)所走路徑, 可立即判斷出接收到的碼符號可立即判斷出接收到的碼符號重新返回到樹根重新返回到樹根, 再作下一個接收碼符號的判斷再作下一個接收碼符號的判斷例題例題:非滿二叉樹非滿二叉樹acdb(0)0(10)00111(110)(111)構(gòu)造二元碼樹構(gòu)造二元碼樹:編碼編碼: 信源序列信源序列X=bacabd 100110010111譯碼譯碼: 100110010111 信源序列信源序列X=

47、bacabd提問提問:為什么碼樹法構(gòu)造的碼就是即時碼？為什么碼樹法構(gòu)造的碼就是即時碼？813.3 離散無記憶（簡單）信源的不等長編碼離散無記憶（簡單）信源的不等長編碼異字頭碼的第一種構(gòu)造方法：異字頭碼的第一種構(gòu)造方法：Shannon-Fano編碼法編碼法（D元編碼，字母表為元編碼，字母表為0, 1, , D-1） （1）將源隨機(jī)變量的事件按概率從大到小排成一列。（2）將此列切分為D段（可能有空段），分別賦予標(biāo)號“0”到“D-1”，稱為1級標(biāo)號。（3）將每個非空段再切分為D段（可能有空段），分別賦予標(biāo)號“0”到“D-1”，稱為2級標(biāo)號。（4）將每個非空段再切分為D段（可能有空段），分別賦予標(biāo)號“

48、0”到“D-1”，稱為3級標(biāo)號。823.3 離散無記憶（簡單）信源的不等長編碼離散無記憶（簡單）信源的不等長編碼如此一直到每個非空段不能再分（只含有一個事件）為止。此時，一個事件的碼字就是這個事件所在的段的標(biāo)號序列，從1級標(biāo)號到末級標(biāo)號。（當(dāng)然，那些空段和它們的標(biāo)號序列是沒有用的，要去掉）為了使平均碼長小，每次切分段時應(yīng)使D段的概率盡可能相近。（注解：當(dāng)然可以把“切分段”操作換為“任意分組”操作，使D組的概率盡可能相近。這樣可以使平均碼長更小。但是，這不是一種有效的操作。 ）83n例例設(shè)有一單符號離散信源設(shè)有一單符號離散信源05. 005. 02 . 03 . 04 . 0)(54321xxx

49、xxxpX對該信源編二進(jìn)制費諾碼。信源符號xi 符號概率p(xi)第1次分組 第2次分組第3次分組碼字 碼長x10.4 00002x40.05100103x50.0510113x20.310102x30.21112信源符號xi 符號概率p(xi)第1分組 第2分組第3分組第4分組碼字 碼長x10.4 001x20.310102x30.2101103x40.051011104x50.05111114平均碼長：n= 2.1編碼效率: =93% 平均碼長：n= 2.0編碼效率: =97.5% 8411()1.9593%2.1H Xnn平均碼長511( )0.4 2 0.3 2 0.2 2 2 (0.

50、05 3) 2.1iiinp x n 521( )0.4 1 0.3 2 0.2 3 2 (0.05 4) 2.0iiinp x n 編碼效率22( ) 1.9597.5%2.0H Xn費諾碼比較適合于每次分組概率都很接近的信源特別是對每次分組概率都相等的信源進(jìn)行編碼時,可達(dá)到理想的編碼效率。85例有一單符號離散無記憶信源對該信源編二進(jìn)制費諾碼,編碼過程如表:12345678,()1/ 41/ 41/81/81/161/161/161/16XxxxxxxxxP X86n信源熵為 H(X)=2.75(比特/符號)n平均碼長為n編碼效率為 =1n之所以如此,因為每次所分兩組的概率恰好相等。(0.2

51、50.25)20.122 30.0625442.75(/)n 比特 符873.3 離散無記憶（簡單）信源的不等長編碼離散無記憶（簡單）信源的不等長編碼異字頭碼的第二種構(gòu)造方法：異字頭碼的第二種構(gòu)造方法：Huffman編碼法編碼法88二元Huffman編碼法編碼法89例子 設(shè)單符號離散無記憶信源如下,要求對信源編二進(jìn)制哈夫曼碼。編碼過程如下表01. 010. 015. 017. 018. 019. 020. 0)(7654321xxxxxxxxpX信源符號xi 符號概率p(xi)編碼過程x10.20 x20.19x30.18x40.17x50.15x60.10 x70.01010.200.190

52、.180.170.150.11010.260.200.190.180.17010.350.260.200.19010.390.350.26010.610.3901碼字101100000101001100111在圖中讀取碼字的時候,要從后向前讀,此時編出來的碼字是可分離的異前置碼。90n熵61. 201. 0log01. 010. 0log10. 015. 0log15. 017. 0log17. 018. 0log18. 019. 0log19. 02 . 0log2 . 0)(XHn平均碼長為71( )0.2 2 0.19 2 0.18 3 0.17 3 0.15 3 0.10 4 0.01

53、 42.74iiiKp x K n編碼效率()()2.6195.3%2.74H XH XRK例例2.源符源符Si概率概率P(Si)S10.4S20.2S30.2S40.1S50.1010001000001001000110100101101001101 合并后概率下放合并后概率下放合并后概率上放合并后概率上放 這兩種編碼哪一種更好呢，我們來計算一下二者的碼長。這兩種編碼哪一種更好呢，我們來計算一下二者的碼長。 符號碼元 / 2 . 241 . 041 . 032 . 022 . 014 . 0)(511iiiKxpK符號碼元 / 2 . 231 . 031 . 022 . 022 . 024

54、. 0)(512iiiKxpKqiiiiKKxpKKE1222)()(兩種編碼的平均碼長是一樣的，都是兩種編碼的平均碼長是一樣的，都是2.2，那一種更好，那一種更好呢，我們可以計算一下平均碼長的方差。呢，我們可以計算一下平均碼長的方差。522111( )()1.36iiiP slL522221( )()0.16iiiP slL定義碼字長度的方差定義碼字長度的方差2：n可見：第二種編碼方法的碼長方差要小許多。意味著第二可見：第二種編碼方法的碼長方差要小許多。意味著第二種編碼方法的碼長變化較小，比較接近于平均碼長。種編碼方法的碼長變化較小，比較接近于平均碼長。l第一種方法編出的第一種方法編出的5

55、5個碼字有個碼字有4 4種不同的碼長；種不同的碼長；l第二種方法編出的碼長只有第二種方法編出的碼長只有2 2種不同的碼長；種不同的碼長；l顯然，顯然，第二種編碼方法更簡單、更容易實現(xiàn)，所以更好第二種編碼方法更簡單、更容易實現(xiàn)，所以更好結(jié)論：結(jié)論：在哈夫曼編碼過程中，對縮減信源符號按概率由大到在哈夫曼編碼過程中，對縮減信源符號按概率由大到小的順序重新排列時，應(yīng)小的順序重新排列時，應(yīng)使合并后的新符號盡可能排在靠使合并后的新符號盡可能排在靠前的位置前的位置，這樣可使合并后的新符號重復(fù)編碼次數(shù)減少，這樣可使合并后的新符號重復(fù)編碼次數(shù)減少，使短碼得到充分利用。使短碼得到充分利用。 965. 0)(KXH

56、結(jié)論結(jié)論兩法平均碼長相同，因而信息率兩法平均碼長相同，因而信息率R、編碼效率、編碼效率 相同相同但碼方差不同，但碼方差不同，碼方差小要好碼方差小要好n各次對縮減信源兩個概率最小的符號分配各次對縮減信源兩個概率最小的符號分配“0”和和“1”碼元是任意的，碼元是任意的，所以可得到不同的碼字。只要所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致在各次縮減信源中保持碼元分配的一致性性，即能得到可分離碼字。即能得到可分離碼字。n不同的碼元分配，得到的具體碼字不同，但碼長不同的碼元分配，得到的具體碼字不同，但碼長ki不變，平均碼長不變，平均碼長 也不變，所以沒有本質(zhì)區(qū)別，也不變，所以沒有本質(zhì)區(qū)

57、別，不會影響碼字的長度。不會影響碼字的長度。n縮減信源時，若合并后的新符號概率與其他符號概率相等，從編碼方縮減信源時，若合并后的新符號概率與其他符號概率相等，從編碼方法上來說，法上來說，這幾個符號的次序可任意排列，編出的碼都是正確的，但這幾個符號的次序可任意排列，編出的碼都是正確的，但得到的得到的碼字不相同碼字不相同。不同的編法得到的不同的編法得到的碼字長度碼字長度k ki i也不盡相同也不盡相同。此時此時將影響碼字的長度，一般將合并的概率放在上面，這樣可獲得較小的碼方差。將影響碼字的長度，一般將合并的概率放在上面，這樣可獲得較小的碼方差。K編碼不唯一編碼不唯一（0 0、1 1分配不同，分配不

58、同，排序不同）排序不同）平均碼長唯一平均碼長唯一為什么哈夫曼編碼方法得到的碼并非是唯一的為什么哈夫曼編碼方法得到的碼并非是唯一的? 95D元Huffman編碼法編碼法（D元編碼，字母表為元編碼，字母表為0, 1, , D-1）（0）如果源隨機(jī)變量的事件的個數(shù)K不是(D-1)的倍數(shù)加1，則添加若干0概率事件使得事件的個數(shù)是(D-1)的倍數(shù)加1 。（1）將概率最小(排序)的D個事件分別賦予標(biāo)號“0”到“D-1”。（2）將這D個事件合并為一個事件，其概率為這D個事件概率之和。重復(fù)（1）-（2），直到事件的個數(shù)等于D。將這D個事件分別賦予標(biāo)號“0”到“D-1”。編碼完畢。此時，一個事件的碼字是這個事件

59、從最后標(biāo)號開始到最先標(biāo)號為止的標(biāo)號序列。（當(dāng)然要去掉那些0概率事件和它們的標(biāo)號序列）為了使短碼得到充分利用，使平均碼長為最短，必須使最后一步的縮減信源有D個信源符號，因此對于D元編碼，信源的符號個數(shù)K必須滿足K= (D-1)r+D=(D-1)(r+1)+1,其中r為縮減的次數(shù)。K-(D-1)r=D96n哈夫曼的編法并不惟一。n對二元Huffman編碼，編碼，每次對縮減信源兩個概率最小的符號分配“0”和“1”碼元是任意的,所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性,即能得到可分離碼字。n對D元Huffman編碼，有類似結(jié)果。編碼，有類似結(jié)果。哈夫曼編碼97哈夫曼編碼n不同的碼

60、元分配,得到的具體碼字不同,但碼長Ki不變,平均碼長也不變,所以沒有本質(zhì)區(qū)別；n縮減信源時,若合并后的新符號概率與其他符號概率相等,從編碼方法上來說,這幾個符號的次序可任意排列,編出的碼都是正確的,但得到的碼字不相同。n不同的編法得到的碼字長度Ki也不盡相同。2022-6-30983.3 離散無記憶（簡單）信源的不等長編碼離散無記憶（簡單）信源的不等長編碼（為什么Shannon-Fano碼和Huffman碼都是異字頭碼？請看p62圖3.4.1，p62圖3.4.2。這些圖都是樹，稱為碼樹，碼樹上的每個碼樹上的每個碼字都在樹梢碼字都在樹梢。這種形狀保證了碼是異字頭碼。如果不是異字頭碼，則有的碼字就