第4章 無失真信源編碼A

1、第第4章章 無失真信源編碼無失真信源編碼 通信的實(shí)質(zhì)是信息的傳輸。而高速度、高質(zhì)量地傳送信息是信息傳輸?shù)幕締栴}。將信源信息通過信道傳送給信宿，怎樣才能做到盡可能不失真而又快速呢？這就需要解決兩個(gè)問題： 第一，在不失真或允許一定失真的條件下，如何用盡可能少的符號(hào)來傳送信源信息； 第二，在信道受干擾的情況下，如何增加信號(hào)的抗干擾能力，同時(shí)又使得信息傳輸率最大。 為了解決這兩個(gè)問題，就要引入信源編碼和信道編碼。一般來說，提高抗干擾能力（降低失真或錯(cuò)誤概率）往往是以降低信息傳輸率為代價(jià)的；反之，要提高信息傳輸率常常又會(huì)使抗干擾能力減弱。二者是有矛盾的。然而在信息論的編碼定理中，已從理論上證明，至少存

2、在某種最佳的編碼或信息處理方法，能夠解決上述矛盾，做到既可靠又有效地傳輸信息。這些結(jié)論對(duì)各種通信系統(tǒng)的設(shè)計(jì)和估價(jià)具有重大的理論指導(dǎo)意義。4.1 編碼的定義編碼的定義編碼實(shí)質(zhì)上是對(duì)信源的原始符號(hào)按一定的數(shù)學(xué)規(guī)則進(jìn)行的一種變換。討論無失真信源編碼，可以不考慮干擾問題，所以它的數(shù)學(xué)描述比較簡單。圖4.1是一個(gè)信源編碼器，它的輸入是信源符 ，同時(shí)存在另一符號(hào) ，一般來說，元素 是適合信道傳輸?shù)模Q為碼符號(hào)（或者碼元）。,21qsssS,21rxxxXjx 編碼器的功能就是將信源符號(hào)集中的符號(hào) （或者長為N的信源符號(hào)序列）變換成由 組成的長度為 的一一對(duì)應(yīng)的序列。is),2, 1(rjxjil 編 碼

3、器,:21qsssS,:21rxxxX輸出圖4.1 無失真信源編碼器輸出的碼符號(hào)序列稱為碼字，長度 稱為碼字長度或簡稱碼長?？梢?，編碼就是從信源符號(hào)到碼符號(hào)的一種映射。若要實(shí)現(xiàn)無失真編碼，則這種映射必須是一一對(duì)應(yīng)的，并且是可逆的。碼符號(hào)的分類碼符號(hào)的分類： 下圖是一個(gè)碼分類圖il即時(shí)碼（非延長碼）非即時(shí)碼唯一可譯碼非唯一可譯碼非奇異碼奇異碼分組碼非分組碼碼下面，我們給出這些碼的定義。1. 二元碼 若碼符號(hào)集為 ，所有碼字都是一些二元序列，則稱為二元碼。二元碼是數(shù)字通信和計(jì)算機(jī)系統(tǒng)中最常用的一種碼。2. 等長碼： 若一組碼中所有碼字的碼長都相同，即 ，則稱為等長碼。3. 變長碼： 若一組碼組中所

4、有碼字的碼長各不相同，則稱為變長碼。1 , 0X),2, 1(qilli4. 非奇異碼： 若一組碼中所有碼字都不相同，則稱為非奇異碼。5. 奇異碼： 若一組碼中有相同的碼字，則稱為奇異碼。6. 唯一可譯碼： 若碼的任意一串有限長的碼符號(hào)序列只能唯一地被譯成所對(duì)應(yīng)的信源符號(hào)序列，則此碼稱為唯一可譯碼，否則就稱為非唯一可譯碼。7. 非即時(shí)碼和即時(shí)碼： 如果接收端收到一個(gè)完整的碼字后，不能立即譯碼，還要等下一個(gè)碼字開始接收后才能判斷是否可以譯碼，這樣的碼叫做非即時(shí)碼。 如果收到一個(gè)完整的碼字以后，就可以立即譯碼，則叫做即時(shí)碼。即時(shí)碼要求任何一個(gè)碼字都不是其他碼字的前綴部分，也叫做異前綴碼。碼樹碼樹：

5、即時(shí)碼的一種簡單構(gòu)造方法是樹圖法。對(duì)給定碼字的全體集合來說，可以用碼樹來描述它。所謂樹，就是既有根、枝，又有節(jié)點(diǎn)。 如圖4.2所示，圖中，最上端A為根節(jié)點(diǎn)，A、B、 C、D、E皆為節(jié)點(diǎn)，E為終端節(jié)點(diǎn)。,21qWWWCABCD000E11111010010001圖4.2 A、B、C、D為中間節(jié)點(diǎn)，中間節(jié)點(diǎn)不安排碼字，而只在終端節(jié)點(diǎn)安排碼字，每個(gè)終端節(jié)點(diǎn)所對(duì)應(yīng)的碼字就是從根節(jié)點(diǎn)出發(fā)到終端節(jié)點(diǎn)走過的路徑上所對(duì)應(yīng)的符號(hào)組成，如圖4.2中的終端節(jié)點(diǎn)E，走過的路徑為ABCDE，所對(duì)應(yīng)的碼符號(hào)分別為0、0、0、1，則E對(duì)應(yīng)的碼字為0001。可以看出，按樹圖法構(gòu)成的碼一定滿足即時(shí)碼的定義（一一對(duì)應(yīng)，非前綴碼）

6、。從碼樹上可以得知，當(dāng)?shù)?階的節(jié)點(diǎn)作為終端節(jié)點(diǎn)，且分配碼字，則碼字的碼長為 。任一即時(shí)碼都可以用樹圖法來表示。當(dāng)碼字長度給定后，用樹圖法安排的即時(shí)碼不是唯一的。如圖4.2中，如果把左樹枝安排為1，右樹枝安排為0，則得到不同的結(jié)果。對(duì)一個(gè)給定的碼，畫出其對(duì)應(yīng)的樹，如果有中間節(jié)點(diǎn)安排了碼字，則該碼一定不是即時(shí)碼。每個(gè)節(jié)點(diǎn)上都有 個(gè)分支的樹稱為滿樹，否則為非滿樹。iir即時(shí)碼的碼樹圖還可以用來譯碼。當(dāng)收到一串碼符號(hào)序列后，首先從根節(jié)點(diǎn)出發(fā)，根據(jù)接收到的第一個(gè)碼符號(hào)來選擇應(yīng)走的第一條路徑，再根據(jù)收到的第二個(gè)符號(hào)來選擇應(yīng)走的第二條路徑，直到走到終端節(jié)點(diǎn)為止，就可以根據(jù)終端節(jié)點(diǎn)，立即判斷出所接收的碼字。然

