信息論與編碼理論基礎(chǔ) 王育民(第三章)1-3

2024/6/231第三章：信源編碼（一）

離散信源無失真編碼§3.1信源及其分類§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼§3.4最佳不等長(zhǎng)編碼2024/6/232通信的根本問題是將信源的輸出在接收端精確地或近似地重新出來。兩個(gè)問題：

1.信源的輸出應(yīng)如何描述，即如何計(jì)算它產(chǎn)生的信息量。2.如何表示信源的輸出，即信源編碼問題。2024/6/233無失真信源編碼保證信源產(chǎn)生的全部信息無損地遞給信宿；限定失真的信源編碼不要求完全精確地復(fù)制出信源的輸出，但要滿足一定的保真度準(zhǔn)則。2024/6/234§3.1信源及其分類信源的概念

（直觀地理解，信源就是信息的來源。但是必須要注意兩點(diǎn)）：在一個(gè)固定的時(shí)刻，信源發(fā)出的是一個(gè)隨機(jī)變量。隨著時(shí)間的延續(xù)，信源發(fā)出一個(gè)又一個(gè)隨機(jī)變量，稱之為一個(gè)隨機(jī)過程。（因此，一般的信源種類太多，其統(tǒng)計(jì)性質(zhì)太復(fù)雜。怎樣做工程實(shí)用的簡(jiǎn)化？）2024/6/235§3.1信源及其分類離散信源信源每隔一個(gè)定長(zhǎng)時(shí)間段就發(fā)出一個(gè)隨機(jī)變量；隨著時(shí)間的延續(xù)，信源發(fā)出的是隨機(jī)變量序列

…U-2U-1U0U1U2…其中Uk為第k個(gè)時(shí)間段發(fā)出的隨機(jī)變量；每個(gè)Uk都是一個(gè)離散型的隨機(jī)變量。§3.1信源及其分類離散無記憶信源離散無記憶信源是這樣的離散信源：隨機(jī)變量…、U-2、U-1、U0、U1、U2、…相互獨(dú)立。離散無記憶簡(jiǎn)單信源離散無記憶簡(jiǎn)單信源是這樣的離散無記憶信源：隨機(jī)變量…、U-2、U-1、U0、U1、U2、…具有相同的概率分布。2024/6/2362024/6/237§3.1信源及其分類小結(jié)離散無記憶簡(jiǎn)單信源

就是時(shí)間離散、事件離散、各隨機(jī)變量獨(dú)立同分布的信源.課程學(xué)習(xí)所面對(duì)的信源將主要是離散無記憶簡(jiǎn)單信源.§3.1信源及其分類一般的信源

