An Improvement of PDLZW implementation with a Modified WSC Updating Technique on FPGA

Authors: Perapong Vichitkraivin, Orachat Chitsobhuk

Abstract:

In this paper, an improvement of PDLZW implementation with a new dictionary updating technique is proposed. A unique dictionary is partitioned into hierarchical variable word-width dictionaries. This allows us to search through dictionaries in parallel. Moreover, the barrel shifter is adopted for loading a new input string into the shift register in order to achieve a faster speed. However, the original PDLZW uses a simple FIFO update strategy, which is not efficient. Therefore, a new window based updating technique is implemented to better classify the difference in how often each particular address in the window is referred. The freezing policy is applied to the address most often referred, which would not be updated until all the other addresses in the window have the same priority. This guarantees that the more often referred addresses would not be updated until their time comes. This updating policy leads to an improvement on the compression efficiency of the proposed algorithm while still keep the architecture low complexity and easy to implement.

Keywords: lossless data compression, LZW algorithm, PDLZW algorithm, WSC and dictionary update.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1070793

References:

[1] T.A. Welch, "A Technique for High-Performance Data Compression," IEEE Computer , vol. 17, no. 6, pp. 8-19, June, 1984.
[2] J. Jiang and S. Jones, "Word-based dynamic algorithms for data compression," Proc. Inst. Elect. Eng.-I , vol. 139, no. 6, pp. 582-586, Dec 1992.
[3] M.-B. Lin, "A parallel VLSI architecture for the LZW data compression algorithm," J. VLSI Signal Process. , vol. 26, no. 3, pp. 369-381, Nov. 2000.
[4] Ch. Su, Ch. Fan and J. Ch. Yo, "Hardware efficient updating technique for LZW CODEC design", 1997 IEEE International Symposium on Circuits and Systems , pp. 2797-2800, June 1997.
[5] The Canterbury Corpus file for testing new compression algorithms. Available: http://corpus.canterbury.ac.nz/index.html.