第5章 信源編碼part2v1(74p)

第5章信源編碼信源編碼（主要內(nèi)容）信源編碼定理信源編碼概念香農(nóng)第一定理香農(nóng)第三定理信源編碼方法離散信源編碼連續(xù)信源編碼相關(guān)信源編碼變換編碼2024/3/202變長碼的編碼方法發(fā)展比較成熟，常見的方法有：香農(nóng)編碼費(fèi)諾編碼霍夫曼編碼游程編碼冗余位編碼2024/3/203香農(nóng)編碼設(shè)有離散無記憶信源，記作：香農(nóng)編碼的編碼步驟如下：(2)令，并用表示第個(gè)碼字之前的累加概率，即：。

將信源符號按概率從大到小依次排列。設(shè)排序后的消息分別記為，對應(yīng)概率為(4)將累加概率用二進(jìn)制表示，去除小數(shù)點(diǎn)，根據(jù)碼長并取小數(shù)點(diǎn)后共

位作為的編碼。(3)確定滿足下列不等式的整數(shù),并令為第個(gè)碼字的長度。編碼步驟香農(nóng)編碼-例1解:(1)按概率從大到小依次排列(2)計(jì)算累加概率例

對信源編香農(nóng)碼。page7(3)計(jì)算碼字長度注意：是對算自信息量，而不是對算。大于等于自信息量最小整數(shù)page8(4)根據(jù)累加概率進(jìn)行編碼注意：此處是按

進(jìn)行編碼，而不是按

編碼。十進(jìn)制小數(shù)二進(jìn)制小數(shù)十進(jìn)制整數(shù)二進(jìn)制整數(shù)碼字碼字碼字注意補(bǔ)零注意補(bǔ)零page10碼字碼字碼字注意補(bǔ)零碼字注意補(bǔ)零page11碼字碼字注意補(bǔ)零碼字注意補(bǔ)零碼字碼字page12碼字碼字碼字碼字碼字碼字注意補(bǔ)零注意補(bǔ)零檢驗(yàn)是否為即時(shí)碼？計(jì)算編碼效率折算后，平均每個(gè)信源符號的最大可能載信量要求平均每個(gè)信源符號傳遞的信息量通過以上實(shí)例發(fā)現(xiàn)，香農(nóng)碼的效率并不算高。當(dāng)所有消息的概率為效率可達(dá)100%。香農(nóng)編碼-例2page15解:(1)按概率從大到小依次排列例編二進(jìn)制香農(nóng)碼。對(2)計(jì)算累加概率(3)計(jì)算各碼字長度碼字01011101101111(4)根據(jù)進(jìn)行編碼(5)計(jì)算編碼效率變長碼的編碼方法發(fā)展比較成熟，常見的方法有：香農(nóng)編碼費(fèi)諾編碼霍夫曼編碼游程編碼冗余位編碼2024/3/2018費(fèi)諾編碼設(shè)有離散無記憶信源，編碼步驟如下：

將信源符號按概率從大到小依次排列。設(shè)排序后的消息分別記為x1,x2,…,xn。(2)將信源符號按概率分成若干組，使每組的概率的和盡量接近或相等。若編二元碼就分兩組，編元碼就分成組。(3)給每組分配一位碼元，碼元的分配是任意的。(4)對每一分組按上述原則繼續(xù)分組，直到概率不可分。page20例

對信源編二元費(fèi)諾碼。解:(1)按概率從大到小依次排列(2)按概率分組(3)為每組分配碼元(4)繼續(xù)分組page21檢驗(yàn)是否為即時(shí)碼？計(jì)算編碼效率

從計(jì)算結(jié)果可看出，編碼效率較高。但這并不意味著費(fèi)諾碼的效率一定高于香農(nóng)碼。

實(shí)踐表明，費(fèi)諾碼比較適合于每次分組的概率的和比較接近的情況。最理想的情況是：每次分組的概率的和都恰好相等，這時(shí)編碼效率可達(dá)100%。例

對信源編二元費(fèi)諾碼。解:(1)按概率從大到小依次排列(2)按概率分組(3)為每組分配碼元(4)繼續(xù)分組(5)編碼效率變長碼的編碼方法發(fā)展比較成熟，常見的方法有：香農(nóng)編碼費(fèi)諾編碼霍夫曼編碼（哈夫曼編碼）游程編碼冗余位編碼2024/3/2024哈夫曼編碼設(shè)有離散無記憶信源，二元碼的編碼步驟如下：

