信息論第5章 無失真信源編碼

第5章無失真信源編碼1編碼的意義通信的基本問題：如何高速、高質(zhì)地傳送信息。高速和高質(zhì)＝魚和熊掌。編碼討論的問題：（1）質(zhì)量一定，如何提高信息傳輸速度（提高編碼效率或壓縮比）---信源編碼（本章討論問題）（2）信道傳輸速度一定，如何提高信息傳輸質(zhì)量（抗干擾能力）----信道編碼（下一章討論）2信源輸出的符號序列,需要變換成適合信道傳輸?shù)姆栃蛄?一般稱為碼序列.對信源輸出的原始符號按照一定的數(shù)學規(guī)則進行的這種變換稱為編碼.完成編碼功能的器件稱為編碼器.接收短有一個譯碼器完成相反的功能.5.1編碼器3編碼：信息的組織方式編碼的實質(zhì)：對信源的原始符號按一定的數(shù)學規(guī)則進行變換。編碼的目的：提高信息傳輸?shù)挠行裕ㄐ旁淳幋a）；提高信息傳輸?shù)目煽啃?。（信源或信道編碼）

4幾個術(shù)語：信源符號：信源輸入S={s1,s2,…,sq}碼符號(碼元)：X={x1,x2,…,xr}碼字Wi：由xj(j=1,2,…,r)組成的長度為li的序列，Wi與si一一對應(yīng)。碼字長度(碼長)：Wi的長度li碼(碼書)：碼字Wi的集合C={W1,W2,…,Wq}編碼器：將信源符號si變換成Wi的設(shè)備5信源編碼信源編碼：把信源符號si映射為碼字Wi的過程。無失真編碼：映射是一一對應(yīng)、可逆的。無失真信源編碼：盡可能精確的再現(xiàn)信源的輸出信源編碼基本思想：盡可能縮短出現(xiàn)概率大的信源符號的碼6通信的根本問題是將信源的輸出，經(jīng)信道傳輸在接收端精確的或近似地重現(xiàn)出來，因此要首先解決兩個問題：

第三章中已經(jīng)回答了第一個問題,這一章要討論的是第二個問題.信源編碼器如下圖所示:7891011定長碼和變長碼12奇異碼和非奇異碼13N次擴展碼141516說明:本章我們討論的都是同價碼,即每個碼元符號所占的傳輸時間是相同的.顯然,對同價碼而言,定長碼中每個碼字的傳輸時間是相同的,而變長碼中每個碼字的傳輸時間不一定相等.175.2分組碼

定義：18奇異性1920唯一可譯性21即時性2223一個碼，若其中所有碼字均處于終端節(jié)點，即端點上，則該碼為非續(xù)長碼。2425不超過終端節(jié)點也叫端點。262728該樹的5個終端節(jié)點W1,W2,W3,W4,W5分別表示5個二進制碼字0，100，111，1010，1011

按樹圖法構(gòu)成的碼一定滿足即時碼的充要條件，因為從根到葉所走的路徑各不相同，而且中間節(jié)點不安排為碼字，所以一定滿足對前綴的限制。29各節(jié)點（包括樹根）長出的樹枝樹等于r30315.3定長碼

（5－1）32若令N＝1，則有即（5－2）（5－3）與5－1式一致。式5－3表示平均每個原始信源符號所需要的碼符號個數(shù)，對于定長碼，平均每個原始信源符號至少需要用個碼符號變換。333435定理5.3.136其中前一部分被視為正定理，后一部分被視為逆定理。373839編碼效率4041425.4變長碼變長碼是在碼符號序列長度N不大時就能編出效率很高而且無失真的信源碼。要實現(xiàn)無失真的信源編碼，變長碼必須是唯一可譯碼。變長碼要滿足唯一可譯碼的條件，它必須是非奇異碼，而且任意有限長N次擴展碼也是非奇異的。為能即時進行譯碼，變長碼還必須是即時碼。435.4.1碼的分類和主要編碼方法44454647485.4.2Kraft不等式49注意：僅僅是存在！5.4.2克拉夫特不等式

