【正文】 以達到壓縮碼率的目的 。如果規(guī)定二元序列是以“0”開始，第一個游程是“0”游程，第二個必為“1”游程，第三個又是“0”游程等等。它們的長度分別稱為游程長度L(0)和L(l)。選題意義：通過本次的畢業(yè)設(shè)計，使我進一步的了解與掌握了游程編碼技術(shù)以及相關(guān)的壓縮編碼方面的知識，使我在課題的實施過程中學會已有知識的應(yīng)用，培養(yǎng)自己自主學習和發(fā)現(xiàn)問題、解決問題的能力。 另外，將測試集中的無關(guān)位（don’tcares ）用特定的方法指定后，這種變游程編碼可以直接對原始測試集操作，因此解碼不需要CSR，降低了解碼器的硬件開銷。 理論分析和實驗結(jié)果證明本方案相對于傳統(tǒng)的游程編碼具有更好的數(shù)據(jù)壓縮效果[4]。(2)交替游程編碼（Alternative RunLengthEncoding），這種編碼算法既考慮測試數(shù)據(jù)中連續(xù)出現(xiàn)的“0”，也考慮連續(xù)出現(xiàn)的“1”，可以大大減少長度較短的游程數(shù)量，提高了編碼效率，硬件開銷也小，取得了比較好的效果[2][3]。在以上編碼方法中，基于游程的編碼壓縮算法的效果是較好的，而且這種壓縮算法的解壓電路是不依賴于測試向量集的，這一點在待測電路重新設(shè)計或測試向量集合發(fā)生修改的情況下特別有用[1]。通過對游程編碼(Run LengthEncoding,RLE)進行研究,最后提出一種實現(xiàn)相對簡單、壓縮效果比較好的算法，采用該算法可以收到比較理想的效果，基本克服由于RLE自身特點而引起的數(shù)據(jù)擴張的現(xiàn)象。附錄 附錄1燕 山 大 學本科畢業(yè)設(shè)計（論文）開題報告課題名稱： 基于游程編碼數(shù)據(jù)壓縮算法設(shè)計與實現(xiàn)學院（系）： 電子工程系 年級專業(yè)： 09通信工程 學生姓名： 李悅 指導教師： 許成謙 完成日期： 2013年3月27日 選題的依據(jù)： 飛速發(fā)展的數(shù)據(jù)壓縮和圖像編碼技術(shù)，給多媒體數(shù)據(jù)傳輸和數(shù)據(jù)存儲帶來極大的快捷和便利。在每次設(shè)計遇到問題時老師不辭辛苦的講解才使得我的設(shè)計順利的進行。[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。數(shù)據(jù)壓縮技術(shù)分析。因此在選用算法之前需要對圖像數(shù)據(jù)進行分析，使用時根據(jù)數(shù)據(jù)表現(xiàn)出的特點，利用算法的思想，靈活使用算法是提高壓縮比的有效手段。最后，給出一點使用無損壓縮算法的建議。游程壓縮作為數(shù)據(jù)壓縮技術(shù)的一個分支，理論淺顯，走過半個多世紀的離散余弦變換理論在數(shù)據(jù)壓縮領(lǐng)域至今不衰；近來，小波變換理論更使數(shù)據(jù)壓縮技術(shù)登峰造極，圖像壓縮的JPEG2000標準是小波理論傲視群雄。為了達到較好的壓縮效果，二值圖像游程編碼需和其它一些編碼混合使用。經(jīng)過這一段的學習，我想我對于知識的獵取是有限的，關(guān)鍵是我學會了如何用認真、嚴謹?shù)膶W習態(tài)度去面對工作，如何用自學的方法來處理問題，如何把書籍和網(wǎng)上查找到的信息運用到實踐中去。為此，本人對游程編碼壓縮原理做了深入的學習，并結(jié)合哈夫曼編碼把其應(yīng)用到二元相關(guān)信源數(shù)據(jù)的壓縮。但應(yīng)當注意要達到很高的效率仍然需要按長序列來計算，這樣才能使平均碼字長度降低。它有兩明顯的個特點：一是哈夫曼編碼方法保證了概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長碼，充分利用了短碼；一是縮減信源的最后兩個碼字總是最后一位不同，從而保證哈夫曼編碼是即時碼。對于小概率的碼字，其長度未達到概率匹配或較長，損失不會太大，也就對平均碼字長度影響較小，這樣就可以對長游程不嚴格按哈夫曼碼步驟進行。但對于二值圖像序列的就能夠很好的體現(xiàn)出游程編碼的壓縮效率，然后在進行哈夫曼編碼就能夠很好的體現(xiàn)出這種方法的壓縮效率。所以進行兩次編碼后的壓縮效率比單一一次的游程編碼的壓縮效率高很多。對于二元序列：00011100001111100011111111110000000000000111110000000000000即（3,0）（3,1)（4,0）（5,1）(3,0)(10,1)(13,0)(5,1)(13,0)編碼圖：解碼圖：進行完編碼后的平均碼長為： （31)信息傳輸速率： （32） 壓縮前二元序列長度為49，進行游程編碼后序列長度為36，再進行哈夫曼編碼后序列長度為29。不過由于本次將‘a(chǎn)’到‘z’都進行了編碼，所以此步省略了，因為編碼表是唯一的。將解碼打印到屏幕，并將解碼結(jié)果存入到新的解碼文件當中。以此類推，一直走到葉子節(jié)點為止，則當前葉子節(jié)點所代表的字符即為前一段密文的解碼結(jié)果。： 在解碼時先打開密碼文件，將之前編碼后得到的密文內(nèi)容存儲到字符串中以便解碼調(diào)用。之后將文件打開，將其中的內(nèi)容存儲到字符串中以便程序編碼調(diào)用。 構(gòu)建哈夫曼編碼表的算法流程圖如圖34： 有了碼表就可以進行編碼了。此時的編碼是逆向的，所以需要將碼值逆向存儲。判斷如果當前節(jié)點為左子則對其編碼‘0’，如果當前節(jié)點為右子則對其編碼‘1’。建立編碼表時要根據(jù)每個出現(xiàn)的字符的權(quán)重對建立的哈夫曼樹的每個葉子節(jié)點進行編碼。即當哈夫曼編碼樹建立之后，對樹的所有葉子節(jié)點進行打印可知道是否有字符遺漏或多余。依次對列表中剩下的字符進行權(quán)重最小的篩選，直到根節(jié)點（如果編碼表共有N個字符，則2*N1就為最終根節(jié)點）為止，也就是當篩選列表為空的時候，哈夫曼樹即建立完成。 初始化樹節(jié)點之后開始建立哈夫曼樹。首先定義適合哈夫曼樹的節(jié)點類型，需要定義的有當前節(jié)點的字符，當前節(jié)點的左子、右子和父親指針。 要完成哈夫曼的編碼需要首先建立哈夫曼樹，之后對所有字符根據(jù)權(quán)重進行編碼，最后再對文件內(nèi)容進行編碼。游程編碼數(shù)據(jù)解壓縮算法流程圖32 圖31游程編碼數(shù)據(jù)壓縮算法游程圖圖32游程編碼數(shù)據(jù)解碼流程圖 哈夫曼編碼是一種常見的壓縮方法。如果相等，則計數(shù)器加1，否則，把寄存器中的字符和計數(shù)器中數(shù)寫入壓縮數(shù)據(jù)文件中，然后再把寄存器中字符不相等的字符放入寄存器中，并把計數(shù)器置1。這種壓縮數(shù)據(jù)的方法, 連續(xù)相同的字符及出現(xiàn)連續(xù)相同的次數(shù)越多，壓縮比就越大，反之，壓縮比就越小。兩者綜合即實現(xiàn)對于二元序列的游程編碼。而對二元序列游程編碼主要是針對于每個游程長度以及總共有多少個游程。73 第3章 游程編碼以及哈弗曼編碼 第3章 游程編碼以及哈夫曼編 游程編碼 游程編碼是針對于二元序列的壓縮編碼方法，在二元序列中，只有兩種符號，即“0”游程和“1”游程，“0”游程和“l(fā)”游程總是交替出現(xiàn)的。下面給出一個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 位）。但對于具體的編碼，M 是事先確定好的常數(shù)，顯然M 的取值范圍在1 和最大組號之間。該編碼方案為了增加0 游程的長度，對填充后的測試數(shù)據(jù)采取了差分處理，即把測試數(shù)據(jù)等長劃分并進行異或邏輯運算。如果相鄰游程的長度在同一組內(nèi)，則同組的后面的相鄰游程的前綴可以省略，則編碼后碼字的前綴越長，則壓縮效果越明顯。例如數(shù)據(jù)串00000000000x 000000000001，其中的x 是無關(guān)位，如果把它填充為0則該數(shù)據(jù)串是一個長度為23 的0 游程，由編碼碼表可知其對應(yīng)的碼字為11101011（8 位）；如果把無關(guān)位賦值為1，則數(shù)據(jù)串變成了兩個長度都為11的相鄰0 游程，其對應(yīng)的碼字為110111 0（7 位），使碼字的長度減少了1 位，提高了數(shù)據(jù)壓縮效果。顯然相鄰相同游程的長度越長，測試數(shù)據(jù)壓縮率就越高。對共游程碼編碼方案，如果有若干相鄰游程相同，則后面的一個或多個相同游程都可以用唯一的標志位來代替，從而大大減少了編碼碼字的長度，即進一步提高了測試數(shù)據(jù)壓縮率。共游程碼（Sharing Run Length Code，SRLC）與共前綴碼的編碼方案類似，該方案注意到初始測試數(shù)據(jù)中有的相鄰游程是相同的，于是就用一個標志位來表示后面的相同游程，所以該方案被稱為共游程碼?？梢姅?shù)據(jù)串00000000000001 和0000000000000001 的游程長度分別為13 和15，都在第三組，前綴都為1110，所以后一游程的碼字前綴用標志位0 表示，其碼字為0 0011。 共前綴碼的前綴都是以1 開始，以0 結(jié)束的數(shù)字串，所以當相鄰游程長度在同一組時，可以用數(shù)字0 來表示后面游程的碼字前綴，后綴則不變，這樣碼字的長度進一步縮短。所謂無關(guān)位是指無論它們的取值是0 還是1 都不會影響測試結(jié)果。如果相鄰游程的長度在同一組，則它們對應(yīng)碼字的前綴是相同的即共前綴，可以用一個標志位來表示這些相鄰游程除第一個游程以外的其他游程的前綴，這樣數(shù)據(jù)壓縮率得以進一步提高。再按哈夫曼編碼或其他方法處理以達到壓縮碼率的目的。 一般情況下游程長度越長，其概率越小，這在以前的計算中也可以看見，而且將隨著長度的增大漸進向零。 游程編碼仍是變長碼，有其固有的缺點，及需要大量的緩沖和優(yōu)質(zhì)的信道。對于隨機的二元序列，各游程長度將是隨機變量，其取值可為1，2，3，…，直到無限?！?”游程和“l(fā)”游程總是交替出現(xiàn)的。 在二元序列中，只有兩種符號，即“0”和“1”，這些符號可連續(xù)出現(xiàn)，連“0”這一段稱為“0”游程，連“1”這一段稱為“1”游程。 游程編碼的基本原理是：用一個符號值或串長代替具有相同值的連續(xù)符號（連續(xù)符號構(gòu)成了一段連續(xù)的“游程”，游程編碼因此而得名），使符號長度少于原始數(shù)據(jù)的長度。 游程長度RL(RunLength)，簡稱游程或游長，指的是由字符(或信號取樣值)構(gòu)成的數(shù)據(jù)流中各個字符重復(fù)出現(xiàn)而形成的字符的長度。它們的父節(jié)點小于其他節(jié)點的父節(jié)點，它們又小于其他所有節(jié)點，只要前一步符合最優(yōu)二叉樹的第二個條件，到這一步仍將符合。符合我們前面說的最優(yōu)二叉樹的第一個條件。然后往前步進，節(jié)點序列中不斷地減少一個節(jié)點，增加兩個節(jié)點，在步進過程中將始終保持是一棵最優(yōu)二叉樹，這是因為:按照哈弗曼樹的建立過程，新增的兩個節(jié)點是當前節(jié)點序列中最小的兩個，其他的任何兩個節(jié)點的父節(jié)點都大于（或等于）這兩個節(jié)點的父節(jié)點，只要前一步是最優(yōu)二叉樹，其他的任何兩個節(jié)點的父節(jié)點就一定都處在它們的父節(jié)點的上層或同層，所以這兩個節(jié)點一定處在當前二叉樹的最低一層。這時一棵最優(yōu)二叉樹就已經(jīng)建成了，它的根就是剩下的這個節(jié)點。然后從節(jié)點序列中去除這兩個節(jié)點，加入它們的父節(jié)點到序列中。 上面這個例子是比較簡單的，實際的文件中，一個字節(jié)有256種可能的取值，所以二叉樹的葉子節(jié)點多達256個，最終的樹形可能非常復(fù)雜，但有一種非常精巧的算法可以快速地建起一棵最優(yōu)二叉樹，（戴?哈夫曼）提出，下面我們先來介紹哈弗曼算法的步驟，然后再來證明通過這么簡單的步驟得出的樹形確實是一棵最優(yōu)二叉樹。 我們知道普通的編碼都是定長的，比如常用的ASCII編碼,每個字符都是8個bit:字符編碼A00101001B00101010C00101011......這樣，計算機就能很方便的把由0和1組成的數(shù)據(jù)流解析成原始信息，但我們知道，在很多情況下，數(shù)據(jù)文件中的字符出現(xiàn)的概率是不均勻的，比如在一篇英語文章中，字母“E”出現(xiàn)的頻率最高，“Z”最低，如果我們使用不定長的bit編碼，頻率高的字母用比較短的編碼表示，頻率低的字母用長的編碼表示，豈不是可以大大縮小文件的空間嗎? 但這就要求編碼要符合“前綴編碼”的要求，即較短的編碼不能是任何較長的編碼的前綴，這樣解析的時候才不會混淆，比如下面的編碼方法就符合前綴原則：字符編碼A0B10C110D1110E11110......根據(jù)這個碼表，下面一段數(shù)據(jù)就可以唯一解析成原始信息了： 111001010111011011110