【正文】 的相關(guān)性,對(duì)于連續(xù)的兩個(gè)或多個(gè)相同游程,后續(xù)每個(gè)游程僅用一位就可以表示?！?”游程和“l(fā)”游程總是交替出現(xiàn)的。 畢業(yè)設(shè)計(jì)工作進(jìn)度安排（1）14周熟悉課題，查閱、搜集相關(guān)資料，并認(rèn)真學(xué)習(xí)研究并撰寫開題報(bào)告。 [10]馬寧 ,朱福萌 ,尹志軍, [11][12]Bo Ye , QianZhao , DuoZhou , XiaohuaWang , MinLuo .Test data pression using alternating variable runlength code .INTEGRATION, the VLSI journal .2011[13]商進(jìn)，[14]方建平,郝　躍,劉紅俠,李　 附錄2燕 山 大 學(xué)本科畢業(yè)設(shè)計(jì)（論文）文獻(xiàn)綜述 課題名稱：基于游程編碼數(shù)據(jù)壓縮算法設(shè)計(jì)與實(shí)現(xiàn)學(xué)院（系）：電子工程系 年級(jí)專業(yè)：09通信工程 學(xué)生姓名：李悅 指導(dǎo)教師：許成謙 完成日期：2013年3月20日 　 一、課題國內(nèi)外現(xiàn)狀數(shù)據(jù)壓縮技術(shù)主要采用兩種方法：一種是“保真率”較高的無損壓縮法；另一種是以損失信息細(xì)節(jié)而換取較高壓縮比的有損壓縮法。（4）變游程編碼，這種編碼算法既考慮測試數(shù)據(jù)中連續(xù)出現(xiàn)的“0 ”，也考慮連續(xù)出現(xiàn)的“1 ”，大大減小了長度較短游程的數(shù)量，提高了編碼效率[5]。五、主要參考文獻(xiàn) [1]王增輝， [2]許川佩，46（25）[3]劉娟，詹文法，[4]詹文法，梁華國，時(shí)峰，黃正峰，[5]彭喜元，[6]于翔。 在對(duì)圖像數(shù)據(jù)進(jìn)行編碼時(shí)，沿一定方向排列的具有相同灰度值的像素可看成是連續(xù)符號(hào)，用字串代替這些連續(xù)符號(hào)，可大幅度減少數(shù)據(jù)量。如何運(yùn)用c語言進(jìn)行游程編碼解決方法：先記錄二元序列中游程個(gè)數(shù)，然后確定每個(gè)游程長度，最后兩者結(jié)合求出結(jié)果及游程編碼結(jié)果，在求出每個(gè)游程在二元序列中所占百分比，以便于之后的哈夫曼編碼。 實(shí)驗(yàn)中討論本文表明：（1），RLH壓縮位圖小于相應(yīng)議員壓縮的位圖，而不管該索引的屬性的基數(shù)，（2）RLHN壓縮位圖是小于相應(yīng)的華壓縮位圖一定范圍內(nèi)的基數(shù)，該索引的屬性，（3）RLH和RLHN壓縮位圖，提供更短的查詢響應(yīng)時(shí)間比華壓縮位圖，對(duì)于某些索引屬性的基數(shù)范圍，以及（4）RLHN確保更短的更新時(shí)間的壓縮比RLH位圖。 每個(gè)位被映射到一個(gè)排在索引表。索引屬性的值是被分割成范圍。在 [5]中 ，提出了另一種形式的分箱 。 作為一個(gè)因此，編碼值表中的格式為 n位圖。位相同的位值（無論是39。）的一個(gè)實(shí)例的值（例如，39。 否則，壓縮比為惡化。39。 的矩陣表示中以壓縮格式所謂的 近似位圖 （AB）。 AB。39。在 RIDBit，密集位圖存儲(chǔ)在B樹的葉子。 埃利亞斯克編碼正整數(shù) x由一個(gè)一元部分和二進(jìn)制的一部分。開發(fā)的壓縮技術(shù)的倒立文件，壓縮整數(shù)，可能代表增量（不同分配辦法）之間的值的序列。 第3節(jié)提出RLH和RLHN壓縮技術(shù)。39。RLH和RLHN壓縮技術(shù)實(shí)施和華實(shí)驗(yàn)比較。 第3節(jié)提出RLH和RLHN壓縮技術(shù)。 在該位圖中，位編號(hào)n設(shè)置為“1”，如果A的第n行的價(jià)值 等于 V。 位設(shè)置為0，因?yàn)榈膶傩?性的第一行中的值是不是一個(gè)女性 如前所述，華和BBC壓縮SION技術(shù)都是基于運(yùn)行長度編碼。39。 填充代表一系列的比特組成的字相同的值。 位圖的COM壓制是由5456位組成的，如圖中 所示。 組2175是同質(zhì)（39。 作為結(jié)果合并組，三最終組被創(chuàng)建，如圖中 所示。 本組包括174了31位。 2 。說明的WAH壓縮的總體思路一個(gè)例子。 接著，詞語被分組為所謂的運(yùn)行。39。 例如，第一位圖描述值 39。 該每個(gè)位圖中的位的數(shù)目的數(shù)目等于行 存儲(chǔ)了表 T中 。本文的結(jié)構(gòu)如下。 為了更好地支持位圖更新中，我們提出的一個(gè)變種的RLH壓縮的技術(shù)，稱為RLHN。 然而，它不同于英國廣播公司（BBC）和華就以下。本文的結(jié)構(gòu)如下。 它是用于壓縮文件號(hào)碼。在 [13,39]的作者提出了一種倒排索引列表中出現(xiàn)的壓縮技術(shù)項(xiàng)t為代表的數(shù)據(jù)文件中塊差距（整數(shù)），而不是塊編號(hào)。 高級(jí)研究實(shí)現(xiàn)位圖索引表示由 FastBit [24,15,19]RIDBit [15] 。39。 139。 AE是基于Bloom過濾器。39。 。 139。英國廣播公司（BBC）和華是基于所謂的 運(yùn)行長度編碼。 第二種方法是基于所謂的 位切片指數(shù) [4,17,37] 。 這樣的技術(shù)減少存儲(chǔ)空間的高屬性基數(shù)。 相關(guān)工作為了提高數(shù)據(jù)訪問的效率支持位圖索引定義屬性高基數(shù)，以下兩種方法在研究文獻(xiàn)中已被提出，即：（1）擴(kuò)展的基本的位圖索引的結(jié)構(gòu)（2）位圖索引的壓縮技術(shù)。位圖索引 [14,17]的基本數(shù)據(jù)之一衍生權(quán)證查詢優(yōu)化結(jié)構(gòu)。 RLHN的N位字壓縮位圖被分成RLH。 5) 記錄下概率為1處到當(dāng)前信號(hào)源符號(hào)之間的0，l序列，從而得到每個(gè)符號(hào)的編碼。 目前已完成任務(wù)情況 學(xué)習(xí)并掌握了更多的c語言程序設(shè)計(jì)方法，比如結(jié)構(gòu)體struct、c文件的讀寫；游程編碼的程序流程圖如圖1；游程編碼又稱“運(yùn)行長度編碼”或“行程編碼”，是一種統(tǒng)計(jì)編碼，該編碼屬于無損壓縮編碼，是柵格數(shù)據(jù)壓縮的重要編碼方法。 一般情況下游程長度越長，其概率越小，這在以前的計(jì)算中也可以看見，而且將隨著長度的增大漸進(jìn)向零。(3)共游程編碼，這種編碼除了像傳統(tǒng)的變長到變長的編碼方案使用較短的代碼字來表示整個(gè)游程,還同時(shí)利用連續(xù)游程之間的相關(guān)性,對(duì)于連續(xù)的兩個(gè)或多個(gè)相同游程,后續(xù)每個(gè)游程僅用一位就可以表示。[7]祝本明，劉桂華。熟悉vc++的應(yīng)用方法，能夠比較熟悉的編寫讀懂程序。 主要的研究內(nèi)容、研究思路：設(shè)計(jì)內(nèi)容 游程編碼是一種是一種相對(duì)比較簡單而且比較容易實(shí)現(xiàn)的無損壓縮編碼，在二元序列中，只有兩種符號(hào)，即“0”和“1”，這些符號(hào)可連續(xù)出現(xiàn)，連“0”這一段稱為“0”游程，連“1”這一段稱為“1”游程。 基于游程編碼中的各種編碼:（1）Golomb碼和FDR碼都是基于測試集中0 個(gè)數(shù)多于1 個(gè)數(shù)的事實(shí)而對(duì)連續(xù)的0 進(jìn)行編碼，并未把連續(xù)的0 和1 都進(jìn)行編碼，因此存在一定的缺陷。 [10]馬寧 ,朱福萌 ,尹志軍, [11][12]Bo Ye , QianZhao , DuoZhou , XiaohuaWang , MinLuo .Test data pression using alternating variable runlength code .INTEGRATION, the VLSI journal .2011[13]商進(jìn)，[14]方建平,郝　躍,劉紅俠,李　 致謝 致謝本設(shè)計(jì)的完成是在我們的導(dǎo)師許成謙老師的細(xì)心指導(dǎo)下進(jìn)行的。可以預(yù)見，新的數(shù)學(xué)理論將不斷為數(shù)據(jù)壓縮技術(shù)輸入新鮮血液，因此數(shù)學(xué)理論決不可偏廢。參考文獻(xiàn) 結(jié)論游程編碼是圖像壓縮的基本算法，因此對(duì)于二元相關(guān)信源數(shù)據(jù)編碼研究變得尤為重要。這次的仿真只是對(duì)于一段很短的二元序列，而且各游程長度也很短，所以還不能過很好的體現(xiàn)出游程編碼的壓縮效率。再對(duì)下一個(gè)字符依次從根節(jié)點(diǎn)開始解碼，如此循環(huán)對(duì)每一段密文進(jìn)行解碼直到解碼結(jié)束。依次對(duì)每一個(gè)葉子節(jié)點(diǎn)進(jìn)行編碼操作，即可得到當(dāng)前哈夫曼樹的編碼表。對(duì)于哈夫曼編碼樹來說，由于哈夫曼編碼是前綴碼，所以所有要編碼的字符最終都將是這顆樹的葉子節(jié)點(diǎn)，而其它節(jié)點(diǎn)并沒有真正的字符意義。它的基本原理是按照信號(hào)出現(xiàn)概率大小順序排列信源信號(hào)，并設(shè)法按逆序分配碼字字長，使編碼的碼字是可辨識(shí)的。我在c語言編碼過程中主要針對(duì)這兩方面進(jìn)行編碼，即通過對(duì)“0”、“1”的變換次數(shù)來確定二元序列中總共有多少個(gè)游程；然后在確定每一個(gè)游程中游程的長度。通過對(duì)ISCAS 89 基準(zhǔn)電路硬故障測試集的分析對(duì)不同的電路各組共前綴次數(shù)的分布不均勻，因此CPRL碼引入了一個(gè)參變量M,M 表示確定的組號(hào)，M 取值不同，編碼結(jié)果就不同。共游程碼的前綴都是以“1”開頭以“0”結(jié)尾的數(shù)字串，沒有以“0”開頭的前綴，所以可以用數(shù)字0 來作為相鄰相同游程的標(biāo)志位，即后面相鄰相同游程的碼字只有1 位。不過由此也可看出待測試數(shù)據(jù)的游程長度加上2 所對(duì)應(yīng)的FDR 碼就是相應(yīng)的共前綴碼，若這兩個(gè)相差為2 的游程長度在同一組內(nèi)，則碼字長度并沒有增加，不會(huì)影響壓縮效果。此外，編程長度可以從一直到無限，這在碼字的選擇和碼表的建立方面都有困難，實(shí)際應(yīng)用是尚需采用某些措施來改進(jìn)。只在各行或者各列數(shù)據(jù)的代碼發(fā)生變化時(shí)，一次記錄該代碼及相同代碼重復(fù)的個(gè)數(shù)，從而實(shí)現(xiàn)數(shù)據(jù)的壓縮。這兩個(gè)新增的節(jié)點(diǎn)是最小的，所以無法和其他上層節(jié)點(diǎn)對(duì)換。某節(jié)點(diǎn)，設(shè)其較大的子節(jié)點(diǎn)為ｍ，較小的子節(jié)點(diǎn)為ｎ，ｍ下的任一層的所有節(jié)點(diǎn)都應(yīng)大于等于ｎ下的該層的所有節(jié)點(diǎn)。（4） 將形成的二叉樹的左節(jié)點(diǎn)標(biāo)0，右節(jié)點(diǎn)標(biāo)1。 (5) 信源符號(hào)所對(duì)應(yīng)的碼字即為費(fèi)諾碼。編碼步驟如下：1）將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列 p（x1）≥p（x2）≥…≥p（xn） （22）2）確定滿足下列不等式整數(shù)碼長Ki： log2p(xi)≤Ki＜log2p(xi)+1 （23）3)為了編成唯一可譯碼，計(jì)算第i個(gè)消息的累加概率 Pi=p(xk) （24）4)將累加概率Pi變成二進(jìn)制數(shù)。另外，在數(shù)字電視領(lǐng)域，信源編碼包括 通用的MPEG—（MPEG—Part10 AVC）編碼等 相應(yīng)地，信道編碼是為了對(duì)抗信道中的噪音和衰減，通過增加冗余，如校驗(yàn)碼等，來提高抗干擾能力以及糾錯(cuò)能力[4]。 信源編碼就是從信源符號(hào)到碼符號(hào)的一種映射f，它把信源輸出的符號(hào)ui變換成碼元序列wi。畫出游程編碼哈夫曼編碼的流程圖，以及得出的結(jié)果圖，最后做出總結(jié)。通過對(duì)游程編碼(Run LengthEncoding,RLE)進(jìn)行研究,結(jié)合哈夫曼編碼。例如一段時(shí)間長度為1 min，圖像尺寸為640480 pixete，每秒播放30幀的非壓縮彩色24位真彩色視頻的信息量為：64048033060：1658880000Bytes，(未含音頻信息的容量)，如果用650 MB的CDR來存放，需要3張。 本文主要介紹了信源編碼的分類、獲得最佳編碼的方法、哈夫曼樹的構(gòu)建方法以及游程編碼的原理和實(shí)現(xiàn)技術(shù)，對(duì)游程長度編碼技術(shù)做了較為全面地研究。游程編碼是針對(duì)于二元序列的一種編碼方法，對(duì)于二值圖像而言是一種編碼方法，對(duì)連續(xù)的黑、白像素?cái)?shù)(游程)以不同的碼字進(jìn)行編碼。 Huffman data pression and depression process, chart and flow chart is given and the results.Keywords　Runlength coding Huffman encoding The pression 1 目 錄摘要 IAbstract II第1章 緒論 1 課題背景 意義 2 2第2章 信源編碼分類 3 信源編碼 3 3 3 4 4 5 6 7 15 15 15 16 16 19第3章 游程編碼以及哈夫曼編 20 游程編碼 20 23 28 30結(jié)論 31參考文獻(xiàn) 33致謝 35附錄1 36附錄2 41附錄3 45附錄4 50第2章 信源編碼分類 第1章 緒論 課題背景信息時(shí)代人們對(duì)使用計(jì)算機(jī)獲取信息、處理信息的依賴性越來越高。無損壓縮雖然壓縮比不是很高，但還原后的文件與原數(shù)據(jù)文件完全相同，從而保證了信息細(xì)節(jié)的不失真，常用的方法有統(tǒng)計(jì)式壓縮法和字典式壓縮法，統(tǒng)計(jì)式壓縮法的編碼方案主要是霍夫曼(Hufman)編碼、算術(shù)編碼(AC)和游程長度編碼(RLC)[2]。但在某些數(shù)據(jù)安全性要求比較苛刻的領(lǐng)域，現(xiàn)在比較流行和壓縮效果好的壓縮算法幾乎都屬于有損范疇，對(duì)原始數(shù)據(jù)壓縮處理后有不同程度的損傷，無法完全恢復(fù)，以至于不能滿足技術(shù)要求，現(xiàn)有的無損壓縮方法，如Huffman、LZ 系列、算術(shù)編碼等壓縮方法盡管在某些方面各有優(yōu)點(diǎn)，但壓縮效果比較差或者算法實(shí)現(xiàn)比較困難，而游程編碼卻是一種是一種非常簡單，且編碼、解碼速度很快編碼方法。由于信源符號(hào)之間存在分布不均勻和相關(guān)性，使得信源存在冗余度，信源編碼的主要任務(wù)就是減少冗余，提高編碼效率。 信源編碼的分類： 離散信源編碼：獨(dú)立信源編碼,可做到無失真編碼； 連續(xù)信源編碼：獨(dú)立信源編碼,只能做到限失真信源編碼； 相關(guān)信源編碼：非獨(dú)立信源編碼。能獲得最佳編碼的方法主要有：香農(nóng)（Shannon）、費(fèi)諾（Fano）、哈夫曼（Huffman）編碼等。所以信源符號(hào)的平均碼長為： （25）