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

1

概念

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

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

例如，我們要傳送一個1，而用64位來傳輸的話就需要表示為00000000_00000000_00000000_00000000_00000000_000000000_00000000_00000001，用這樣的方式來傳輸一個1需要消耗8Byte的存儲，屬實是很浪費存儲空間，而使用Varint編碼對它進行壓縮后，我們只需要一個Byte就能將它傳輸出去，大大節省了存儲空間，避免了資源的浪費。

2

設計原理

下面我們就來介紹一下Varint編碼是如何對原有數據進行編碼處理的。在介紹Varint編碼原理之前，我們先介紹一下字節數據的兩種排序方式，大端和小端。大端數據指的是將高位的數據存在低位的地址中，例如將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，即逆序存入寄存器中，這種方式就稱之為大端序。小端序即反之，高位的數據存入高地址，低位的數據放入低地址。

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

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

（1）首先從最后一個字節開始進行編碼，最后一個字節為00110011，按照編碼規則我們取后七位，即截取0110011，因為后面還有數據，則最高位取1，然后與截取的有效數據組合在一起組成第一個有效數據組10110011，然后放在整個數據的最高位。

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

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

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

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

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

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

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

3

架構設計

設計架構如下圖：

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

仿真測試及結果

仿真測試代碼如下：

`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

仿真結果：

將得到的仿真結果與上文經過Varint編碼壓縮后的結果對比可知，仿真結果正確。

6

總結

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

原文標題：壓縮算法 | 基于FPGA的Varint編碼實現（附代碼）

文章出處：【微信公眾號：FPGA技術江湖】歡迎添加關注！文章轉載請注明出處。

責任編輯：haq