與麥克米倫不等式

克拉夫特（kraft）不等式505152定理5.4.3若存在一個碼長為l1，l2，…，lq的惟一可譯碼，則一定存在具有相同碼長的即時碼。若存在一個碼長為l1，l2，…，lq的惟一可譯碼滿足Kraft不等式（定理5.4.2）

存在具有相同碼長的即時碼（定理5.4.1）任何一個惟一可譯碼均可用一個即時碼來代替，而不改變?nèi)我淮a字的長度。即時碼可用樹圖法來構(gòu)造。因此要構(gòu)造惟一可譯碼，只需討論構(gòu)造即時碼。535.4.3唯一可譯碼的判別準則若碼長l1,l2,…,lq不滿足Kraft不等式à不是惟一可譯碼；反之，l1,l2,…,lq滿足Kraft不等式的碼，不一定是惟一可譯碼。結(jié)論：不能用克拉夫特不等式，只能根據(jù)定義判斷碼C是否是惟一可譯碼。判別依據(jù)：非惟一可譯變長碼有限長的碼符號序列能譯成兩種不同的碼字序列。54例：如下圖中情況發(fā)生，其中Ai，Bi都是碼字(Ai,Bi

C)。

B1一定是A1的前綴，而A1的尾隨后綴一定是另一碼字B2的前綴，B2的尾隨后綴又是其他碼字的前綴。最后，碼符號序列的尾部一定是一個碼字。55判別準則：5657唯一可譯碼的判別方法唯一可譯碼的判斷方法：方法一：（可確切判斷）計算出分組碼中所有可能的尾隨后綴集合F，觀察F中有沒有包含任一碼字，若無則為唯一可譯碼，否則一定不是唯一可譯碼。方法二：步驟如下

1。觀察是否是非奇異碼。若是奇異碼則一定不是唯一可譯碼。2。計算是否滿足Kraft不等式。若不滿足則一定不是唯一可譯碼。3。畫出碼樹，觀察是否滿足即時碼的樹圖的構(gòu)造，若滿足則是唯一可譯碼。585.4.4變長編碼定理對于已知信源S可用碼符號X進行變長編碼，而且對同一信源可有多種即時碼或惟一可譯碼。選擇哪一種呢？從高速度傳輸信息的角度，希望用短的碼符號組成碼字，即用碼長作為選擇準則-----引進碼的平均長度。59平均碼長6061對于某一信源和某一碼符號集來說，若有一個惟一可譯碼，其平均長度小于所有其他惟一可譯碼的平均長度，則該碼稱為緊致碼，或稱最佳碼無失真信源編碼的基本問題

找出緊致碼。62636465定理4.8（香農(nóng)信息論的主要定理之一）的結(jié)論：要做到無失真的信源編碼，編碼每個信源符號平均所需最少的r元碼元數(shù)為信源的熵Hr(S)。即Hr(S)是無失真信源壓縮的極限值。若編碼的平均碼長小于信源的熵值Hr(S)，則惟一可譯碼不存在，在譯碼或反變換時必然要帶來失真或差錯。通過對擴展信源進行變長編碼，當N∞時，平均碼長Hr(S)。66香農(nóng)第一定理的物理意義無失真信源編碼的實質(zhì)：對離散信源進行變換

變換后信源符號(信道的輸入信源)盡可能為等概率分布新信源符號平均所含的信息量達到最大à

使信道的信息傳輸率R達到信道容量C，實現(xiàn)信源與信道理想的統(tǒng)計匹配。無失真信源編碼定理通常又稱為無噪信道編碼定理。表述為：若信道的信息傳輸率R不大于信道容量C，總能對信源的輸出進行適當?shù)木幋a，使得在無噪無損信道上能無差錯地以最大信息傳輸率C傳輸信息，但要使信道的信息傳輸率R大于C而無差錯地