連續(xù)信源：有時(shí)間連續(xù)的信源，也有事件連續(xù)的信源；有記憶信源：信源在不同時(shí)刻發(fā)出的隨機(jī)變量相互依賴；有限記憶信源：在有限時(shí)間差內(nèi)的信源隨機(jī)變量相互依賴；非簡(jiǎn)單信源：信源在不同時(shí)刻發(fā)出的隨機(jī)變量具有不同的概率分布。馬爾可夫信源：信源隨機(jī)過程是馬爾可夫過程。2024/6/238§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼編碼實(shí)質(zhì)上是對(duì)信源的原始符號(hào)按一定的數(shù)學(xué)規(guī)則進(jìn)行的一種變換，映射成碼字以適合信道傳輸。2024/6/2392024/6/2310§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼設(shè)有一個(gè)離散無記憶簡(jiǎn)單信源，信源發(fā)出的隨機(jī)變量序列為：…U-2U-1U0U1U2…。設(shè)信源隨機(jī)變量U1的事件有K個(gè)：{a1,a2,…,aK}，則L維信源隨機(jī)向量(U1U2…UL)的事件有KL個(gè)：{(u1u2…uL)|其中每個(gè)分量ul跑遍{a1,a2,…,aK}}?！?.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼P((U1U2…UL)=(u1u2…uL))=P(U1=u1)P(U2=u2)…P(UL=uL)=P(U1=u1)P(U1=u2)…P(U1=uL)=q(u1)q(u2)…q(uL)2024/6/23112024/6/2312§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼設(shè)有一個(gè)含D個(gè)字母的字母表。對(duì)于(U1U2…UL)的每一個(gè)事件(u1u2…uL)，都用一個(gè)字母串(c1c2…)來表示。這種表示方法稱為D元編碼；每一個(gè)事件(u1u2…uL)所對(duì)應(yīng)的字母串(c1c2…)稱為一個(gè)碼字。2024/6/2313§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼例：離散無記憶簡(jiǎn)單信源發(fā)出的隨機(jī)變量序列為：…U-2U-1U0U1U2…，其中U1的事件有3個(gè)：{晴,云,陰}.將(U1U2)進(jìn)行2元編碼.§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼(U1U2)有9個(gè)事件{（晴晴），（晴云），（晴陰），（云晴），（云云），（云陰），（陰晴），（陰云），（陰陰）}2024/6/2314§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼用字母表{0,1}對(duì)(U1U2)的事件進(jìn)行2元編碼如下：（晴晴）→0000，（晴云）→0001，（晴陰）→0011，（云晴）→0100，（云云）→0101，（云陰）→0111，（陰晴）→1100，（陰云）→1101，（陰陰）→1111。2024/6/23152024/6/2316§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼如果限定所有碼字的長(zhǎng)度都為N（即每個(gè)碼字都是一個(gè)長(zhǎng)度為N的字母串，或稱為N維向量），則稱此編碼為等長(zhǎng)編碼，能夠選擇的不同碼字的個(gè)數(shù)為DN。2024/6/2317§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼如果限定每個(gè)碼字的長(zhǎng)度都≤N（即每個(gè)碼字都是一個(gè)長(zhǎng)度≤N的字母串），則稱此編碼為不等長(zhǎng)編碼，能夠選擇的不同碼字的個(gè)數(shù)為D1+D2+…+DN=D(DN-1)/(D-1)。2024/6/2318§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼問題：在不等長(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í)別問題。2024/6/2319§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼對(duì)等長(zhǎng)碼若對(duì)每個(gè)消息都至少有一個(gè)碼字與之對(duì)應(yīng)，且不同的消息對(duì)應(yīng)不同的碼字，則稱這樣的碼為單義可譯碼或唯一可譯碼。在無擾傳輸時(shí)，單義可譯碼的譯碼錯(cuò)誤概率為0，又稱為無錯(cuò)編碼。2024/6/2320§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼無錯(cuò)編碼

(U1U2…UL)的不同事件用不同的碼字來表示。消息集是K元字母表L長(zhǎng)消息序列，編碼成D元N長(zhǎng)碼字。能夠?qū)崿F(xiàn)無錯(cuò)編碼的充要條件是DN≥KL即NlogD≥LlogK或NlogD/L

≥

logK(下界)2024/6/2321§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼編碼速率

R=NlogD/L實(shí)現(xiàn)無錯(cuò)編碼的充要條件是

編碼速率R=NlogD/L≥logK2024/6/2322§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼

有錯(cuò)編碼

(U1U2…UL)的有些不同事件用相同的碼字來表示。2024/6/2323§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼編碼速率的說明實(shí)際的編碼速率的計(jì)算公式為R=NlogD/L，似乎可以人為地任意設(shè)置N和L，因而可以人為地任意設(shè)置編碼速率。?

§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼事實(shí)并非如此，存在著編碼設(shè)備的編碼速率R0，它是編碼設(shè)備的性能指標(biāo).這就是說，選擇N和L，必須使得實(shí)際的編碼速率NlogD/L不能超過編碼設(shè)備的編碼速率R0

：R=NlogD/L≤R0

2024/6/23242024/6/2325§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼有錯(cuò)編碼的譯碼方法與“譯碼錯(cuò)誤”概率當(dāng)使用有錯(cuò)編碼時(shí)，必須給出譯碼方法（即：一個(gè)碼字可能表示幾個(gè)不同的事件，究竟翻譯成哪個(gè)事件）?！白g碼錯(cuò)誤”的概率定義為pe=P{(U1U2…UL)=(u1u2…uL)|(u1u2…uL)的碼字在譯碼時(shí)并不譯為(u1u2…uL)}。2024/6/2326§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼在無錯(cuò)編碼的前提下，編碼的最低代價(jià)當(dāng)R≥logK時(shí)，能夠?qū)崿F(xiàn)無錯(cuò)編碼。（DN≥KL）當(dāng)R<H(U1)時(shí)，無論怎樣編碼都是有錯(cuò)編碼。

