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

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

4幾個(gè)術(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)出來，因此要首先解決兩個(gè)問題：

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

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

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

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

與麥克米倫不等式

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

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

C)。

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

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

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

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

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