【正文】 一種改進的游程編碼算法 .西南科技大學學報 . [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ù)壓縮技術分析。 （ 5） 1617周總結畢設，完成論文，準備答辯 。 （ 2） 510周學會運用游程編碼壓縮 /解壓信源數(shù)據(jù)的算法，并計算相應數(shù)據(jù)；準備中期報告 （ 3） 1113周學習并編寫相對應的 c語言程序已達到數(shù)據(jù)壓縮與解壓。 編寫 c 程序來實現(xiàn)游程壓縮以及相應的解壓縮。 設計思路 熟悉游程編碼完成，能夠完成信源數(shù)據(jù)的游程壓縮，然后按照哈 夫曼編碼方法處理數(shù)據(jù)已達到壓縮碼率的目的。將任何 (二元 )序列變換成一一對應的游程長度序列，再按哈夫曼編碼或其他方法處理以達到壓縮碼率的目的 。如果規(guī)定二元序列是以“ 0”開始，第一個游程是“ 0”游程，第二個必為“ 1”游程，第三個又是“ 0”游程等等。它們的長度分別稱為游程長度 L(0)和 L(l)。 選題意義：通過本次的畢業(yè)設計，使我進一步的了解與掌握了游程編碼技術以及相關的壓縮編碼方面的知識，使我在課題的實施過程中學會已有知識的應用，培養(yǎng)自己自主學習和發(fā)現(xiàn)問題、解決問題的能力。 另外，將測試集中的無關位（ don’ tcares ）用特定的方法指定后，這種變游程編碼可以直接對原始測試集操作，因此解碼不需要 CSR，降低了解碼器的硬件開銷。 理論分析和實驗結果證明本方案相對于傳統(tǒng)附錄 37 的游程編碼具有更好的數(shù)據(jù)壓縮效果 [4]。 (2) 交 替 游 程 編 碼 （ Alternative RunLengthEncoding），這種編碼算法既考慮測試數(shù)據(jù)中連續(xù)出現(xiàn)的“ 0”，也考慮連續(xù)出現(xiàn)的“ 1”，可以大大減少長度較短的游程數(shù)量，提高了編碼效率，硬件開銷也小，取得了比較好的效果 [2][3]。在以上編碼方法中，基于游程的編碼壓縮算法的效果是較好的，而且這種壓縮算法的解壓電路是不依賴于測試向量集的，這一點在待測電路重新設計或測試向量集合發(fā)生修改的情況下特別 有用[1]。通過對游程編碼 (Run LengthEncoding,RLE)進行研究 ,最后提出一種實現(xiàn)相對簡單、壓縮效果比較好的算法，采用該算法可以收到比較理想的效果，基本克服由于 RLE 自身特點而引起的數(shù)據(jù)擴張的現(xiàn)象。 附錄 35 附錄 1 燕 山 大 學 本科畢業(yè)設計（論文）開題報告 課題名稱： 基于游程編碼數(shù)據(jù)壓縮算法設計與實現(xiàn) 學院（系）： 電子工程系 年級專業(yè)： 09 通信工程 學生姓名： 李悅 指導教師： 許成謙 完成日期： 2021 年 3 月 27 日 燕山大學本科生畢業(yè)設計（論文） 36 一、 選題的依據(jù)： 飛速發(fā)展的數(shù)據(jù)壓縮和圖像編碼技術，給多媒體數(shù)據(jù)傳輸和數(shù)據(jù)存儲帶來極大的快捷和便利。在每次設計遇到問題時老師不辭辛苦的講解才使得我的設計順利的進行。一種改進的游程編碼算法 .西南科技大學學報 . [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ù)據(jù)進行分析，使用時根據(jù)數(shù)據(jù)表現(xiàn)出的特點，利用算法的思想，靈活使用算法是提高壓縮比的有效手段。 最后，給出一點使用無損壓縮算法的建議。 游程壓縮作為數(shù)據(jù)壓縮技術的一個分支，理論淺顯，走過半個多世紀的離散余弦變換理論在數(shù)據(jù)壓縮領域至今不衰；近來，小波變換理論更使數(shù)據(jù)壓縮技術登峰造極，圖像壓縮的 JPEG2021 標準是小波理論傲視群雄。為了達到較好的壓縮效果，二值圖像游程編 碼需和其它一些編碼混合使用。經(jīng)過這一段的學習，我想我對于知識的獵取是有限的，關鍵是我學會了如何用認真、嚴謹?shù)膶W習態(tài)度去面對工作，如何用自學的方法來處理問題，如何把書籍和網(wǎng)上查找到的信息運用到實踐中去。為此，本人對游程編碼壓縮原理做了深入的學習，并結合哈夫曼編碼把其應用到二元相關信源數(shù)據(jù)的壓縮。但應當注意要達到很高的效率仍然需要按長序列來計算，這樣才能使平均碼字長度降低。它有兩明顯的個特點： 一是哈夫曼編碼方法保證了概率大的符號對應于短碼，概率 小的符號對應于長碼，充分利用了短碼；一是縮減信源的最后兩個碼字總是最后一位不同，從而保證哈夫曼編碼是即時碼。對于小概率的碼字，其長度未達到概率匹配或較長，損失不會太大，也就對平均碼字長度影響較小，這樣就可以對長游程不嚴格按哈夫曼碼步驟進行。但對于 二值圖像序列的就能夠很好的體現(xiàn)出游程編碼的壓縮效率，然后在進行哈夫曼編碼就能夠很好的體現(xiàn)出這種方法的壓縮效率。所以進行兩次編碼后的壓縮效率比單一一次的游程編碼的壓縮效率高很多。 圖 解碼算法流程圖 燕山大學本科生畢業(yè)設計（論文） 28 運行結果 對于二元序列：00011100001111100011111111110000000000000111110000000000000 即（ 3,0）（ 3,1)（ 4,0）（ 5,1） (3,0)(10,1)(13,0)(5,1)(13,0)編碼圖： 解碼圖： 第 3章 游程編碼以及哈弗曼編碼 29 進行完編碼后的平均碼長為： （ 31) 信息傳輸速率： （ 32） 壓縮前二元序列長度為 49，進行游程編碼后序列長度為 36，再進行哈夫曼編碼后序列長度為 29。不過由于本次將‘ a’到‘ z’都進行了編碼，所以此步省略了，因為編碼表是唯一的。將解碼打印到屏幕，并將解碼結果存入到新的解碼文件當中。以此類推，一直走到葉子節(jié)點為止，則當前葉子節(jié)點所代表的字符即為前一段密文的解碼結果。 編碼流程圖如圖 ： 圖 編碼算法流程圖 第 3章 游程編碼以及哈弗曼編碼 27 在解碼時先打開密碼文件，將之前編碼后得到的密文內(nèi)容存儲到 字符串中以便解碼調(diào)用。之后將文件打開，將其中的內(nèi)容存儲到字符串中以便程序編碼調(diào)用。 構建哈夫曼編碼表的算法流程圖如圖 34： 圖 構建哈夫曼編碼表的 算法流程圖 燕山大學本科生畢業(yè)設計（論文） 26 有了碼表就可以進行編碼了。此時的編碼是逆向的，所以需要將碼值逆向存儲。判斷如果當前節(jié)點為左子則對其編碼‘ 0’，如果當前節(jié)點為右子則對其編碼‘ 1’。建立編碼表時要根據(jù)每個出現(xiàn)的字符的權重對建立的哈夫曼樹的每個葉子節(jié)點進行編碼。即當哈夫曼編碼樹建立之后，對樹的所有葉子節(jié)點進行打印可知道是否有字符遺漏或多余。依次對列表中剩下的字符進行權重最小的篩選，直到 根節(jié)點（如果編碼表共有 N 個字符，則 2*N1 就為最終根節(jié)點）為止，也就是當篩選列表為空的時候，哈夫曼樹即建立完成。 初始化樹節(jié)點之后開始建立哈夫曼樹。首先定義適合哈夫曼樹的節(jié)點類型，需要定義的有當前節(jié)點的字符，當前節(jié)點的左子、右子和父親指針。 要完成哈夫曼的編碼需要首先建立哈夫曼樹，之后對所有字符根據(jù)權重進行編碼，最后再對文件內(nèi)容進行編碼。 游程編碼數(shù)據(jù)解壓縮算法流程圖 32 第 3章 游程編碼以及哈弗曼編碼 21 圖 31 游程編碼數(shù)據(jù)壓縮算法游程圖 打 開 源 數(shù) 據(jù) 文 件 與壓 縮 后 的 數(shù) 據(jù) 文 件從 元 數(shù) 據(jù) 文 件 中 讀 取 一 個 字 符將 字 符 放 入 寄 存 器計 數(shù) 器 c o u n t = 1是 否 讀 到 文 件 尾在 源 數(shù) 據(jù) 文 件 中 讀 下 一 個 字 符 讀 取 的 字 符 與 寄 存 器 中 的字 符 是 否 相 等計 數(shù) 器 加 1 c o u n t = c o u n t = 1關 閉 源 數(shù) 據(jù) 文 件 和 壓 縮 文 件將 寄 存 器 字 符 和 計數(shù) 器 中 的 數(shù) 寫 入 數(shù)據(jù) 壓 縮 文 件將 最 后 讀 取 的 字 符放 入 寄 存 器 計 數(shù) 器置 1 c o u n t = 1Y e sN oY e s燕山大學本科生畢業(yè)設計（論文） 22 圖 32 游程編碼數(shù)據(jù)解碼流程圖 打 開 源 數(shù) 據(jù) 文 件 與 恢 復 后 的 數(shù)據(jù) 文 件判 斷 是 否 為 文 件 尾從 壓 縮 文 件 中 讀 取 字 符 以及 該 字 符 的 連 續(xù) 的 個 數(shù)讀 取 的 字 符 及 連 續(xù) 個 數(shù) 是 否 寫 完在 恢 復 文 件 中 寫 入 從 壓 縮 文件 中 讀 取 的 字 符關 閉 恢 復 數(shù) 據(jù) 文 件 和 數(shù) 據(jù) 壓縮 文 件Y e sN oN oY e s第 3章 游程編碼以及哈弗曼編碼 23 哈夫曼編碼過程 哈夫曼編碼是一種常見的壓縮方法。如果相等，則計數(shù)器加 1，否則，把寄存器中的字符和計數(shù)器中數(shù)寫入壓縮數(shù)據(jù)文件中，然后再把寄存器中字符不相等的字符放入寄存器中，并把計數(shù)器置 1。這種壓縮數(shù)據(jù)的方法 , 連續(xù)相同的字符及出現(xiàn)連續(xù)相同的次數(shù)越多，壓縮比就越大，反之，壓縮比就越小。兩者綜合即實現(xiàn)對于二元序列的游程編碼。而對二元序 列游程編碼主要是針對于每個游程長度以及總共有多少個游程。 燕山大學本科生畢業(yè)設計（論文） 20 第 3 章 游程編碼以及哈夫曼編 游程編碼 游程編碼是針對于二元序列的壓縮編碼方法，在二元序列中，只有兩種符號，即“ 0”游程和“ 1”游程，“ 0”游程和“ l”游程總是交替出現(xiàn)的。 下面給出一個 CPRL 碼的編碼實例：（參變量 M=1） 編碼前的初始測試數(shù)據(jù)： 0000001 0000001 0000111 0010111 1010010； 對應的差分測試數(shù)據(jù)： 0000001 0000000 0000110 0010000 1000101（ 35 位）； 差分后的測試數(shù)據(jù)對應的