將信源符號按概率從大到小依次排列。設(shè)排序后的消息分別記為。

給兩個(gè)概率最小的信源符號和各分配一個(gè)碼符號“0”和“1”，將這兩個(gè)信源符號合并成一個(gè)新符號，并用作為新符號的概率，結(jié)果得到一個(gè)只包含個(gè)信源符號的新信源。將該信源稱為第一次縮減信源，用表示。page26(3)將縮減信源的符號仍按概率從大到小的順序排列，重復(fù)步驟2，得到只含個(gè)符號的縮減信源。(4)重復(fù)上述步驟，直至縮減信源只剩兩個(gè)符號為止。此時(shí)所剩兩個(gè)符號的概率之和必為1。然后從最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號所對應(yīng)的碼字。例

對編二元哈夫曼碼(1)排序(2)第一次縮減信源(3)第二，三，…次縮減信源(4)最后一級概率碼字page28檢驗(yàn)是否為即時(shí)碼？計(jì)算編碼效率：從計(jì)算結(jié)果可看出，編碼效率較高。page30問題：哈夫曼方法所編的碼字是否唯一？例

對編二元哈夫曼碼。解:(1)排序答案：不唯一。

1.每次分配碼字，0和1都是任意的。

2.當(dāng)新符號的概率與已有符號相等時(shí)，這些符號誰在前，誰在后，也會(huì)導(dǎo)致編碼結(jié)果不同；而且所得編碼方案性能也有差異。page31(2)第一次縮減信源(3)第二，三，…次縮減信源(4)最后一級概率碼字方案一：每次符號概率相等時(shí)，新碼字都排在最后面。碼元/符號page32概率碼字方案二：每次符號概率相等時(shí)，新碼字都排在最上面。碼元/符號page33方案一方案二從直觀上看，方案二的各碼字之間，碼字長度更均勻。由此得出結(jié)論：

在哈夫曼編碼過程中，對縮減信源符號按概率由大到小的順序重新排列時(shí)，應(yīng)使合并后的新符號盡可能排在靠上的位置，這樣可使合并后的新符號重復(fù)編碼次數(shù)減少，碼字間長度更加均勻。練習(xí)：設(shè)有信源

(1)編二進(jìn)制哈夫曼碼(2)計(jì)算平均碼長及編碼效率碼字概率(1)(2)計(jì)算平均碼長及編碼效率比特/符號多元哈夫曼編碼page36多（）元碼的編碼步驟：(1)按概率從大到小排序。(2)挑出概率最小的

個(gè)信源符號，分別賦予碼符號，并將概率的和賦予合并后的新符號，得到。(3)按相同步驟計(jì)算。(4)直到最后一級，倒序讀出碼字。多元碼的編碼過程與二元碼基本類似，但可能會(huì)遇到如下問題：可能出現(xiàn)最后一級信源，信源符號數(shù)不足

