信息論第5章 無(wú)失真信源編碼

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

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

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

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

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

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

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

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

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

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

11、長(zhǎng)編碼，進(jìn)行變長(zhǎng)編碼，而且對(duì)同一信源可有多種即時(shí)碼或惟一可譯而且對(duì)同一信源可有多種即時(shí)碼或惟一可譯碼。碼。選擇哪一種呢？從高速度傳輸信息的角度，選擇哪一種呢？從高速度傳輸信息的角度，希望用短的碼符號(hào)組成碼字，即用碼長(zhǎng)作為希望用短的碼符號(hào)組成碼字，即用碼長(zhǎng)作為選擇準(zhǔn)則選擇準(zhǔn)則-引進(jìn)碼的平均長(zhǎng)度。引進(jìn)碼的平均長(zhǎng)度。60平均碼長(zhǎng)平均碼長(zhǎng)6162對(duì)于某一信源和某一碼符號(hào)集來(lái)說(shuō)，若有一個(gè)對(duì)于某一信源和某一碼符號(hào)集來(lái)說(shuō)，若有一個(gè)惟一可譯碼，其平均長(zhǎng)度小于所有其他惟一可惟一可譯碼，其平均長(zhǎng)度小于所有其他惟一可譯碼的平均長(zhǎng)度，則該碼稱為緊致碼，或稱最譯碼的平均長(zhǎng)度，則該碼稱為緊致碼，或稱最佳碼佳碼 無(wú)失真信源

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

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