信息論與編碼講義第七講

信息論與編碼講義第七講第一頁，共十六頁，2022年，8月28日2023/3/131§3.1信源及其分類信源的概念

（直觀地理解，信源就是信息的來源。但是這里必須要注意兩點）：在一個固定的時刻，信源發(fā)出的是一個隨機變量。隨著時間的延續(xù)，信源發(fā)出的是一個隨機過程。（因此，一般的信源種類太多，其統(tǒng)計性質太復雜。怎樣做工程實用的簡化？）第二頁，共十六頁，2022年，8月28日2023/3/132§3.1信源及其分類離散信源信源每隔一個定長時間段就發(fā)出一個隨機變量；隨著時間的延續(xù)，信源發(fā)出的是隨機變量序列…U-2U-1U0U1U2…，其中Uk為第k個時間段發(fā)出的隨機變量；每個Uk都是一個離散型的隨機變量。離散無記憶信源離散無記憶信源是這樣的離散信源：隨機變量…、U-2、U-1、U0、U1、U2、…相互獨立。離散無記憶簡單信源離散無記憶簡單信源是這樣的離散無記憶信源：隨機變量…、U-2、U-1、U0、U1、U2、…具有相同的概率分布。第三頁，共十六頁，2022年，8月28日2023/3/133§3.1信源及其分類（總結：離散無記憶簡單信源就是時間離散、事件離散、各隨機變量獨立同分布的信源。課程學習所面對的信源將主要是離散無記憶簡單信源）一般的信源

連續(xù)信源：有時間連續(xù)的信源，也有事件連續(xù)的信源；有記憶信源：信源在不同時刻發(fā)出的隨機變量相互依賴；有限記憶信源：在有限時間差內(nèi)的信源隨機變量相互依賴；非簡單信源：信源在不同時刻發(fā)出的隨機變量具有不同的概率分布。馬爾可夫信源：信源隨機過程是馬爾可夫過程。第四頁，共十六頁，2022年，8月28日2023/3/134§3.2離散無記憶（簡單）信源的等長編碼（順序地敘述以下的概念）（1）設有一個離散無記憶簡單信源，信源發(fā)出的隨機變量序列為：…U-2U-1U0U1U2…。設信源隨機變量U1的事件有K個：{a1,a2,…,aK}，則L維信源隨機向量(U1U2…UL)的事件有KL個：{(u1u2…uL)|其中每個分量ul跑遍{a1,a2,…,aK}}。（2）設有一個含D個字母的字母表{b1,b2,…,bD}。需要用字母串來表示(U1U2…UL)的事件，每一個事件都要用一個字母串來表示。這種表示方法稱為D元編碼；每一個事件所對應的字母串稱為一個碼字。

第五頁，共十六頁，2022年，8月28日2023/3/135§3.2離散無記憶（簡單）信源的等長編碼例：離散無記憶簡單信源發(fā)出的隨機變量序列為：…U-2U-1U0U1U2…。其中U1的事件有3個：{晴,云,陰}。(U1U2)有9個事件{（晴晴），（晴云），（晴陰），（云晴），（云云），（云陰），（陰晴），（陰云），（陰陰）}。用字母表{0,1}對(U1U2)的事件進行2元編碼如下：（晴晴）→0000，（晴云）→0001，（晴陰）→0011，（云晴）→0100，（云云）→0101，（云陰）→0111，（陰晴）→1100，（陰云）→1101，（陰陰）→1111。第六頁，共十六頁，2022年，8月28日2023/3/136§3.2離散無記憶（簡單）信源的等長編碼（3）如果限定碼字的長度為N（即每個碼字都是一個N維向量），則稱此編碼為等長編碼，能夠選擇的不同碼字的個數(shù)為DN。（4）如果限定碼字的長度為≤N（即每個碼字都是一個≤N維的向量），則稱此編碼為不等長編碼，能夠選擇的不同碼字的個數(shù)為D1+D2+…+DN=D(DN-1)/(D-1)。（注意：在不等長編碼中，并不能同時使用D(DN-1)/(D-1)個不同的碼字。一個長度為2的字母串究竟是兩個長度為1的碼字相連，還是一個長度為2的碼字？無法識別。在等長編碼中不存在這樣的識別問題）第七頁，共十六頁，2022年，8月28日2023/3/137§3.2離散無記憶（簡單）信源的等長編碼（本節(jié)以下將專門討論等長編碼）（5）編碼速率

R=NlogD/L。（6）無錯編碼

(U1U2…UL)的不同事件用不同的碼字來表示。能夠實現(xiàn)無錯編碼的充要條件是DN≥KL。（即編碼速率R=NlogD/L≥logK）（7）有錯編碼

