無失真信源編碼ppt課件(編輯修改稿)

　

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