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

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.

Authors:

• Perapong Vichitkraivin
• Orachat Chitsobhuk

Keywords:

• lossless data compression
• LZW algorithm
• PDLZW algorithm
• WSC and dictionary update.

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.