FPGA-Based Lossless Data Compression using Huffman and LZ77 Algorithms

Abstract

Lossless data compression algorithms are widely used by data communication systems and data storage systems to reduce the amount of data transferred and stored. GZIP is a popular, patent-free compression program that delivers good compression ratios. This paper presents hardware implementations for the LZ77 encoders and Huffman encoders that form the basis for a full hardware implementation of a GZIP encoder. The designs have been implemented as state machines in VHDL in such a way that they are suitable for implementation using either FPGA or ASIC technologies. Performance metrics and resource utilization results obtained for a prototype implementation running on an Altera DE2 board are presented. Ultimately, the goal is to utilized the LZ77 encoders and Huffman encoders described in this paper to build a fully-functional, hardware design for a GZIP encoder that could be used in data communication systems and data storage systems to boost overall system performance.