基于LZW壓縮算法的以太網凈荷壓縮VLSI實現

馮肖雄　邱超

摘要：LZW算法是一種串表壓縮算法，在音視頻領域應用廣泛，本文充分利用該算法高壓縮率的特點，并提出一種適合VLSI的加速電路框架，將其運用在以太網報文傳輸領域中，通過優良的壓縮效果，極大程度提高了以太網報文有效載荷傳輸效率。

[關鍵詞]LZWVSLIFPGA

LZW算法應用在以太網業務傳輸的方式是將以太網輸入業務流的幀頭和凈荷剝離，只保留凈荷部分，并識別其為長度不一的“短語”，并把它們存入“短語字典”，同時給每個“短語”賦予一個碼字索引。只要短語的碼字比特短于短語的比特，就達到了壓縮的目的。數據的重復性越高，則匹配率越高，壓縮效果越顯著。另一個顯著提高壓縮率的方法是字典的容量，在LZW編碼算法中先建立初始字典，再分解輸入流為短語索引，這個短語若不在初始字典內，就將其存入擴展字典，擴展字典和初始字典共同構成編碼器的字典。建立初始字典是將擴展的ASCII碼存入，使其成為字典的前256項，即0～255項，而擴展字典根據版本資源情況而定，在壓縮率與資源之間尋求折中。

1算法原理

壓縮：

LZW的編碼原理是：先建立初始化字典，然后將待編碼的以太凈荷數據流分解成“短語詞條”。編碼器以字節為單位逐個輸入字符，并累積串聯成一個多字節的字符串，即"短語詞條”I。若I是字典中已有的索引項，則作為前綴與下一個字節x，形成新詞條Ix。當I在字典內，而Ix不在字典內時，編碼器首先輸出指向字典內詞條I的地址映射;再將Ix作為新索引項存入擴展字典，并為其確定新的地址空間;然后把x賦值給I，當做新詞條的前綴首字符。重復上述過程，直到輸入字節都處理完為止。

下面用實例說明LZW碼編碼過程：設輸入序列為acabfxxcomeon

（1）先建初始化字典，將ASCII碼的前256項輸入，即0～255項;

（2）將首字符a預置為前綴字符I，即I=a，查字典后知道I在字典內，那么繼續輸入序列的第二個字節c，即有Ix=ac，查字典后知道Ix不在字典內。則編碼器先輸出指向字典索引項I=a相應的碼字1，再把Ix=ac作為新詞條存入字典，并編碼得碼字為4。再將x賦值給I，即此時I=c，當作新詞條的前綴字符重復上述做法，得到編碼表，按照此遍歷的方法一直到報文的最后一個字符。

2電路實現結構

工作流程：

壓縮模塊基本結構如圖1所示，包括第1級FIFO模塊，負責將1G業務以太網報文進行轉存工作，該FIFO存儲報文時，會刪掉原始報文的包間隔信息，在FIFO的讀方向，會分離出報文頭部信息和Pload信息。

對于報文頭部信息，將其存到HeaderRAM模塊，Payload部分信息存入PayLoadRAM模塊中。當PayloadRAM模塊有報文存在時，啟動Compression模塊，讀取報文信息，并進行壓縮，將壓縮后的報文寫入CompressedDataRAM模塊，壓縮后的報文有時候長度可能比壓縮前的報文還長，如果遇到此情況，就讀取非壓縮的報文信息。這部分功能是在CompreSelect模塊中完成的。

當報文壓縮完畢后，啟動CombineHeader&Payload模塊，該模塊內部有調度狀態機，將報文頭信息和壓縮后的Payload信息進行組合，送給后級FIFO模塊，最后一級調度模塊將后級FIFO模塊中的報文進行組幀，發送壓縮報文到鏈路上。

3結論

本文提出了一種適配LZW壓縮算法的電路實現結構，并以1G報文業務壓縮為例，給出了VLSI實現模塊，后經過FPGA上板調試，實際進行Testcenter打流后，實測壓縮效果顯著，是一種非常高效的壓縮電路。

參考文獻

[1]吳宇新，余松煜.對LZW算法的改進及其在圖像無損壓縮中的應用，上海交通大學圖像通信與信息處理研究所，1998（09）：34-35.