基于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.