【文章內(nèi)容簡介】 二二 .香農(nóng)編碼香農(nóng)編碼 : ①① 將信源發(fā)出的將信源發(fā)出的 q個(gè)消息符號(hào)按其概率的逆減次序排列個(gè)消息符號(hào)按其概率的逆減次序排列計(jì)算第計(jì)算第 i個(gè)消息的二進(jìn)制碼字的碼長個(gè)消息的二進(jìn)制碼字的碼長 li,并取整并取整③ 為了編成唯一可譯碼，首先計(jì)算第 i個(gè)消息的累加概率⑤⑤ 根據(jù)碼長根據(jù)碼長 li, 對(duì)對(duì) ④④ 的結(jié)果取小數(shù)點(diǎn)后的結(jié)果取小數(shù)點(diǎn)后 li位數(shù)作為第位數(shù)作為第 i個(gè)消息的碼字個(gè)消息的碼字④④ 將累加概率將累加概率 Pi變成二進(jìn)制數(shù)變成二進(jìn)制數(shù)②② 利用利用例例 57：： 消息序號(hào)消息序號(hào) Si 概率概率 p(Si) –logp(Si) 碼長碼長 Li 累加概率累加概率 pi 二進(jìn)制碼二進(jìn)制碼 S1 2 0 00 S2 2 01 S3 3 101 S4 4 1110 ② 用 0， 1碼符號(hào)分別代表概率最小的兩個(gè)信源符號(hào)，并將這兩個(gè)概率最小的信源符號(hào)合并成一個(gè)，從而得到只包含 q1個(gè)符號(hào)的新信源 S1,稱為縮減信號(hào)源。三三 .二元二元 Huffman編碼編碼①① 將信源發(fā)出的將信源發(fā)出的 q個(gè)信源按其概率依次從大到小排列個(gè)信源按其概率依次從大到小排列③③ 把縮減信源把縮減信源 S1的符號(hào)按概率從大到小排列，再將其最后兩個(gè)的符號(hào)按概率從大到小排列，再將其最后兩個(gè)概率最小的符號(hào)合并成一個(gè)符號(hào)，并分別用概率最小的符號(hào)合并成一個(gè)符號(hào)，并分別用 0和和 1碼元表示，這碼元表示，這樣形成樣形成 q2個(gè)符號(hào)的新信源個(gè)符號(hào)的新信源 S2。④④ 依此類推，直至信源只剩兩個(gè)符號(hào)為止，并分別用依此類推，直至信源只剩兩個(gè)符號(hào)為止，并分別用 “0”和和“1”表示。表示。⑤⑤ 從最后一級(jí)縮減信源開始，向前返回，得出各信源符號(hào)所對(duì)從最后一級(jí)縮減信源開始，向前返回，得出各信源符號(hào)所對(duì)應(yīng)的碼符號(hào)序列，即相應(yīng)碼字。應(yīng)的碼符號(hào)序列，即相應(yīng)碼字。例例 58信源符號(hào) Si 概率 p(Si) 編碼過程 碼字 Wi 碼長 li S1 S2 S3 S1 S2 S3 S4 S5 0 1010 01編碼過程：編碼過程：1 101200030010400114用樹圖檢驗(yàn)是否為即時(shí)碼用樹圖檢驗(yàn)是否為即時(shí)碼0A0 100 111010000010 0011(1)每次對(duì)信號(hào)縮減時(shí)，賦予最后兩個(gè)概率最小的符號(hào)每次對(duì)信號(hào)縮減時(shí)，賦予最后兩個(gè)概率最小的符號(hào) 用用 “0”和和 “1”是可任意的。是可任意的。(2)對(duì)信源進(jìn)行縮減時(shí)兩個(gè)概率最小的符號(hào)合并后的概率與其他對(duì)信源進(jìn)行縮減時(shí)兩個(gè)概率最小的符號(hào)合并后的概率與其他符號(hào)概率相同時(shí)，可任意排序。符號(hào)概率相同時(shí)，可任意排序。經(jīng)哈夫曼編碼方法得到的碼并非是唯一的經(jīng)哈夫曼編碼方法得到的碼并非是唯一的 ,造成非唯一造成非唯一的原因：的原因： 碼字 Wi 碼長 l i S1 00 2 S2 10 2 S3 11 2 S4 010 3 S5 011 301010101例題例題 58：：A00 111000 10 110 1010 011 即時(shí)碼即時(shí)碼由此可見：由此可見：結(jié)論： 當(dāng)進(jìn)行哈夫曼編碼時(shí)，為了得到質(zhì)量好的碼，應(yīng)使合當(dāng)進(jìn)行哈夫曼編碼時(shí)，為了得到質(zhì)量好的碼，應(yīng)使合并的信源符號(hào)位于縮減信源序列盡可能高的位置，這樣可充分并的信源符號(hào)位于縮減信源序列盡可能高的位置，這樣可充分利用短碼。利用短碼。 r元哈夫曼碼可由二元哈夫曼碼的編碼方法推廣得到。只是編碼過程中構(gòu)成縮減信源時(shí)，每次將 r個(gè)概率最小的符號(hào)合并，并分別用 0， 1， … ， r1碼元表示。 為了充分利用短碼，使哈夫曼碼的平均碼長最短，必須是最后一個(gè)縮減信源有 r個(gè)信源符號(hào)。因此，對(duì)于 r元哈夫曼碼，信源 S的符號(hào)個(gè)數(shù) q必須滿足 如果信源 S的符號(hào)個(gè)數(shù) q不滿足上式，則增補(bǔ)一些概率為0的信源符號(hào)。四四 .r元哈夫曼碼元哈夫曼碼例例 59： 有一離散無記憶信源碼元集 X=(0,1,2)， 對(duì) S進(jìn)行 3元哈夫曼編碼 。解：解：信源符號(hào) 概率 編碼過程 碼字 Wi 碼長 li Si p(