第4章無失真信源編碼B

1、上節(jié)課回顧最佳編碼-香農(nóng)碼、費(fèi)諾碼、哈夫曼編碼上節(jié)課回顧：編碼的一些術(shù)語和概念編碼的一些術(shù)語和概念：定長碼、變長碼；奇異碼、非奇異碼；唯一可譯碼；即時(shí)碼、非即時(shí)碼；碼樹唯一可譯碼的判斷唯一可譯碼的判斷：尾隨后綴判斷法；定長編碼定理定長編碼定理：二元碼的平均長度大于等于信源的熵；變長編碼定理變長編碼定理：香農(nóng)第一定理，二元碼的平均長度大于等于碼的平均符號(hào)熵；4.4 最佳編碼最佳編碼香農(nóng)第一定理給除了信源熵與編碼后的平均碼長之間的關(guān)系，同時(shí)也指出可已通過編碼使平均碼長達(dá)到極限值，因此，香農(nóng)第一定理是一個(gè)極限定理。但定理中并沒有告訴我們?nèi)绾蝸順?gòu)造這種碼。下面我們介紹三種編碼方法：香農(nóng)碼、費(fèi)諾碼以及哈

2、夫曼編碼。這三種碼的平均碼長都比較短。1. 香農(nóng)編碼方法香農(nóng)編碼方法因?yàn)槠骄a長是各個(gè)碼的概率平均，可以想象，應(yīng)該使出現(xiàn)概率大的信源符號(hào)編碼后碼長盡量短一些。三種編碼方法的出發(fā)點(diǎn)都是如此。香農(nóng)編碼嚴(yán)格意義上來說不是最佳碼。香農(nóng)編碼是采用信源符號(hào)的累計(jì)概率分布函數(shù)來分配碼字。則香農(nóng)編碼方法如下：(1)將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列：(2)確定滿足下列不等式的整數(shù)碼長 ：(3)為了編成唯一可以碼，計(jì)算第 個(gè)消息的累加概率)()()(21nxpxpxpiK1)(log)(log22iiixpKxpi11)(ikkixpP設(shè)信源符號(hào)集 ，并設(shè)所有的P(x)0，,21qxxxX(4)將累加概率

3、 變換成二進(jìn)制數(shù)。(5)取 二進(jìn)制數(shù)的小數(shù)點(diǎn)后 位即為該消息符號(hào)的二進(jìn)制碼字。 可以證明，這樣得到的編碼一定是唯一可譯碼，且碼長比較短，接近于最佳編碼。 也可以不對(duì)信源消息符號(hào)按概率大小排列，這時(shí)香農(nóng)編碼方案如下：iPiPiK(1)求出修正累計(jì)概率分布函數(shù)為(2)確定滿足下式的碼長(3)將修正累加概率 變換成二進(jìn)制數(shù)。(4)取 二進(jìn)制小數(shù)點(diǎn)后 位即為該消息符號(hào)的二進(jìn)制編碼。）iikkixpxpP(21)(11Xxxik,1)(1logiixpKiPiPiK例題：設(shè)信源共有7個(gè)符號(hào)組成，其概率如表所示，求其香農(nóng)碼。信源消息符號(hào)符號(hào)概率 0.20 0.19 0.18 0.17 0.15 0.10

4、0.011x2x3x4x5x6x7xix)(ixpix1x2x3x4x5x6x7xiPiK符號(hào)概率累加概率碼字長度 碼 字0.2002.3430000.190.22.4130010.180.392.4830110.170.572.5631000.150.742.7431010.100.893.34411100.010.996.6671111110)(ixp)(log2ixp以 為例，累加概率 ，變成二進(jìn)制數(shù)，為0.1001，轉(zhuǎn)換的方法是：用 乘以2，如果整數(shù)部分有進(jìn)位，則小數(shù)點(diǎn)后第一位為1，否則為0，將其小數(shù)部分再做同樣的處理，得到小數(shù)點(diǎn)后的第二位，依此類推，直到得到了滿足要求的位數(shù)，或者沒有

5、小數(shù)部分了為止。 4i356.356.2117.0log17.0log44242KKK，因此即57.0iPiP例如現(xiàn)在 ，乘以2為1.14，整數(shù)部分有進(jìn)位，所以小數(shù)點(diǎn)后第一位為1，將小數(shù)部分即0.14再乘以2，得0.28，沒有整數(shù)進(jìn)位，所以小數(shù)點(diǎn)后第二位為0，依此類推，可得到其對(duì)應(yīng)的二進(jìn)制數(shù)為0.1001。可以看出，編碼所得的碼字，沒有相同的，所以是非奇異碼，也沒有一個(gè)碼字是其它碼字的前綴，所以是即時(shí)碼。唯一可譯碼。平均碼長為：57.0iP平均碼長為：平均信息傳輸率為 香農(nóng)編碼的效率不高，實(shí)用意義不大，但對(duì)其它編碼方法有很好的理論指導(dǎo)意義。 符號(hào)碼元 /14.3)(71iiiKxpK碼元/83

6、1. 014. 361. 2)(bitKXHR2. 費(fèi)諾編碼方法費(fèi)諾編碼方法費(fèi)諾編碼也不是最佳編碼方法，但有時(shí)可以得到最佳編碼。費(fèi)諾編碼方法如下： 首先，將信源符號(hào)以概率遞減的次序排列起來，將排列好的信源符號(hào)分成兩組，使每一組的概率之和相接近，并各賦予一個(gè)二元碼符號(hào)“0”或者“1”；然后，將每一組的信源符號(hào)再分成兩組，使每一小組的符號(hào)概率之和也接近相等，并又分別賦予一個(gè)二元碼符號(hào)。 依此下去，直到每一個(gè)小組只剩下一個(gè)信源符號(hào)為止。這樣，信源符號(hào)所對(duì)應(yīng)的碼符號(hào)序列則為編得的碼字。例題：信源符號(hào)及其概率仍如香農(nóng)碼中的例題所示。編碼過程及編碼結(jié)果如下表所示，可以求得，該費(fèi)諾碼的平均碼長為符號(hào)碼元/7

7、4. 2)(71iiiKxpK 消息符號(hào)符號(hào)概率第一次分組第二次分組第三次分組第四次分組二元碼字碼長0.20 0 0 00 20.19 1 0 010 30.18 1 011 30.17 1 0 10 20.15 1 0 110 30.10 1 0 1110 40.01 1 1111 4ix1x2x3x4x5x6x7x)(ixp信息傳輸率為例題：離散無記憶信源及其符號(hào)概率分布如下表所示，求其費(fèi)諾碼。 求費(fèi)諾碼的過程也表示在表中。碼的平均長度為 ，信源的熵為 因此是最佳碼。原因是概率分布滿足一定的條件。碼元/953. 074. 261. 2)(bitKXHR符號(hào)碼元/75. 2K符號(hào)/75. 2

8、)(bitXH 信源符號(hào)符號(hào)概率第一次分組第二次分組第三次分組第四次分組碼字碼長1/4 0 0 00 21/4 1 01 21/8 1 0 0 100 31/8 1 101 31/16 1 0 0 1100 41/16 1 1101 41/16 1 0 1110 41/16 1 1111 41x2x3x4x5x6x7x8x3. 哈夫曼編碼方法哈夫曼編碼方法 1952年哈夫曼提出了一種構(gòu)造最佳碼的方法。它是一種最佳的逐個(gè)符號(hào)的編碼方法。其編碼步驟如下：(1) 將q個(gè)信源符號(hào)按概率分布的大小，以遞減次序排列起來，設(shè)(2) 用“0”和“1”碼符號(hào)分別代表概率最小的兩個(gè)信源符號(hào)，并將這兩個(gè)概率最小的符

9、號(hào)合并成一個(gè)符號(hào)，合并的符號(hào)概率為兩個(gè)符號(hào)概率之和，從而得到只包含q-1個(gè)符號(hào)的新信源，稱為縮減信源縮減信源。)()()(21qxpxpxp(3)把縮減信源的符號(hào)仍舊按概率大小以遞減次序排列，再將其概率最小的兩個(gè)信源符號(hào)分別用“0”和“1”表示，并將其合并成一個(gè)符號(hào)，概率為兩符號(hào)概率之和，這樣又形成了q-2個(gè)符號(hào)的縮減信源。(4)依此繼續(xù)下去，直至信源只剩下兩個(gè)符號(hào)為止。將這最后兩個(gè)信源符號(hào)分別用“0”和“1”表示。(5)然后從最后一級(jí)縮減信源開始，向前返回，就得出各信源符號(hào)所對(duì)應(yīng)的碼符號(hào)序列，即對(duì)應(yīng)的碼字。 信源符號(hào)符號(hào)概率 編 碼 過 程碼字碼長0.201020.191120.180003

10、0.1700130.1501030.10011040.0101114010.200.190.180.170.150.110.260.200.190.180.1701010.260.350.200.19010.350.260.39010.390.61011x2x3x4x5x6x7x例題：下表是一個(gè)哈夫曼編碼的整個(gè)過程。其平均碼長為信息傳輸率為從表中編碼過程可以看出，哈夫曼編碼方法得到的碼一定是即時(shí)碼。因?yàn)檫@種編碼方法不會(huì)使任一碼字的前綴為碼字。這一點(diǎn)在用碼樹形式來表示的時(shí)候，看得更清楚。符號(hào)碼元/72. 2)(71iiiKxpK碼元/9596. 072. 261. 2)(bitKXHR0.100

11、.010.110.150.260.170.180.350.610.200.190.39 1010101010101下圖是用碼樹形式進(jìn)行哈夫曼編碼的過程，由于代表信源符號(hào)的節(jié)點(diǎn)都是終端節(jié)點(diǎn)，因此其編碼不可能是其它終端節(jié)點(diǎn)對(duì)應(yīng)的編碼的前綴。另外，由于哈夫曼編碼總是把概率大的符號(hào)安排在離根節(jié)點(diǎn)近的終端節(jié)點(diǎn)，所以其碼長比較小，因此得到的編碼整體平均碼長就比較小。哈夫曼編碼得到的碼不是唯一的，因?yàn)槊看螌?duì)縮減信源中兩個(gè)概率最小的符號(hào)編碼的時(shí)候，“0”和“1”的安排是任意的。另外當(dāng)兩個(gè)符號(hào)的概率相同的時(shí)候，排列的次序也是隨意的，所以可能導(dǎo)致不同的編碼結(jié)果，但最后的平均碼長一定是一樣的。在這種情況下，怎么樣來

