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

1、常用信源編碼方法常用信源編碼方法 游程游程編碼編碼信息理論與編碼工程技術(shù)學院工程技術(shù)學院電氣與電子信息系電氣與電子信息系郭堃郭堃Page 2課程簡介課程簡介 尋找信息傳輸過程中的共同規(guī)律，以尋找信息傳輸過程中的共同規(guī)律，以提高信息傳輸?shù)奶岣咝畔鬏數(shù)挠行杂行?、可靠性可靠性和和保密性保密性，使達到信息傳輸系統(tǒng)最優(yōu)化。使達到信息傳輸系統(tǒng)最優(yōu)化。 本次課內(nèi)容概要本次課內(nèi)容概要Page 3信源編碼信源編碼游程編碼游程編碼1、游程編碼在傳真文件中的應(yīng)用2、MH編碼游程編碼的不足及發(fā)展游程編碼的不足及發(fā)展 莫爾斯電碼莫爾斯電碼Page 4一、信源編碼一、信源編碼信源編碼簡介信源編碼簡介 信源編碼就是把

2、信源符號變換到碼符號的一種映射。 編碼的目的就是將原始數(shù)據(jù)進行壓縮，提高通信效率。 信源編碼分為：無失真壓縮編碼和限失真壓縮編碼。Page 5數(shù)據(jù)壓縮原理數(shù)據(jù)壓縮原理 根據(jù)信源的統(tǒng)計特性，用短碼來代替頻繁出現(xiàn)的原始數(shù)據(jù)，從而達到壓縮的目的。常見的信源編碼方法常見的信源編碼方法“游程編碼”、“霍夫曼編碼”、“字典編碼”、“算術(shù)編碼”等 Page 6簡介簡介游程編碼又稱“游程長度編碼”、“運行長度編碼”或“行程編碼”，該編碼屬于無失真壓縮編碼 。主要應(yīng)用在二值文件數(shù)據(jù)壓縮：傳真文件、二值圖像壓縮、音頻信號壓縮等 Page 7二、游程編碼二、游程編碼編碼原理編碼原理原始數(shù)據(jù)有一定的相關(guān)性，往往連續(xù)出

3、現(xiàn)同樣的消息，將同一個消息連續(xù)出現(xiàn)的序列稱為游程。該游程可以用一個消息的樣本和對于出現(xiàn)的次數(shù)來表示，譯碼時可以根據(jù)樣本和數(shù)量進行數(shù)據(jù)恢復?；揪幋a格式：Page 8符號碼 標識碼 游程長度例如某數(shù)據(jù)片段：例如某數(shù)據(jù)片段：BBBBBBBBBBXXXXXXXXXAAAAAAUUUUBBBBBBBBBBXXXXXXXXXAAAAAAUUUUUUUUUUUUUUUUUUUUUU游程編碼為：B#10X#9A#6U#13 原始數(shù)據(jù)共38個字符，編碼后共14個字符。由此可見游程編碼的符號序列長度遠遠少于原始信源符號序列長度。Page 91 1、游程編碼在傳真文件壓縮中的應(yīng)、游程編碼在傳真文件壓縮中的應(yīng)用用編

4、碼器編碼器掃描掃描譯碼器譯碼器打印打印Page 10原稿原稿打印稿打印稿Page 11二值圖像 掃描后傳真圖像屬于二值數(shù)據(jù)，在計算機中是用像素來表示，我們把一副圖像細分成很多行，又把每行分為很多像素。像素只有兩種取值：0表示背景（白色），1表示前景（黑色）。 總共有55個白游程以及54個黑游程。如果每個游程用一個字節(jié)（8位）進行編碼來提高效率。每個字節(jié)第一位表示黑白，剩下7個比特表示游程長度（0127）。109個游程總共需要872bit。 Page 12例：下圖是一幅1050黑白二值圖像“Hi Mom” 0011 01000011 0100 1000 00101000 0010改進方法：改進方

