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