7、后從樹根繼續(xù)下一個(gè)碼字的判斷。這樣，就可以將接收到的一串碼符號(hào)序列譯成對(duì)應(yīng)的信源符號(hào)序列。克拉夫特（Kraft）不等式 定理4.1 對(duì)于碼符號(hào)為 的任意唯一可譯碼，其碼字為 ，所對(duì)應(yīng)的碼長為 ，則必定滿足克拉夫特不等式 反之，若碼長滿足上面的不等式，則一定存在具有這樣碼長的即時(shí)碼。,21rxxxXqWWW,21qlll,2111qilir 注意：克拉夫特不等式只是說明唯一可譯碼是否存在，并不能作為唯一可譯碼的判據(jù)（可以排除，不能肯定）。如0，10，010，111滿足克拉夫特不等式，但卻不是唯一可譯碼。例題：設(shè)二進(jìn)制碼樹中 ，對(duì)應(yīng)的 ，由上述定理，可得因此不存在滿足這種碼長的唯一可譯碼?？梢杂脴?/p>

8、碼進(jìn)行檢查。,4321xxxxX 3, 2, 2, 14321llll18922222322141ili唯一可譯碼的判斷法（變長）： 將碼C中所有可能的尾隨后綴組成一個(gè)集合F，當(dāng)且僅當(dāng)集合F中沒有包含任一碼字，則可判斷此碼C為唯一可譯碼。集合F的構(gòu)成方法： 首先，觀察碼C中最短的碼字是否是其它碼字的前綴，若是，將其所有可能的尾隨后綴排列出。而這些尾隨后綴又有可能是某些碼字的前綴，再將這些尾隨后綴產(chǎn)生的新的尾隨后綴列出，然后再觀察這些新的尾隨后綴是否是某些碼字的前綴，再將產(chǎn)生的尾隨后綴列出，依此下去，直到?jīng)]有一個(gè)尾隨后綴是碼字的前綴為止。這樣，首先獲得了由最短的碼字能引起的所有尾隨后綴，接著，按

9、照上述步驟將次短碼字、等等所有碼字可能產(chǎn)生的尾隨后綴全部列出。由此得到由碼C的所有可能的尾隨后綴的集合F。例題：設(shè)碼C=0,10,1100,1110,1011,1101，根據(jù)上述測(cè)試方法，判斷是否是唯一可譯碼。解：碼C=0,10,1100,1110,1011,1101 1. 先看最短的碼字：“0”，它不是其他碼字 前綴，所以沒有尾隨后綴。 2. 再觀察碼字“10”，它是碼字“1011”的前綴， 因此有尾隨后綴：1011001001 所以，集合F=11，00，10，01，其中“10”為碼字，故碼C不是唯一可譯碼。4.2 定長編碼定理定長編碼定理前面已經(jīng)說過，所謂信源編碼，就是將信源符號(hào)序列變換成

