[工學(xué)]第8章無失真的信源編碼-在線瀏覽
2025-03-08 12:05本頁面
【正文】 費諾編碼 ? 題中碼字還可用碼樹來表示，如圖所示。 ? 編碼步驟 ? 二進(jìn)制哈夫曼編碼 ? m進(jìn)制哈夫曼編碼 第七節(jié) 霍夫曼編碼 —— 編碼步驟 ? 將信源符號按概率從大到小的順序排列，令 p(x1)≥ p(x2)≥…≥ p(xn) ? 給兩個概率最小的信源符號 p(xn1)和 p(xn)各分配一個碼位“ 0”和“ 1”，將這兩個信源符號合并成一個新符號，并用這兩個最小的概率之和作為新符號的概率，結(jié)果得到一個只包含 (n－ 1)個信源符號的新信源。 ? 將縮減信源 S1的符號仍按概率從大到小順序排列，重復(fù)步驟 2，得到只含 (n－ 2)個符號的縮減信源 S2。然后從最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號所對應(yīng)的碼字。編碼過程如下圖（后頁）。若從前向后讀取碼字，則碼字不可分離。 ? 信源熵為： ? 平均碼長為 ? 編碼效率為 ? 若采用定長編碼，碼長 K=3，則編碼效率 ? 可見哈夫曼的編碼效率提高了 %。 ? 每次對縮減信源兩個概率最小的符號分配“ 0”和“ 1”碼元是任意的，所以可得到不同的碼字。 ? 不同的碼元分配，得到的具體碼字不同，但碼長 ki不變，平均碼長 也不變，所以沒有本質(zhì)區(qū)別； ? 縮減信源時，若合并后的新符號概率與其他符號概率相等，從編碼方法上來說， 這幾個符號的次序可任意排列，編出的碼都是正確的，但得到的 碼字不相同 。 K例： 單符號離散無記憶信源 ，用 兩種不同的方法對其編二進(jìn)制哈夫曼碼。 1 2 3 4 5, , , , ,( ) 0 . 4 0 . 2 0 . 2 0 . 1 0 . 1X x x x x xPX? ? ? ?? ????? ? ? ?第七節(jié) 霍夫曼編碼 —— 二進(jìn)制哈夫曼編碼 si li Wi 概率 s1 s2 s3 s4 s5 1 2 3 4 4 1 01 000 0010 0011 0 1 0 1 0 1 這兩種編碼哪一種更好呢，我們來計算一下二者的碼長。 第七節(jié) 霍夫曼編碼 —— 二進(jìn)制哈夫曼編碼 兩種編碼的平均碼長是一樣的，都是 ，那一種更好呢，我們可以計算一下平均碼長的方差。意味著第二種編碼方法的碼長變化較小，比較接近于平均碼長。 結(jié)論 ： 在哈夫曼編碼過程中，對縮減信源符號按概率由大到小的順序重新排列時，應(yīng) 使合并后的新符號盡可能排在靠前的位置 ，這樣可使合并后的新符號重復(fù)編碼次數(shù)減少，使短碼得到充分利用。 ? 二進(jìn)制碼不存在非全樹的情況，因為后續(xù)枝數(shù)是一時，這個枝就可以去掉使碼字長度縮短。 k為信源縮減次數(shù)。顯然 sm－ 1，若 s=m－ 1，意味著某個中間節(jié)點之后只有一個分枝，為了節(jié)約碼長，這一分枝可以省略。非全樹時，有 s個碼字不用： ? 第一次對最小概率符號分配碼元時就只取 (m－ s)個，分別配以 0,1,…, m－ s－ 1，把這些符號的概率相加作為一個新符號的概率，與其它符號一起重新排列。 第七節(jié) 霍夫曼編碼 —— m進(jìn)制哈夫曼編碼 例：對如下單符號離散無記憶信源 (例 )編三進(jìn)制哈夫曼碼。 1 2 3 4 5 6 7 8, , , , ,( ) 0 . 4 0 . 1 8 0 . 1 0 . 1 0 . 0 7 0 . 0 6 0 . 0 5 0 . 0 4X x x x x x x x xPX? ? ? ?? ????? ? ? ?第七節(jié) 霍夫曼編碼 —— m進(jìn)制哈夫曼編碼 第七節(jié) 霍夫曼編碼 —— m進(jìn)制哈夫曼編碼 ? 平均碼長為： ? 信息率為： ? 編碼效率為： ? 可見：哈夫曼的編碼效率相當(dāng)高，對編碼器的要求也簡單得多。 第八節(jié) 游程編碼、算術(shù)編碼 ? 香農(nóng)編碼、費諾編碼、哈夫曼編碼主要是針對無記憶信源。 第八節(jié) 游程編碼、算術(shù)編碼、冗余編碼 ? 游程 ：數(shù)字序列中連續(xù)出現(xiàn)相同符號的一段。 ? 連“ 0”這一段稱為“ 0”游程，它的長度稱為 游程長度 L(0)； ? 連“ 1”這一段稱為“ 1”游程，它的游程長度用 L(1)表示。 ? 對于隨機(jī)序列，游程長度是隨機(jī)的其取值可為 1,2,3,… ，直至無窮。 ? 游程變換 ：是一種一一對應(yīng)的變換，也是可逆變換。 ? 游程變換 將二元序列變換成了多元序列 ；這樣就適合于用其他方法，如哈夫曼編碼，進(jìn)一步壓縮信源，提高通信效率。 游程編碼 第八節(jié) 游程編碼、算術(shù)編碼、冗余編碼 ② 二元獨立序列游程長度的熵 ? 若二元序列的概率特性已知，由于二元序列與游程變換序列的一一對應(yīng)性，可計算出游程序列的概率特性。 游程編碼 第八節(jié) 游程編碼、算術(shù)編碼、冗余編碼 游程編碼 ? 游程長度至少是 1，理論上，游程長度可以是無窮，但很長的游程實際出現(xiàn)的概率非常小。因為游程變換是一一對應(yīng)的可逆變換，所以變換后熵值不變。 ? 假設(shè)“ 0”游程長度的哈夫曼編碼效率為 η0，“ 1”游程長度的哈夫曼編碼效率為 η1，由編碼效率的定義和式 ()可得對應(yīng)二元序列的編碼效率（信源熵和信息率之比為編碼效率 η=H(X)/R） ? 當(dāng)“ 0”游程和“ 1”游程的編碼效率都很高時，采用游程編碼的效率也很高，至少不會低于較小的那個效率。 01[ ( 0 ) ] [ ( 1 ) ]0 1 0 1[ ( 0 ) ] [ ( 1 ) ]H L H LH L H L???? ? ? ? ????? ? ?假設(shè) ，則有游程編碼 第八節(jié) 游程編碼、算術(shù)編碼、冗余編碼 算術(shù)編碼 ? 算術(shù)編碼不同于哈夫曼碼，它 是非分組（非塊）碼 。 ? 算術(shù)編碼利用了 累積概率 的概念。 ? 因為在編碼過程中，每輸入一個符號要進(jìn)行乘法和加法運算，所以稱此編碼方法為算術(shù)編碼。 第八節(jié) 游程編碼、算術(shù)編碼、冗余編碼 算術(shù)編碼 ? 設(shè)信源符號集 A={a1,a2,… ,an}，其相應(yīng)概率分布為 P (ai)， P (ai) 0(i=1,2, … ,n) ? 信源符號的累積分布函數(shù)為： 所得
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1