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

1、1第第5 5章章 無失真信源編碼無失真信源編碼2編碼的意義編碼的意義通信的基本問題通信的基本問題：如何高速、高質(zhì)地傳送信息。如何高速、高質(zhì)地傳送信息。高速和高質(zhì)魚和熊掌。高速和高質(zhì)魚和熊掌。編碼討論的問題編碼討論的問題：（1 1）質(zhì)量一定，如何提高信息傳輸速度（提高編碼效率或壓縮比）質(zhì)量一定，如何提高信息傳輸速度（提高編碼效率或壓縮比）- 信源編碼（本章討論問題）信源編碼（本章討論問題）（2 2）信道傳輸速度一定，如何提高信息傳輸質(zhì)量（抗干擾能力）信道傳輸速度一定，如何提高信息傳輸質(zhì)量（抗干擾能力） -信道編碼（下一章討論）信道編碼（下一章討論）3信源輸出的符號序列,需要變換成適合信道傳輸?shù)姆?/p>

2、號序列,一般稱為碼序列.對信源輸出的原始符號按照一定的數(shù)學規(guī)則進行的這種變換稱為編碼.完成編碼功能的器件稱為編碼器.接收短有一個譯碼器完成相反的功能.5.1 編碼器4編碼編碼：信息的組織方式：信息的組織方式編碼的實質(zhì)編碼的實質(zhì)：對信源的原始符號按一定：對信源的原始符號按一定的數(shù)學規(guī)則進行的數(shù)學規(guī)則進行變換變換。編碼的目的編碼的目的：提高信息傳輸?shù)挠行裕ㄐ旁淳幋a）；提高信息傳輸?shù)挠行裕ㄐ旁淳幋a）；提高信息傳輸?shù)目煽啃?。（信源或信道提高信息傳輸?shù)目煽啃浴＃ㄐ旁椿蛐诺谰幋a）編碼） 5幾個術(shù)語：幾個術(shù)語：信源符號信源符號：信源輸入：信源輸入S=s1,s2,sq碼符號碼符號 (碼元碼元)：X=x1,

3、x2,xr碼字碼字Wi： 由由xj (j=1,2,r)組成的長度為組成的長度為 li 的序列，的序列，Wi與與si一一對應(yīng)。一一對應(yīng)。碼字長度碼字長度 (碼長碼長)： Wi的長度的長度li碼碼 (碼書碼書)：碼字：碼字Wi的集合的集合C=W1,W2,Wq 編碼器編碼器：將信源符號：將信源符號si變換成變換成Wi的設(shè)備的設(shè)備6信源編碼信源編碼信源編碼信源編碼：把信源符號：把信源符號si映射為碼字映射為碼字Wi的的過程。過程。 無失真編碼無失真編碼：映射是一一對應(yīng)、可逆的。：映射是一一對應(yīng)、可逆的。無失真信源編碼無失真信源編碼：盡可能精確的再現(xiàn)信：盡可能精確的再現(xiàn)信源的輸出源的輸出 信源編碼基本思

4、想信源編碼基本思想：盡可能縮短出現(xiàn)概：盡可能縮短出現(xiàn)概率大的信源符號的碼率大的信源符號的碼 7通信的根本問題是將信源的輸出，經(jīng)信道傳輸在接收端精確的或近似地重現(xiàn)出來，因此要首先解決兩個問題： 第三章中已經(jīng)回答了第一個問題,這一章要討 論的是第二個問題.信源編碼器如下圖所示:89101112定長碼和變長碼13奇異碼和非奇異碼14N次擴展碼151617說明:本章我們討論的都是同價碼同價碼,即每個碼元符號所占的傳輸時間是相同的.顯然,對同價碼而言,定長碼中每個碼字的傳輸時間是相同的,而變長碼中每個碼字的傳輸時間不一定相等.185.2 分組碼定義：19奇異性2021唯一可譯性22即時性2324一個碼，