這是因?yàn)镽<H(U1)≤logK。（DN<KL）

如果H(U1)=logK，則以上兩種情形已經(jīng)概括了全部情形。但如果H(U1)<logK，則還有一種情形。當(dāng)logK>R>H(U1)時(shí)，雖然無論怎樣編碼都是有錯(cuò)編碼，但可以適當(dāng)?shù)鼐幋a和譯碼使譯碼錯(cuò)誤的概率pe任意小。這就是所謂“漸進(jìn)無錯(cuò)編碼”。2024/6/2327§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼logKH(U1)·RRR無錯(cuò)編碼不能漸進(jìn)無錯(cuò)編碼漸進(jìn)無錯(cuò)編碼○

·○○○2024/6/2328§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼漸進(jìn)無錯(cuò)編碼

簡(jiǎn)單地說就是：當(dāng)R>H(U1)時(shí)，可以適當(dāng)?shù)鼐幋a和譯碼使得譯碼錯(cuò)誤的概率pe任意小。2024/6/2329§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼漸進(jìn)無錯(cuò)編碼嚴(yán)格地說就是：設(shè)給定了編碼設(shè)備的編碼速率R0，R0>H(U1)。則對(duì)任意的ε>0，總存在一個(gè)L0，使得對(duì)任意的L>L0，都有對(duì)(U1U2…UL)的等長(zhǎng)編碼和對(duì)應(yīng)的譯碼方法，滿足①實(shí)際的編碼速率R=NlogD/L≤R0，②譯碼錯(cuò)誤的概率pe<ε。2024/6/2330§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼漸進(jìn)無錯(cuò)編碼的原理

大數(shù)定律。隨著L的增加，(U1U2…UL)的所有事件中，某些事件所占的比例越來越?。ā?），其發(fā)生的概率卻越來越大（→1）。2024/6/2331§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼不能漸進(jìn)無錯(cuò)的編碼

簡(jiǎn)單地說就是：當(dāng)R<H(U1)時(shí)，無論怎樣編碼和譯碼都不能使譯碼錯(cuò)誤的概率pe任意小。

嚴(yán)格地說就是：設(shè)給定了編碼設(shè)備的編碼速率R0，R0<H(U1)，則無論怎樣編碼和譯碼都不能同時(shí)滿足①實(shí)際的編碼速率R≤R0，②譯碼錯(cuò)誤的概率pe任意小。2024/6/2332§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼設(shè)…U-2U-1U0U1U2…是離散無記憶（簡(jiǎn)單）信源的輸出隨機(jī)變量序列。設(shè)U1的概率分布為取Vl是Ul的如下函數(shù)：當(dāng)Ul=ak時(shí)，Vl=loga(1/qk)。則①隨機(jī)變量序列…V-2V-1V0V1V2…相互獨(dú)立，具有相同的概率分布；②2024/6/2333§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼取IL是(V1V2…VL)的如下函數(shù)：則①IL最終是(U1U2…UL)的函數(shù)；②③因此有切比雪夫不等式：對(duì)任意ε>0有P{(U1U2…UL)=(u1u2…uL)|H(U1)-ε≤IL≤H(U1)+ε}≥2024/6/2334§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼取定L0使得則當(dāng)L≥L0時(shí)總有因此當(dāng)L≥L0時(shí)總有P{(U1U2…UL)=(u1u2…uL)|H(U1)-ε≤IL≤H(U1)+ε}≥1-ε。2024/6/2335§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼定義3.2.1(p50)定義TU(L,ε)={(u1u2…uL)|H(U1)-ε≤IL≤H(U1)+ε}，稱TU(L,ε)為ε-典型序列集。稱TU(L,ε)的補(bǔ)集為非ε-典型序列集。（綜上所述有）定理3.2.1(信源劃分定理，p51)對(duì)任意ε>0，取L0使得則當(dāng)L≥L0時(shí)總有P{(U1U2…UL)∈TU(L,ε)}≥1-ε。2024/6/2336§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（簡(jiǎn)記H(U)=H(U1)。設(shè)以下的對(duì)數(shù)都是以2為底的。）系3.2.1(特定典型序列出現(xiàn)的概率，p58)若一個(gè)特定的事件(u1u2…uL)∈TU(L,ε)，則2-L(H(U)+ε)≤P{(U1U2…UL)=(u1u2…uL)}≤2-L(H(U)-ε)。證明設(shè)(u1u2…uL)∈TU(L,ε)。注意到此時(shí)H(U)-ε≤IL≤H(U)+ε，2024/6/2337§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼所以2024/6/2338§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼系3.2.2(典型序列的數(shù)量，p52)(1-ε)2L(H(U)-ε)≤|TU(L,ε)|≤2L(H(U)+ε)。證明一方面，2024/6/2339§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼另一方面，2024/6/2340§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（如果采用2元編碼，且對(duì)數(shù)都是以2為底的，則編碼速率為R=NlogD/L=N/L。）補(bǔ)充引理