(U1U2…UL)的有些不同事件用相同的碼字來表示。（8）有錯編碼的譯碼方法與“譯碼錯誤”概率當使用有錯編碼時，必須給出譯碼方法（一個碼字究竟翻譯成哪個事件）?！白g碼錯誤”的概率定義為pe=P{(U1U2…UL)=(u1u2…uL)|(u1u2…uL)的碼字在譯碼時并不譯為(u1u2…uL)}。第八頁，共十六頁，2022年，8月28日2023/3/138§3.2離散無記憶（簡單）信源的等長編碼（關于編碼速率的說明：編碼速率本來是編碼設備的性能指標。這就是說，首先有了編碼設備的編碼速率R0，然后選擇N和L，使得實際的編碼速率NlogD/L不能超過編碼設備的編碼速率R0

：R=NlogD/L≤R0。當編碼速率R比較高時，可以選擇比較大的N，因此可供選擇的碼字比較多，因此更容易設計出能夠快速識別的碼，降低譯碼的難度。當編碼速率R比較低時，意味著使用低成本的編碼設備。此時只能選擇不大的N，因此更需要編碼的技巧。）第九頁，共十六頁，2022年，8月28日2023/3/139§3.2離散無記憶（簡單）信源的等長編碼（9）在無錯編碼的前提下，編碼的最低代價當R≥logK時，能夠實現(xiàn)無錯編碼。當R<H(U1)時，無論怎樣編碼都是有錯編碼。這是因為R<H(U1)≤logK。（如果H(U1)=logK，則以上兩種情形已經(jīng)概括了全部情形。但如果H(U1)<logK，則還有一種情形）當logK>R>H(U1)時，雖然無論怎樣編碼都是有錯編碼，但可以適當?shù)鼐幋a和譯碼使譯碼錯誤的概率pe任意小。這就是所謂“漸進無錯編碼”。第十頁，共十六頁，2022年，8月28日2023/3/1310§3.2離散無記憶（簡單）信源的等長編碼（10）漸進無錯編碼（簡單地說就是：當R>H(U1)時，可以適當?shù)鼐幋a和譯碼使得譯碼錯誤的概率pe任意小。嚴格地說就是：）設給定了編碼設備的編碼速率R0，R0>H(U1)。則對任意的ε>0，總存在一個L0，使得對任意的L>L0，都有對(U1U2…UL)的等長編碼和對應的譯碼方法，滿足①實際的編碼速率R=NlogD/L≤R0，②譯碼錯誤的概率pe<ε。（11）漸進無錯編碼的原理大數(shù)定律。隨著L的增加，(U1U2…UL)的所有事件中，某些事件所占的比例越來越?。ā?），其發(fā)生的概率卻越來越大（→1）。第十一頁，共十六頁，2022年，8月28日2023/3/1311§3.2離散無記憶（簡單）信源的等長編碼（12）不能漸進無錯的編碼（簡單地說就是：當R<H(U1)時，無論怎樣編碼和譯碼都不能使譯碼錯誤的概率pe任意小。嚴格地說就是：）設給定了編碼設備的編碼速率R0，R0<H(U1)。則無論怎樣編碼和譯碼都不能同時滿足①實際的編碼速率R≤R0，②譯碼錯誤的概率pe任意小。第十二頁，共十六頁，2022年，8月28日2023/3/1312§3.2離散無記憶（簡單）信源的等長編碼設…U-2U-1U0U1U2…是離散無記憶（簡單）信源的輸出隨機變量序列。設U1的概率分布為取Vl是Ul的如下函數(shù)：當Ul=ak時，Vl=loga(1/qk)。則①隨機變量序列…V-2V-1V0V1V2…相互獨立，具有相同的概率分布；②第十三頁，共十六頁，2022年，8月28日2023/3/1313§3.2離散無記憶（簡單）信源的等長編碼取IL是(V1V2…VL)的如下函數(shù)：則①IL最終是(U1U2…UL)的函數(shù)；②③因此有切比雪夫不等式：對任意ε>0有P{(U1U2…UL)=(u1u2…uL)|H(U1)-ε≤IL≤H(U1)+ε}≥第十四頁，共十六頁，2022年，8月28日2023/3/1314§3.2離散無記憶（簡單）信源的等長編碼取L0使得則當L≥L0時總有因此當L≥L0時總有P{(U1U2…UL)=(u1u2…uL)|H(U1)-ε≤IL≤H(U1)+ε}≥1-ε。第十五頁，共十六頁，2022年，8月28日2023/3/1315§3.2離散無記憶（簡單）信源的等長編碼定義(p46)定義TU(L,ε)={(u1u2…uL)|H(U1)-ε≤I