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

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

2課程簡(jiǎn)介

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

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

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

莫爾斯電碼Page

4一、信源編碼信源編碼簡(jiǎn)介

信源編碼就是把信源符號(hào)變換到碼符號(hào)的一種映射。

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

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

Page

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

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

Page

6簡(jiǎn)介

游程編碼又稱“游程長(zhǎng)度編碼”、“運(yùn)行長(zhǎng)度編碼”或“行程編碼”，該編碼屬于無失真壓縮編碼。

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

Page

7二、游程編碼編碼原理

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

基本編碼格式：Page

8符號(hào)碼標(biāo)識(shí)碼游程長(zhǎng)度例如某數(shù)據(jù)片段：

BBBBBBBBBBXXXXXXXXXAAAAAAUUUUUUUUUUUUU

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

原始數(shù)據(jù)共38個(gè)字符，編碼后共14個(gè)字符。由此可見游程編碼的符號(hào)序列長(zhǎng)度遠(yuǎn)遠(yuǎn)少于原始信源符號(hào)序列長(zhǎng)度。Page

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

10原稿打印稿Page

11二值圖像

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

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

Page

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

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

132、MH編碼

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

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

Page

14

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

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

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

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

例如：5個(gè)黑像素 129個(gè)白像素=128+1

Page

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

17MH編碼傳送格式Page

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

17

(白)

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

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

（1）游程編碼屬于變長(zhǎng)編碼，每個(gè)碼字傳送時(shí)間長(zhǎng)短不一，需要大量的緩沖寄存器。

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

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