設(shè)給定一個(gè)R0>H(U)。對(duì)每個(gè)正整數(shù)L，對(duì)應(yīng)地取整數(shù)N=[R0L]（R0L的下取整）。則N/L≤R0，limL→+∞N/L=R0。任取正數(shù)ε≤(R0-H(U))/2，存在正整數(shù)L0，當(dāng)L>L0時(shí)（1）N/L≥R0-(R0-H(U))/2=H(U)+(R0-H(U))/2≥H(U)+ε。（2）P{(U1U2…UL)∈TU(L,ε)}≥1-ε。（由定理3.2.1）2024/6/2341§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼定理3.2.2(無錯(cuò)編碼正定理，p53)

給定編碼設(shè)備的編碼速率R0，R0>H(U)。則對(duì)任意的ε>0，總存在一個(gè)L0，使得對(duì)任意的L>L0，都有對(duì)(U1U2…UL)的2元等長(zhǎng)編碼方法和對(duì)應(yīng)的譯碼方法，①實(shí)際的編碼速率R滿足R0≥R>H(U)，②“譯碼錯(cuò)誤”的概率pe<ε。2024/6/2342§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼證明首先聲明，所有的對(duì)數(shù)計(jì)算都是以2為底的。此時(shí)實(shí)際的編碼速率為R=N/L。任取正數(shù)ε≤(R0-H(U))/2，取補(bǔ)充引理所描述的L0，則|TU(L,ε)|≤2L(H(U)+ε)

（由系3.2.2）≤2LR=2N

（由補(bǔ)充引理的（1））這就是說，典型序列集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è)事件。2024/6/2343§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼對(duì)應(yīng)的譯碼：所有的碼字均譯為它所表示的TU(L,ε)中的事件。結(jié)論：①實(shí)際的編碼速率R滿足R0≥R>H(U)；②“譯碼錯(cuò)誤”的概率pe=P((U1U2…UL)不屬于TU(L,ε))=1-P((U1U2…UL)∈TU(L,ε))<ε。得證。

定理3.2.2(無錯(cuò)編碼反定理，p60)設(shè)給定編碼設(shè)備的編碼速率R0，滿足R0<H(U)。當(dāng)限制實(shí)際的編碼速率R≤R0時(shí)，無論怎樣編碼和譯碼都不能使“譯碼錯(cuò)誤”的概率任意小。（沒有證明）2024/6/2344§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼漸進(jìn)無錯(cuò)編碼的要求給定離散無記憶簡(jiǎn)單信源：…U-2U-1U0U1U2…；給定編碼設(shè)備的編碼速率R0，滿足R0>H(U)；給定一個(gè)任意小的正數(shù)ε>0；要求：選擇合適的L，N，對(duì)(U1U2…UL)進(jìn)行合適的2元N長(zhǎng)編碼，使得

①實(shí)際的編碼速率R=N/L滿足R≤R0；

