【正文】 中的各個(gè)符號(hào)盡可能地相互獨(dú)立，即解除相關(guān)性；使編碼中各個(gè)符號(hào)出現(xiàn)的概率盡可能地相等，即概率均勻化。許多圖形和視頻文件，如 BMP， .TIF及 .AVI 等，都采用了這種壓縮方法，尤其適用于文本 (文件 )數(shù)據(jù)壓縮，它主要是去除文本中的冗余字符或字節(jié)中的冗余位以達(dá)到減少數(shù)據(jù)文件所占的存儲(chǔ)空間的目的 [6]。 游程編碼即需大量的緩沖和優(yōu)質(zhì)信道，所以對(duì)數(shù)據(jù)游程編碼后在進(jìn)一步的進(jìn)行哈夫曼編碼已達(dá)到更完善的數(shù)據(jù)壓縮。多媒體計(jì)算機(jī)系統(tǒng)面臨的是數(shù)值、文字、語言、音樂、圖形、動(dòng)畫、靜圖像、電視視頻圖像等多種媒體承載的由模擬量轉(zhuǎn)化成數(shù)字量信息的吞吐、存儲(chǔ)和傳輸?shù)膯栴}。所以通過對(duì)于游程編碼的研究能夠比較快捷語簡(jiǎn)單的實(shí)現(xiàn)對(duì)于數(shù)據(jù)的無損壓縮。 編碼的作用： 信源編碼的作用之一是設(shè)法減少碼元數(shù)目和降低碼元速率，即通常所說的數(shù)據(jù)壓縮：作用之二是將信源的模擬信號(hào)轉(zhuǎn)化成數(shù)字信號(hào)，以實(shí)現(xiàn)模擬信號(hào)的數(shù)字化傳輸。 費(fèi)諾編碼步驟： （ 1） 將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列： nppp ??? ?21 。 哈夫曼編碼是用概率匹配方法進(jìn)行信源編碼。 這樣一步步逆推下去，在這個(gè)過程中哈弗曼樹每 一步都始終保持著是一棵最優(yōu)二叉樹。 幾種基于游程相關(guān)性的數(shù)據(jù)壓縮方案 1）共前綴碼 共前綴碼編碼時(shí)也是按照一定規(guī)律用盡量短的碼字來表示游程形式的初始測(cè)試數(shù)據(jù)，但該編碼壓縮方案進(jìn)一步考慮了相鄰游程之間存在的聯(lián)系。 燕山大學(xué)本科生畢業(yè)設(shè)計(jì)（論文） 18 3）共前綴連續(xù)長(zhǎng)度碼 共前綴連續(xù)長(zhǎng)度碼（ Co Prefixal Run Length codes， CPRL）也考慮了相鄰游程的相關(guān)性。 數(shù)據(jù)壓縮算法流程如下： 1) 打開源數(shù)據(jù)文件和壓縮后的數(shù)據(jù)文 件； 2) 從源數(shù)據(jù)文件中讀取字符 , 并把它放入一個(gè)寄存器中，然后再循環(huán)讀取后面的字符，并與寄存器中的字符相比較。編碼時(shí)要從葉子節(jié)點(diǎn)出發(fā)向根節(jié)點(diǎn)進(jìn)行逆向編碼。需要的時(shí)候可以在 Encoder 函數(shù)中先進(jìn)行判定。 二元相關(guān)游程編碼一般不直接應(yīng)用與多灰度圖像，但比較適于二值圖像的編碼，例如傳真圖像的編碼等。但在某些數(shù)據(jù)安全性要求比較苛刻的領(lǐng)域，現(xiàn)在比較流行和壓縮效果好的壓縮算法幾乎都屬于有損范疇，對(duì)原始數(shù)據(jù)壓縮處理后有不同程度的損傷，無法完全恢復(fù)，以至于不能滿足技術(shù)要求，現(xiàn)有的無損壓縮方法，如 Huffman、 LZ 系列、算術(shù)編碼等壓縮方法盡管在某些方面各有優(yōu)點(diǎn)，但壓縮效果比較差 或者算法實(shí)現(xiàn)比較困難，因此十分有必要對(duì)無損壓縮算法進(jìn)行研究。對(duì)于隨機(jī)的二元序列，各游程長(zhǎng)度將是隨機(jī)變量，其取值可為 1， 2， 3，?，直到無限。 青海大學(xué)學(xué)報(bào) . [7]祝本明，劉桂華。 二、 主要的研究?jī)?nèi)容、研究思路： 設(shè)計(jì)內(nèi)容 游程編碼是一種是一種相對(duì)比較簡(jiǎn)單而且比較容易實(shí)現(xiàn)的無損壓縮編碼，在二元序列中，只有兩種符號(hào)，即“ 0”和“ 1”，這些符號(hào)可連續(xù)出現(xiàn)，連“ 0”這一段稱為“ 0”游程，連“ 1”這 一段稱為“ 1”游程。 [10]馬寧 ,朱福萌 ,尹志軍 , 蔣林輝 .改進(jìn)游程編碼在天氣雷達(dá)數(shù)據(jù)壓縮中的應(yīng)用 .解放軍理工大學(xué)學(xué)報(bào) .2021 [11]譚紅 .一種基于游程編碼的顯存壓縮算法 .電子工程師 . [12]Bo Ye , QianZhao , DuoZhou , XiaohuaWang , MinLuo .Test data pression using alternating variable runlength code .INTEGRATION, the VLSI journal .2021 [13]商進(jìn)，張禮勇 .一種雙游程編碼的測(cè)試數(shù)據(jù)壓縮方案 .哈爾濱理工大學(xué)學(xué)報(bào) . 參考文獻(xiàn) 33 [14]方建平 ,郝 躍 ,劉紅俠 ,李 康 .應(yīng)用混合游程編碼的 SOC 測(cè)試數(shù)據(jù)壓縮方法 .電子學(xué)報(bào) . 燕山大學(xué)本科生畢業(yè)設(shè)計(jì)（論文） 34 致謝 本設(shè)計(jì)的完成是在我們的導(dǎo)師 許成謙 老師的細(xì)心指導(dǎo)下進(jìn)行的。 參考文獻(xiàn) 31 結(jié)論 游程編碼是圖像壓縮的基本算法，因此對(duì)于二元相關(guān)信源數(shù)據(jù)編碼研究變得尤為重要。再對(duì)下一個(gè)字符依次從根節(jié)點(diǎn)開始解碼，如此循環(huán)對(duì)每一段密文進(jìn)行解碼直到解碼結(jié)束。 對(duì)于哈夫曼編碼樹來說，由于哈夫曼編碼是前綴碼，所以所有要編碼的字符最終都將是這顆樹的葉子節(jié)點(diǎn)，而其它節(jié)點(diǎn)并沒有真正的字符意義。我在 c語言編碼過程中主要針對(duì)這兩方面進(jìn)行編碼，即通過對(duì)“ 0”、“ 1”的變換次數(shù)來確定二元序列中總共有多少個(gè)游程；然后在確定每一個(gè)游程中游程的長(zhǎng)度。 共游程碼的前綴都是以“ 1”開頭以“ 0”結(jié)尾的數(shù)字串，沒有以“ 0”開頭的前綴，所以可以用數(shù)字 0 來作為相鄰相同游程的標(biāo)志位，即后面相鄰相同游程的碼字只有 1 位。此外，編程長(zhǎng)度可以從一直到無限，這在碼字的選擇和碼表的建立方面都有困難，實(shí)際應(yīng)用是尚需采用某些措施來改進(jìn)。 這兩個(gè)新增的節(jié)點(diǎn)是最小的，所以無法和其他上層節(jié)點(diǎn)對(duì)換。 （ 4） 將形成的二叉樹的左節(jié)點(diǎn)標(biāo) 0，右節(jié)點(diǎn)標(biāo) 1。編碼步驟如下： 1）將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列 p（ x1）≥ p（ x2）≥?≥ p（ xn） （ 22） 2）確定滿足下列不等式整數(shù)碼長(zhǎng) Ki： log2p(xi)≤ Ki＜ log2p(xi)+1 （ 23） 3)為了編成唯一可譯碼，計(jì)算第 i個(gè)消息的累加概率 Pi=???11ikp(xk) （ 24） 4)將累加概率 Pi變成二進(jìn)制數(shù)。 信源編碼的理論基礎(chǔ) 信源編碼就是從信源符號(hào)到碼符號(hào)的一種映射 f，它把信源輸出的符號(hào)ui 變換成碼元序列 wi。通過對(duì)游程編碼 (Run LengthEncoding,RLE)進(jìn)行研究 ,結(jié)合哈夫曼編碼。包括游程數(shù)據(jù)壓縮、解壓縮過程，并給出了流程圖 ；哈夫曼數(shù)據(jù)壓縮、解壓縮過程，并給出流程圖和結(jié)果圖。 關(guān)鍵詞 游程編碼 哈夫曼編碼 壓縮 Abstract II Abstract This graduation design is mainly based on runlength coding data pression algorithm design and implementation of runlength coding is very simple, encoding and decoding speed, wide application. Runlength coding is a coding method for binary sequence, is a kind of coding method for binary image, the black and white pixels of continuous (run) in different code code word. Runlength coding is a kind of simple nondestructive data pression method, the advantage is that of pression and depression are very fast. Its method is to calculate a continuous length of data pression, the downside is to not repeat data instead of increasing capacity. Runlength coding is need a lot of buffer and channel, so the data after the runlength coding in further Huffman encoding has reached more . Source coding is mainly introduced in this paper the classification, the optimal method of coding, Huffman tree, construction methods, and the runlength coding principle and implementation technology, the length of the runlength encoding technology is done more prehensive research. Including the runlength data pression and depression process, and gives the flow chart。 最后 找到 一種實(shí)現(xiàn)相對(duì)簡(jiǎn)單、壓縮效果比較好的 方 法， 即對(duì)游程編碼后的數(shù)據(jù)在進(jìn)一步的進(jìn)行哈夫曼編碼， 采用該 方 法可以收到比較理想的效果。 信源編碼定義如圖 21： 信 源 編 碼 器U { u 1 ， u 2 ? u l }W { w 1 , w 2 ? w k }X { x 1 ， x 2 ? x r } 圖 21信源編碼定義圖 燕山大學(xué)本科生畢業(yè)設(shè)計(jì)（論文） 4 信源編碼理論是信息論的一個(gè)重要分支 ,其理論基礎(chǔ)是信源編碼 的兩個(gè)定理。 5)取 Pi二進(jìn)制數(shù)的小數(shù)點(diǎn)后 Ki位即為該消息符號(hào)的二進(jìn)制碼字。把從最上面的根節(jié)點(diǎn)到最下面的葉子節(jié)點(diǎn)途中遇到的 0， 1序列串起來，就得到了各個(gè)符號(hào)的編碼。符合我們前面第 2章 信源編碼分類 15 說的最優(yōu)二叉樹的第一個(gè)條件。 一般情況下游程長(zhǎng)度越長(zhǎng)，其概率越小，這在以前的計(jì)算中也可以看見，而且將隨著長(zhǎng)度的增大漸進(jìn)向零。顯然相鄰相同游程的長(zhǎng)度越長(zhǎng)，測(cè)試數(shù)據(jù)壓縮率就越高。兩者綜合即實(shí)現(xiàn)對(duì)于二元序列的游程編碼。即當(dāng)哈夫曼編碼樹建立之后，對(duì)樹的所有葉子節(jié)點(diǎn)進(jìn)行打印可知道是否有字符遺漏或多余。將解碼打印到屏幕，并將解碼結(jié)果存入到新的解碼文件當(dāng)中。為此，本人對(duì)游程編碼壓縮原理做了深入的學(xué)習(xí)，并結(jié)合哈夫曼編碼把其應(yīng)用到二元相關(guān)信源數(shù)據(jù)的壓縮。在每次設(shè)計(jì)遇到問題時(shí)老師不辭辛苦的講解才使得我的設(shè)計(jì)順利的進(jìn)行。它們的長(zhǎng)度分別稱為游程長(zhǎng)度 L(0)和 L(l)。一種改進(jìn)的游程編碼算法 .西南科技大學(xué)學(xué)報(bào) . [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。如果規(guī)定二元序列是以“ 0”開始，第一個(gè)游程是“ 0”游程，第二個(gè)必為“ 1”游程，第三個(gè)又是“ 0”游程等等。 附錄 35 附錄 1 燕 山 大 學(xué) 本科畢業(yè)設(shè)計(jì)（論文）開題報(bào)告 課題名稱： 基于游程編碼數(shù)據(jù)壓縮算法設(shè)計(jì)與實(shí)現(xiàn) 學(xué)院（系）： 電子工程系 年級(jí)專業(yè)： 09 通信工程 學(xué)生姓名： 李悅 指導(dǎo)教師： 許成謙 完成日期： 2021 年 3 月 27 日 燕山大學(xué)本科生畢業(yè)設(shè)計(jì)（論文） 36 一、 選題的依據(jù)： 飛速發(fā)展的數(shù)據(jù)壓縮和圖像編碼技術(shù)，給多媒體數(shù)據(jù)傳輸和數(shù)據(jù)存儲(chǔ)帶來極大的快捷和便利。經(jīng)過這一段的學(xué)習(xí)，我想我對(duì)于知識(shí)的獵取是有限的，關(guān)鍵是我學(xué)會(huì)了如何用認(rèn)真、嚴(yán)謹(jǐn)?shù)膶W(xué)習(xí)態(tài)度去面對(duì)工作，如何用自學(xué)的方法來處理問題，如何把書籍和網(wǎng)上查找到的信息運(yùn)用到實(shí)踐中去。不過由于本次