10、另一個(gè)序列（碼字）。設(shè)信源輸出符號(hào)序列長度為L，碼字的長度為 ，編碼的目的，就是要是信源的信息率最小，也就是說，要用最少的符號(hào)來代表信源。在定長編碼中，對(duì)每一個(gè)信源序列， 都是定值，設(shè)等于K，我們的目的是尋找最小K值。要實(shí)現(xiàn)無失真的信源編碼，要求信源符號(hào) 與碼字是一一對(duì)應(yīng)的，并求由碼字組成的符號(hào)序列的逆變換也是唯一的（唯一可譯碼）。LKLK), 2 , 1(qiiX 則當(dāng)L足夠大時(shí)，必可使譯碼差錯(cuò)小于 ；反之，當(dāng) 時(shí)，譯碼差錯(cuò)一定是有限值，當(dāng)L足夠大時(shí)，譯碼幾乎必定出錯(cuò)。定長編碼定理定長編碼定理： 由L個(gè)符號(hào)組成的、每個(gè)符號(hào)熵為 的無記憶平穩(wěn)信源符號(hào)序列 ，可用 個(gè)符號(hào) （每個(gè)符號(hào)有m中可能值

11、）進(jìn)行定長變碼。對(duì)任意 ，只要)(XHLLXXX21LKLKYYY210, 0)(logXHmLKLL2)(logXHmLKLL所以等長編碼定理告訴我們，只要碼字傳輸?shù)男畔⒘看笥谛旁葱蛄袛y帶的信息量，總可以實(shí)現(xiàn)幾乎無失真的編碼。條件時(shí)所取得符號(hào)數(shù)L足夠大。設(shè)差錯(cuò)概率為 ，信源序列的自方差為 則有：P22)()()(XxIEXi22)(LXP 式中，左邊是輸出碼字每符號(hào)所能載荷的最大信息量mLKLlog 當(dāng) 和 均為定值時(shí)，只要L足夠大， 可小于任一整數(shù) ，即 此時(shí)要求：)(2X2P22)(LX22)(XL 只要 足夠小，就可以幾乎無差錯(cuò)地譯碼，當(dāng)然代價(jià)是L變得更大。令為碼字最大平均符號(hào)信息量。

12、定義編碼效率為：mLKKLlogKXHL)( 最佳編碼效率為 無失真信源編碼定理從理論上闡明了編碼效率接近于1的理想編碼器的存在性，它使輸出符號(hào)的信息率與信源熵之比接近于1，但要在實(shí)際中實(shí)現(xiàn)，則要求信源符號(hào)序列的L非常大進(jìn)行統(tǒng)一編碼才行，這往往是不現(xiàn)實(shí)的。)()(XHXHLL例題：設(shè)離散無記憶信源概率空間為信源熵為自信息方差為04. 005. 006. 007. 01 . 01 . 018. 04 . 087654321xxxxxxxxPX符號(hào)/55. 2log)(812bitppXHiii82. 7)()(log)(log)(2)(log)(log)(2)(log)(log)()()(812

13、228181812222812222812222iiiiiiiiiiiiiiiiiiiXHpppXHppXHppXHpXHppXHppXHxIEX對(duì)信源符號(hào)采用定長二元編碼，要求編碼效率 ，無記憶信源有 ，因此可以得到如果要求譯碼錯(cuò)誤概率 ，則%90)()(XHXHL%90)()(XHXH28. 0610872210108 . 9(）XL由此可見，在對(duì)編碼效率和譯碼錯(cuò)誤概率的要求不是十分苛刻的情況下，就需要 個(gè)信源符號(hào)一起進(jìn)行編碼，這對(duì)存儲(chǔ)和處理技術(shù)的要求太高，目前還無法實(shí)現(xiàn)。如果用3比特來對(duì)上述信源的8個(gè)符號(hào)進(jìn)行定長二元編碼，L=1，此時(shí)可實(shí)現(xiàn)譯碼無差錯(cuò)，但編碼效率只有2.55/3=85%。

14、因此，一般說來，當(dāng)L有限時(shí)，高傳輸效率的定長碼往往要引入一定的失真和譯碼錯(cuò)誤。解決的辦法是可以采用變長編碼。810L4.3 變長編碼定理變長編碼定理在變長編碼中，碼長是變化的。對(duì)同一信源，其即時(shí)碼或唯一可譯碼可以有許多種。究竟哪一種好呢？從高速傳輸信息的觀點(diǎn)來考慮，當(dāng)然 希望選擇由短的碼符號(hào)組成的碼字，就是用碼長來作為選擇準(zhǔn)則，為此我們引入碼的平均長度。 設(shè)信源為)(,),(,),(,2211qqxpxxpxxpxPX 編碼后的碼字為 其碼長分別為 因?yàn)閷?duì)唯一可譯碼來說，信源符號(hào)與碼字是一一對(duì)應(yīng)的，所以有 則這個(gè)碼的平均長度為qWWW,21qlll,21), 2 , 1)()(qixpWpii

15、qiiilxpK1)( 它是每個(gè)信源符號(hào)平均需用的碼元數(shù)。 對(duì)某一信源來說，若有一個(gè)唯一可譯碼，其平均長度小于所有其它的唯一可譯碼的平均長度，則該碼稱為緊致碼，或稱最佳碼。無失真變長信源編碼的基本問題就是要找最佳碼。單個(gè)符號(hào)變長編碼定理單個(gè)符號(hào)變長編碼定理： 若一離散無記憶信源的符號(hào)熵為H(X)，每個(gè)信源符號(hào)用m進(jìn)制碼元進(jìn)行變長編碼，一定存在一種無失真編碼方法，其碼字平均長度 滿足下面的不等式K1log)(log)(mXHKmXH離散平穩(wěn)無記憶序列變長編碼定理（香農(nóng)第一離散平穩(wěn)無記憶序列變長編碼定理（香農(nóng)第一定理）定理）： 對(duì)于平均符號(hào)熵為 的離散平穩(wěn)無記憶信源，必存在一種無失真信源編碼方法，

16、使平均信息率 滿足下面的不等式 其中， 為任意小正數(shù)。)(XHLR)()(XHRXHLL 上面的兩個(gè)定理實(shí)際上是一樣的，可以由第一個(gè)推導(dǎo)出第二個(gè)。設(shè)用m進(jìn)制碼元做變長編碼，序列長度為L個(gè)信源符號(hào)，則該序列所對(duì)應(yīng)的碼字的平均長度 滿足下面的不等式 而平均輸出信息率為 故有LK1log)(log)(mXLHKmXLHLLLmLKRLlogLmXHRXHLLlog)()(當(dāng)L足夠大時(shí)，可使因此Lmlog)()(XHRXHLL 香農(nóng)第一編碼定理給出了碼字的平均長度的下界和上界。但并不是說大于這上界不能構(gòu)成唯一可譯碼，而是因?yàn)槲覀兛偸窍Ｍ?盡可能短。定理說明當(dāng)平均碼長小于上界時(shí)，唯一可譯碼也存在。也就是

