游程編碼(蠻詳細的)

1、摘要為了減少信源輸出符號序列中的剩余度、提高符號的平均信息量，對信源輸出的符號序列所施行的變換。具體說，就是針對信源輸出符號序列的統(tǒng)計特性來尋找某種方法，把信源輸出符號序列變換為最短的碼字序列，使后者的各碼元所載荷的平均信息量最大，同時又能保證無失真地恢復(fù)原來的符號序列。最原始的信源編碼就是莫爾斯電碼，另外還有ASCII碼和電報碼都是信源編碼。但現(xiàn)代通信應(yīng)用中常見的信源編碼方式有：Huffman編碼、算術(shù)編碼、L-Z編碼，這三種都是無損編碼，另外還有一些有損的編碼方式。信源編碼的目標(biāo)就是使信源減少冗余，更加有效、經(jīng)濟地傳輸，最常見的應(yīng)用形式就是壓縮。 相應(yīng)地，信道編碼是為了對抗信道中的噪音和衰

2、減，通過增加冗余，如校驗碼等，來提高抗干擾能力以及糾錯能力。關(guān)鍵詞：信源；信道；編碼；游程編碼1課題描述游程編碼又稱“運行長度編碼”或“行程編碼”，是一種統(tǒng)計編碼，該編碼屬于無損壓縮編碼，是柵格數(shù)據(jù)壓縮的重要編碼方法。對于二值圖有效。在對圖像數(shù)據(jù)進行編碼時，沿一定方向排列的具有相同灰度值的像素可看成是連續(xù)符號，用字串代替這些連續(xù)符號，可大幅度減少數(shù)據(jù)量。相應(yīng)地，信道編碼是為了對抗信道中的噪音和衰減，通過增加冗余，如校驗碼等，來提高抗干擾能力以及糾錯能力。2 信源編碼2.1概念一種以提高通信有效性為目的而對信源符號進行的變換；為了減少或消除信源剩余度而進行的信源符號變換，對輸入信息進行編碼，優(yōu)化

3、信息和壓縮信息并且打成符合標(biāo)準(zhǔn)的數(shù)據(jù)包 2.2信源編碼作用 信源編碼的作用之一是設(shè)法減少碼元數(shù)目和降低碼元速率，即通常所說的數(shù)據(jù)壓縮：作用之二是將信源的模擬信號轉(zhuǎn)化成數(shù)字信號，以實現(xiàn)模擬信號的數(shù)字化傳輸。 2.3編碼方式 最原始的信源編碼就是莫爾斯電碼，另外還有ASCII碼和電報碼都是信源編碼。但現(xiàn)代通信應(yīng)用中常見的信源編碼方式有：Huffman編碼、算術(shù)編碼、L-Z編碼，這三種都是無損編碼，另外還有一些有損的編碼方式。信源編碼的目標(biāo)就是使信源減少冗余，更加有效、經(jīng)濟地傳輸，最常見的應(yīng)用形式就是壓縮。另外，在數(shù)字電視領(lǐng)域，信源編碼包括 通用的MPEG2編碼和H.264（MPEGPart10 A

4、VC）編碼等。相應(yīng)地，信道編碼是為了對抗信道中的噪音和衰減，通過增加冗余，如校驗碼等，來提高抗干擾能力以及糾錯能力。 2.4通信系統(tǒng)模型 信源-信源編碼-信道編碼-信道傳輸+噪聲-信道解碼-信源解碼-信宿 一般信息論的書上都會有信源編碼和信道編碼的具體講解，包括具體的編碼方法。 2.5描述 為了減少信源輸出符號序列中的剩余度、提高符號的平均信息量，對信源輸出的符號序列所施行的變換。具體說，就是針對信源輸出符號序列的統(tǒng)計特性來尋找某種方法，把信源輸出符號序列變換為最短的碼字序列，使后者的各碼元所載荷的平均信息量最大，同時又能保證無失真地恢復(fù)原來的符號序列。 既然信源編碼的基本目的是提高碼字序列中

5、碼元的平均信息量，那么，一切旨在減少剩余度而對信源輸出符號序列所施行的變換或處理，都可以在這種意義下歸入信源編碼的范疇，例如過濾、預(yù)測、域變換和數(shù)據(jù)壓縮等。當(dāng)然，這些都是廣義的信源編碼。 一般來說，減少信源輸出符號序列中的剩余度、提高符號平均信息量的基本途徑有兩個：使序列中的各個符號盡可能地互相獨立；使序列中各個符號的出現(xiàn)概率盡可能地相等。前者稱為解除相關(guān)性，后者稱為概率均勻化。 信源編碼的一般問題可以表述如下： 若某信源的輸出為長度等于M的符號序列集合 式中符號A為信源符號表，它包含著K個不同的符號，A=k|k=1,K，這個信源至多可以輸出KM個不同的符號序列。記U=KM。所謂對這個信源的輸

