《信息論與編碼》 課件 第5章信源編碼

1第5章信源編碼目的：提高通信系統(tǒng)的有效性，即通過編碼，用盡可能短的編碼序列符號來表示原信源序列?；舅枷胧牵?.盡可能去除原消息序列中符號之間的相關(guān)性；2.盡可能使編碼后各符號出現(xiàn)的概率相等。2第5章信源編碼主要解決兩個方面的問題：1.“信源編碼是用盡可能短的編碼序列符號來表示原信源序列”，這個“短”，有沒有極限？如果有，該極限是多少？2.用什么方法達(dá)到或者接近該極限？3非分組碼和分組碼將長消息序列按順序分成若干個符號一組，對每一組獨立進(jìn)行編碼，稱為分組碼；否則稱為非分組碼。定長碼和變長碼若編碼后的碼字長度都相同，則稱為定長碼；否則稱為變長碼。5.1信源編碼的有關(guān)概念5.1.1幾個概念4奇異碼和非奇異碼若編碼前的信源組和編碼后的碼字是一一對應(yīng)的，則稱為非奇異碼；否則稱為奇異碼。非唯一可譯碼和唯一可譯碼如果任意有限長的碼元序列都只能被唯一地分割成一個個的碼字，則稱為唯一可譯碼；否則稱為非唯一可譯碼。5.1信源編碼的有關(guān)概念5非即時碼和即時碼在接收端接收碼元序列的過程中，如果接收到的碼元序列已經(jīng)組成了一個碼字，但接收端并不能立即判斷出，還要等下一個碼字開始接收的時候才能判斷出前者已經(jīng)是一個完整碼字，從而開始譯碼，則稱為非即時碼；反之則稱為即時碼。5.1信源編碼的有關(guān)概念65.1信源編碼的有關(guān)概念5-1編碼的分類75.1信源編碼的有關(guān)概念信源符號ai符號出現(xiàn)的概率p(ai)碼1碼2碼3碼4碼5a11/2000011a21/40111101001a31/8100000100001a41/811110110000001例5-1表5-1中的分組碼1、碼2、碼3、碼4和碼5，從上述的4個方面分別判斷屬于什么類型的碼。表5-1碼的不同屬性85.1.2克勞福特不等式唯一可譯碼存在的充分和必要條件各碼字的長度Ki應(yīng)符合克勞夫特不等式：

其中m是進(jìn)制，n是信源可能取值的符號數(shù)。9例：設(shè)對符號集{ai,i=1,2,3,4}進(jìn)行二進(jìn)制編碼；(1)對應(yīng)的碼長分別為K1＝1,K2＝2,K3＝2,K4＝3，試判斷是否存在這樣的唯一可譯碼；(2)

若K1=1,

K2=2,

K3=3,

K4=3又如何？答：(1)由克勞福特定理可得：因此不存在滿足這種碼長的唯一可譯碼。

10(2)由克勞福特定理可得：因此滿足這種碼長的唯一可譯碼是存在的,例如{0，10，110，111}。

克勞夫特不等式只是用來說明唯一可譯碼是否存在，并不能作為唯一可譯碼的判據(jù)。例如，{0,10,010,111}11無失真信源編碼定理定長信源編碼定理變長信源編碼定理限失真信源編碼定理

5.2信源編碼定理125.2.1無失真信源編碼（香農(nóng)第一定理）X＝(X1X2…Xi…XL)Xi

{a1,a2,…,ai,…,an}

nL種信源編碼器Yk

{b1,b2,…,bj,…,bm}

M=mKL種

KL

logm用Y表示L長的信源序列X，則送出一個信源符號所需要的信息率平均為

編碼目的：使最小。

13無失真信源編碼定理研究的內(nèi)容:最小信息率為多少時，才能得到無失真的譯碼？若小于這個信息率是否還能無失真地譯碼?

無記憶平穩(wěn)信源平均符號熵為HL(X)，對任意

，只要

則當(dāng)L足夠大時，必可使譯碼差錯概率小于δ；即可實現(xiàn)幾乎無失真編碼；

反之，當(dāng)時，譯碼差錯一定是有限值，而L足夠大時，譯碼幾乎必定出錯。141.無失真定長信源編碼定理：碼字所能攜帶的信息量大于信源序列輸出的信息量，則可以使傳輸幾乎無失真，當(dāng)然條件是L足夠大。反之，當(dāng)時，不可能構(gòu)成無失真的編碼，也就是不可能做一種編碼器，能使收端譯碼時差錯概率趨于零。當(dāng)時，則為臨界狀態(tài)，可能無失真，也可能有失真。15說明：L,,

