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

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

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

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

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

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

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

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