今天是畫師第二次和各位大俠見面，執(zhí)筆繪畫FPGA江湖，本人最近項目經(jīng)驗，寫了篇基于FPGA的Varint編碼（壓縮算法）實現(xiàn)，這里分享給大家，僅供參考。如有轉(zhuǎn)載，請在文章底部留言，請勿隨意轉(zhuǎn)載，否則有責(zé)必究。

1

概念

什么是Varint編碼呢？首先我們來介紹一下Varint編碼，Varint編碼就是一種用一個或多個字節(jié)將數(shù)據(jù)序列化，并對數(shù)據(jù)進行壓縮的方法，因此也可以稱之為Varint壓縮算法。

在進行數(shù)據(jù)傳輸過程，我們經(jīng)常用大位寬來進行數(shù)據(jù)的傳輸。有時候是32位或者64位傳輸某個數(shù)據(jù)，然而，一直使用大位寬來傳輸數(shù)據(jù)也有它的缺點，比如傳輸很小的數(shù)據(jù)時，會造成資源的浪費。

例如，我們要傳送一個1，而用64位來傳輸?shù)脑捑托枰硎緸?0000000_00000000_00000000_00000000_00000000_000000000_00000000_00000001，用這樣的方式來傳輸一個1需要消耗8Byte的存儲，屬實是很浪費存儲空間，而使用Varint編碼對它進行壓縮后，我們只需要一個Byte就能將它傳輸出去，大大節(jié)省了存儲空間，避免了資源的浪費。

2

設(shè)計原理

下面我們就來介紹一下Varint編碼是如何對原有數(shù)據(jù)進行編碼處理的。在介紹Varint編碼原理之前，我們先介紹一下字節(jié)數(shù)據(jù)的兩種排序方式，大端和小端。大端數(shù)據(jù)指的是將高位的數(shù)據(jù)存在低位的地址中，例如將0x01234567存入一個64位的寄存器reg，則存入高位reg［7］的是7，然后依次是reg［6］=6、reg［5］=5、reg［4］=4、reg［3］=3、reg［2］=2、reg［1］=1、reg［0］=0，即逆序存入寄存器中，這種方式就稱之為大端序。小端序即反之，高位的數(shù)據(jù)存入高地址，低位的數(shù)據(jù)放入低地址。

在這基礎(chǔ)上我們再來講Varint編碼的原理，Varint編碼使用的就是大端序。Varint編碼將有無效數(shù)據(jù)去除，然后將效數(shù)據(jù)分成若干個組，每個組為8位，即一個字節(jié)，除去最后一個字節(jié)外，其余有效組最高位均為1，最后一個字節(jié)最高位為0。有效組最高位為1即代表這個字節(jié)后面還有有效數(shù)據(jù)組，當(dāng)有效數(shù)據(jù)組最高位為0時則代表當(dāng)前有效組為最后一個有效字節(jié)，除去最高位，其余位均為有效數(shù)據(jù)。

我們可以舉個例子來更加詳細的說明這個原理。 仍然以64位數(shù)據(jù)為例，如00000000_00000000_00010001_11011001_00110011_10101001_11001100_00110011。編碼步驟如下：

（1）首先從最后一個字節(jié)開始進行編碼，最后一個字節(jié)為00110011，按照編碼規(guī)則我們?nèi)『笃呶?，即截?110011，因為后面還有數(shù)據(jù)，則最高位取1，然后與截取的有效數(shù)據(jù)組合在一起組成第一個有效數(shù)據(jù)組10110011，然后放在整個數(shù)據(jù)的最高位。

（2）然后是第二個數(shù)據(jù)，同樣往前取七位，得到0011000，同樣在本組最高位補1，即得到10011000，組合第一個數(shù)據(jù)組則為10110011_10011000。

（3）第三個數(shù)據(jù)，再往前取七位，得到0100111，在本有效數(shù)據(jù)組最高位補1，得到10100111，再拼接到前面的有效數(shù)據(jù)組之后，即10110011_10011000_10100111。

（4）第四個數(shù)據(jù)，同樣的方式往前取七位，得到0011101，最高位補1，得到10011101，繼續(xù)拼接在有效數(shù)據(jù)組后面，即10110011_10011000_10100111_10011101。

（5）第五個數(shù)據(jù)，再往前取七位，得到0010011，在最高位補1，得到10010011，繼續(xù)往有效數(shù)據(jù)組后拼接，得到10110011_10011000_10100111_10011101_10010011。

（6）第六個數(shù)據(jù)，按照上述方法，可得10111011，拼接后可得10110011_10011000_10100111_10011101_10010011_10111011。

（7）第七個數(shù)據(jù)，取得0000100，由觀察得知，這個有效數(shù)據(jù)組之后均為0，即有效數(shù)據(jù)已全部截取完畢，則按照Varint編碼規(guī)則，最高位補0，完成編碼，將數(shù)據(jù)全部拼接后得到進行Varint編碼后的數(shù)據(jù)，即10110011_10011000_10100111_10011101_10010011_10111011_00000100。

