Lossless Data Compression for Embedded Systems

Many of today's embedded systems are providing more sophisticated solutions to a wide variety of applications and industries. With this increase in sophistication, there is a corresponding increase in the amount of data being collected and stored. This rise in data volume is placing even more emphasis on design solutions that need to meet stringent performance requirements while staying within cost targets.

Collecting and storing large amounts of data can create a number of technical challenges. In addition, the embedded system itself can become overtaxed by the increased burden imposed by processing large amounts of data. Faced with the issues of collecting and storing data, embedded system designers are finding data compression as a viable means of dealing with large amounts of data.

Embedded Data Compression
Data compression is all around us. We see it in a variety of products, such as, high definition televisions, DVD and MP3 players, cell phones, digital cameras, fax machines, automobiles, etc. When you look at all the embedded products out there you will quickly see that data compression is an integral part of their operation.

There are a significant number of data compression techniques available to meet the specific needs of most applications. But whatever the solution may be, all compression algorithms fall into two main categories, lossy and lossless data compression.

Lossy data compression is used in applications where an acceptable amount of data loss is allowed in the compression algorithm. We see lossy data compression predominantly in the areas of imagery, video, and audio applications.

When it comes to lossless data compression, there are two options you can choose, Statistical or Dictionary-Based compression methods. The method chosen is based primarily upon the type of data being compressed.

Statistical-based compression programs exploit the statistical redundancy of individual characters within the data. The program counts each individual character and determines its frequency of occurrence. Those characters with the highest frequency of occurrence are assigned the shortest codes, thereby taking up less memory.

Dictionary-based compression programs do not use statistics or variable-length codes. Instead they select strings of characters and encode each string as a fixed-length token using a dictionary. For each string of characters that occur in the data, a token is used to represent it. Dictionary-based compression is the most popular method used for lossless data compression.

Lossless Data Compression
Lossless data compression, as its name implies, is the process of compressing data without altering or destroying its original content. This form of compression is specifically for applications where a loss in data cannot be tolerated.

There are a number of lossless data compression algorithms to choose from and most vary in methodology, code size and complexity. The one you choose will depend primarily on the specific structure of the data, as well as the objectives of your particular application.

A number of websites offer embedded source code that is compatible with most of the popular compression standards, such as PKZIP, GZIP, 7ZIP, or UNIX's Compress program.

Whichever compression standard is chosen, chances are it will require a large amount of RAM memory. Typically, the more RAM you dedicate to the compression program the higher the compression ratio.

However, not all embedded systems support large blocks of RAM memory that can be allocated to a hungry compression algorithm. For embedded designs with limited RAM memory the challenge is to find software that can achieve acceptable efficiencies within a small memory footprint.

This article describes a lossless compression algorithm based on the popular LZW compression standard. This compression technique is capable of achieving respectable compression ratios, typically on the order of 50 " 60%, while consuming about 2K of RAM. In larger RAM memory sizes, 8K or 16K, it is possible to achieve 80% efficiency or more.