數(shù)據(jù)壓縮與信源編碼第3講霍夫曼編碼.ppt

1、數(shù)據(jù)壓縮和源代碼第3課霍夫曼編碼，西安市電子科技大學(xué)電子工程學(xué)學(xué)院講座：林森浩，Huffman編碼算法，基本規(guī)則發(fā)生概率高的符號(hào)使用較短的編碼。發(fā)生概率最低的兩個(gè)符號(hào)使用相同長(zhǎng)度的編碼。特定步驟按從高到低的順序排列符號(hào)發(fā)生的概率。將兩個(gè)概率最低的符號(hào)合并成一個(gè)符號(hào)。概率之和是新符號(hào)的概率。重復(fù)以上兩個(gè)步驟，直到概率為1牙齒。每次合并符號(hào)時(shí)，用0和1分隔兩個(gè)符號(hào)。如果從根節(jié)點(diǎn)開始搜索每個(gè)符號(hào)，并記錄0，1序列，則它將成為該符號(hào)的編碼。Huffman編碼算法，a2 (0.4)，a1 (0.2)，a3 (0.2)，a4 (0.1)，a5 (0.1)，a2 (0.4)，a2 huffer，Huffma

2、n編碼算法，Huffman編碼平均代碼長(zhǎng)度=0.2 * 2 0.4 * 1 0.2 * 3 0.1 * 4 0.1 * 4=2.2位，假定每個(gè)內(nèi)部節(jié)點(diǎn)的所有子節(jié)點(diǎn)的概率總和表示該節(jié)點(diǎn)的值，Huffman編碼，1.0，a2，Huffman編碼算法，a2 (0.4)，a1 (0.2)，a3 (0.2)，a4 (0.1)，a5 (0.1)，a2 (0.4)，a2 Hofman編碼Huffman編碼算法、A2 (0.4)、A1 (0.2)、A3 (0.2)、A4 (0.1)、A5 (0.1)、A2 (1，0，1，0，1，0，0)哪個(gè)霍夫曼編碼最好？答案是：最小方差霍夫曼碼，最小方差霍夫曼碼合并兩個(gè)符號(hào)

3、時(shí)，如果三個(gè)以上符號(hào)概率最小，則將剛剛合并的符號(hào)放在概率相同的符號(hào)的頂部。最小方差Huffman編碼算法，a2 (0.4)、a1 (0.2)、a3 (0.2)、a4 (0.1)、a5 (0.1)、a2 (0.4)、a2，為什么代碼長(zhǎng)度方差較小的編碼最好？假定特定速度的源(例如，1000symbol/秒，Huffman編碼平均代碼長(zhǎng)度為2.2bits)，則平均編碼代碼流輸出為2200bit/秒，信道帶寬為220bit/秒，滿足傳輸要求。對(duì)于特定速度的源，如最小分布式Huffman編碼算法、1000symbol/秒、Huffman編碼平均代碼長(zhǎng)度2.2bits，平均編碼代碼流輸出為2200bit/

4、秒，假定通道帶寬為2200bit/秒，可以滿足傳輸，如果源連續(xù)輸出a2，則編碼1代碼流輸出為200bit/秒如果源連續(xù)輸出a5，則編碼1代碼流輸出為4000比特/秒，并且通道帶寬不足。最小分布式Huffman編碼算法，為了充分利用通道帶寬，必須緩沖編碼輸出的代碼流，以便在通道帶寬不足時(shí)存儲(chǔ)代碼流，在通道帶寬豐富時(shí)發(fā)送。如果源連續(xù)輸出a2，則編碼1碼流輸出為1000比特/秒，浪費(fèi)通道帶寬。如果源連續(xù)輸出a5，則編碼1代碼流輸出為4000比特/秒，并且通道帶寬不足。，最小方差僅編碼算法，1，1，1，1，1，1，a5，1，1，1，1，1，1，1，1編碼的代碼長(zhǎng)度分布越小，緩沖區(qū)就越小因此，最佳Huf

5、fman編碼是最小分布式Huffman編碼。如果源連續(xù)輸出a2，則編碼1碼流輸出為1000比特/秒，浪費(fèi)通道帶寬。如果源連續(xù)輸出a5，則編碼1代碼流輸出為4000比特/秒，并且通道帶寬不足。不是只有赫夫曼編碼功能，赫夫曼編碼方法組成的代碼。Huffman編碼功能，Huffman編碼的代碼長(zhǎng)度可變，但不需要其他同步代碼。例如，根據(jù)編碼1，100110111111111可以解釋為a1a2a3a4a5。例如，根據(jù)代碼3，10001101010011可以解釋為a1a2a3a4a5。Huffman代碼字、Huffman代碼字是從Huffman代碼字中特別挑選出來(lái)的，目的是在解碼時(shí)方便檢測(cè)代碼字符的長(zhǎng)度。(阿爾伯特愛因斯坦，Northern Exposure(美國(guó)電視電視劇)，代碼，下面兩個(gè)代碼中的代碼2是規(guī)范Huffman代碼單詞。Huffman代碼字規(guī)范，Huffman代碼字規(guī)范first 6=0；for x 3360=5 down to 1 do firstx=(firstx 1 num LX 1