17、說，定理給出的是最佳碼的最短平均碼長，并指出這個(gè)最短的平均碼長與信源熵是有關(guān)的。 編碼效率為 剩余度（冗余度）為LKLmXHXHKXHLLLlog)()()(KXHL)(11其信源熵為若用二元定長編碼（0，1）來構(gòu)造一個(gè)即時(shí)碼： ，這時(shí)平均碼長為編碼效率為符號(hào)/811. 034log434log41)(22bitXH1, 021xx信源符號(hào)二元碼符號(hào)/1K811. 0)(KXH例題：設(shè)離散無記憶信源的概率空間為414321xxPX輸出的信息率為再對(duì)長度為2的信源序列進(jìn)行變長編碼，其即時(shí)碼如下表所示：符號(hào)/811.0bitR 序列序列概率 即時(shí)碼 序列序列概率 即時(shí)碼 9/16 0 3/16 1

18、10 3/16 10 1/16 11111xx21xx12xx22xx這個(gè)碼的平均長度為每一單個(gè)符號(hào)的平均碼長為其編碼效率為信源符號(hào)二元碼符號(hào)/162731613163216311692K信源符號(hào)二元碼符號(hào)/322722KK961. 027811. 0322二元碼符號(hào)/961. 02bitR 編碼復(fù)雜了，但信息傳輸率和效率有了提高。 同樣可以求得信源序列長度增加到3和4時(shí)，進(jìn)行變長編碼所得的編碼效率和信息傳輸率分別為 如果對(duì)這一信源采用定長二元碼編碼，要求編碼效率達(dá)到96%，允許譯碼錯(cuò)誤概率 ，985. 03961. 04二元碼符號(hào)/985. 03bitR 二元碼符號(hào)/991. 04bitR 510則可以算出自信息方差為 為需要的信源序列長度為4715. 0)()(log)(22122XHppXiii96. 004. 0811. 0811. 096. 0811. 0)()(XHXH7221013. 4)(XL 可以看出，使用定長編碼時(shí)，為了使編碼效率較高（96%），需要對(duì)非常