The patent describes a compression algorithm known commonly as LZW after its inventors, Abraham Lempel, Jacob Ziv, and Terry Welch. (Welch alone is listed as the inventor on patent 4,558,302, though this work was derived from an earlier patent which names Lempel and Ziv as well.)

Sperry merged with Burroughs Corporation in 1986 to form the Unisys Corporation. Unisys retained all of Sperry's patents, including LZW, which it will continue to hold until the patent's expiration in 2003.

US Patent 4,558,302

(By no means is LZW specific to GIF files; the algorithm is also used in the TIFF image format, as well as a number of compression programs and hardware devices. However, this analysis focuses on its use in GIFs.)

CompuServe's engineers decided to use the LZW algorithm for the compression part of the GIF standard. When work started on the GIF format, CompuServe was unaware of the Unisys patent on the algorithm. Because the LZW algorithm had been so widely described in printed articles and other references, the programmers at CompuServe assumed that the algorithm was in the public domain.

In 1988, one of the GIF principals allegedly discovered that the compression algorithm was patented, and reported this information to management for further inquiry. CompuServe then contacted Unisys and was not told to discontinue use of LZW or to pay any royalties. To date, however, none of these allegations have been confirmed by either company. What is known is that CompuServe and others continued to use GIF freely and without interference from Unisys, for seven years.

In 1994, CompuServe and Unisys announced plans for a license fee to the public. Software companies selling products which made use of the GIF format would be required to pay Unisys 0.45% of the selling price (with a ten-cent minimum and ten-dollar maximum). No payment of any royalty to CompuServe was required; as had been the case before, CompuServe's contribution remained free to the public.

Unisys stirred up a furious response in early 1999 when it demanded that some operators of noncommercial web sites containing GIF images pay the company a one-time license fee of $5000, whether or not the images had been created with licensed software. Unisys demanded even larger payments from some commercial sites. In the case of AccuWeather, Inc., operator of the accuweather.com, Unisys demanded a license fee of $3.8 million. (AccuWeather refused to agree to the terms of the license and subsequently switched to another file format.)

AccuWeather Case

Looking for a non-patented replacement to GIF, a new graphics standard, PNG (Portable Network Graphics) was developed with the help of CompuServe. Technically, PNG is superior to GIF as a lossless compression standard, producing smaller files with no difference in quality; unfortunately, as of May 2000, support for the format in applications is not nearly as widespread as GIF. Additionally, PNG does not (yet) support animated images, which limits the use of PNG in online advertisements.

Not surprisingly, libertarians on the web railed against Unisys. The emergence of new standards like PNG led to such net events as Burn All GIFs Day, in which webmasters were implored to take all of the GIF images off of their sites and replace them identical images in other, free formats.

Seeking to avoid negative publicity, Unisys backed off from its hard-line public stance on the issue, but still requires license fees for use of LZW in software and in images on the web, and continues to be successful in collecting fees from software developers.

The PNG Standard

CompuServe had alternatives to LZW compression when it created the GIF standard, but they were less appealing, and there appeared to be no compelling reason not to use LZW, since it was mistakenly assumed to be patent-free.

In turn, many other software developers turned to GIF since they assumed that it too would be free. "If we had known," said one developer quoted on the web, "we would never have used it." Clear alternatives existed, but CompuServe's failure to discover the patent, combined with Unisys's failure to aggressively defend its patent from the outset, created a vaccuum of information.

This "bait-and-switch" scenario that makes the LZW patent and its applicability to GIF images both so interesting and troubling. Among the problems that the League for Programming Freedom claims for software patents is that the sheer number of patents makes searching for and identifying relevant patents extremely difficult.

The LZW case illustrates one of the biggest problems with software patents--the very nature of software and algorithms leads programmers and scientists to freely adopt and exchange ideas that have been published in academic and non-academic literature. Without clear indication that a particular idea or algorithm has been patented (or has a patent pending), the alternative is for programmers to ignore everything of uncertain origin. Clearly, this solution does not seem optimal, since its primary consequence would be to thwart progress.