12、判斷一個(gè)碼的好壞呢？我們引進(jìn)碼字長度 偏離平均長度 的方差 ，即iKK2 方差越小，說明各個(gè)碼的長度都比較接近平均長度，這樣編碼器和解碼器就可以比較簡單，這樣的碼就認(rèn)為是好碼。因此，在哈夫曼編碼的過程中，當(dāng)縮減信源的概率分布重新排列時(shí)，應(yīng)使合并得來的概率和盡可能處于最高的位置，這樣可使合并的元素重復(fù)編碼次數(shù)減少，使短碼得到充分利用。qiiiiKKxpKKE1222)()(例題：如下表是又一個(gè)哈夫曼編碼的過程。信源符號(hào)符號(hào)概率 編 碼 過 程碼字 碼長0.4110.20120.200030.10010 40.10011 40.40.20.20.2010.40.40.2010.60.40101從以

13、上的編碼實(shí)例中可以看出，哈夫曼編碼具有以下三個(gè)特點(diǎn)：(1)哈夫曼編碼方法保證了概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的符號(hào)對(duì)應(yīng)于長碼，且短碼得到充分利用。(2)每次縮減信源的最后兩個(gè)碼字總是最后一位碼元不同，前面各位碼元相同。(3)每次縮減信源的最長兩個(gè)碼字有相同的碼長。這三個(gè)特點(diǎn)保證了所得的哈夫曼編碼一定是最佳碼。變長編碼的特點(diǎn)變長編碼的特點(diǎn)：(1)平均碼長短；(2)對(duì)編解碼設(shè)備要求高。 當(dāng)使用變長編碼時(shí)，為了提高編碼效率，往往需要把一個(gè)很長的序列一起進(jìn)行編碼，這樣雖可以使平均碼長減小，但具體到某一個(gè)特定的信源符號(hào)，則有可能比定長編碼得到的碼字長度還要長。這將使編解碼設(shè)備的復(fù)雜度提高，原因如下：設(shè)信

14、源的輸出速率為S=N/T，若符號(hào)的平均碼長為 ，則當(dāng)信道傳輸速率剛好為時(shí)可以滿足條件。設(shè)N個(gè)碼字的長度分別為 ，即在此期間輸入了存儲(chǔ)器 比特碼元符號(hào)，輸出至信道RT比特碼元符號(hào)，則在存儲(chǔ)器內(nèi)還剩余X比特，KKSR NiKi, 2 , 1,iiKRTKXNii1 是隨機(jī)變量，其均值和方差為 式中，m是信源符號(hào)集中信源符號(hào)的個(gè)數(shù)。 當(dāng)N足夠大時(shí)，X將近似于正態(tài)分布， 其均值和方差為iKmjjjiKpKEK1212222KKpKKEmjjjiTRKSRTKNXE)(令則Y也是正態(tài)分布，均值為0，方差為1。于是可得下列概率式中 是誤差函數(shù)，可以通過查表求得其值。22NxxXEXY)()()(AAYPA

15、YP)( A如果滿足 ，則EX=0，于是 ，下面我們看變長編碼時(shí)對(duì)存儲(chǔ)器容量的要求。為了避免存儲(chǔ)器溢出或取空，設(shè)起始時(shí)存儲(chǔ)器半滿，并設(shè)存儲(chǔ)器容量為 ，則當(dāng) 時(shí)，也就是YA時(shí)，存儲(chǔ)器將溢出；當(dāng) 時(shí)，也就是YA時(shí)，存儲(chǔ)器將取空。因此，存儲(chǔ)器取空和溢出的概率都是 ，如果要求取空和溢出的概率都小于 ，則存儲(chǔ)器的容量應(yīng)該大于 ，即 。KSR xXY/xA2xAXxAX)( A)( AxA2xAC2如果 ，則當(dāng) 時(shí)，平均來說輸出比輸入快，容易取空；而當(dāng) 時(shí)，平均來說輸入比輸出快，容易溢出。因此，在這種情況下， 存儲(chǔ)器的容量應(yīng)該比 時(shí)的容量要大。當(dāng)存儲(chǔ)器容量一定時(shí)，隨著時(shí)間T的增加，碼字的個(gè)數(shù)N也會(huì)相應(yīng)地增

16、加，當(dāng)N大到一定程度，由于 ，則一定會(huì)有 ，這時(shí)取空和溢出的概率都會(huì)大于 ，T越大，發(fā)生錯(cuò)誤（取空或溢出）的概率越大。對(duì)于無限長的信息，用變長編碼，不管存儲(chǔ)器容量有多大，一定會(huì)發(fā)生取空或溢出的錯(cuò)誤，這就是變長編碼的缺點(diǎn)所在。KSR KSR KSR KSR 22NxCAx2)( A所以在實(shí)際的變長編碼傳輸系統(tǒng)中，或者限定信息的長度，或者通過檢測存儲(chǔ)器的狀態(tài)，并通過停止信源輸出（要溢出時(shí)）或插入空閑標(biāo)志（取空時(shí)）來解決這個(gè)問題。(3)有誤碼傳播現(xiàn)象。在理想情況下，變長編碼可以無失真地譯碼。但是，如果這種變長編碼由信道傳輸發(fā)生誤碼時(shí)，因?yàn)橐粋€(gè)碼字前面有某一個(gè)碼元錯(cuò)了，就可能誤認(rèn)為是另一個(gè)碼字而錯(cuò)誤地點(diǎn)斷。結(jié)果后面一系列的碼字也會(huì)譯錯(cuò)，這