,δ三者之間有什么關(guān)系？對于給定的

和δ，多大的L算足夠大？16問題：式中

為信源序列的自信息方差，

為一正數(shù)。當(dāng)

和

2均為定值時，只要L足夠大，Pe可以小于任一正數(shù)

。即，如果給定差錯概率上界δ，則

越小，要求的編碼長度L就越大。L越大，編碼器越復(fù)雜，且時延越大，在有時延要求的場合，往往難以滿足實時性要求。增加

，可以減小對編碼長度L的要求，但以犧牲編碼效率為代價：17討論：18例題5-3：設(shè)離散無記憶信源概率空間為若要求編碼效率為90%，譯碼差錯概率δ≤10-6試求所需要的編碼序列長度L。19例題5-3：自信息方差為：若要求編碼效率η=90%：若要求編碼效率δ≤10-6：當(dāng)L有限時，要做到高編碼效率、低錯誤率，對于定長編碼來說是不可能做到的。對例5-3中的信源，有8種不同的信源符號取值（a1~a8），如果用二進(jìn)制序列來表示的話，每個符號需要3

bit（3位二進(jìn)制數(shù)可以表示8中不同的符號）。但由于不是等概率的，所以其熵H(X)=2.55

bit，按照無失真定長信源編碼定理，其極限編碼長度是2.55bit，而，也就是說，只能表示5.856種不同的符號，其余的符號怎么辦？實際上，由于a1~a8中部分符號的概率較小，如果序列長度L足夠大，則總有某種序列出現(xiàn)的概率足夠小，對這些概率足夠小的序列，如果不設(shè)計對應(yīng)的編碼碼字，造成的錯誤概率也非常小。20思考：212.無失真變長信源編碼定理：平均碼長：定長編碼中，由于所有的碼字都使用相同的長度，限制了其靈活性，導(dǎo)致或者效率不高，或者復(fù)雜度太高（L太大）。變長編碼可以對出現(xiàn)概率大的信源盡量用短碼，從而提高編碼效率.（統(tǒng)計匹配）222.無失真變長信源編碼定理：(1).單符號變長編碼定理若離散單符號信源X：xi∈{a1,a2,…,an}的熵為H(X)，對每個單符號進(jìn)行無失真變長編碼，設(shè)yj∈{b1,b2,…,bm}。則23(2).離散平穩(wěn)無記憶序列變長編碼定理

對于平均符號熵為HL(X)的離散平穩(wěn)無記憶信源，必存在一種無失真編碼方法，使平均信息率滿足不等式其中

為任意小正數(shù)。24例題5-4：設(shè)離散無記憶信源概率空間為試討論其編碼效率。若L=1,用二元定長編碼(0，1)來構(gòu)造一個即時碼：x1→0，x2→1。平均碼長＝1二元碼符號/信源符號

編碼效率為輸出的信息率為25（續(xù)）例題5-4：若對長度為L=2的信源序列進(jìn)行變長編碼，其即時碼如表5-2所示。26（續(xù)）例題5-4：xip(xi)即時碼x1x19/160x1x23/1610x2x13/16110x2x21/16111表5-2長度為2的信源序列對應(yīng)的即時碼該碼平均長度：單符號平均碼長：編碼效率為：27（續(xù)）例題5-4：28（續(xù)）例題5-4：L＝3

η3=0.985

R3＝0.985比特/二元碼符號

L＝4

η4=0.991

R4＝0.991比特/二元碼符號

29（續(xù)）例題5-4：定長二元碼編碼，要求編碼效率達(dá)到96％時，允許譯碼錯誤概率δ≤10-5

。305.2.2限失真信源編碼（香農(nóng)第三定理）

信息率失真函數(shù)給出了失真小于D時所必須具有的最小信息率R(D)；只要信息率大于R(D)，一定可以找到一種編碼，使譯碼后的失真小于D。

限失真信源編碼定理：對于任意的D≥0和

＞0，當(dāng)信息率R>R(D)時，一定存在一種編碼方法，其譯碼失真小于或等于D+

，條件是編碼的信源序列長度L足夠長。反之，如果R<R(D)，則無論采用什么編碼方法，其譯碼失真必大于D。315.2.2限失真信源編碼（香農(nóng)第三定理）香農(nóng)第三定理是一個存在性定理，它只說明一定存在一種滿足要求的編碼方法。至于如何尋找這種最佳壓縮編碼方法，定理中沒有給出。在實際應(yīng)用中，該理論主要存在以下兩類問題：（1）符合實際信源的R(D)函數(shù)的計算相當(dāng)困難；（2）即使求得了符合實際的信息率失真函數(shù)，還需要研究采用何種編碼方法，才能達(dá)到或接近極限值R(D)。325.2.2限失真信源編碼（香農(nóng)第三定理）33香農(nóng)編碼哈弗曼編碼算術(shù)編碼（非分組碼）