5、若其中所有碼字均處于終端節(jié)點，即端點上，則該碼為非續(xù)長碼。2526不超過終端節(jié)點也叫端點。272829該樹的該樹的5 5個個終端節(jié)點終端節(jié)點W1,W2,W3W1,W2,W3,W4,W5,W4,W5分分別表示別表示5 5個個二進制碼二進制碼字字0 0，100100，111111，10101010，10111011按樹圖法構(gòu)成的碼一定滿足即時碼的充要條件，因為從根到葉所走的按樹圖法構(gòu)成的碼一定滿足即時碼的充要條件，因為從根到葉所走的路徑各不相同，而且中間節(jié)點不安排為碼字，所以一定滿足對前綴的路徑各不相同，而且中間節(jié)點不安排為碼字，所以一定滿足對前綴的限制。限制。30各節(jié)點（包括樹根）長出的樹枝樹等

6、于r31325.35.3定長碼定長碼（51）33若令N1，則有qlrlog即lrq （52）（53）與51式一致。式53表示平均每個原始信源符號所需要的碼符號個數(shù)，對于定長碼，平均每個原始信源符號至少需要用 個碼符號變換。qrlog343536定理5.3.137其中前一部分被視為正定理，后一部分被視為逆定理。其中前一部分被視為正定理，后一部分被視為逆定理。383940編碼效率4142435.45.4變長碼變長碼變長碼是在碼符號序列長度N不大時就能編出效率很高而且無失真的信源碼。要實現(xiàn)無失真的信源編碼，變長碼必須是唯一可譯碼唯一可譯碼。變長碼要滿足唯一可譯碼的條件，它必須是非奇異碼非奇異碼，而且

7、任意有限長N次擴展碼也是非奇異的。為能即時進行譯碼，變長碼還必須是即時碼即時碼。445.4.1 碼的分類和主要編碼方法45464748495.4.2 Kraft不等式50注意：僅僅是存在！5.4.2 克拉夫特不等式 與麥克米倫不等式 克拉夫特（kraft）不等式515253定理定理5.4.3 若存在一個碼長為若存在一個碼長為l1，l2，lq的惟一可譯碼，則一定存在具有相同碼的惟一可譯碼，則一定存在具有相同碼長的即時碼。長的即時碼。若存在一個碼長為若存在一個碼長為l1，l2，lq的惟一可譯碼的惟一可譯碼 滿足滿足Kraft不等式（定理不等式（定理5.4.2） 存在具有相同碼長的即時碼（定理存在具

8、有相同碼長的即時碼（定理5. 4.1）任何一個惟一可譯碼均可用一個即時碼來代替，任何一個惟一可譯碼均可用一個即時碼來代替，而不改變?nèi)我淮a字的長度。而不改變?nèi)我淮a字的長度。即時碼可用樹圖法來構(gòu)造。因此要構(gòu)造惟一可即時碼可用樹圖法來構(gòu)造。因此要構(gòu)造惟一可譯碼，只需討論構(gòu)造即時碼。譯碼，只需討論構(gòu)造即時碼。545.4.3 唯一可譯碼的判別準則若碼長若碼長l1, l2, , lq l1, l2, , lq 不滿足不滿足KraftKraft不等式不等式 不是惟一可譯碼；反之，不是惟一可譯碼；反之， l1, l2, , lq l1, l2, , lq 滿滿足足KraftKraft不等式的碼，不一定是惟一可

9、譯碼。不等式的碼，不一定是惟一可譯碼。結(jié)論：不能用克拉夫特不等式，只能根據(jù)定義結(jié)論：不能用克拉夫特不等式，只能根據(jù)定義判斷碼判斷碼C C是否是惟一可譯碼。是否是惟一可譯碼。判別依據(jù)：非惟一可譯變長碼判別依據(jù)：非惟一可譯變長碼 有限長的碼有限長的碼符號序列能譯成兩種不同的碼字序列。符號序列能譯成兩種不同的碼字序列。55例：如下圖中情況發(fā)生，其中例：如下圖中情況發(fā)生，其中Ai，Bi都是都是碼字碼字(Ai,Bi C)。 B1一定是一定是A1的前綴，而的前綴，而A1的尾隨后綴一的尾隨后綴一定是另一碼字定是另一碼字B2的前綴，的前綴，B2的尾隨后綴的尾隨后綴又是其他碼字的前綴。最后，碼符號序又是其他碼字