②“譯碼錯(cuò)誤”的概率pe<ε。2024/6/2345漸進(jìn)無錯(cuò)編碼的步驟①由U1的概率分布計(jì)算②取L滿足。③取整數(shù)N=[R0L]（R0L下取整）。④取典型序列集2024/6/2346漸進(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,ε)中的事件。（注解：顯然滿足R≤R0；|TU(L,ε)|≤2N，因此碼字足夠用；譯碼錯(cuò)誤的概率為pe=P((U1U2…UL)=(u1u2…uL)|(u1u2…uL)不屬于TU(L,ε))<ε；一般來說，ε越小，要求L越大，因此對(duì)應(yīng)的N越大。）2024/6/2347§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼例設(shè)2024/6/2348§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼設(shè)給定編碼設(shè)備的編碼速率R0=0.5。則R0>0.037587148=H(U1)。希望：①2元編碼的實(shí)際編碼速率R≤R0；②譯碼錯(cuò)誤的概率不超過ε。其中取ε=0.1。找L使得2024/6/2349§3.2離散無記憶（簡(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,ε)中的事件。另一方面，TU(L,ε)中的事件有更加簡(jiǎn)單的表達(dá)方式。當(dāng)事件(u1u2…uL)中a1的個(gè)數(shù)為k，a2的個(gè)數(shù)為L(zhǎng)-k時(shí)，2024/6/2350§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼事件(u1u2…uL)屬于典型序列集TU(L,0.1)；當(dāng)且僅當(dāng)2024/6/2351§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼當(dāng)事件(u1u2…u253)中a1的個(gè)數(shù)不超過4時(shí)，(u1u2…u253)∈TU(253,0.1)；否則(u1u2…u253)不屬于TU(253,0.1)。(u1u2…u253)∈TU(253,0.1)的概率不小于0.9；(u1u2…u253)∈TU(253,0.1)的個(gè)數(shù)為2024/6/2352§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼對(duì)L=253，對(duì)應(yīng)地取整數(shù)N=[R0L]=126。則N/L<R0，這就是說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.355557444<2126，碼字足夠用。2元編碼的譯碼方法：將碼字譯為它所表示的TU(253,0.1)中的事件(u1u2…u253)。于是，譯碼錯(cuò)誤的概率為P((u1u2…u253)不屬于TU(253,0.1))≤ε=0.1。2024/6/2353§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼取ε=0.05。找L使得即L=2020。有P{(U1U2…UL)=(u1u2…uL)|

-0.05≤IL-H(U)≤0.05}≥0.95。另一方面，當(dāng)事件(u1u2…uL)中a1的個(gè)數(shù)為k，a2的個(gè)數(shù)為L(zhǎng)-k時(shí)，2024/6/2354§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼事件(u1u2…uL)屬于典型序列集TU(L,0.05)；當(dāng)且僅當(dāng)-0.05≤IL-H(U)≤0.05；當(dāng)且僅當(dāng)2024/6/2355§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼設(shè)L=2020。此時(shí)0.01028137L=20.7683674。當(dāng)事件(u1u2…u2020)中a1的個(gè)數(shù)不超過20時(shí)，(u1u2…u2020)∈TU(2020,0.05)；否則(u1u2…u2020)不屬于TU(2020,0.05)。(u1u2…u2020)∈TU(2020,0.05)的概率不小于0.95；(u1u2…u2020)∈TU(2020,0.05)的個(gè)數(shù)為2024/6/2356§3.2離散無記憶（簡(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)碼字表示，該碼字已經(jīng)用于表示了TU(2020,0.05)中的一個(gè)事件。由于|TU(2020,0.05)|≤2176.92603896<21010，碼字足夠用。2元編碼的譯碼方法：將碼字譯為它所表示的TU(2020,0.05)中的事件(u1u2…u2020)。于是，譯碼錯(cuò)誤的概率為P((u1u2…u2020)不屬于TU(2020,0.05))≤ε=0.05。2024/6/2357§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼取ε=0.01。找L使得即L=252435。有P{(U1U2…UL)=(u1u2…uL)|

-0.01≤IL-H(U)≤0.01}≥0.99。另一方面，當(dāng)事件(u1u2…uL)中a1的個(gè)數(shù)為k，a2的個(gè)數(shù)為L(zhǎng)-k時(shí)，2024/6/2358§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼事件(u1u2…uL)屬于典型序列集TU(L,0.01)；當(dāng)且僅當(dāng)-0.01≤IL-H(U)≤0.01；當(dāng)且僅當(dāng)2024/6/2359§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼設(shè)L=252435。此時(shí)0.00274372L=692.61096；0.00525628L=1326.8690。

