Graphics Interchange Format - Unisys and LZW Patent Enforcement

Unisys and LZW Patent Enforcement

In 1977 and 1978, Jacob Ziv and Abraham Lempel published a pair of papers on a new class of lossless data-compression algorithms, now collectively referred to as LZ77 and LZ78. In 1983, Terry Welch developed a fast variant of LZ78 which was named Lempel–Ziv–Welch (LZW).

Welch filed a patent application for the LZW method in June 1983. The resulting patent, US 4558302, granted in December 1985, was assigned to Sperry Corporation who subsequently merged with Burroughs Corporation in 1986 and formed Unisys. Further patents were obtained in the United Kingdom, France, Germany, Italy, Japan and Canada.

In June 1984, an article by Welch was published in the IEEE magazine which publicly described the LZW technique for the first time. LZW became a popular data compression technique and, when the patent was granted, Unisys entered into licensing agreements with over a hundred companies.

The popularity of LZW led CompuServe to choose it as the compression technique for their GIF format, developed in 1987. At the time, CompuServe was not aware of the patent. Unisys became aware that the GIF format used the LZW compression technique and entered into licensing negotiations with CompuServe in January 1993. The subsequent agreement was announced on 24 December 1994. Unisys stated that they expected all major commercial on-line information services companies employing the LZW patent to license the technology from Unisys at a reasonable rate, but that they would not require licensing, or fees to be paid, for non-commercial, non-profit GIF-based applications, including those for use on the on-line services.

Following this announcement, there was widespread condemnation of CompuServe and Unisys, and many software developers threatened to stop using the GIF format. The PNG format (see below) was developed in 1995 as an intended replacement. However, obtaining support from the makers of Web browsers and other software for the PNG format proved difficult and it was not possible to replace the GIF format, although PNG has gradually increased in popularity. The libungif library allowed GIFs to be decoded but not encoded without use of the Unisys LZW patent.

In August 1999, Unisys changed the details of their licensing practice, announcing the option for owners of Billboard and Intra net Web sites to obtain licenses on payment of a one-time license fee of $5000 or $7500. Such licenses were not required for website owners or other GIF users who had used licensed software to generate GIFs. Nevertheless, Unisys was subjected to thousands of online attacks and abusive emails from users believing that they were going to be charged $5000 or sued for using GIFs on their websites. Despite giving free licenses to hundreds of non-profit organizations, schools and governments, Unisys was completely unable to generate any good publicity and continued to be condemned by individuals and organizations such as the League for Programming Freedom who started the "Burn All GIFs" campaign.

The US LZW patent expired on 20 June 2003. The counterpart patents in the United Kingdom, France, Germany and Italy expired on 18 June 2004, the Japanese counterpart patents expired on 20 June 2004 and the counterpart Canadian patent expired on 7 July 2004. Consequently, while Unisys has further patents and patent applications relating to improvements to the LZW technique, the GIF format may now be used freely