【正文】 損傷，無法完全恢復(fù)，以至于不能滿足技術(shù)要求，現(xiàn)有的無損壓縮方法，如Huffman、LZ 系列、算術(shù)編碼等壓縮方法盡管在某些方面各有優(yōu)點(diǎn)，但壓縮效果比較差或者算法實(shí)現(xiàn)比較困難，因此十分有必要對(duì)無損壓縮算法進(jìn)行研究。從設(shè)計(jì)的選題到資料的搜集直至最后設(shè)計(jì)的修改的整個(gè)過程中，花費(fèi)了許老師很多的寶貴時(shí)間和精力，在此向?qū)煴硎局孕牡馗兄x！導(dǎo)師嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度，開拓進(jìn)取的精神和高度的責(zé)任心都將使學(xué)生受益終生！ 還要感謝和我同一設(shè)計(jì)小組的幾位同學(xué)，是你們?cè)谖移綍r(shí)設(shè)計(jì)中和我一起探討問題，并指出我設(shè)計(jì)上的誤區(qū)，使我能及時(shí)的發(fā)現(xiàn)問題把設(shè)計(jì)順利的進(jìn)行下去，沒有你們的幫助我不可能這樣順利地結(jié)稿，在此表示深深謝意。 [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)行的。[7]祝本明，劉桂華。 參考文獻(xiàn)[1]王增輝， [2]許川佩，46（25）[3]劉娟，詹文法，[4]詹文法，梁華國(guó)，時(shí)峰，黃正峰，[5]彭喜元，[6]于翔。由于每種無損壓縮都有自己的適用范圍，壓縮比受不失真要求的限制，真正意義上高壓縮比的通用無損壓縮算法目前哈有待繼續(xù)研究?？梢灶A(yù)見，新的數(shù)學(xué)理論將不斷為數(shù)據(jù)壓縮技術(shù)輸入新鮮血液，因此數(shù)學(xué)理論決不可偏廢。本文中我才用游程編碼和哈夫曼編碼混合使用。二元相關(guān)游程編碼一般不直接應(yīng)用與多灰度圖像，但比較適于二值圖像的編碼，例如傳真圖像的編碼等。經(jīng)過這段時(shí)間的學(xué)習(xí)與實(shí)踐，我對(duì)二元相關(guān)信源游程編碼與信號(hào)編碼的發(fā)展及現(xiàn)狀有了更深刻的認(rèn)識(shí)，意識(shí)到數(shù)據(jù)壓縮與解壓對(duì)于信息時(shí)代的巨大影響及其潛在的經(jīng)濟(jì)效益，并對(duì)Microcsoft Visual C++軟件有了進(jìn)一步的了解。參考文獻(xiàn) 結(jié)論游程編碼是圖像壓縮的基本算法，因此對(duì)于二元相關(guān)信源數(shù)據(jù)編碼研究變得尤為重要。哈夫曼變長(zhǎng)碼的效率是相當(dāng)高的，它可以單個(gè)信源符號(hào)編碼或用L較小的信源序列編碼，對(duì)編碼器的設(shè)計(jì)來說也簡(jiǎn)單的多。哈夫曼碼是用概率匹配方法進(jìn)行信源編碼。游程編碼是一種簡(jiǎn)單的快捷的編碼方法，能夠有效的對(duì)二元序列進(jìn)行無損壓縮，一般情況下，游程長(zhǎng)度越大，其概率越小，而且隨著長(zhǎng)度的增大逐漸趨向零。這次的仿真只是對(duì)于一段很短的二元序列，而且各游程長(zhǎng)度也很短，所以還不能過很好的體現(xiàn)出游程編碼的壓縮效率。即總的壓縮效率為59%，而游程壓縮效率為80%。需要的時(shí)候可以在Encoder 函數(shù)中先進(jìn)行判定。在解碼之前，還應(yīng)該先確認(rèn)之前是否建立了哈夫曼樹并且是否構(gòu)建了編碼表。再對(duì)下一個(gè)字符依次從根節(jié)點(diǎn)開始解碼，如此循環(huán)對(duì)每一段密文進(jìn)行解碼直到解碼結(jié)束。開始對(duì)密文的字符串進(jìn)行解碼，樹索引從根節(jié)點(diǎn)開始走，當(dāng)密文中的當(dāng)前字符是‘0’的時(shí)候，則索引走向左子節(jié)點(diǎn)；當(dāng)是‘1’的時(shí)候，則走向右子節(jié)點(diǎn)。開始對(duì)需要編碼的字符進(jìn)行編碼，將字符逐一讀取與剛剛建立的編碼表中的每個(gè)葉子節(jié)點(diǎn)代表的字符進(jìn)行比較，找出相同的對(duì)象，并將當(dāng)前節(jié)點(diǎn)的編碼打印到屏幕，并將編碼存入到新建的密碼文件當(dāng)中。首先需要建立一個(gè)原始文件，在文件中輸入需要編碼的內(nèi)容。依次對(duì)每一個(gè)葉子節(jié)點(diǎn)進(jìn)行編碼操作，即可得到當(dāng)前哈夫曼樹的編碼表。以此類推進(jìn)行編碼直到根節(jié)點(diǎn)為止。編碼時(shí)要從葉子節(jié)點(diǎn)出發(fā)向根節(jié)點(diǎn)進(jìn)行逆向編碼。 建立哈夫曼樹的流程圖如圖33：圖33構(gòu)建哈夫曼樹流程圖 構(gòu)建完哈夫曼樹后，根據(jù)建立哈夫曼樹建立哈夫曼碼表。對(duì)于哈夫曼編碼樹來說，由于哈夫曼編碼是前綴碼，所以所有要編碼的字符最終都將是這顆樹的葉子節(jié)點(diǎn)，而其它節(jié)點(diǎn)并沒有真正的字符意義。先在所有可能出現(xiàn)的字符中篩選出當(dāng)前權(quán)重最小的兩個(gè)字符，將這兩個(gè)字符分別作為新節(jié)點(diǎn)的左子和右子建立一個(gè)小的二叉樹，并將兩個(gè)字符的權(quán)重之和賦值給新節(jié)點(diǎn)，將新二叉樹放入篩選字符中，再將篩選過的兩個(gè)字符從篩選列表中淘汰掉。在建立哈夫曼樹之前還需要對(duì)出現(xiàn)的字符和權(quán)重進(jìn)行統(tǒng)計(jì)和記錄，并且定義一個(gè)可以篩選出最小權(quán)重的函數(shù)。 建立哈夫曼樹的思想。它的基本原理是按照信號(hào)出現(xiàn)概率大小順序排列信源信號(hào)，并設(shè)法按逆序分配碼字字長(zhǎng)，使編碼的碼字是可辨識(shí)的。游程編碼數(shù)據(jù)壓縮算法流程圖如圖31：數(shù)據(jù)解碼算法流程如下： 1) 打開壓縮數(shù)據(jù)文件和恢復(fù)文件； 2) 從壓縮文件中循環(huán)讀出字符和該字符連續(xù)的個(gè)數(shù), 在恢復(fù)文件中連續(xù)寫入從壓縮文件中讀出的字符, 寫的次數(shù)等于該字符連續(xù)的個(gè)數(shù):。數(shù)據(jù)壓縮算法流程如下： 1) 打開源數(shù)據(jù)文件和壓縮后的數(shù)據(jù)文件； 2) 從源數(shù)據(jù)文件中讀取字符, 并把它放入一個(gè)寄存器中，然后再循環(huán)讀取后面的字符，并與寄存器中的字符相比較。 用游程編碼壓縮數(shù)據(jù)時(shí)，首先要計(jì)算每次連續(xù)相同字符的個(gè)數(shù)，然后將每次連續(xù)相同的字符及個(gè)數(shù)保存起來。我在c語言編碼過程中主要針對(duì)這兩方面進(jìn)行編碼，即通過對(duì)“0”、“1”的變換次數(shù)來確定二元序列中總共有多少個(gè)游程；然后在確定每一個(gè)游程中游程的長(zhǎng)度。如果規(guī)定二元序列是以“0”開始，第一個(gè)游程是“0”游程，第二個(gè)必為“1”游程，第三個(gè)又是“0”游程等等。 本章主要介紹了信源編碼中的幾種最佳信源變長(zhǎng)編碼:香農(nóng)（Shannon）、費(fèi)諾（Fano）、哈夫曼（Huffman）編碼，以及這幾種編碼的編碼過程,然后主要介紹了哈夫曼樹的構(gòu)成步驟，以及游程編碼的算法和編碼特點(diǎn)。 CPRL 碼的具體編碼方法如下：若待編碼的0 游程長(zhǎng)度所在的組號(hào)≤M,則直接用FDR 碼字表示CPRL 碼字，原因是組號(hào)小的碼字前綴位數(shù)也短；若待編碼的0 游程長(zhǎng)度所在的組號(hào)≥M，且相鄰游程長(zhǎng)度在同一組內(nèi)，則后面的游程CPRL碼字由該游程長(zhǎng)度對(duì)應(yīng)的FDR 碼字省略前綴，并在剩下的碼字后綴后面加上一個(gè)標(biāo)志位0 組成，同組相鄰的第一個(gè)游程的CPRL 碼字由對(duì)應(yīng)的FDR 碼字加上標(biāo)志位1 組成；若待編碼的0 游程長(zhǎng)度所在的組號(hào)≥M，且相鄰游程長(zhǎng)度不在同一組內(nèi)，則各游程的CPRL 碼字由對(duì)應(yīng)的FDR 碼字加一位標(biāo)志位組成。通過對(duì)ISCAS 89 基準(zhǔn)電路硬故障測(cè)試集的分析對(duì)不同的電路各組共前綴次數(shù)的分布不均勻，因此CPRL碼引入了一個(gè)參變量M,M 表示確定的組號(hào)，M 取值不同，編碼結(jié)果就不同。由于初始測(cè)試數(shù)據(jù)集中存在大量的無關(guān)位，可以適當(dāng)?shù)膶?duì)這些無關(guān)位進(jìn)行賦值填充，增加0 游程的長(zhǎng)度，這些游程長(zhǎng)度在同組的概率很高。3）共前綴連續(xù)長(zhǎng)度碼共前綴連續(xù)長(zhǎng)度碼（Co Prefixal Run Length codes，CPRL）也考慮了相鄰游程的相關(guān)性。由于初始測(cè)試數(shù)據(jù)中存在著大量的無關(guān)位，可以有意識(shí)的對(duì)它們進(jìn)行賦值填充，以增加長(zhǎng)度相同的相鄰游程的數(shù)量，從而降低碼字的長(zhǎng)度。共游程碼的前綴都是以“1”開頭以“0”結(jié)尾的數(shù)字串，沒有以“0”開頭的前綴，所以可以用數(shù)字0 來作為相鄰相同游程的標(biāo)志位，即后面相鄰相同游程的碼字只有1 位。顯然該編碼方案的數(shù)據(jù)壓縮率比共前綴碼高一些，不考慮相鄰游程的長(zhǎng)度相同的前提下，編碼方法與共前綴碼相同。2）共游程碼 前面介紹的共前綴碼是利用游程長(zhǎng)度同組的前綴相同，用標(biāo)志位0 加碼字后綴來表示后面的游程，從而進(jìn)一步壓縮初始測(cè)試數(shù)據(jù)。下面給出一個(gè)共前綴編碼的實(shí)例：編碼前的初始測(cè)試數(shù)據(jù)： 000000001 1 0000001 000000000000010000000000000001（47 位）；編碼后的碼字：110100 1000 110010 11100001 00011（29 位）。不過由此也可看出待測(cè)試數(shù)據(jù)的游程長(zhǎng)度加上2 所對(duì)應(yīng)的FDR 碼就是相應(yīng)的共前綴碼，若這兩個(gè)相差為2 的游程長(zhǎng)度在同一組內(nèi)，則碼字長(zhǎng)度并沒有增加，不會(huì)影響壓縮效果。同組共前綴碼的前綴和后綴的位數(shù)相同，前綴和后綴相加對(duì)應(yīng)的十進(jìn)制數(shù)比對(duì)應(yīng)的游程長(zhǎng)度多2，也就是說跟FDR 碼相比，相同的碼字所表示的游程長(zhǎng)度少2，使壓縮效果受到一些影響，因此對(duì)初始測(cè)試數(shù)據(jù)進(jìn)行無關(guān)位(don’t cares bit)填充時(shí)，要盡量時(shí)這種影響降到最低。1）共前綴碼 共前綴碼編碼時(shí)也是按照一定規(guī)律用盡量短的碼字來表示游程形式的初始測(cè)試數(shù)據(jù)，但該編碼壓縮方案進(jìn)一步考慮了相鄰游程之間存在的聯(lián)系。對(duì)于小概率的碼字，其長(zhǎng)度為達(dá)到概率匹配或較長(zhǎng)，損失不會(huì)太大，也就是對(duì)平均碼字長(zhǎng)度影響較小。此外，編程長(zhǎng)度可以從一直到無限，這在碼字的選擇和碼表的建立方面都有困難，實(shí)際應(yīng)用是尚需采用某些措施來改進(jìn)。 將任何(二元)序列變換成一一對(duì)應(yīng)的游程長(zhǎng)度序列，再按哈夫曼編碼或其他方法處理以達(dá)到壓縮碼率的目的[9]。如果規(guī)定二元序列是以“0”開始，第一個(gè)游程是“0”游程，第二個(gè)必為“1”游程，第三個(gè)又是“0”游程等等。它們的長(zhǎng)度分別稱為游程長(zhǎng)度L(0)和L(l)。只在各行或者各列數(shù)據(jù)的代碼發(fā)生變化時(shí)，一次記錄該代碼及相同代碼重復(fù)的個(gè)數(shù)，從而實(shí)現(xiàn)數(shù)據(jù)的壓縮。如果給出了形成串的字符，串的長(zhǎng)度以及串的位置，就能恢復(fù)出原來的數(shù)據(jù)流，游程長(zhǎng)度編碼(RLC)就是用二進(jìn)制碼字給出這些信息的一類方法。 這樣一步步逆推下去，在這個(gè)過程中哈弗曼樹每一步都始終保持著是一棵最優(yōu)二叉樹。只要前一步是最優(yōu)二叉樹，由于這兩個(gè)新增的節(jié)點(diǎn)是最小的，即使同層有其他節(jié)點(diǎn)，也無法和同層其他節(jié)點(diǎn)重新結(jié)合，產(chǎn)生比它們的父節(jié)點(diǎn)更小的上層節(jié)點(diǎn)來和同層的其他節(jié)點(diǎn)對(duì)換。這兩個(gè)新增的節(jié)點(diǎn)是最小的，所以無法和其他上層節(jié)點(diǎn)對(duì)換。 比如上面的例子，哈弗曼樹建立的過程如下:1) 列出原始的節(jié)點(diǎn)數(shù)據(jù)： 圖24原始節(jié)點(diǎn)2) 將最小的兩個(gè)節(jié)點(diǎn)C和E結(jié)合起來：圖25C和E結(jié)合3) 再將新的節(jié)點(diǎn)和A組合起來 圖26新節(jié)點(diǎn)結(jié)合圖 4) 再將D節(jié)點(diǎn)加入 圖27新節(jié)點(diǎn)結(jié)合圖5) 如此循環(huán)，最終得到一個(gè)最優(yōu)二叉樹 圖28最優(yōu)二叉樹圖生成的數(shù)據(jù)文件長(zhǎng)度為： 3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63 下面我們用逆推法來證明對(duì)于各種不同的節(jié)點(diǎn)序列，用哈弗曼算法建立起來的樹總是一棵最優(yōu)二叉樹：當(dāng)這個(gè)過程中的節(jié)點(diǎn)序列只有兩個(gè)節(jié)點(diǎn)時(shí)（比如前例中的15和18），肯定是一棵最優(yōu)二叉樹，一個(gè)編碼為0，另一個(gè)編碼為1，無法再進(jìn)一步優(yōu)化。重復(fù)上面兩個(gè)步驟，直到節(jié)點(diǎn)序列中只剩下唯一一個(gè)節(jié)點(diǎn)。 哈夫曼算法的步驟是這樣的：從各個(gè)節(jié)點(diǎn)中找出最小的兩個(gè)節(jié)點(diǎn)，給它們建一個(gè)父節(jié)點(diǎn)，值為這兩個(gè)節(jié)點(diǎn)之和。某節(jié)點(diǎn)，設(shè)其較大的子節(jié)點(diǎn)為ｍ，較小的子節(jié)點(diǎn)為ｎ，ｍ下的任一層的所有節(jié)點(diǎn)都應(yīng)大于等于ｎ下的該層的所有節(jié)點(diǎn)。 哈弗曼編碼幾乎是所有壓縮算法的基礎(chǔ)，其實(shí)這個(gè)算法并不復(fù)雜，簡(jiǎn)單的理解就是，如何用更短的bit來編碼數(shù)據(jù)。哈夫曼編碼是用概率匹配方法進(jìn)行信源編碼。對(duì)表21中的信源數(shù)據(jù)進(jìn)行哈夫曼編碼，編碼過程如表23。（4） 將形成的二叉樹的左節(jié)點(diǎn)標(biāo)0，右節(jié)點(diǎn)標(biāo)1。（2） 每一次選出頻率最小的兩個(gè)值，作為二叉樹的兩個(gè)葉子節(jié)點(diǎn)，將和作為它們的根節(jié)點(diǎn)，這兩個(gè)葉子節(jié)點(diǎn)不再參與比較，新的根節(jié)點(diǎn)參與比較。它的基本原理是按照信號(hào)出現(xiàn)概率大小順序排列信源信號(hào)，并設(shè)法按逆序分配碼字字長(zhǎng)，使編碼的碼字是可辨識(shí)的。則該費(fèi)諾編碼的平均碼長(zhǎng)：（27）信息傳輸速率 （28）表22費(fèi)諾編碼過程消息符號(hào)Ai消息概率P（Ai）第一次分組第二次分組第三次分組第四次分組二元碼字碼長(zhǎng)KiA100002A2100103A310113A410102A5101103A61011104A7111114顯然費(fèi)諾碼要比上述香農(nóng)碼的平均碼長(zhǎng)小，消息傳輸速率大，說明編碼效率高。 (5) 信源符號(hào)所對(duì)應(yīng)的碼字即為費(fèi)諾碼。（3）將每一大組的信源符號(hào)再分為兩組，使劃分后的兩個(gè)組的概率之和近似相同，并對(duì)各組賦予一個(gè)二進(jìn)制符號(hào)“0”和“1”。費(fèi)諾編碼步驟：（1） 將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列： 。設(shè)信源共7個(gè)符號(hào)消息，其概率和累加概率如表21，則其香農(nóng)編碼過程如表21。編碼步驟如下：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=p(xk) （24）4)將累加概率Pi變成二進(jìn)制數(shù)。這種編碼方法就是香農(nóng)編碼。 香農(nóng)第一定理指出了平均碼長(zhǎng)與信源之間的關(guān)系，同時(shí)也指出了可以通過編碼使平均碼長(zhǎng)達(dá)到極限值，這是一個(gè)很重要的極限定理。為此必須將概率大的信息符號(hào)編以短的碼字，概