基于FPGA的Varint編碼設(shè)計(jì)原理和實(shí)現(xiàn)

今天是畫師第二次和各位大俠見面，執(zhí)筆繪畫FPGA江湖，本人最近項(xiàng)目經(jīng)驗(yàn)，寫了篇基于FPGA的Varint編碼（壓縮算法）實(shí)現(xiàn)，這里分享給大家，僅供參考。如有轉(zhuǎn)載，請(qǐng)?jiān)谖恼碌撞苛粞裕?qǐng)勿隨意轉(zhuǎn)載，否則有責(zé)必究。

1

概念

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

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

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

2

設(shè)計(jì)原理

下面我們就來介紹一下Varint編碼是如何對(duì)原有數(shù)據(jù)進(jìn)行編碼處理的。在介紹Varint編碼原理之前，我們先介紹一下字節(jié)數(shù)據(jù)的兩種排序方式，大端和小端。大端數(shù)據(jù)指的是將高位的數(shù)據(jù)存在低位的地址中，例如將0x01234567存入一個(gè)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ǔ)上我們?cè)賮碇vVarint編碼的原理，Varint編碼使用的就是大端序。Varint編碼將有無效數(shù)據(jù)去除，然后將效數(shù)據(jù)分成若干個(gè)組，每個(gè)組為8位，即一個(gè)字節(jié)，除去最后一個(gè)字節(jié)外，其余有效組最高位均為1，最后一個(gè)字節(jié)最高位為0。有效組最高位為1即代表這個(gè)字節(jié)后面還有有效數(shù)據(jù)組，當(dāng)有效數(shù)據(jù)組最高位為0時(shí)則代表當(dāng)前有效組為最后一個(gè)有效字節(jié)，除去最高位，其余位均為有效數(shù)據(jù)。

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

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

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

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

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

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

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

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

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

3

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

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

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

仿真測(cè)試及結(jié)果

仿真測(cè)試代碼如下：

`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é)果對(duì)比可知，仿真結(jié)果正確。

6

總結(jié)

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

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

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

責(zé)任編輯：haq