An Efficient Implementation of LZW Decompression Using Block RAMs in the FPGA (Preliminary Version)

Abstract

LZW algorithm is one of the most important compression and decompression algorithms. The main contribution of this paper is to present an efficient hardware architecture of LZW decompression algorithm and to implement it in an FPGA. In our implementation, the codes of a compressed file is read one by one, and the dictionary table is continuously updated until the table is full. For each code of the compressed file, an inverse of string corresponding to this code is sequentially written to an output buffer. The length of this string and the address of the forefront of this string is stored. The inverse of string can be output reversely from the output buffer using the stored length and forefront address. Since output buffer uses dual-port block RAMs, input of the inverse strings and output of the original strings are performed in parallel. The experimental results show that our FPGA module of LZW decompression on Virtex-7 family FPGA uses 287 slice registers, 282 slice LUTs and 7 block RAMs with 36k-bit. One LZW decompression module is more than 2 times faster than sequential LZW decompression on a single CPU. Since the proposed FPGA module uses a few resources of the FPGA, we implement 34 LZW decompression modules which works in parallel in the FPGA. In other words, our implementation runs up to 64 times faster than sequential LZW decompression on a single CPU.