基于LZW壓縮算法的以太網(wǎng)凈荷壓縮VLSI實(shí)現(xiàn)

馮肖雄　邱超

摘要：LZW算法是一種串表壓縮算法，在音視頻領(lǐng)域應(yīng)用廣泛，本文充分利用該算法高壓縮率的特點(diǎn)，并提出一種適合VLSI的加速電路框架，將其運(yùn)用在以太網(wǎng)報(bào)文傳輸領(lǐng)域中，通過(guò)優(yōu)良的壓縮效果，極大程度提高了以太網(wǎng)報(bào)文有效載荷傳輸效率。

[關(guān)鍵詞]LZWVSLIFPGA

LZW算法應(yīng)用在以太網(wǎng)業(yè)務(wù)傳輸?shù)姆绞绞菍⒁蕴W(wǎng)輸入業(yè)務(wù)流的幀頭和凈荷剝離，只保留凈荷部分，并識(shí)別其為長(zhǎng)度不一的“短語(yǔ)”，并把它們存入“短語(yǔ)字典”，同時(shí)給每個(gè)“短語(yǔ)”賦予一個(gè)碼字索引。只要短語(yǔ)的碼字比特短于短語(yǔ)的比特，就達(dá)到了壓縮的目的。數(shù)據(jù)的重復(fù)性越高，則匹配率越高，壓縮效果越顯著。另一個(gè)顯著提高壓縮率的方法是字典的容量，在LZW編碼算法中先建立初始字典，再分解輸入流為短語(yǔ)索引，這個(gè)短語(yǔ)若不在初始字典內(nèi)，就將其存入擴(kuò)展字典，擴(kuò)展字典和初始字典共同構(gòu)成編碼器的字典。建立初始字典是將擴(kuò)展的ASCII碼存入，使其成為字典的前256項(xiàng)，即0～255項(xiàng)，而擴(kuò)展字典根據(jù)版本資源情況而定，在壓縮率與資源之間尋求折中。

1算法原理

壓縮：

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

下面用實(shí)例說(shuō)明LZW碼編碼過(guò)程：設(shè)輸入序列為acabfxxcomeon

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

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

2電路實(shí)現(xiàn)結(jié)構(gòu)

工作流程：

壓縮模塊基本結(jié)構(gòu)如圖1所示，包括第1級(jí)FIFO模塊，負(fù)責(zé)將1G業(yè)務(wù)以太網(wǎng)報(bào)文進(jìn)行轉(zhuǎn)存工作，該FIFO存儲(chǔ)報(bào)文時(shí)，會(huì)刪掉原始報(bào)文的包間隔信息，在FIFO的讀方向，會(huì)分離出報(bào)文頭部信息和Pload信息。

對(duì)于報(bào)文頭部信息，將其存到HeaderRAM模塊，Payload部分信息存入PayLoadRAM模塊中。當(dāng)PayloadRAM模塊有報(bào)文存在時(shí)，啟動(dòng)Compression模塊，讀取報(bào)文信息，并進(jìn)行壓縮，將壓縮后的報(bào)文寫(xiě)入CompressedDataRAM模塊，壓縮后的報(bào)文有時(shí)候長(zhǎng)度可能比壓縮前的報(bào)文還長(zhǎng)，如果遇到此情況，就讀取非壓縮的報(bào)文信息。這部分功能是在CompreSelect模塊中完成的。

當(dāng)報(bào)文壓縮完畢后，啟動(dòng)CombineHeader&Payload模塊，該模塊內(nèi)部有調(diào)度狀態(tài)機(jī)，將報(bào)文頭信息和壓縮后的Payload信息進(jìn)行組合，送給后級(jí)FIFO模塊，最后一級(jí)調(diào)度模塊將后級(jí)FIFO模塊中的報(bào)文進(jìn)行組幀，發(fā)送壓縮報(bào)文到鏈路上。

3結(jié)論

本文提出了一種適配LZW壓縮算法的電路實(shí)現(xiàn)結(jié)構(gòu)，并以1G報(bào)文業(yè)務(wù)壓縮為例，給出了VLSI實(shí)現(xiàn)模塊，后經(jīng)過(guò)FPGA上板調(diào)試，實(shí)際進(jìn)行Testcenter打流后，實(shí)測(cè)壓縮效果顯著，是一種非常高效的壓縮電路。

參考文獻(xiàn)

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