常用信源編碼方法之游程編碼

常用信源編碼方法——游程編碼信息理論與編碼工程技術(shù)學(xué)院電氣與電子信息系郭堃Page

2課程簡介

尋找信息傳輸過程中的共同規(guī)律，以提高信息傳輸?shù)挠行浴⒖煽啃院捅Ｃ苄?，使達到信息傳輸系統(tǒng)最優(yōu)化。

本次課內(nèi)容概要Page

3第一節(jié)信源編碼游程編碼1、游程編碼在傳真文件中的應(yīng)用2、MH編碼游程編碼的不足及發(fā)展第二節(jié)第三節(jié)

莫爾斯電碼Page

4一、信源編碼信源編碼簡介

信源編碼就是把信源符號變換到碼符號的一種映射。

編碼的目的就是將原始數(shù)據(jù)進行壓縮，提高通信效率。

信源編碼分為：無失真壓縮編碼和限失真壓縮編碼。

Page

5數(shù)據(jù)壓縮原理

根據(jù)信源的統(tǒng)計特性，用短碼來代替頻繁出現(xiàn)的原始數(shù)據(jù)，從而達到壓縮的目的。常見的信源編碼方法“游程編碼”、“霍夫曼編碼”、“字典編碼”、“算術(shù)編碼”等

Page

6簡介

游程編碼又稱“游程長度編碼”、“運行長度編碼”或“行程編碼”，該編碼屬于無失真壓縮編碼。

主要應(yīng)用在二值文件數(shù)據(jù)壓縮：傳真文件、二值圖像壓縮、音頻信號壓縮等

Page

7二、游程編碼編碼原理

原始數(shù)據(jù)有一定的相關(guān)性，往往連續(xù)出現(xiàn)同樣的消息，將同一個消息連續(xù)出現(xiàn)的序列稱為游程。該游程可以用一個消息的樣本和對于出現(xiàn)的次數(shù)來表示，譯碼時可以根據(jù)樣本和數(shù)量進行數(shù)據(jù)恢復(fù)。

基本編碼格式：Page

8符號碼標識碼游程長度例如某數(shù)據(jù)片段：

BBBBBBBBBBXXXXXXXXXAAAAAAUUUUUUUUUUUUU

游程編碼為：B#10X#9A#6U#13

原始數(shù)據(jù)共38個字符，編碼后共14個字符。由此可見游程編碼的符號序列長度遠遠少于原始信源符號序列長度。Page

91、游程編碼在傳真文件壓縮中的應(yīng)用電話網(wǎng)編碼器掃描譯碼器打印Page

10原稿打印稿Page

11二值圖像

掃描后傳真圖像屬于二值數(shù)據(jù)，在計算機中是用像素來表示，我們把一副圖像細分成很多行，又把每行分為很多像素。像素只有兩種取值：0表示背景（白色），1表示前景（黑色）。

總共有55個白游程以及54個黑游程。如果每個游程用一個字節(jié)（8位）進行編碼來提高效率。每個字節(jié)第一位表示黑白，剩下7個比特表示游程長度（0~127）。109個游程總共需要872bit。

Page

12例：下圖是一幅10×50黑白二值圖像“HiMom”

0011010010000010改進方法：（1）黑白交替出現(xiàn)，規(guī)定第一游程為白，這樣可省略符號碼，只需對長度編碼。（2）不同長度游程概率不同，對長度進行霍夫曼編碼，大概率編短碼，小概率編長碼。（3）白游程長度一般都比黑游程長度大，可考慮分開編碼。Page

132、MH編碼

MH編碼又叫修正的霍夫曼編碼，是ITU向各國推薦使用的編碼方案。先逐行游程編碼，再進行霍夫曼編碼。該方案是根據(jù)多個傳真樣本為概率統(tǒng)計依據(jù)而進行編碼的。

用途：黑白二值文件傳真的數(shù)據(jù)壓縮

Page

14

分辨度要求：A4幅面文件(210mm×297mm)有兩種分辨度

（1）一頁A4幅面有1188條掃描線，每條掃描線有1728個像素的掃描分辨率，約2.05M像素。

（2）一頁A4幅面有2376條掃描線，每條掃描線有1728個像素的掃描分辨率，約4.1M像素。Page

15MH編碼規(guī)范如下：(1)黑白游程分別對應(yīng)不同的碼表；(2)游程長度在0～63時，直接查表用相應(yīng)的結(jié)尾碼作為碼字；(3）游程長度在64～1728范圍內(nèi)時，用組合碼加上結(jié)尾碼作為相應(yīng)的碼字；

例如：5個黑像素 129個白像素=128+1

Page

16游程長度白游程碼字黑游程碼字000110101000011011110001110102011111310001041011011511000011611100010游程長度白游程碼字黑游程碼字641101100000111112810010000011001000256011011100000101101132000110110000000110011384001101110000001101004480110010000000011010151201100101000000110110010010+0001110011結(jié)尾碼碼表0~63組合碼碼表64~1728(4)為保證收發(fā)同色，規(guī)定每行的第一個游程為白游程(長度可以為零)，每行用一個結(jié)束碼(EOL)終止；EOL格式：000000000001，即11個“0”后1個“1”(5)在傳輸時，每頁數(shù)據(jù)之前加一個結(jié)束碼，每頁尾部連續(xù)實用6個結(jié)束碼。(6)填充碼FILL：為了保證每個掃描行數(shù)據(jù)傳輸時間達到收發(fā)雙方約定的最小傳輸時間，在長度不夠的編碼的結(jié)束碼前插入合適的“0”序列。Page

17MH編碼傳送格式Page

18EOL數(shù)據(jù)EOL數(shù)據(jù)填充EOL數(shù)據(jù)???數(shù)據(jù)EOL數(shù)據(jù)6個EOLT<TT頁首頁尾第1行第2行…末行結(jié)尾碼[例]設(shè)某頁傳真文件中某一掃描行的像素點為：

17

(白)

5（黑）55（白）10（黑）1641（白）1010110011010110000000100010011010+00101010000000000001Page

191600+41EOL原一行為1728個像素，用“0”表示白，用“l(fā)”表示黑，需1728位二元碼元。MH碼只需用54位二元碼元，數(shù)據(jù)壓縮比為1728:54＝32，壓縮效率很高。不足之處：

（1）游程編碼屬于變長編碼，每個碼字傳送時間長短不一，需要大量的緩沖寄存器。

（2）游程編碼只能檢錯不能糾錯，一般只適合優(yōu)質(zhì)的信道。

（3）只適用于二值圖像壓縮。多元則需對游程碼加以改進，配合其他編碼算法來實現(xiàn)高效壓縮。Page