5.3常用信源編碼方法345.3.1

香農(nóng)編碼將信源消息符號按其出現(xiàn)的概率大小依次排列確定滿足下列不等式的整數(shù)碼長Ki

5.3常用信源編碼方法35香農(nóng)編碼為了編成唯一可譯碼，計算第i個消息的累加概率將累加概率Pi變換成二進(jìn)制數(shù)。取Pi二進(jìn)數(shù)的小數(shù)點后Ki位即為該消息符號的二進(jìn)制碼字。

5.3常用信源編碼方法36香農(nóng)編碼為了編成唯一可譯碼，計算第i個消息的累加概率將累加概率Pi變換成二進(jìn)制數(shù)。取Pi二進(jìn)數(shù)的小數(shù)點后Ki位即為該消息符號的二進(jìn)制碼字。

37香農(nóng)編碼

香農(nóng)編碼的基本做法：是把長度為1的整個累積概率區(qū)間，按照信源符號集中q個信源符號的概率大小，分成q份不同長度的子區(qū)間（每份子區(qū)間的長度正比于對應(yīng)符號的概率大?。?，將每種信源符號xi，映射到其對應(yīng)子區(qū)間上的一個點。這樣，每個信源符號xi映射區(qū)間都是不重疊的，從而可以保證唯一可譯碼，而且可以證明，也是即時碼；另一方面，碼字長度由其概率決定，概率大的用短碼。

38香農(nóng)編碼

例5.4設(shè)信源共7個符號消息

信源消息符號ai符號概率p(ai)累加概率Pi-logp(ai)碼字長度Ki碼字a10.2002.343000a20.190.22.413001a30.180.392.483011a40.170.572.563100a50.150.742.743101a60.100.893.3441110a70.010.996.667111111039香農(nóng)編碼

香農(nóng)編碼效率不高，不具有實際應(yīng)用價值，但其概率匹配的思想很有指導(dǎo)意義。405.3.2