將上述進行Varint編碼后得到的有效數(shù)據(jù)組與原數(shù)據(jù)相比，節(jié)省了一個字節(jié)的存儲資源。解碼只要將上述過程逆序進行即可，這里就不過多贅述。熟悉完了Varint編碼的原理，下面我們就可以開始進行設(shè)計了。

3

架構(gòu)設(shè)計

設(shè)計架構(gòu)如下圖：

將本設(shè)計模塊命名為varint_encode，clk為輸入時鐘，rst_n為復(fù)位信號，idata為64位是輸入數(shù)據(jù)，ivalid為數(shù)據(jù)有效信號，odata0~odata7為輸出的有效數(shù)據(jù)，ovalid0~ovalid7為伴隨輸出有效數(shù)據(jù)的數(shù)據(jù)有效信號。由于FPGA輸出的數(shù)據(jù)位寬都是固定的，因此需要將各個壓縮后的位寬都定義一遍。

仿真測試及結(jié)果

仿真測試代碼如下：

`timescale 1ns/1ps

module varint_encode_tb;

reg clk; reg rst_n; reg ivalid; reg ［63:0］ idata; wire ［63:0］ odata0; wire ［55:0］ odata1; wire ［47:0］ odata2; wire ［39:0］ odata3; wire ［31:0］ odata4; wire ［23:0］ odata5; wire ［15:0］ odata6; wire ［7:0］ odata7; wire ovalid0; wire ovalid1; wire ovalid2; wire ovalid3; wire ovalid4; wire ovalid5; wire ovalid6; wire ovalid7;

varint_encode varint_encode_inst（

.clk （clk）， .rst_n （rst_n）， .idata （idata）， .ivalid （ivalid）， .odata0 （odata0）， .odata1 （odata1）， .odata2 （odata2）， .odata3 （odata3）， .odata4 （odata4）， .odata5 （odata5）， .odata6 （odata6）， .odata7 （odata7）， .ovalid0 （ovalid0）， .ovalid1 （ovalid1）， .ovalid2 （ovalid2）， .ovalid3 （ovalid3）， .ovalid4 （ovalid4）， .ovalid5 （ovalid5）， .ovalid6 （ovalid6）， .ovalid7 （ovalid7） ）;

initial clk = 1‘b0; always # 10 clk = ~clk; initial begin rst_n = 1’b0; ivalid = 1‘b0; idata = 64’d0; # 201; rst_n = 1‘b1; # 200;

@ （posedge clk）; # 2; idata = 64’b00000000_00000000_00010001_11011001_00110011_10101001_11001100_00110011; ivalid = 1‘b1; @ （posedge clk）; # 2; idata = 64’d0; ivalid = 1‘b0; @ （posedge clk）; # 2; idata = 64’b00000000_00000001_00010001_11011001_00110011_10101001_11001100_00110011; ivalid = 1‘b1; @ （posedge clk）; # 2; idata = 64’d0; ivalid = 1‘b0; @ （posedge clk）; # 2; idata = 64’b00000000_00000000_00000001_11011001_00110011_10101001_11001100_00110011; ivalid = 1‘b1; @ （posedge clk）; # 2; idata = 64’d0; ivalid = 1‘b0; @ （posedge clk）; # 2; idata = 64’b00000000_00000000_00000000_00000001_00110011_10101001_11001100_00110011; ivalid = 1‘b1; @ （posedge clk）; # 2; idata = 64’d0; ivalid = 1‘b0; @ （posedge clk）; # 2; idata = 64’b00000000_00000000_00000000_00000000_00000000_10101001_11001100_00110011; ivalid = 1‘b1; @ （posedge clk）; # 2; idata = 64’d0; ivalid = 1‘b0; # 2000; $stop; end

endmodule

仿真結(jié)果：

將得到的仿真結(jié)果與上文經(jīng)過Varint編碼壓縮后的結(jié)果對比可知，仿真結(jié)果正確。

6

總結(jié)

在進行原理理解與設(shè)計實現(xiàn)的時候，需要注意，逆序是字節(jié)的逆序，并非每一bit的數(shù)據(jù)都要進行逆序，且最高位是補位，代表后面還有無數(shù)據(jù)，并非是實際數(shù)據(jù)，在進行解碼的時候要注意去掉每一個有效數(shù)據(jù)組的最高位，再進行拼接，這樣得到的數(shù)據(jù)才是正確的數(shù)據(jù)，否則得到的將是錯誤數(shù)據(jù)。考慮到FPGA位寬定義的局限性，需要對每一個可能性的位寬大小均進行定義，并且定義一個相應(yīng)的脈沖信號，告訴后級模塊哪一個數(shù)據(jù)是有效的，這樣設(shè)計才不會出錯，否則輸出的大小與原來輸入的大小相同，也就失去了設(shè)計的意義。

原文標(biāo)題：壓縮算法 | 基于FPGA的Varint編碼實現(xiàn)（附代碼）

文章出處：【微信公眾號：FPGA技術(shù)江湖】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。

責(zé)任編輯：haq