6、出 進行編碼，就是用一個新的符號表B的符號序列集合V來表示信源輸出的符號序列集合U。若V的各個序列的長度等于 N，即 式中新的符號表B共含L個符號，B=bl|l=1,L。它總共可以編出LN個不同的碼字。類似地,記VLN。為了使信源的每個輸出符號序列都能分配到一個獨特的碼字與之對應(yīng)，至少應(yīng)滿足關(guān)系 VLNUKM 或者 N/MlogK/logL。 假若編碼符號表B的符號數(shù)L與信源符號表A的符號數(shù)K相等，則編碼后的碼字序列的長度N必須大于或等于信源輸出符號序列的長度M；反之，若有NM，則必須有LK。只有滿足這些條件，才能保證無差錯地還原出原來的信源輸出符號序列(稱為碼字的唯一可譯性)?？墒牵谶@些條

7、件下，碼字序列的每個碼元所載荷的平均信息量不但不能高于，反而會低于信源輸出序列的每個符號所載荷的平均信息量。這與編碼的基本目標(biāo)是直接相矛盾的。下面的幾個編碼定理，提供了解決這個矛盾的方法。它們既能改善信息載荷效率，又能保證碼字唯一可譯。 離散無記憶信源的定長編碼定理：對于任意給定的0，只要滿足條件 N/M(H(U)+)/logL。那么，當(dāng)M足夠大時,上述編碼幾乎沒有失真;反之,若這個條件不滿足，就不可能實現(xiàn)無失真的編碼。式中H(U)是信源輸出序列的符號熵。 通常,信源的符號熵H(U)logK，因此,上述條件還可以表示為 【H(U)+】/logLN/MlogK/logL。特別,若有KL,那么,只

8、要H(U)logK,就可能有NM，從而提高信息載荷的效率。由上面這個條件可以看出，H(U)離logK越遠,通過編碼所能獲得的效率改善就越顯著。實質(zhì)上，定長編碼方法提高信息載荷能力的關(guān)鍵是利用了漸近等分性,通過選擇足夠大的M,把本來各個符號概率不等因而H(U)logK的信源輸出符號序列變換為概率均勻的典型序列，而碼字的唯一可譯性則由碼字的定長性來解決。 離散無記憶信源的變長編碼定理 變長編碼是指V的各個碼字的長度不相等。只要V中各個碼字的長度 Ni(i1，V)滿足克拉夫特不等式 這 V個碼字就能唯一地正確劃分和譯碼。離散無記憶信源的變長編碼定理指出：若離散無記憶信源的輸出符號序列為， 式中 Ak

9、|k=1,K,符號熵為H(U)，對U進行唯一可譯的變長編碼，編碼字母表B的符號數(shù)為L,即B=bl|l=1,L,那么必定存在一種編碼方法，使編出的碼字Vi(vi1,viNi)，(i=1,V)，具有平均長度嚻： MH(U)/logL嚻MH(U)/logL+1 若L=K，則當(dāng)H(U)logKlogL時,必有嚻M；H(U)離logK越遠，則嚻越小于M。 具體實現(xiàn)唯一可譯變長編碼的方法很多，但比較經(jīng)典的方法還是仙農(nóng)編碼法、費諾編碼法和霍夫曼編碼法。其他方法都是這些經(jīng)典方法的變形和發(fā)展。所有這些經(jīng)典編碼方法，都是通過以短碼來表示常出現(xiàn)的符號這個原則來實現(xiàn)概率的均勻化，從而得到高的信息載荷效率；同時，通過遵

10、守克拉夫特不等式關(guān)系來實現(xiàn)碼字的唯一可譯。 霍夫曼編碼方法的具體過程是：首先把信源的各個輸出符號序列按概率遞降的順序排列起來，求其中概率最小的兩個序列的概率之和，并把這個概率之和看作是一個符號序列的概率，再與其他序列依概率遞降順序排列（參與求概率之和的這兩個序列不再出現(xiàn)在新的排列之中），然后，對參與概率求和的兩個符號序列分別賦予二進制數(shù)字0和1。繼續(xù)這樣的操作,直到剩下一個以1為概率的符號序列。最后，按照與編碼過程相反的順序讀出各個符號序列所對應(yīng)的二進制數(shù)字組，就可分別得到各該符號序列的碼字。 例如，某個離散無記憶信源的輸出符號序列及其對應(yīng)的概率分布為 對這些輸出符號序列進行霍夫曼編碼的具體步

11、驟和結(jié)果如表。 由表中可以看出，在碼字序列中碼元0和1的概率分別為10/21和11/21，二者近乎相等，實現(xiàn)了概率的均勻化。同時，由于碼字序列長度滿足克拉夫特不等式 22-2+32-3+22-41 因而碼字是唯一可譯的，不會在長的碼字序列中出現(xiàn)劃錯碼字的情況。 以上幾個編碼定理，在有記憶信源或連續(xù)信源的情形也有相應(yīng)的類似結(jié)果。在實際工程應(yīng)用中，往往并不追求無差錯的信源編碼和譯碼，而是事先規(guī)定一個譯碼差錯率的容許值，只要實際的譯碼差錯率不超過這個容許值即認為滿意（見信息率-失真理論和多用戶信源編碼）。游程長度編碼的主要思想是將一個相同值的連續(xù)申用其值和申長(重復(fù)的個數(shù))的數(shù)對二元組來替代。例如，

