[信息與通信]6無失真信源編碼-資料下載頁
2024-10-18 22:14本頁面
【正文】 Huffman編碼 ? 最佳編碼 ? Huffman編碼方法 最佳編碼 ? 最佳編碼：對于 S，將其編碼為二進制的單義碼，若此代碼的平均長度不大于其他任何方法的平均長度，則稱此代碼為最佳代碼，與之對應的編碼方法稱為最佳編碼方法。 ? 香農第一定理給出了信源熵與編碼后的平均碼長之間的關系，同時也指出可以通過編碼使平均碼長達到極限值，因此，香農第一定理是一個極限定理。但定理中并沒有告訴我們如何來構造這種碼。 Huffman編碼 ? 最佳編碼 ? Huffman編碼 Huffman編碼 Huffman編碼的步驟 1. 將 q個信源符號按概率分布 p(si)的大小 ,以遞減次序由大到小 ,自上而下排成一列 。 2. 對處于最下面的概率最小的 r個信源符號 , 各分配一個碼元 a1, a2, …, ar.將處于最下面的概率最小的 r個信源符號合并成一個新符號，并用這 r個最小概率之和作為新符號的概率。結果得到一個只包含 (qr+1)個信源符號的新信源。稱為信源的第一次縮減信源，用 S1表示 。 3. 將縮減信源 S1的符號仍按概率從大到小的順序排列，重復上面的步驟，得到只含 ((qr+1)r+1)個符號的縮減信源 S2 。 4. 重復上面的步驟 ,直至縮減信源的符號數(shù)小于或等于 r為止，此時所剩符號的概率之和必為 1。然后從最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號對應的碼字。 例 設信源共有 7個符號組成，其概率如表所示，求其 Huffman碼。 信源符號 xi 符號概率 p(xi) x1 x2 x3 x4 x5 x6 x7 信源 符號 符號概率 編 碼 過 程 碼字 碼長 x1 10 2 x2 11 2 x3 000 3 x4 001 3 x5 010 3 x6 0110 4 x7 0111 4 0 1 0 1 0 1 0 1 0 1 0 1 Huffman編碼 ? 特點： ? 編碼不是唯一的 ? 保證了概率大的符號對應于短碼，概率小的符號對應于長碼，而且短碼得到充分利用 ? 每次縮減信源的最后二個碼字總是最后一位碼元不同，前面各位碼元相同（二元碼情況） ? 每次縮減信源的最長兩個碼字具有相同碼長 ? 后三個特點保證了所得到 Huffman碼一定是最佳碼 Huffman編碼 ? 哈夫曼編碼得到的碼不是唯一的，但最后的平均碼長一定是一樣的。在這種情況下，怎么樣來判斷一個碼的好壞呢？ ? 引入碼字長度 ni偏離平均碼長 的方差 σ2，即 ? 方差越小，說明各個碼的長度都比較接近平均長度，這樣編碼器和解碼器就可以比較簡單，這樣的碼就認為是好碼 ? 因此，在哈夫曼編碼的過程中，當縮減信源的概率分布重新排列時，應使合并得來的概率和盡可能處于最高的位置，這樣可使合并的元素重復編碼次數(shù)減少，使短碼得到充分利用。 n? ? ? ?2221()ni i iiE n n p x n n????? ? ? ?????
教學課件相關推薦
鄂ICP備17016276號-1