個(gè)的情況。page38在碼樹圖中，某些分枝從第一級就被砍掉，從而造成平均碼長偏長的情況。解決辦法：從最后一級縮減信源倒著排，保證最后一級有m個(gè)符號。要求最后一級縮減信源保證有m個(gè)符號，則有：倒數(shù)第二級倒數(shù)第三級……第一級例：，求：第一級信源符號所需保留個(gè)數(shù)。為保證每次縮減均為m個(gè)變1個(gè)，第一級符號所缺的個(gè)數(shù)：第一級符號保留的個(gè)數(shù)：第一級保留【保留+欠缺=m】其中：*page40方案1：碼元/符號方案2：碼元/符號page41計(jì)算方案2的編碼效率：練習(xí)：(1)編三進(jìn)制哈夫曼碼(2)計(jì)算平均碼長及編碼效率第一級應(yīng)保留解：(1)關(guān)鍵是求第一級信源應(yīng)保留的符號個(gè)數(shù)page42(2)計(jì)算平均碼長及編碼效率碼元/符號比特/符號2024/3/2043r元霍夫曼碼二進(jìn)制霍夫曼碼的編碼方法可以很容易推廣到r進(jìn)制的情況。只是編碼過程中構(gòu)成縮減信源時(shí)，每次都是將r個(gè)概率最小的符號合并，并分別用0,1,…,(r-1)碼符號表示。例設(shè)有離散無記憶信源碼符號集X＝(0,1,2)，試構(gòu)造一種三進(jìn)制霍夫曼碼。2024/3/2044其中信源s9是增補(bǔ)的，令其概率為零.碼符號集X＝(0,1,2)，試構(gòu)造一種三進(jìn)制霍夫曼碼page45定理：哈夫曼碼是緊致碼。說明：這里只證明二元哈夫曼碼是緊致碼，其結(jié)論可推廣到多元哈夫曼碼。思路：采用類似數(shù)學(xué)歸納法的證明方法。證明最后一級縮減信源是緊致碼假設(shè)級縮減信源是緊致碼證明級縮減信源是緊致碼證明：對于二元碼，最后一級縮減信源只有2個(gè)信源符號，因此一定是緊致碼。消息數(shù)級縮減信源的平均碼長第i個(gè)消息的概率第i個(gè)消息的碼長在所有可能的唯一可譯碼編碼方案中，的長度最短。假設(shè)級縮減信源對應(yīng)的編碼是緊致碼，因此有：對于級縮減信源，一定有條消息，而且其中某兩個(gè)消息的概率的和一定為級某消息的概率。page47只要是緊致碼，則縮減前信源的編碼也是緊致碼與碼長無關(guān)的常數(shù)變長碼的編碼方法發(fā)展比較成熟，常見的方法有：香農(nóng)編碼費(fèi)諾編碼霍夫曼編碼游程編碼冗余位編碼2024/3/2048游程編碼與游程變換2024/3/2049“0”游程“1”游程游程長度序列(游程序列)：何謂游程？回答：數(shù)字序列中連續(xù)出現(xiàn)相同符號的一段。例：二元序列：…000101110010001…前面方法針對無記憶信源，對于有記憶信源前面方法編碼效率不高，一般采用其它編碼。如：游程編碼。游程變換:

用交替出現(xiàn)的“0”游程和“1”游程的長度，來表示任意二元序列…31132131…為多元序列游程編碼與游程變換說明說明：游程變換規(guī)定游程序列從“0”開始游程變換是一一對應(yīng)變換，也是可逆變換它減弱了二元序列的相關(guān)性可對變換得到的多元序列采用其它編碼方法，如：哈夫曼編碼，可進(jìn)一步壓縮信源，提高通信效率多元序列也可以變換成游程序列，但是需要增加標(biāo)志位，可能會(huì)抵消壓縮編碼得到的好處，意義不大。所以主要討論二元序列。2024/3/2050游程序列的概率特性2024/3/2051問題：變換得到的游程序列的概率特性？分析：若二元序列的概率特性已知，可計(jì)算出游程序列的概率特性。因?yàn)樵蚨蛄信c游程序列一一對應(yīng)。“0”游程長度概率為：p[L(0)]=p0L(0)-1p1;

“0”游程長度的熵為：H[L(0)]=H(p0)/p1;“0”游程序列的平均長度為：l0=E[L(0)]=1/p1設(shè)二元序列為獨(dú)立序列，其中“0”和“1”出現(xiàn)的概率分別為p0和p1，L(0)為某“0”游程長度，則可以推出：游程序列的概率特性2024/3/2052當(dāng)二元序列有相關(guān)性時(shí)，需要討論聯(lián)合（或條件）概率，有類似結(jié)論。下面進(jìn)行推導(dǎo)。算得原二元序列的熵為：H(X)={H[L(0)]+H[L(1)]}/(l0+l1)=H(p0)=H(p1)“1”游程可推出類似結(jié)論：p[L(1)]=p1L(1)-1p0;H[L(1)]=H(p0)/p0;l1=E[L(1)]=1/p02024/3/20530/1游程長度的概率：p[L(0)]/p[L(1)]0/1游程長度的概率：p[L(0)]/p[L(1)]2024/3/2054同理，有2024/3/2055平均游程長度：E[L(0)]/E[L(1)]平均游程長度：2024/3/20560/1游程長度的熵：H[L(0)]/H[L(1)]0/1游程長度的熵：H[L(0)]/H[L(1)]57二元序列的熵H(X)0游程序列的熵與1游程序列的熵之和除以它們的平均游程長度之和。H(X)={H[L(0)]+H[L(1)]}/(l0+l1)={H(p0)/p1+H(p0)/p0

}/(1/

p1+1/p0)=H(p0)=H(p1)游程變換后符號熵沒有變。原因：游程變換是一一對應(yīng)變換2024/3/2058有相關(guān)性的二元序列游程變換若原二元序列是二階馬氏鏈，由它變換而來的游程序列將是獨(dú)立序列。0游程：10X；1游程：01X對于高階馬氏鏈，若階數(shù)大于2，經(jīng)變換的游程序列將不再是獨(dú)立序列。如三階馬氏鏈：Y10X→一階馬氏鏈一般k階馬氏鏈，由之變換而來的游程序列將為k-2階馬氏鏈。2024/3/2059游程序列編碼從前面可知，通過游程變換來解除或減弱二元序列的相關(guān)性是相當(dāng)有效的，因此對游程序列進(jìn)行哈夫曼編碼可達(dá)到較高的編碼效率。分別對“0”游程和“1”游程的長度進(jìn)行哈夫曼編碼，當(dāng)0游程和1游程的編碼效率都很高時(shí)，采用游程編碼的效率也很高。游程長度：60建立游程長度和碼字間的碼表困難實(shí)際上，游程長，出現(xiàn)概率小概率小的碼字對平均碼長影響小對長碼進(jìn)行截?cái)嗵幚碛纬涕L度與碼字之間的碼表2024/3/2061取適當(dāng)值n，游程長度為1,2,…,2n-1,2n，所有大于2n者，都按2n處理。所有長度大于等于2n的游程，只有一個(gè)碼字C，需要按右表進(jìn)一步區(qū)分。當(dāng)游程長度大于或等于2n+1時(shí)，需要兩個(gè)或兩個(gè)以上的C。概率小，碼字長。0游程和1游程應(yīng)分別編碼，建立各自的碼字和碼表。碼字可重復(fù)，C必須不同。如：C0

