An improved LZW data compression algorithm and its VLSI implementation

Improved LZW algorithm was introduced. By adding a preprocessor to conventional LZW configuration for decreasing correlation between original data, the single large dictionary in conventional implementation was partitioned into a dictionary set that consisted of several small address space dictionaries. As doing so the dictionary set has small lookup time, and can operate in parallel. Besides, XOR-based hash function, which computed the dictionary index as the exclusive-or of the parent index and the present character, has been applied. Simulation results show that the improved algorithm has better compression ratio for image data than conventional LZW algorithm and DLZW (dynamic LZW) algorithm, and has competitive performance for text data with DLZW algorithm. The parallel VLSI implementation of the improved algorithm is proposed, and is realized using FPGA XC4VLX15-10. Experiment results show that the chip can yield a compression rate of 198.4 Mbytes/s, it is about 6.9 times the compression rate of implementing conventional LZW, and 3.2 times the compression rate of implementing DLZW.