10、的前綴。最后，碼符號序列的尾部一定是一個碼字。列的尾部一定是一個碼字。56判別準則：判別準則：5758唯一可譯碼的判別方法唯一可譯碼的判斷方法：方法一 ： （可確切判斷）計算出分組碼中所有可能的尾隨后綴集合F，觀察F中有沒有包含任一碼字，若無則為唯一可譯碼，否則一定不是唯一可譯碼。方法二： 步驟如下 1。觀察是否是非奇異碼。若是奇異碼則一定不是唯一可譯碼。2。計算是否滿足Kraft不等式。若不滿足則一定不是唯一可譯碼。3。畫出碼樹，觀察是否滿足即時碼的樹圖的構(gòu)造，若滿足則是唯一可譯碼。595.4.45.4.4變長編碼定理變長編碼定理對于已知信源對于已知信源S S可用碼符號可用碼符號X X進行變

11、長編碼，進行變長編碼，而且對同一信源可有多種即時碼或惟一可譯而且對同一信源可有多種即時碼或惟一可譯碼。碼。選擇哪一種呢？從高速度傳輸信息的角度，選擇哪一種呢？從高速度傳輸信息的角度，希望用短的碼符號組成碼字，即用碼長作為希望用短的碼符號組成碼字，即用碼長作為選擇準則選擇準則-引進碼的平均長度。引進碼的平均長度。60平均碼長平均碼長6162對于某一信源和某一碼符號集來說，若有一個對于某一信源和某一碼符號集來說，若有一個惟一可譯碼，其平均長度小于所有其他惟一可惟一可譯碼，其平均長度小于所有其他惟一可譯碼的平均長度，則該碼稱為緊致碼，或稱最譯碼的平均長度，則該碼稱為緊致碼，或稱最佳碼佳碼 無失真信源

12、編碼的基本問題無失真信源編碼的基本問題找出緊致碼。找出緊致碼。63646566定理定理4.84.8（香農(nóng)信息論的主要定理之一）的結(jié)論：（香農(nóng)信息論的主要定理之一）的結(jié)論：要做到無失真的信源編碼，編碼每個信源符號平均所要做到無失真的信源編碼，編碼每個信源符號平均所需最少的需最少的r r元碼元數(shù)為信源的熵元碼元數(shù)為信源的熵Hr(S) Hr(S) 。即。即Hr(S) Hr(S) 是無是無失真信源壓縮的極限值。失真信源壓縮的極限值。若編碼的平均碼長小于信源的熵值若編碼的平均碼長小于信源的熵值Hr(S) Hr(S) ，則惟一可，則惟一可譯碼不存在，在譯碼或反變換時必然要帶來失真或差譯碼不存在，在譯碼或反

13、變換時必然要帶來失真或差錯。錯。通過對擴展信源進行變長編碼，當通過對擴展信源進行變長編碼，當N N 時，平均碼長時，平均碼長 Hr(S) Hr(S) 。67香農(nóng)第一定理的物理意義香農(nóng)第一定理的物理意義無失真信源編碼的實質(zhì)無失真信源編碼的實質(zhì)：對離散信源進行變換：對離散信源進行變換 變換后信源符號變換后信源符號(信道的輸入信源信道的輸入信源)盡可能為等概盡可能為等概率分布率分布 新信源符號平均所含的信息量達到最大新信源符號平均所含的信息量達到最大 使信道的信息傳輸率使信道的信息傳輸率R達到信道容量達到信道容量C，實，實現(xiàn)信源與信道理想的統(tǒng)計匹配?，F(xiàn)信源與信道理想的統(tǒng)計匹配。無失真信源編碼定理通常又稱為無失真信源編碼定理通常又稱為無噪信道編碼定無噪信道編碼定理理。表述為：若信道的信息傳輸率。表述為：若信道的信息傳輸率R不大于信道不大于信道容量容量C，總能對信源的輸出進行適當?shù)木幋a，使，總能對信源的輸出進行適當?shù)木幋a，使得在無噪無損信道上能無差錯地以最大信息傳輸?shù)迷跓o噪無損信道上能無差錯地以最大信息傳輸率率C傳輸信息，但要使