【正文】 ................................. 29 數(shù)據(jù)測試表格 .................................................................................................................... 29 與已有的 LZ 系列的實(shí)現(xiàn)對(duì)比 ......................................................................................... 30 第七章 LZ4 解壓縮算法硬件實(shí)現(xiàn) ................................................................................................ 31 LZ4 解壓核總體框架 ........................................................................................................ 31 LZ4 解壓驗(yàn)證結(jié)構(gòu)圖 ........................................................................................................ 31 LZ4 解壓核內(nèi)部模塊功能說明 ........................................................................................ 32 輸入模擬 FIFO ........................................................................................................... 32 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 v 數(shù)據(jù)解壓控制模塊 ..................................................................................................... 33 輸出控制模塊 ............................................................................................................. 34 輸出 RAM 模塊 .......................................................................................................... 34 LZ4 解壓核輸出速度計(jì)算 ................................................................................................ 34 第八章 總結(jié) ...................................................................................................................................... 36 參 考 文 獻(xiàn) ...................................................................................................................................... 37 致 謝 .......................................................................................................................................... 38 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 1 第一章 引 言 課題研究背景及意義 隨著信息時(shí)代的到來，人們對(duì)數(shù)據(jù)越來越依賴，數(shù)據(jù)交換量日益增大，海量數(shù)據(jù)帶來的大規(guī)模數(shù)據(jù)處理也變得更加復(fù)雜。而且，經(jīng)過壓縮的數(shù)據(jù)在一定程度上是對(duì)原始數(shù)據(jù)的加密，從而更加地提高數(shù)據(jù)的安全性 [1]。圖像、視頻、音頻等不是十分注重細(xì)節(jié)的數(shù)據(jù)大多數(shù)都采用有損壓縮技術(shù)，用于此類應(yīng)用場景的有 MPEG， ， 等當(dāng)今流行的壓縮技術(shù) [2][3]。 人們對(duì)無損壓縮技術(shù)的研究已經(jīng)有很長的一段時(shí)間，其中 LZ 系列的壓縮算法和最小冗余度構(gòu)造算法 Huffman 算法屬于最重要的無損壓縮技術(shù)。 但是，當(dāng)今很多壓縮解壓方案都是基于軟件方式的實(shí)現(xiàn)。特別是當(dāng)壓縮解壓大量數(shù)據(jù)時(shí)，占有的 CPU 資源是非常大的，而且由于 CPU 采用的指令工作方式使得速度很慢，另外系統(tǒng)非常不穩(wěn)定，很難滿足一些特殊環(huán)境下的應(yīng)用要求。 現(xiàn)代 VLSI 技術(shù)的發(fā)展使得采用硬件方式來實(shí)現(xiàn)壓縮解壓成為可能。即它可以： l、提高了壓縮解壓的速度，有利于實(shí)時(shí)性處理； 節(jié)省了寶貴的 CPU 資源。如今已經(jīng)有不少采用硬件方式的壓縮解壓方案在信息產(chǎn)業(yè)的各個(gè)環(huán)節(jié)被應(yīng)用， 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 2 具有長遠(yuǎn)的發(fā)展前景 [6][7]。通過對(duì)現(xiàn)有的 LZ4文獻(xiàn)以及官方的 C程序，了解并掌握 LZ4算法的壓縮和解壓原理。通過算法流程圖，將整個(gè)算法細(xì)分成許多子模塊，每個(gè)子模塊實(shí)現(xiàn) 一個(gè)簡單的功能，通過流程控制將每個(gè)模塊關(guān)聯(lián)起來，最后實(shí)現(xiàn)每個(gè)子模塊都處于同時(shí)工作狀態(tài)，提高壓縮速度，實(shí)現(xiàn)并行處理功能。 第三章對(duì) LZ4 無損壓縮算法原理進(jìn)行了詳細(xì)的介紹，包括 LZ4 數(shù)據(jù)格式以及 LZ4 算法流程。 第五章介紹了 LZ4 無損壓縮算法硬件實(shí)現(xiàn) 程序的結(jié)構(gòu)以及每個(gè)模塊的功能，同時(shí)給出了在 kintex7 kc705 開發(fā)板上運(yùn)行的到的一些資源消耗信息。 第七章是根據(jù)壓縮算法而做的解壓算法的 FPGA 實(shí)現(xiàn)，其中詳細(xì)介紹了解壓流程以及解壓程序中每個(gè)模塊的功能。 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 3 第二章 基本原理和常用算法 數(shù)據(jù)壓縮的前提是數(shù)據(jù)可以被壓縮 。根據(jù)數(shù)據(jù)的信息量、熵和冗余度可以計(jì)算出壓縮后的最小體積，但是由于算法原理、數(shù)據(jù)格式不同會(huì)導(dǎo)致始終達(dá)不到理論值。 數(shù)據(jù)信息量、熵和冗余度介紹 信息量是指一個(gè)隨機(jī)事件的不確定性，通常用熵來表示。一個(gè)消息的可能性越小 ，其信息就越多；消息的可能性越大，其信息就越少。 將信息所有可能事件的信息量進(jìn)行平均，就得到信息的熵。冗余度 R 定義為： （ ） LZ 系列算法概述 LZ 系列算法起源于兩位以色列研究者 和 在 1977 年發(fā)布的 LZ77 數(shù)據(jù)壓縮 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 4 的通用算法，該算法與 Huffman 及 算術(shù)編碼 更加有效，通過不斷的發(fā)展演變最后提出了很多改進(jìn)算法，比如 1978 年由二人提出的改進(jìn)算法 LZ78 以及 1984 年 提出的 LZW 算法等。 LZ7 LZSS、 LZ7 LZW 算法都是通過創(chuàng)建字典 進(jìn)行壓縮的算法， LZ77 和 LZSS 里的詞典是指當(dāng)前數(shù)據(jù)是否在以前出現(xiàn)過的數(shù)據(jù)中出現(xiàn)過，出現(xiàn)過就用出現(xiàn)過的字符的位置代替當(dāng)前數(shù)據(jù)，而不同的是 LZ78 以及 LZW 是將出現(xiàn)過的數(shù)據(jù)進(jìn)行編碼，如果當(dāng)前數(shù)據(jù)在以前出現(xiàn)過，則用編碼代替當(dāng)前數(shù)據(jù)。 LZ4 算法簡介 LZ4 算法也屬于 LZ 系列算法，其主要概念與 LZ77 算法一致。 LZ4 的預(yù)讀緩存區(qū)域?yàn)?4 個(gè)字節(jié)，而滑動(dòng)窗口的大小可以根據(jù)實(shí)際需要進(jìn)行修改。而整個(gè) LZ4 壓縮后的文件就是有許多個(gè)類似的序列組合而成。以下介紹了整個(gè) LZ4 無損壓縮算法的原理，包括壓縮后的數(shù)據(jù)格式。 數(shù)據(jù)流格式 下圖給出了 LZ4 壓縮后的數(shù)據(jù)流格式 [10]，其中前面 4Byte 是表示這個(gè)文件是什么格式，通常是一個(gè)特定的數(shù)字來代表其是 LZ4 壓縮文件，后面的 315Byte 用來表示整個(gè)數(shù)據(jù)流的大小。其后的 4 個(gè)字節(jié)都是 0，用來表示數(shù)據(jù)結(jié)束。 圖 數(shù)據(jù)流格式簡圖 官方 LZ4 格式 LZ4 的格式如下 [9][11]： （ 1） 數(shù)據(jù)格式 每一個(gè)輸入的數(shù)據(jù)塊可以壓縮成若干個(gè)序列， 每個(gè)序列都包含有令牌（ token）、字符串（ literals）、字符串長度（ literal length）、偏移量（ offset）以及匹配長度（ match length）。 低 4 位代表匹配字符長度，當(dāng)匹配字符長度大于等于 19 時(shí)低 4 位為 15；當(dāng)匹配字符長度小于 19 時(shí)，低 4 位等于匹配字符長度減去 4。 若 token 高 4 位等于 15，則需要在該序列后添加一個(gè)字節(jié)來表示完整的長度值。這樣，兩個(gè)位置的值組合共同表示完整的長度。 （ 4） literals 該序列為未壓縮的數(shù)據(jù)，由原數(shù)據(jù)復(fù)制得到，該數(shù)據(jù)跟在 token 和 literal length 后面。該序列有一個(gè)規(guī)則，即 0 是一個(gè)無效值，不能使用，1 代表“當(dāng)前位置減一個(gè)字節(jié)”。 （ 6） match length 表示匹配數(shù)據(jù)的長度。匹配長度若超出 15，采取的措施和 literal length 里面采取的方法一致。 2）不能匹 配最后 12 個(gè)字節(jié)的數(shù)據(jù)。 3）最后一個(gè)序列匹配長度為 0， offset 為 0。若按照原來的格式，則必須先計(jì)算出不可匹配字符長度，然后再將不可匹配字符輸出，這樣數(shù)據(jù)輸出的時(shí)間開銷將變大，因此會(huì)減小壓縮速度。修改后的數(shù)據(jù)格式如下： 說明： token、 offset 的格式與標(biāo)準(zhǔn)格式一致。 當(dāng) token 高 4 為為 15 時(shí)， literal length 為 2 個(gè)字節(jié)，位于不可匹配字符中第 1 17 個(gè)字節(jié)，字符長度大小為 literal length 中以前一個(gè)字節(jié)為高 8 位和后一個(gè)字節(jié)為低 8 位組合成的一個(gè) 16 位的數(shù)據(jù)。 當(dāng) token 低 4 為 15 時(shí)， match length 為 2 個(gè)字節(jié)，位于 offset 后兩個(gè)字節(jié)，實(shí)際匹配長度大小為 match length 中以前一個(gè)字節(jié)為高 8 位和后一個(gè)字節(jié)為低 8 位組合成的一個(gè) 16 位的數(shù)據(jù)、 token 后四位和 4 相加的結(jié)果。這個(gè)哈希表的映射關(guān)系為 (key, value)： key 是 4 個(gè)字節(jié)的二進(jìn)制數(shù)。 選擇哈希表的大小時(shí)要根據(jù) 實(shí)際要求作出選擇： 1）如果側(cè)重壓縮比，則可以將哈希表設(shè)置大一些。 哈希表使用的內(nèi)存默認(rèn)值為 16KB，能裝進(jìn) L1 cache，這也是 LZ4 壓縮速度快的一個(gè)原因。 Hash 值計(jì)算采用整數(shù)哈希算法。 計(jì)算哈 希值時(shí)，輸入為 4 個(gè)字節(jié)的二進(jìn)制數(shù)，輸出可以分為 2 字節(jié)值、 4 字節(jié)值兩種哈希值。 2）令下個(gè)地址為 forwardIp，它的哈希值為 forwardH (下個(gè)循環(huán)賦值給 ip、 h)。 ） ref 為初始值，沒有匹配，繼續(xù)往下查找。 ）如果 ref 不在滑動(dòng)窗口內(nèi)，放棄當(dāng)前值，繼續(xù)向下查找。 ）如果 ref 在滑動(dòng)窗口內(nèi)，且對(duì)應(yīng)的 4 個(gè)字節(jié)一樣，表明找到了 match，退出匹配查找。 流操作 流操作循環(huán)步驟： 1）讀取 4 字節(jié)，根據(jù) hash 算法計(jì)算 hash 值。 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 9 3）若查找到了匹配則向后繼續(xù)查找計(jì)算匹配長度，否則返回第一步讀取后 4 個(gè)字節(jié)繼續(xù)查找。如果地址移動(dòng)到了最后 5 個(gè)字節(jié)，則采取相應(yīng)的算法規(guī)則，最后 5 個(gè)字節(jié)單獨(dú)作為一個(gè)序列不進(jìn)行匹配。 2）讀取 stream describe 判斷文件大小，確定末尾地址 3）讀取第一個(gè)序列的 token，即 stream describe 后一個(gè)字節(jié)。若 token 高 4 位小于 15，說明不可匹配字符長度就等于 token 高 4 位的值。 5）根據(jù)不可匹配字符長度計(jì)算出 offset 的位置，讀取 offset 的倆個(gè)字節(jié)，將其拼接成一個(gè) 16 位的數(shù)據(jù)，根據(jù) offset 確定匹配的位置。若token 低 4 位小于 15，說明可匹配字符長度等于 token 低 4 位的值再加上 4。 8）待拷貝完成后，讀取下一個(gè) token，按照上述規(guī)則繼續(xù)往下解壓直到解壓到末尾地址結(jié)束。 2）讀取 stream describe 判斷文件大小，確定 末尾地址 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 10 3）讀取第一個(gè)序列的 token，即 stream describe 后一個(gè)字節(jié)。將第 1 17 個(gè)字節(jié)合并成一個(gè) 16 位的數(shù)據(jù) literal length，不可匹配字符長度就等于 literal length 加上 15。 4）確定不可匹配