哈夫曼編碼哈夫曼編碼是按照概率匹配思想構(gòu)建的一種具有實際使用價值的編碼方法。哈夫曼編碼是唯一可譯碼、即時碼。411.哈夫曼樹圖5-1碼樹結(jié)構(gòu)圖42碼樹樹根樹枝數(shù)節(jié)點終端節(jié)點節(jié)數(shù)非滿樹滿樹碼字的起點碼的進(jìn)制數(shù)碼字或碼字的一部分碼字碼長變長碼等長碼432哈夫曼編碼(碼樹法)設(shè)信源符號集X={x1,x2,…,xq}，對應(yīng)的概率為p(X)={p(x1),p(x2),…,p(xq)}，且所有的p(x)>0，其編碼步驟如下：以q個信源符號的概率為權(quán)值，構(gòu)造q個帶權(quán)值的節(jié)點。每個節(jié)點作為一棵樹，構(gòu)造一個具有q棵樹的森林；在森林中選出兩棵根節(jié)點權(quán)值最小的樹作為一棵新樹的左、右子樹，且置新樹的附加根節(jié)點權(quán)值為其左、右子樹上根節(jié)點權(quán)值之和；442哈夫曼編碼(碼樹法)從森林中刪除這兩棵樹，同時把新樹加入到森林中；重復(fù)步驟②、③，直到森林中只有一棵樹為止，此樹便是哈夫曼樹，需要編碼的q個符號為該哈夫曼樹的q個終端節(jié)點；(將哈夫曼樹中指向左子樹的分支標(biāo)記為“0”，指向右子樹的分支標(biāo)記為“1”，從根節(jié)點到每個終端節(jié)點路徑上的“0”、“1”組成的序列作為各個終端節(jié)點對應(yīng)的編碼，即得哈夫曼編碼。452哈夫曼編碼(碼樹法)例5-6：設(shè)給定信源X={x1,x2,x3,x4,x5,x6,x7}，對應(yīng)的概率為p(X)={0.2,0.19,0.18,0.17,0.15,0.10,0.01}。給出哈夫曼編碼過程。0.010.100.110.150.260.170.180.350.610.190.200.3910010

1010101圖5-2

碼樹法哈夫曼編碼過程462哈夫曼編碼(圖表法)將q個信源符號按概率分布的大小，以遞減次序排列起來，設(shè)用“0”和“1”碼符號分別代表概率最小的兩個信源符號，并將兩個概率最小的符號合并成一個符號，合并的符號概率為兩個符號概率之和，從而得到只包含q-1個符號的新信源，稱為縮減信源。472哈夫曼編碼(圖表法)把縮減信源的符號仍舊按概率大小以遞減次序排列，再將其概率最小的兩個信源符號分別用“0”和“1”表示，并將其合并成一個符號，概率為兩符號概率之和，這樣又形成了q-2個符號的縮減信源。依此繼續(xù)下去，直至信源只剩下兩個符號為止。將這最后兩個信源符號分別用“0”和“1”表示。然后從最后一級縮減信源開始，向前返回，就得出各信源符號所對應(yīng)的碼符號序列，即對應(yīng)的碼字。482哈夫曼編碼(圖表法)表5-2圖表法哈夫曼編碼過程例5-6：設(shè)給定信源X={x1,x2,x3,x4,x5,x6,x7}，對應(yīng)的概率為p(X)={0.2,0.19,0.18,0.17,0.15,0.10,0.01}。給出哈夫曼編碼過程。492哈夫曼編碼信源符號xi概率p(xi)碼字Wi碼長Kix10.20102x20.19112x30.180003x40.170013x50.150103x60.1001104x70.0101114502哈夫曼編碼

碼元/符號

bit/符號

51哈夫曼編碼結(jié)果并不是唯一的哈夫曼樹的左右分支表示“0”或者“1”，是可以互換的；當(dāng)有多個節(jié)點具有相同的概率時，選擇哪些節(jié)點進(jìn)行合并是任意的。如果縮減信源中有兩個以上的節(jié)點概率相同，則應(yīng)優(yōu)先選擇未被合并過（或合并次數(shù)少）的節(jié)點進(jìn)行合并，以便盡量減小編碼方差，從而減小編碼設(shè)備復(fù)雜度。52哈夫曼編碼結(jié)果并不是唯一的例

設(shè)有離散無記憶信源給出哈夫曼編碼過程。532哈夫曼編碼哈夫曼碼是用概率匹配方法進(jìn)行信源編碼。哈夫曼碼的編碼方法保證了概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長碼，充分利用了短碼；縮減信源的最后二個碼字總是最后一位不同，從而保證了哈夫曼碼是即時碼。545.3.3

算術(shù)編碼香農(nóng)編碼和哈夫曼編碼，都是基于分組的塊編碼。分組編碼方法沒有考慮到組間符號的相關(guān)性，因此編碼效率會有所損失。增加碼長可以考慮更多符號間的相關(guān)性，但會增加編碼復(fù)雜度及編碼時延。算術(shù)編碼是一種非分組編碼方法，其基本思路是借鑒香農(nóng)編碼的區(qū)間映射思想。555.3.3

算術(shù)編碼算術(shù)編碼從全序列出發(fā)，將不同的信源序列的累計概率映射到[0,1]區(qū)間上，使每個序列對應(yīng)區(qū)間上的一點，也就是說，把區(qū)間[0,1]分成許多互不重疊的小區(qū)間，不同的信源序列對應(yīng)不同的小區(qū)間，可以證明，只要這些小區(qū)間互不重疊，就可以編得即時碼。0(P1)P2

P3

P4P5……1

……p1

p2p3p4565.3.3

算術(shù)編碼問題：是否需要等到要編碼的序列全部都已知以后才開始進(jìn)行區(qū)間映射（編碼）嗎？設(shè)P(S)表示序列S的累積概率（即其對應(yīng)的子區(qū)間的起始點），A(S)為序列S對應(yīng)的子區(qū)間長度，C(S)表示對序列S編碼得到的的碼字，pr表示m進(jìn)制單符號xr的概率，Pr(r=0,1,2,…,m-1)表示m進(jìn)制單符號xr的累計概率?？山⑦f推更新過程：575.3.3

算術(shù)編碼符號符號概率pi符號累積概率Pja0.100(1/2)0.000b0.010(1/4)0.100c0.001(1/8)0.110d0.001(1/8)0.111例5-7

有4個符號a，b，c，d構(gòu)成簡單序列S＝abda，各符號及其對應(yīng)概率如下表（二進(jìn)制），試給出算術(shù)編解碼過程。585.3.3

算術(shù)編碼設(shè)起始狀態(tài)為空序列?，則A(?)＝1，P(?)＝0。595.3.3

算術(shù)編碼設(shè)起始狀態(tài)為空序列?，則A(?)＝1，P(?)＝0。605.3.3

算術(shù)編碼故編碼后的碼字C(