5、法：（1）黑白交替出現(xiàn)，規(guī)定第一游程為白，這樣可省略符號碼，只需對長度編碼。（2）不同長度游程概率不同，對長度進行霍夫曼編碼，大概率編短碼，小概率編長碼。（3）白游程長度一般都比黑游程長度大，可考慮分開編碼。Page 132 2、MHMH編碼編碼MH編碼又叫修正的霍夫曼編碼，是ITU向各國推薦使用的編碼方案。先逐行游程編碼，再進行霍夫曼編碼。該方案是根據(jù)多個傳真樣本為概率統(tǒng)計依據(jù)而進行編碼的。用途：用途：黑白二值文件傳真的數(shù)據(jù)壓縮Page 14分辨度要求：分辨度要求：A4幅面文件(210mm297mm ) 有兩種分辨度 （1）一頁A4幅面有1188條掃描線，每條掃描線有1728個像素的掃描分辨

6、率，約2.05M像素。（2）一頁A4幅面有2376條掃描線，每條掃描線有1728個像素的掃描分辨率，約4 . 1M 像素。Page 15MHMH編碼規(guī)范如下：編碼規(guī)范如下：(1) 黑白游程分別對應(yīng)不同的碼表；(2)游程長度在0 06363時，直接查表用相應(yīng)的結(jié)尾碼作為碼字；( 3）游程長度在646417281728范圍內(nèi)時，用組合碼加上結(jié)尾碼作為相應(yīng)的碼字；例如：例如： 5 5個黑像素個黑像素 129 129個白像素個白像素=128+1 =128+1 Page 16游程長度游程長度白游程碼字白游程碼字黑游程碼字黑游程碼字0 00011010100110101000011011100001101

7、111 10001110001110100102 20111011111113 31000100010104 4101110110110115 511001100001100116 61110111000100010游程長度游程長度白游程碼字白游程碼字黑游程碼字黑游程碼字64641101111011000001111000001111128128100101001000001100100000001100100025625601101110110111000001011011000001011011320320001101100011011000000011001100000011001138

8、43840011011100110111000000110100000000110100448448011001000110010000000011010100000011010151251201100101011001010000001101100000000110110010010+00011110010+00011100110011結(jié)尾碼碼表結(jié)尾碼碼表063063組合碼碼表組合碼碼表641728641728(4) 為保證收發(fā)同色，規(guī)定每行的第一個游程為白游程(長度可以為零)，每行用一個結(jié)束碼(EOL) 終止；EOL格式：000000000001，即11個“0”后1個“1”(5) 在傳輸時

9、，每頁數(shù)據(jù)之前加一個結(jié)束碼，每頁尾部連續(xù)實用6個結(jié)束碼。(6)填充碼FILL：為了保證每個掃描行數(shù)據(jù)傳輸時間達到收發(fā)雙方約定的最小傳輸時間，在長度不夠的編碼的結(jié)束碼前插入合適的“0”序列。Page 17MHMH編碼傳送格式編碼傳送格式Page 18EOL 數(shù)據(jù) EOL 數(shù)據(jù) 填充 EOL 數(shù)據(jù) 數(shù)據(jù) EOL 數(shù)據(jù) 6個EOLTTT頁首頁首頁尾頁尾第第1行行第第2行行末行末行結(jié)尾碼結(jié)尾碼 例例 設(shè)某頁傳真文件中某一掃描行的像素點為：設(shè)某頁傳真文件中某一掃描行的像素點為： 1717 ( (白白) ) 5 5（黑）（黑） 5555（白）（白） 1010（黑）（黑）16411641（白）（白）1010

10、11 0011 01011000 0000100 010011010+ 00101010000000000001Page 191600+41 EOL 原一行為原一行為17281728個像素，用個像素，用“0”0”表示白，用表示白，用“l(fā)”l”表示表示黑，需黑，需17281728位二元碼元。位二元碼元。MHMH碼只需用碼只需用5454位二元碼元，位二元碼元，數(shù)據(jù)壓縮比為數(shù)據(jù)壓縮比為1728:541728:543232，壓縮效率很高。，壓縮效率很高。不足之處：不足之處： （1）游程編碼屬于變長編碼，每個碼字傳送時間長短不一，需要大量的緩沖寄存器。（2）游程編碼只能檢錯不能糾錯，一般只適合優(yōu)質(zhì)的信道。（3）只適用于二值圖像壓縮。多元則需對游程碼加以改進，配合其他編碼算法來實現(xiàn)高效壓縮