第4章無失真信源編碼B

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

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

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

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

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

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

7、4. 2)(71iiiKxpK 消息符號符號概率第一次分組第二次分組第三次分組第四次分組二元碼字碼長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信息傳輸率為例題：離散無記憶信源及其符號概率分布如下表所示，求其費諾碼。 求費諾碼的過程也表示在表中。碼的平均長度為 ，信源的熵為 因此是最佳碼。原因是概率分布滿足一定的條件。碼元/953. 074. 261. 2)(bitKXHR符號碼元/75. 2K符號/75. 2

8、)(bitXH 信源符號符號概率第一次分組第二次分組第三次分組第四次分組碼字碼長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)造最佳碼的方法。它是一種最佳的逐個符號的編碼方法。其編碼步驟如下：(1) 將q個信源符號按概率分布的大小，以遞減次序排列起來，設(shè)(2) 用“0”和“1”碼符號分別代表概率最小的兩個信源符號，并將這兩個概率最小的符

9、號合并成一個符號，合并的符號概率為兩個符號概率之和，從而得到只包含q-1個符號的新信源，稱為縮減信源縮減信源。)()()(21qxpxpxp(3)把縮減信源的符號仍舊按概率大小以遞減次序排列，再將其概率最小的兩個信源符號分別用“0”和“1”表示，并將其合并成一個符號，概率為兩符號概率之和，這樣又形成了q-2個符號的縮減信源。(4)依此繼續(xù)下去，直至信源只剩下兩個符號為止。將這最后兩個信源符號分別用“0”和“1”表示。(5)然后從最后一級縮減信源開始，向前返回，就得出各信源符號所對應(yīng)的碼符號序列，即對應(yīng)的碼字。 信源符號符號概率 編 碼 過 程碼字碼長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例題：下表是一個哈夫曼編碼的整個過程。其平均碼長為信息傳輸率為從表中編碼過程可以看出，哈夫曼編碼方法得到的碼一定是即時碼。因為這種編碼方法不會使任一碼字的前綴為碼字。這一點在用碼樹形式來表示的時候，看得更清楚。符號碼元/72. 2)(71iiiKxpK碼元/9596. 072. 261. 2)(bitKXHR0.100

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

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

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

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

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

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