【文章內(nèi)容簡介】 據(jù)集中存在大量的無關(guān)位，可以適當(dāng)?shù)膶@些無關(guān)位進行賦值填充，增加0 游程的長度，這些游程長度在同組的概率很高。該編碼方案為了增加0 游程的長度，對填充后的測試數(shù)據(jù)采取了差分處理，即把測試數(shù)據(jù)等長劃分并進行異或邏輯運算。通過對ISCAS 89 基準(zhǔn)電路硬故障測試集的分析對不同的電路各組共前綴次數(shù)的分布不均勻，因此CPRL碼引入了一個參變量M,M 表示確定的組號，M 取值不同，編碼結(jié)果就不同。但對于具體的編碼，M 是事先確定好的常數(shù)，顯然M 的取值范圍在1 和最大組號之間。 CPRL 碼的具體編碼方法如下：若待編碼的0 游程長度所在的組號≤M,則直接用FDR 碼字表示CPRL 碼字，原因是組號小的碼字前綴位數(shù)也短；若待編碼的0 游程長度所在的組號≥M，且相鄰游程長度在同一組內(nèi)，則后面的游程CPRL碼字由該游程長度對應(yīng)的FDR 碼字省略前綴，并在剩下的碼字后綴后面加上一個標(biāo)志位0 組成，同組相鄰的第一個游程的CPRL 碼字由對應(yīng)的FDR 碼字加上標(biāo)志位1 組成；若待編碼的0 游程長度所在的組號≥M，且相鄰游程長度不在同一組內(nèi)，則各游程的CPRL 碼字由對應(yīng)的FDR 碼字加一位標(biāo)志位組成。下面給出一個CPRL 碼的編碼實例：（參變量M=1）編碼前的初始測試數(shù)據(jù)：0000001 0000001 0000111 0010111 1010010；對應(yīng)的差分測試數(shù)據(jù)： 0000001 0000000 0000110 0010000 1000101（35位）；差分后的測試數(shù)據(jù)對應(yīng)的FDR 碼：110000 110101 00 1001 1010 1001 01（28 位）；對應(yīng)的CPRL 碼字：1100001 1010 00 10011 101 010 01（26 位）。 本章主要介紹了信源編碼中的幾種最佳信源變長編碼:香農(nóng)（Shannon）、費諾（Fano）、哈夫曼（Huffman）編碼，以及這幾種編碼的編碼過程,然后主要介紹了哈夫曼樹的構(gòu)成步驟，以及游程編碼的算法和編碼特點。75 第3章 游程編碼以及哈弗曼編碼 第3章 游程編碼以及哈夫曼編 游程編碼 游程編碼是針對于二元序列的壓縮編碼方法，在二元序列中，只有兩種符號，即“0”游程和“1”游程，“0”游程和“l(fā)”游程總是交替出現(xiàn)的。如果規(guī)定二元序列是以“0”開始，第一個游程是“0”游程，第二個必為“1”游程，第三個又是“0”游程等等。而對二元序列游程編碼主要是針對于每個游程長度以及總共有多少個游程。我在c語言編碼過程中主要針對這兩方面進行編碼，即通過對“0”、“1”的變換次數(shù)來確定二元序列中總共有多少個游程；然后在確定每一個游程中游程的長度。兩者綜合即實現(xiàn)對于二元序列的游程編碼。 用游程編碼壓縮數(shù)據(jù)時，首先要計算每次連續(xù)相同字符的個數(shù)，然后將每次連續(xù)相同的字符及個數(shù)保存起來。這種壓縮數(shù)據(jù)的方法, 連續(xù)相同的字符及出現(xiàn)連續(xù)相同的次數(shù)越多，壓縮比就越大，反之，壓縮比就越小。數(shù)據(jù)壓縮算法流程如下： 1) 打開源數(shù)據(jù)文件和壓縮后的數(shù)據(jù)文件； 2) 從源數(shù)據(jù)文件中讀取字符, 并把它放入一個寄存器中，然后再循環(huán)讀取后面的字符，并與寄存器中的字符相比較。如果相等，則計數(shù)器加1，否則，把寄存器中的字符和計數(shù)器中數(shù)寫入壓縮數(shù)據(jù)文件中，然后再把寄存器中字符不相等的字符放入寄存器中，并把計數(shù)器置1。游程編碼數(shù)據(jù)壓縮算法流程圖如圖31：數(shù)據(jù)解碼算法流程如下： 1) 打開壓縮數(shù)據(jù)文件和恢復(fù)文件； 2) 從壓縮文件中循環(huán)讀出字符和該字符連續(xù)的個數(shù), 在恢復(fù)文件中連續(xù)寫入從壓縮文件中讀出的字符, 寫的次數(shù)等于該字符連續(xù)的個數(shù):。游程編碼數(shù)據(jù)解壓縮算法流程圖32 圖31游程編碼數(shù)據(jù)壓縮算法游程圖圖32游程編碼數(shù)據(jù)解碼流程圖 哈夫曼編碼是一種常見的壓縮方法。它的基本原理是按照信號出現(xiàn)概率大小順序排列信源信號，并設(shè)法按逆序分配碼字字長，使編碼的碼字是可辨識的。 要完成哈夫曼的編碼需要首先建立哈夫曼樹，之后對所有字符根據(jù)權(quán)重進行編碼，最后再對文件內(nèi)容進行編碼。 建立哈夫曼樹的思想。首先定義適合哈夫曼樹的節(jié)點類型，需要定義的有當(dāng)前節(jié)點的字符，當(dāng)前節(jié)點的左子、右子和父親指針。在建立哈夫曼樹之前還需要對出現(xiàn)的字符和權(quán)重進行統(tǒng)計和記錄，并且定義一個可以篩選出最小權(quán)重的函數(shù)。 初始化樹節(jié)點之后開始建立哈夫曼樹。先在所有可能出現(xiàn)的字符中篩選出當(dāng)前權(quán)重最小的兩個字符，將這兩個字符分別作為新節(jié)點的左子和右子建立一個小的二叉樹，并將兩個字符的權(quán)重之和賦值給新節(jié)點，將新二叉樹放入篩選字符中，再將篩選過的兩個字符從篩選列表中淘汰掉。依次對列表中剩下的字符進行權(quán)重最小的篩選，直到根節(jié)點（如果編碼表共有N個字符，則2*N1就為最終根節(jié)點）為止，也就是當(dāng)篩選列表為空的時候，哈夫曼樹即建立完成。對于哈夫曼編碼樹來說，由于哈夫曼編碼是前綴碼，所以所有要編碼的字符最終都將是這顆樹的葉子節(jié)點，而其它節(jié)點并沒有真正的字符意義。即當(dāng)哈夫曼編碼樹建立之后，對樹的所有葉子節(jié)點進行打印可知道是否有字符遺漏或多余。 建立哈夫曼樹的流程圖如圖33：圖33構(gòu)建哈夫曼樹流程圖 構(gòu)建完哈夫曼樹后，根據(jù)建立哈夫曼樹建立哈夫曼碼表。建立編碼表時要根據(jù)每個出現(xiàn)的字符的權(quán)重對建立的哈夫曼樹的每個葉子節(jié)點進行編碼。編碼時要從葉子節(jié)點出發(fā)向根節(jié)點進行逆向編碼。判斷如果當(dāng)前節(jié)點為左子則對其編碼‘0’，如果當(dāng)前節(jié)點為右子則對其編碼‘1’。以此類推進行編碼直到根節(jié)點為止。此時的編碼是逆向的，所以需要將碼值逆向存儲。依次對每一個葉子節(jié)點進行編碼操作，即可得到當(dāng)前哈夫曼樹的編碼表。 構(gòu)建哈夫曼編碼表的算法流程圖如圖34： 有了碼表就可以進行編碼了。首先需要建立一個原始文件，在文件中輸入需要編碼的內(nèi)容。之后將文件打開，將其中的內(nèi)容存儲到字符串中以便程序編碼調(diào)用。開始對需要編碼的字符進行編碼，將字符逐一讀取與剛剛建立的編碼表中的每個葉子節(jié)點代表的字符進行比較，找出相同的對象，并將當(dāng)前節(jié)點的編碼打印到屏幕，并將編碼存入到新建的密碼文件當(dāng)中。： 在解碼時先打開密碼文件，將之前編碼后得到的密文內(nèi)容存儲到字符串中以便解碼調(diào)用。開始對密文的字符串進行解碼，樹索引從根節(jié)點開始走，當(dāng)密文中的當(dāng)前字符是‘0’的時候，則索引走向左子節(jié)點；當(dāng)是‘1’的時候，則走向右子節(jié)點。以此類推，一直走到葉子節(jié)點為止，則當(dāng)前葉子節(jié)點所代表的字符即為前一段密文的解碼結(jié)果。再對下一個字符依次從根節(jié)點開始解碼，如此循環(huán)對每一段密文進行解碼直到解碼結(jié)束。將解碼打印到屏幕，并將解碼結(jié)果存入到新的解碼文件當(dāng)中。在解碼之前，還應(yīng)該先確認(rèn)之前是否建立了哈夫曼樹并且是否構(gòu)建了編碼表。不過由于本次將‘a(chǎn)’到‘z’都進行了編碼，所以此步省略了，因為編碼表是唯一的。需要的時候可以在Encoder 函數(shù)中先進行判定。對于二元序列：00011100001111100011111111110000000000000111110000000000000即（3,0）（3,1)（4,0）（5,1）(3,0)(10,1)(13,0)(5,1)(13,0)編碼圖：解碼圖：進行完編碼后的平均碼長為： （31)信息傳輸速率： （32） 壓縮前二元序列長度為49，進行游程編碼后序列長度為36，再進行哈夫曼編碼后序列長度為29。即總的壓縮效率為59%，而游程壓縮效率為80%。所以進行兩次編碼后的壓縮效率比單一一次的游程編碼的壓縮效率高很多。這次的仿真只是對于一段很短的二元序列，而且各游程長度也很短，所以還不能過很好的體現(xiàn)出游程編碼的壓縮效率。但對于二值圖像序列的就能夠很好的體現(xiàn)出游程編碼的壓縮效率，然后在進行哈夫曼編碼就能夠很好的體現(xiàn)出這種方法的壓縮效率。游程編碼是一種簡單的快捷的編碼方法，能夠有效的對二元序列進行無損壓縮，一般情況下，游程長度越大，其概率越小，而且隨著長度的增大逐漸趨向零。對于小概率的碼字，其長度未達到概率匹配或較長，損失不會太大，也就對平均碼字長度影響較小，這樣就可以對長游程不嚴(yán)格按哈夫曼碼步驟進行。哈夫曼碼是用概率匹配方法進行信源編碼。它有兩明顯的個特點：一是哈夫曼編碼方法保證了概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長碼，充分利用了短碼；一是縮減信源的最后兩個碼字總是最后一位不同，從而保證哈夫曼編碼是即時碼。哈夫曼變長碼的效率是相當(dāng)高的，它可以單個信源符號編碼或用L較小的信源序列編碼，對編碼器的設(shè)計來說也簡單的多。但應(yīng)當(dāng)注意要達到很高的效率仍然需要按長序列來計算，這樣才能使平均碼字長度降低。參考文獻 結(jié)論游程編碼是圖像壓縮的基本算法，因此對于二元相關(guān)信源數(shù)據(jù)編碼研究變得尤為重要。為此，本人對游程編碼壓縮原理做了深入的學(xué)習(xí)，并結(jié)合哈夫曼編碼把其應(yīng)用到二元相關(guān)信源數(shù)據(jù)的壓縮。經(jīng)過這段時間的學(xué)習(xí)與實踐，我對二元相關(guān)信源游程編碼與信號編碼的發(fā)展及現(xiàn)狀有了更深刻的認(rèn)識，意識到數(shù)據(jù)壓縮與解壓對于信息時代的巨大影響及其潛在的經(jīng)濟效益，并對Microcsoft Visual C++軟件有了進一步的了解。經(jīng)過這一段的學(xué)習(xí)，我想我對于知識的獵取是有限的，關(guān)鍵是我學(xué)會了如何用認(rèn)真、嚴(yán)謹(jǐn)?shù)膶W(xué)習(xí)態(tài)度去面對工作，如何用自學(xué)的方法來處理問題，如何把書籍和網(wǎng)上查找到的信息運用到實踐中去。二元相關(guān)游程編碼一般不直接應(yīng)用與多灰度圖像，但比較適于二值圖像的編碼，例如傳真圖像的編碼等。為了達到較好的壓縮效果，二值圖像游程編碼需和其它一些編碼混合使用。本文中我才用游程編碼和哈夫曼編碼混合使用。游程壓縮作為數(shù)據(jù)壓縮技術(shù)的一個分支，理論淺顯，走過半個多世紀(jì)的離散余弦變換理論在數(shù)據(jù)壓縮領(lǐng)域至今不衰；近來，小波變換理論更使數(shù)據(jù)壓縮技術(shù)登峰造極，圖像壓縮的JPEG2000標(biāo)準(zhǔn)是小波理論傲視群雄?？梢灶A(yù)見，新的數(shù)學(xué)理論將不斷為數(shù)據(jù)壓縮技術(shù)輸入新鮮血液，因此數(shù)學(xué)理論決不可偏廢。最后，給出一點使用無損壓縮算法的建議。由于每種無損壓縮都有自己的適用范圍，壓縮比受不失真要求的限制，真正意義上高壓縮比的通用無損壓縮算法目前哈有待繼續(xù)研究。因此在選用算法之前需要對圖像數(shù)據(jù)進行分析，使用時根據(jù)數(shù)據(jù)表現(xiàn)出的特點，利用算法的思想，靈活使用算法是提高壓縮比的有效手段。 參考文獻[1]王增輝， [2]許川佩，46（25）[3]劉娟，詹文法，[4]詹文法，梁華國，時峰，黃正峰，[5]彭喜元，[6]于翔。數(shù)據(jù)壓縮技術(shù)分析。[7]祝本明，劉桂華。[8]Michal Stabno，Robert :Bitmap pression technique based on runlength and Huffman [9]Cristiano M. Agulhari, Ivanil S. Bonatti, Pedro . Adaptive Run Length Encoding method for the pression Engineering amp。 [10]馬寧 ,朱福萌 ,尹志軍, [11][12]Bo Ye , QianZhao , DuoZhou , XiaohuaWang , MinLuo .Test data pression using alternating variable runlength code .INTEGRATION, the VLSI journal .2011[13]商進，[14]方建平,郝　躍,劉紅俠,李　 致謝 致謝本設(shè)計的完成是在我們的導(dǎo)師許成謙老師的細心指導(dǎo)下進行的。在每次設(shè)計遇到問題時老師不辭辛苦的講解才使得我的設(shè)計順利的進行。從設(shè)計的選題到資料的搜集直至最后設(shè)計的修改的整個過程中，花費了許老師很多的寶貴時間和精力，在此向?qū)煴硎局孕牡馗兄x！導(dǎo)師嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度，開拓進取的精神和高度的責(zé)任心都將使學(xué)生受益終生！ 還要感謝和我同一設(shè)計小組的幾位同學(xué)，是你們在我平時設(shè)計中和我一起探討問題，并指出我設(shè)計上的誤區(qū)，使我能及時的發(fā)現(xiàn)問題把設(shè)計順利的進行下去，沒有你們的幫助我不可能這樣順利地結(jié)稿，在此表示深深謝意。附錄 附錄1燕 山 大 學(xué)本科畢業(yè)設(shè)計（論文）開題報告課題名稱： 基于游程編碼數(shù)據(jù)壓縮算法設(shè)計與實現(xiàn)學(xué)院（系）： 電子工程系