當(dāng)事件(u1u2…u252435)中a1的個(gè)數(shù)不超出閉區(qū)間[693，1326]內(nèi)時(shí)，(u1u2…u252435)∈TU(252435,0.01)；否則(u1u2…u252435)不屬于TU(252435,0.01)。(u1u2…u252435)∈TU(252435,0.01)的概率不小于0.99；(u1u2…u252435)∈TU(252435,0.01)的個(gè)數(shù)為2024/6/2360§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼對(duì)L=252435，對(duì)應(yīng)地取整數(shù)N=[R0L]=126217。則N/L<R0，這就是說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.6617<2126217，碼字足夠用。2元編碼的譯碼方法：將碼字譯為它所表示的TU(252435,0.01)中的事件(u1u2…u252435)。于是，譯碼錯(cuò)誤的概率為P((u1u2…u252435)不屬于TU(252435,0.01))≤ε=0.01。2024/6/2361§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（直觀理解）等長(zhǎng)編碼定理（信源劃分定理）1.信源序列集=典型序列集（高概率集，>=1-\epsilon）+非典型序列集（低概率集）；2.將典型序列集中的信源序列一一編碼（無錯(cuò)編碼），而將非典型序列集中的信源序列編碼成剛才的一個(gè)碼字；3.典型序列集勢(shì)約為2^{LH(U)}，占K^L少,非典型序列集勢(shì)占多。2024/6/2362§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼（順序地?cái)⑹鲆韵碌母拍睿?）不等長(zhǎng)編碼的優(yōu)越性總體上減少碼字的長(zhǎng)度。（2）不等長(zhǎng)編碼的特殊問題

①唯一可譯性，或者叫做可識(shí)別性。對(duì)于一個(gè)碼，如果存在一種譯碼方法，使任意若干個(gè)碼字所組成的字母串只能唯一地被翻譯成這幾個(gè)碼字所對(duì)應(yīng)的事件序列。這個(gè)碼就被稱為是唯一可譯的。解決方案：適當(dāng)?shù)鼐幋a，使得每個(gè)碼字都具有識(shí)別標(biāo)記。（注解：一個(gè)唯一可譯的、碼字長(zhǎng)度不超過N的D元碼，其碼字個(gè)數(shù)小于D(DN-1)/(D-1)個(gè)。這是因?yàn)閮蓚€(gè)碼字c(1)和c(2)連接成的字母串c(1)c(2)不能是碼字）2024/6/2363§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼②平均碼字長(zhǎng)度。設(shè)信源隨機(jī)變量U的概率分布為{ak,q(ak),k=1~K}，事件ak對(duì)應(yīng)的碼字長(zhǎng)度為nk，則平均碼字長(zhǎng)度為希望小。解決方案：概率大的事件用短碼字。③實(shí)時(shí)譯碼和容量限制。2024/6/2364§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼唯一可譯性的兩種解決方法定義3.3.2(p55)若①事件與碼字一一對(duì)應(yīng)；②每個(gè)碼字的開頭部分都是一個(gè)相同的字母串；③這個(gè)字母串僅僅出現(xiàn)在碼字的開頭，不出現(xiàn)在碼字的其它部位，也不出現(xiàn)在兩個(gè)碼字的結(jié)合部。則稱這個(gè)字母串為逗號(hào)，稱此碼為逗點(diǎn)碼。定義3.3.4(p55)若①事件與碼字一一對(duì)應(yīng)；②每個(gè)碼字都不是另一個(gè)碼字的開頭部分（字頭）。則稱此碼為異字頭碼。2024/6/2365§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼注解逗點(diǎn)碼顯然是唯一可譯的，識(shí)別碼字的方法為：見到逗號(hào)就識(shí)別為一個(gè)碼字的開始。異字頭碼也是唯一可譯的，識(shí)別碼字的方法為：見到一個(gè)碼字就識(shí)別為一個(gè)碼字。（許多具體的異字頭碼有更加簡(jiǎn)便的識(shí)別碼字的方法）2024/6/2366§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼例觀察表3.3.1(p55)。事件概率碼A碼B碼C碼Da10.50000a20.25011001a30.125100110011a40.125101111101112024/6/2367§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼碼A不是唯一可譯的。碼B不是唯一可譯的。碼C是唯一可譯的，識(shí)別碼字的方法為：見“0”或“111”就是一個(gè)碼字的結(jié)束。實(shí)際上，碼C是異字頭碼。碼D是唯一可譯的，識(shí)別碼字的方法為：見“0”就是一個(gè)碼字的開始。實(shí)際上，碼D是逗點(diǎn)碼，其中“0”是逗號(hào)。碼C不是逗點(diǎn)碼。碼D不是異字頭碼。碼C的平均碼長(zhǎng)比碼D的平均碼長(zhǎng)?。捍aC的平均碼長(zhǎng)為1×0.5+2×0.25+3×0.125+3×0.125=1.75；碼D的平均碼長(zhǎng)為1×0.5+2×0.25+3×0.125+4×0.125=1.875。2024/6/2368§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼異字頭碼的第一種構(gòu)造方法：Shannon-Fano編碼法（D元編碼，字母表為{0,1,…,D-1}）

