【正文】 通過計(jì)算可以得出壓縮速度為： 124— 140MByte/s。 4）如果 match_length 不為 0，寫入 match_length。通過匹配長度大小判斷 token 后 4 位的大小。 （ 5） token 計(jì)算模塊 圖 token 計(jì)算模塊框圖 功能： 對不可匹配字符進(jìn)行緩存、計(jì)算不可匹配字符長度、計(jì)算 token 高 4 位大小、給出寫入控制時(shí)寫入 token 的時(shí)機(jī)。 說明： 通過 U32ip 計(jì)算出 ash 值，再據(jù) hash 值執(zhí)行對 hash 表的寫入讀出，若當(dāng)前地址與 hash表中的地址之差小于 64k 則表示 hash 表中的地址有效， 若大于 64k 則表示 hash 表中的地址無效，寫入當(dāng)前地址再計(jì)算下一個(gè)數(shù)據(jù)的 hash 值重復(fù)上面的步驟。 （ 3） Ref 控制模塊 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 24 圖 Ref 控制模塊框圖 功能： 實(shí)現(xiàn)對 Ref 的寫入、復(fù)位、以及加 1 計(jì)算。當(dāng)信號 go 為 1 時(shí)，對 ip 執(zhí)行加 1 運(yùn)算。 LZ4 核總體框架 想要輸入數(shù)據(jù)開始壓縮之前將復(fù)位信號 rst1 置 0， input_en 和 wea_ip 置 1，然后輸入數(shù)據(jù)以及數(shù)據(jù)地址，每個(gè)數(shù)據(jù)對應(yīng)一個(gè)地址，輸入結(jié)束后，將 input_en 和 wea_ip 置 0，當(dāng) all_end為 1 時(shí)表示可以輸出數(shù)據(jù)，數(shù)據(jù)大小為 op， 將 op 之內(nèi)的數(shù)據(jù)通過 out_dop 輸出， out_op 是其對應(yīng)的地址。 占用資源不算多，壓縮速度快且穩(wěn)定不受沖突的影響。 時(shí)序變長，最低壓縮速度無法保證。 硬件易于實(shí)現(xiàn)，每次循環(huán)完成 hash值計(jì)算、判斷。 最大壓縮速度：只要單位時(shí)間內(nèi)產(chǎn)生的序列越少，壓縮速度越快。而當(dāng) literal_ip_go 為 0 時(shí)間隔一個(gè)時(shí)鐘就啟動匹配控制 ip 移動。 3）等到后向匹配查找結(jié)束后，若匹配字符長度大于等于 19 則接在 offset 后面寫入 match length，若匹配字符長度小于 19，則不用寫 match length。若不可匹配字符的大小大于 15 時(shí)， literal length 等于不可匹配字符的大小減去 15。 4）剩余數(shù)據(jù)生成一個(gè)單獨(dú)的序列， offset 為 0，匹配長度為 0。若 Ref小于當(dāng)前 ip 值且不為 0，同時(shí) U32Ref 等于 U32ip 則說明當(dāng)前 4 個(gè)字節(jié)與地址在 Ref 處的 4個(gè)字節(jié)相同，啟動匹配程序進(jìn)入步驟 3；否則繼續(xù)。同時(shí) hash 表以及 4 字節(jié)存儲空間寫輸入使能。 方案三 硬件框圖 方案三的結(jié)構(gòu)結(jié)合了以上兩個(gè)方案，同樣需要優(yōu)化硬件結(jié)構(gòu)，縮短時(shí)序。 最小壓縮速度：由于沖突數(shù)量并不可預(yù)測，所以最低速度無法通過計(jì)算獲得，只能通過估計(jì)大概數(shù)值。 State 是用于返回讀取匹配的 4 字節(jié)的狀態(tài)切換標(biāo)志，每個(gè) 時(shí)鐘加一。 2）第一個(gè)序列完成后，依次寫入 token、 literal length、 literal、 offset、 match length。 ? literal length：核心控制處于步驟 2 時(shí)，通過對控制 ip 模塊的控制信號時(shí)長進(jìn)行計(jì)數(shù)，獲得不可匹配字符的大小，若其小于 15 則 literal length 為 0，且不輸出。 6）一個(gè)序列查找完成，增加 ip，控制移位寄存 器，使移位寄存器中不再有前面的匹配字符，然后回到步驟 2,開始查找下一個(gè)序列。進(jìn)入步驟 4。同時(shí)寫入當(dāng)前的 ip 值以及移位寄存器輸出的 32 位數(shù)據(jù) U32ip。 算法流程 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 15 （ 1）方案二核心算法流程： 1）啟動壓縮時(shí)，通過 ip 控制，每個(gè)時(shí)鐘 ip 加一，同時(shí)控制移位寄存器移位，當(dāng) ip 等于4 時(shí)啟動 hash 計(jì)算得出 hash 值。 方案二 硬件框圖 與方案一不同的是，方案二需要優(yōu)化硬件結(jié)構(gòu)，縮短時(shí)序，同時(shí)去掉那個(gè) 32 位 64k 地址的 RAM塊，通過返回讀取緩存中的數(shù)據(jù)然后再進(jìn)行沖突判斷，這樣做的好處在于減少了 RAM資源的消耗，可以使程序消耗更少的資源。而找到匹配后每 2 個(gè)狀態(tài) ip 加 1，也就是 ip 每 2 個(gè)時(shí)鐘加 1。 state 是用于匹配查找狀態(tài)切換標(biāo)志，每個(gè)時(shí)鐘加一。 2）第一個(gè)序列完成后，依次寫入 token、 literal length、 literal、 offset、 match length。 ? literal length：核心控制處于步驟 2 到步驟 4 時(shí)，通過對控制 ip 模塊的脈沖計(jì)數(shù)，獲得不可匹配字符的大小，若其小于 15 則 literal length 為 0，且不輸出。 7）一個(gè)序列查找完成，增加 ip，控制移位寄存器，使移位寄存器中不再有前面的匹配字符，然后回到步驟 2，開始查找下一個(gè)序列。若 ip 移動到倒數(shù)第 5 個(gè)字節(jié)時(shí)跳到步驟 8。 3）再過一個(gè)時(shí)鐘，讀出 hash 表中的地址 Ref 以及 4 字節(jié)存儲空間中的 4 個(gè)字節(jié) U32Ref。 以下為方案一的硬件框圖： 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 12 圖 方案一硬件框圖 下面將具體介紹方案一的算法流程。 方案一的硬件模塊分為輸入緩存、 ip 控制、移位寄存器等 9 個(gè)模塊，通過 ip 控制將輸入緩存中的數(shù)據(jù)讀出傳送給移位寄存器，而移位寄存器將數(shù)據(jù)變成 32 位數(shù)據(jù)傳輸給核心控制模塊進(jìn)行 hash 計(jì)算、匹配查找的操作，直到查找到匹配后，讀出匹配處的地址，根據(jù)地址讀出緩存中該地址后的數(shù)據(jù)，然后繼續(xù)后向匹配查找。 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 11 第四章 LZ4 無損壓縮算法硬件實(shí)現(xiàn)方案 本章節(jié)提出了三個(gè)不同的硬件實(shí)現(xiàn)方案，每個(gè)方案都有各自的側(cè)重點(diǎn)，方案一簡單，方案二提高速度的同時(shí)減少 RAM 資源消耗，方案三壓縮速度快。 6）若 token 低 4 位為 15，則從 offset 的兩個(gè)字節(jié)后讀取兩個(gè)字節(jié)，將這兩個(gè)字節(jié)合并成一個(gè) 16 位的數(shù)據(jù) match length，不可匹配字符長度就等于 match length 加上 19。將第 1 17 個(gè)字節(jié)合并成一個(gè) 16 位的數(shù)據(jù) literal length，不可匹配字符長度就等于 literal length 加上 15。 8）待拷貝完成后，讀取下一個(gè) token，按照上述規(guī)則繼續(xù)往下解壓直到解壓到末尾地址結(jié)束。 5）根據(jù)不可匹配字符長度計(jì)算出 offset 的位置，讀取 offset 的倆個(gè)字節(jié)，將其拼接成一個(gè) 16 位的數(shù)據(jù)，根據(jù) offset 確定匹配的位置。 2）讀取 stream describe 判斷文件大小，確定末尾地址 3）讀取第一個(gè)序列的 token，即 stream describe 后一個(gè)字節(jié)。 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 9 3）若查找到了匹配則向后繼續(xù)查找計(jì)算匹配長度，否則返回第一步讀取后 4 個(gè)字節(jié)繼續(xù)查找。 ）如果 ref 在滑動窗口內(nèi)，且對應(yīng)的 4 個(gè)字節(jié)一樣，表明找到了 match，退出匹配查找。 ） ref 為初始值，沒有匹配，繼續(xù)往下查找。 計(jì)算哈 希值時(shí)，輸入為 4 個(gè)字節(jié)的二進(jìn)制數(shù)，輸出可以分為 2 字節(jié)值、 4 字節(jié)值兩種哈希值。 哈希表使用的內(nèi)存默認(rèn)值為 16KB，能裝進(jìn) L1 cache，這也是 LZ4 壓縮速度快的一個(gè)原因。這個(gè)哈希表的映射關(guān)系為 (key, value)： key 是 4 個(gè)字節(jié)的二進(jìn)制數(shù)。 當(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ù)。若按照原來的格式，則必須先計(jì)算出不可匹配字符長度，然后再將不可匹配字符輸出，這樣數(shù)據(jù)輸出的時(shí)間開銷將變大，因此會減小壓縮速度。 2）不能匹 配最后 12 個(gè)字節(jié)的數(shù)據(jù)。 （ 6） match length 表示匹配數(shù)據(jù)的長度。 （ 4） literals 該序列為未壓縮的數(shù)據(jù)，由原數(shù)據(jù)復(fù)制得到，該數(shù)據(jù)跟在 token 和 literal length 后面。 若 token 高 4 位等于 15，則需要在該序列后添加一個(gè)字節(jié)來表示完整的長度值。 圖 數(shù)據(jù)流格式簡圖 官方 LZ4 格式 LZ4 的格式如下 [9][11]： （ 1） 數(shù)據(jù)格式 每一個(gè)輸入的數(shù)據(jù)塊可以壓縮成若干個(gè)序列， 每個(gè)序列都包含有令牌（ token）、字符串（ literals）、字符串長度（ literal length）、偏移量（ offset）以及匹配長度（ match length）。 數(shù)據(jù)流格式 下圖給出了 LZ4 壓縮后的數(shù)據(jù)流格式 [10]，其中前面 4Byte 是表示這個(gè)文件是什么格式，通常是一個(gè)特定的數(shù)字來代表其是 LZ4 壓縮文件，后面的 315Byte 用來表示整個(gè)數(shù)據(jù)流的大小。而整個(gè) LZ4 壓縮后的文件就是有許多個(gè)類似的序列組合而成。 LZ4 算法簡介 LZ4 算法也屬于 LZ 系列算法，其主要概念與 LZ77 算法一致。冗余度 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 算法等。一個(gè)消息的可能性越小 ，其信息就越多；消息的可能性越大，其信息就越少。根據(jù)數(shù)據(jù)的信息量、熵和冗余度可以計(jì)算出壓縮后的最小體積，但是由于算法原理、數(shù)據(jù)格式不同會導(dǎo)致始終達(dá)不到理論值。 第七章是根據(jù)壓縮算法而做的解壓算法的 FPGA 實(shí)現(xiàn)，其中詳細(xì)介紹了解壓流程以及解壓程序中每個(gè)模塊的功能。 第三章對 LZ4 無損壓縮算法原理進(jìn)行了詳細(xì)的介紹，包括 LZ4 數(shù)據(jù)格式以及 LZ4 算法流程。通過對現(xiàn)有的 LZ4文獻(xiàn)以及官方的 C程序，了解并掌握 LZ4算法的壓縮和解壓原理。即它可以： l、提高了壓縮解壓的速度，有利于實(shí)時(shí)性處理； 節(jié)省了寶貴的 CPU 資源。特別是當(dāng)壓縮解壓大量數(shù)據(jù)時(shí)，占有的 CPU 資源是非常大的，而且由于 CPU 采用的指令工作方式使得速度很慢，另外系統(tǒng)非常不穩(wěn)定，很難滿足一些特殊環(huán)境下的應(yīng)用要求。 人們對無損壓縮技術(shù)的研究已經(jīng)有很長的一段時(shí)間，其中 LZ 系列的壓縮算法和最小冗余度構(gòu)造算法 Huffman 算法屬于最重要的無損壓縮技術(shù)。而且，經(jīng)過壓縮的數(shù)據(jù)在一定程度上是對原始數(shù)據(jù)的加密，從而更加地提高數(shù)據(jù)的安全性 [1]。 LZ4。目前，無損壓縮算法大多數(shù)都是基于軟件方式的實(shí)現(xiàn)，但是這在很多場合下已經(jīng)不能滿足高速數(shù)字系統(tǒng)的要求，所以基于硬件方 式的實(shí)現(xiàn)成為了新的研究熱點(diǎn)。 編號 南京航空航天大學(xué) 畢業(yè) 設(shè)計(jì) 題 目 無損數(shù)據(jù)壓縮算法的 FPGA 實(shí)現(xiàn) 學(xué)生姓名 梅發(fā)強(qiáng) 學(xué) 號 041220318 學(xué) 院 電子信息工程學(xué)院 專 業(yè) 信息工程 班 級 0412206 指導(dǎo)教師 劉偉強(qiáng) 副教授 二 〇一六 年五月 南京航空航天大學(xué) 本科畢業(yè)設(shè)計(jì)（論文）誠信承諾書 本人鄭重聲明：所呈交的畢業(yè)設(shè)計(jì)（論文）（題目： 無損數(shù)據(jù)壓縮算法的 FPGA 實(shí)現(xiàn) ）是本人在導(dǎo)師的指導(dǎo)下獨(dú)立進(jìn)行研究所取得的成果。目前已有 LZ7 LZ78及 LZW 等算法的硬件實(shí)現(xiàn)，但是都存在搜索窗口較小，壓縮率較低，速度較慢等缺陷。 Verilog。 數(shù)據(jù)壓縮通常分為無損壓縮和有損壓縮?，F(xiàn)在流行的壓縮技術(shù)基本上都是由這些算法衍生而來 [4][5]。所以，如何有效提高壓縮算法的效率，減少龐大數(shù)據(jù)量壓縮解壓給 CPU 和內(nèi)存帶來的壓力成為了現(xiàn)在壓縮解壓技術(shù)的主要發(fā)展方向。因?yàn)橛?件方式相比軟件方式實(shí)現(xiàn)的速度快很多，依靠電路實(shí)現(xiàn)不需要循環(huán)的指令計(jì)算，而且能夠采取并行的實(shí)現(xiàn)方式，這樣降低了資源和能源的消耗。在對 LZ4算法足夠了解后，將算法細(xì)分成幾個(gè)步驟得出算法流程圖。 第四章提供了三個(gè) LZ4 無損壓縮算法 的 硬件實(shí)現(xiàn)方案 ，并詳細(xì)介紹了每個(gè)方案的實(shí)現(xiàn)流程 以及每個(gè)方案的優(yōu)缺點(diǎn)，同時(shí)對其性能做出了詳細(xì)的比較。 第八章是對整個(gè)論文的總結(jié)。不過可以通過理論來知道為何數(shù)據(jù)可以被壓縮，也可以通過這些理論來指導(dǎo)數(shù)據(jù)壓縮的實(shí)現(xiàn)。 信息論中把一個(gè)事件（如字符）所攜帶的信息量定義為 [8]： （ ） 其中 P（ Xi）為實(shí)踐發(fā)生（字符 Xi）的概率。這些衍生改進(jìn)的算法統(tǒng)稱