12、在圖像編碼中，可以定義沿特定方向上具有相同灰度值的相鄰像素為一輪，其延續(xù)的長度稱之為延續(xù)的行程，即游程。游程終點位置由前一游程終點的相對距離確定，這樣就可以由灰度游程串來表示圖像數(shù)據(jù)。例如，若沿水平方向有一串M 個像素具有相同的灰度N，則按游程長度編碼后，只傳遞兩個值(N，M)就可以代替這M 個像素的M個灰度值NJ簡單來說，游程長度編碼的主要任務(wù)是統(tǒng)計連續(xù)相同字符的個數(shù)，解碼時要根據(jù)字符及連續(xù)相同字符的個數(shù)，恢復(fù)原來的數(shù)據(jù)。3 編碼的實現(xiàn)3.1 游程編碼算法 編碼的基本原理是：用一個符號值或串長代替具有相同值的連續(xù)符號（連續(xù)符號構(gòu)成了一段連續(xù)的“行程”。行程編碼因此而得名），使符號長度少于原始

13、數(shù)據(jù)的長度。只在各行或者各列數(shù)據(jù)的代碼發(fā)生變化時，一次記錄該代碼及相同代碼重復(fù)的個數(shù)，從而實現(xiàn)數(shù)據(jù)的壓縮。在m元序列中，可能m種游程，連著出現(xiàn)m種符號ar的游程，其長度L（r）就是r游程長度，這是一個隨機變量。用L（r）也可構(gòu)成游程序列但是這種變換必須再加一些符號，才能成為一一對應(yīng)或可逆的。游程長度編碼的主要思想是將一個相同值的連續(xù)申用其值和申長(重復(fù)的個數(shù))的數(shù)對二元組來替代。例如，在圖像編碼中，可以定義沿特定方向上具有相同灰度值的相鄰像素為一輪，其延續(xù)的長度稱之為延續(xù)的行程，即游程。游程終點位置由前一游程終點的相對距離確定，這樣就可以由灰度游程串來表示圖像數(shù)據(jù)。例如，若沿水平方向有一串M

14、個像素具有相同的灰度N，則按游程長度編碼后，只傳遞兩個值(N，M)就可以代替這M 個像素的M個灰度值NJ簡單來說，游程長度編碼的主要任務(wù)是統(tǒng)計連續(xù)相同字符的個數(shù)，解碼時要根據(jù)字符及連續(xù)相同字符的個數(shù)，恢復(fù)原來的數(shù)據(jù)。3.2 游程編碼特點 游程編碼仍是變長碼，有其固有的缺點，及需要大量的緩沖和優(yōu)質(zhì)的信道。此外，編程長度1可以從一直到無限，這在碼字的選擇和碼表的建立方面都有困難，實際應(yīng)用是尚需采用某些措施來改進。一般情況下游程長度越長，其概率越小，這在以前的計算中也可以看見，而且將隨著長度的增大漸進向零。對于小概率的碼字，其長度為達到概率匹配或較長，損失不會太大，也就是對平均碼字長度影響較小。再按

15、哈夫曼編碼或其他方法處理以達到壓縮碼率的目的 。3.3 Matlab程序設(shè)計實驗源程序以及相關(guān)結(jié)果如下： image1=imread(C:Program FilesMATLAB71work1girl.jpg); %讀入圖像 imshow(image1); %顯示原圖像 % 以下程序是將原圖像轉(zhuǎn)換為二值圖像 image2=image1(:); %將原始圖像寫成一維的數(shù)據(jù)并設(shè)為 image2 image2length=length(image2); % 計算image2的長度 for i=1:1:image2length % for 循環(huán)，目的在于轉(zhuǎn)換為二值圖像If image2(i)=127im

16、age2(i)=255;else image2(i)=0;endend image3=reshape(image2,146,122); % 重建二維數(shù)組圖像，并設(shè)為image3 figure,imshow(image3); % 以下程序為對原圖像進行游程編碼，壓縮 X=image3(:); %令X為新建的二值圖像的一維數(shù)據(jù)組 x=1:1:length(X); % 顯示游程編碼之前的圖像數(shù)據(jù) figure,plot(x,X(x); j=1; image4(1)=1; for z=1:1:(length(X)-1) % 游程編碼程序段if X(z)=X(z+1)image4(j)=image4(j

17、)+1;elsedata(j)=X(z); % data(j)代表相應(yīng)的像素數(shù)據(jù)j=j+1;image4(j)=1;endend data(j)=X(length(X); % 最后一個像素數(shù)據(jù)賦給data image4length=length(image4); % 計算游程編碼后的所占字節(jié)數(shù)，記為image4length y=1:1:image4length ; % 顯示編碼后數(shù)據(jù)信息 figure,plot(y,image4(y); CR=image2length/image4length; % 比較壓縮前于壓縮后的大小 % 下面程序是游程編碼解壓 l=1; for m=1:image4length for n=1:1:image4(m); rec_image(l)=data(m); l=l+1; end end u=1:1