（1）將源隨機(jī)變量的事件按概率從大到小排成一行。（2）將此行切分為D段（可能有空段），分別賦予標(biāo)號(hào)“0”到“D-1”，稱為1級(jí)標(biāo)號(hào)。（3）將每個(gè)非空段再切分為D段（可能有空段），分別賦予標(biāo)號(hào)“0”到“D-1”，稱為2級(jí)標(biāo)號(hào)。（4）將每個(gè)非空段再切分為D段（可能有空段），分別賦予標(biāo)號(hào)“0”到“D-1”，稱為3級(jí)標(biāo)號(hào)。…。2024/6/2369§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼如此一直到每個(gè)非空段不能再分（只含有一個(gè)事件）為止。此時(shí)，一個(gè)事件的碼字就是這個(gè)事件所在的段的標(biāo)號(hào)序列，從1級(jí)標(biāo)號(hào)到末級(jí)標(biāo)號(hào)。（當(dāng)然，那些空段和它們的標(biāo)號(hào)序列是沒有用的，要去掉）為了使平均碼長(zhǎng)小，每次切分段時(shí)應(yīng)使D段的概率盡可能相近。（注解：當(dāng)然可以把“切分段”操作換為“任意分組”操作，使D組的概率盡可能相近。這樣可以使平均碼長(zhǎng)更小。但是，這不是一種有效的操作。）2024/6/2370例設(shè)有一單符號(hào)離散信源對(duì)該信源編二進(jìn)制費(fèi)諾碼。信源符號(hào)xi

符號(hào)概率p(xi)第1次分組第2次分組第3次分組碼字碼長(zhǎng)x10.400002x40.05100103x50.0510113x20.310102x30.21112信源符號(hào)xi

符號(hào)概率p(xi)第1分組第2分組第3分組第4分組碼字碼長(zhǎng)x10.4001x20.310102x30.2101103x40.051011104x50.05111114平均碼長(zhǎng)：n=2.1編碼效率:η=93%平均碼長(zhǎng)：n=2.0編碼效率:η=97.5%2024/6/2371平均碼長(zhǎng)編碼效率費(fèi)諾碼比較適合于每次分組概率都很接近的信源特別是對(duì)每次分組概率都相等的信源進(jìn)行編碼時(shí),可達(dá)到理想的編碼效率。2024/6/2372例有一單符號(hào)離散無記憶信源對(duì)該信源編二進(jìn)制費(fèi)諾碼,編碼過程如表:2024/6/2373信源熵為H(X)=2.75(比特/符號(hào))平均碼長(zhǎng)為編碼效率為

