Frank Wolff
Department of EECS, Case School of Engineering
Lempel-Ziv compression (LZ77, LZ78, LZW) schemes are well known in the software
world. These schemes belong to a family of dictionary-based compression techniques
using a sliding text window. They are also lossless by nature as opposed to
other lossy compression techniques used in image compression such as JPEG
or MPEG formats. LZW compression not only reduces the size of the data but
also reduces the communication time to transfer this reduced data. Examples
of software tools that successfully employ LZW techniques are PKZip, GNU gzip,
GIF and PNG image formats.
Recently, LZW techniques are finding their way into hardware, specifically
embedded systems such as Internet Appliances, PDAs, cell phones, etc. Embedded
systems handle and manipulate large volumes of data in real-time. Systems
on a Chip (SoC) are an enabling technology for embedded systems, and this
facilitates the implementation of LZW hardware compression of embedded data
and Field Programmable Gate Arrays (FPGAs).
One approach to alleviate these problems is to reduce the volume of test
data by using data compression techniques. In this talk, we will present a
novel adaptation of the much-utilized Lempel-Ziv compression in software as
it applies directly to hardware. The compression scheme is adapted to accommodate
bit strings rather than character sets. Moreover, we exploit the large presence
of don't cares in uncompressed test sets that we generated using commercial
ATPG tools and reconfigurable data as applied to FPGAs.