或C1游程長度≥2nC之后為一個(gè)n位的自然碼（C0

或C1）2nC00…002n+1C00…01……2n+1-1C11…112n+1

C00…00C00…002n+2-1C00…00C11…11……變長碼的編碼方法發(fā)展比較成熟，常見的方法有：香農(nóng)編碼哈夫曼編碼費(fèi)諾編碼游程編碼冗余位編碼2024/3/2062冗余位編碼（Lynch-Davission）何謂冗余位？回答：信源序列中不攜帶信息的符號。

比如：語音中的話語間歇、圖像的單一背景部分。2024/3/2063分析：此類符號，除了符號數(shù)目或所占時(shí)長外，可不必傳送，去掉一部分可以提高通信效率。冗余位編碼：

分解信源序列為冗余位序列和冗余位序列，分別編碼。冗余位編碼（Lynch-Davission）設(shè)有多元信源序列：x

為信息位；y

冗余位x1,x2,…xm1,y,y,…,y,xm1+1,xm1+2,…,xm2,y,y,…

可用下面兩個(gè)序列來代替：冗余位序列：111,…,100,…,000111,…,111000信息位序列：x1,x2,…xm1,xm1+1,xm1+2,…,xm2,…2024/3/2064一個(gè)多元信源序列=

一個(gè)二元序列+一個(gè)縮短的多元序列對兩個(gè)序列分別編碼，可有效地壓縮信源二元序列進(jìn)行游程編碼多元序列直接采用哈夫曼編碼分幀傳送冗余位序列：L-D編碼要求同時(shí)傳送兩個(gè)序列，才能在接收端實(shí)時(shí)恢復(fù)出原來的多元信源序列，實(shí)用上有困難，通常采用分幀傳送的方式L-D編碼：在冗余位序列中取N個(gè)符號作為一幀，編成一個(gè)碼字，其后就把本幀中的信息位按序排列，再取下一幀作同樣處理。在接收端根據(jù)這些碼字和信息序列進(jìn)行譯碼。每個(gè)碼字中含有：信息位的數(shù)量Q和位置信息T2024/3/2065L-D編碼的譯碼過程收端收到Q和T后，如下譯碼，求解出信息位的位置：2024/3/2066編碼Q和TQ可以取0到N的各種值，共N+1種，故2024/3/2067例：對一冗余位序列編L-D碼2024/3/2068一冗余位序列：001000000010000，N=15這里Q=2，n1=3，n2=11，則Q=2和T=47的譯碼過程收端收到Q=2和T=47后，如下譯碼：2024/3/2069Q=2和T=47的譯碼過程-續(xù)2024/3/2070對例題的說明當(dāng)Q為0或N時(shí)，相當(dāng)于全0或全1序列，此時(shí)T值為0，在編碼時(shí)只需編Q值，對于N=15，得0000或1111L-D編碼與哈夫曼碼不同，不需要已知概率特性。也就是編成的碼字與概率特性無關(guān)，而與一