η=1之所以如此,因?yàn)槊看嗡謨山M的概率恰好相等。2024/6/2374§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼異字頭碼的第二種構(gòu)造方法：Huffman編碼法2024/6/2375二元Huffman編碼法2024/6/2376例子

設(shè)單符號(hào)離散無記憶信源如下,要求對(duì)信源編二進(jìn)制哈夫曼碼。編碼過程如下表信源符號(hào)xi

符號(hào)概率p(xi)編碼過程x10.20x20.19x30.18x40.17x50.15x60.10x70.01010.200.190.180.170.150.11010.260.200.190.180.17010.350.260.200.19010.390.350.26010.610.3901碼字101100000101001100111在圖中讀取碼字的時(shí)候,要從后向前讀,此時(shí)編出來的碼字是可分離的異前置碼。2024/6/2377熵平均碼長(zhǎng)為編碼效率2024/6/2378D元Huffman編碼法（D元編碼，字母表為{0,1,…,D-1}）（0）如果源隨機(jī)變量的事件的個(gè)數(shù)K不是(D-1)的倍數(shù)加1，則添加若干0概率事件使得事件的個(gè)數(shù)是(D-1)的倍數(shù)加1。（1）將概率最小的D個(gè)事件分別賦予標(biāo)號(hào)“0”到“D-1”。（2）將這D個(gè)事件合并為一個(gè)事件，其概率為這D個(gè)事件概率之和。重復(fù)（1）-（2），直到事件的個(gè)數(shù)等于D。將這D個(gè)事件分別賦予標(biāo)號(hào)“0”到“D-1”。編碼完畢。此時(shí)，一個(gè)事件的碼字是這個(gè)事件從最后標(biāo)號(hào)開始到最先標(biāo)號(hào)為止的標(biāo)號(hào)序列。（當(dāng)然要去掉那些0概率事件和它們的標(biāo)號(hào)序列）為了使短碼得到充分利用，使平均碼長(zhǎng)為最短，必須使最后一步的縮減信源有D個(gè)信源符號(hào)，因此對(duì)于D元編碼，信源的符號(hào)個(gè)數(shù)K必須滿足K=(D-1)r+D=(D-1)(r+1)+1,其中r為縮減的次數(shù)。K-(D-1)r=D2024/6/2379哈夫曼的編法并不惟一。對(duì)二元Huffman編碼，每次對(duì)縮減信源兩個(gè)概率最小的符號(hào)分配“0”和“1”碼元是任意的,所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性,即能得到可分離碼字。對(duì)D元Huffman編碼，有類似結(jié)果。哈夫曼編碼2024/6/2380哈夫曼編碼不同的碼元分配,得到的具體碼字不同,但碼長(zhǎng)Ki不變,平均碼長(zhǎng)也不變,所以沒有本質(zhì)區(qū)別；縮減信源時(shí),若合并后的新符號(hào)概率與其他符號(hào)概率相等,從編碼方法上來說,這幾個(gè)符號(hào)的次序可任意排列,編出的碼都是正確的,但得到的碼字不相同。不同的編法得到的碼字長(zhǎng)度Ki也不盡相同。2024/6/2381§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼（為什么Shannon-Fano碼和Huffman碼都是異字頭碼？請(qǐng)看p62圖3.4.1，p62圖3.4.2。這些圖都是樹，稱為碼樹，碼樹上的每個(gè)碼字都在樹梢。這種形狀保證了碼是異字頭碼。如果不是異字頭碼，則有的碼字就不在樹梢，而在中間節(jié)點(diǎn)。）P56,若一個(gè)碼樹的各分支都能延伸到最高級(jí)端點(diǎn)（共有D^{n_K}個(gè)碼字），就稱為滿樹，否則為非滿樹。若消息占滿了所有的端節(jié)點(diǎn)，即樹上每一個(gè)中間節(jié)點(diǎn)都有D個(gè)分支，稱為全樹。2024/6/2382定理3.3.1(Kraft不等式，p57)設(shè)信源隨機(jī)變量共有K個(gè)事件。則：各碼字長(zhǎng)度分別為n1、n