Throughput-Optimal Hardware Implementation of LZW Decompression on the FPGA

The main contribution of this paper is to present a throughput-optimal FPGA implementation of LZW decompression algorithm. Since LZW decompression creates a dictionary table by reading codes of a compressed file one by one, its parallelization is not an easy task. However, in this work, continuously given LZW-compressed codes, the proposed circuit can decompress them with no interruption. In the same time, the circuit starts outputting the decompressed byte-data in several clock cycles after the first code of the input is provided. We have the proposed circuit on Xilinx Virtex-7 XCVX485T-2 and evaluated the performance. The experimental results show that our proposed circuit can decompress a LZW-compressed TIFF image of size 4096x3072 in 42.82 ms.

I. Introduction

Lossless data compression that preserves all information of the original data is one of the most important tasks in the area of computer engineering. It is always used to improve the efficiency of data transmission and save the storage of data. In this paper, we focus on LZW compression [1] which is used in Unix utility “compress” and in GIF image format. LZW compression is included in TIFF standard [2], which is widely used in the area of commercial digital printing. Since dictionary tables are created by reading input data one by one, LZW compression and decompression are hard to parallelize. The main goal of this paper is to develop an efficient hardware architecture of LZW decompression and implement it in an FPGA.