第6章2 霍夫曼碼、算術(shù)碼和lzw碼

1、第6節(jié)霍夫曼碼霍夫曼碼1.1952年霍夫曼(Huffman)提出的，是歷史記錄中第一個最優(yōu)即時碼。2.二元霍夫曼碼的構(gòu)造方法：根據(jù)信源符號的概率自底向上地構(gòu)造碼樹，步驟二元霍夫曼碼的構(gòu)造方法：根據(jù)信源符號的概率自底向上地構(gòu)造碼樹，步驟如下：如下：（1）將信源U的n個符號ui按概率p(ui)從大到小排列，構(gòu)成碼樹的葉節(jié)點。（2）將兩個最小的概率值相加，構(gòu)成二者的父節(jié)點。（3）將所有沒有父節(jié)點的概率值按從大到小重新排列。（4）重復(fù)（2）與（

2、3）直到根節(jié)點出現(xiàn)，即步驟（2）中兩個概率值相加=1.例6110.5，0.25，0.125，0.125解：1）畫出碼樹包括各節(jié)點對應(yīng)的概率值。2）平均碼長：2）編碼效率：3）信源熵（信源的信息傳輸率）：4）信源的相對熵率（信源的信息傳輸效率）：3.二分組霍夫曼碼二分組霍夫曼碼例6120.7，0.3結(jié)論結(jié)論：對于“小消息信源”，必須用分組長度較大的霍夫曼碼，才能獲得較大的編碼效率與較好的壓縮效果。這是提高編碼效率的重要途徑。4.最優(yōu)分組碼

3、最優(yōu)分組碼定義定義1.令S為一離散信源，用一個新符號取代S中兩個概率最小的信源符號，并把這兩個最小概率合并為該新符號的概率，而其它信源符號及其概率不變，所得的信源S(1)稱為信源S的（一次）縮減信源縮減信源，并稱S為S(1)的擴展信源。擴展信源。n步縮減信源步縮減信源S(n).2.令C是信源S的一個即時碼，其中有兩個碼字w’與w’’長度最大且相等，用其最大真前綴替換C中的w’與w’’所得的即時碼C(1)稱為C的（一次）縮減縮減碼，碼，并

4、稱C為C(1)的擴展碼。與擴展碼。與n步縮減碼分別記為和步縮減碼分別記為和Cn。顯然，信源每縮減一次，其符號總數(shù)減1；即時碼每縮減一次其碼字總數(shù)減1.引理引理1令C為即時碼，C(1)是碼C的一個縮減碼，則兩個碼的平均碼長之間有如下關(guān)系：LC=LC(1)p’p’’其中p’與p’’分別是C中被合并的兩個碼字的概率。證明證明設(shè)S有q個符號，概率分別為pi，碼C中對應(yīng)的碼字長為li，其中對應(yīng)于概率p’的碼字長記為l’，則（1）碼長不同導(dǎo)致信源編

5、碼器不能勻速輸出碼元符號，因此不能直接與信道連接。解決辦法是添加緩沖寄存器。（2）存在差錯擴散的問題。解決辦法是使用糾錯碼提高數(shù)據(jù)的抗干擾能力。（3）霍夫曼碼的編譯碼都需要查找碼本，碼本太大的話，占用內(nèi)存大且費時。因此，不能對太大的擴展信源進行編碼。為進一步提高編碼效率，需要改用非分組碼，例如算術(shù)碼、字典碼。（4）霍夫曼碼屬于概率匹配碼，需要知道信源的統(tǒng)計特性，且不能適應(yīng)信源概率變化。可改用具有自適應(yīng)性的算術(shù)編碼，或字典碼。第7節(jié)算術(shù)碼

6、算術(shù)碼仍設(shè)U為離散無記憶信源。1.特點：特點：1）非分組碼，全序列編碼：是一個非分組碼，全序列編碼：是一個雙射，可將任意長的:01fU?信源序列編碼為“一個”碼字。2）用信源序列S的累積概率F(S)的一個近似值作為S的碼字，該近似值的長度由S的自信息量或概率p(S)確定。2.累積概率累積概率||||()()lexTSTSFSpT????注意注意，累積概率值中不含p(S)。遞推公式遞推公式：(用樹圖說明)()()()()FSuFSpSFu

7、??3.累積概率區(qū)間累積概率區(qū)間長度相同的信源序列的累積概率有如下關(guān)系：1210()()()1()()()miiiFSFSFSFSFSpS?????????將單位區(qū)間[01]劃分為若干不相交的小區(qū)間：稱為序列S的累積概率區(qū)間累積概率區(qū)間。[()()())SIFSFSpS??用樹圖說明各累積概率區(qū)間的包含與不相交關(guān)系用樹圖說明各累積概率區(qū)間的包含與不相交關(guān)系。4.編碼方法編碼方法基本思想基本思想：（1）計算信源序列S的“累積概率”F(S)