GIF and LZW patents: how compression shaped the history of PNG

The 1977 paper by Jacob Ziv and Abraham Lempel belongs to the LZ77 family, which refers back to sequences already encountered. LZ78, associated with their 1978 paper, builds a dictionary of sequences. DEFLATE, later used by PNG, combines LZ77 with Huffman coding; it is distinct from the LZW used in GIF.

In June 1984, Terry A. Welch published a description of fast dictionary compression based on LZ78. LZW stands for Lempel–Ziv–Welch. Publication of an algorithm does not mean that implementations are free of patent claims. Treating “publicly described” as “unrestricted to implement” misses the central issue in this history.

LZW represents recurring sequences with dictionary codes. If the encoder and decoder share the initial dictionary and update rules, the decoder can reconstruct the sequences without receiving the completed dictionary. This teaching example starts with A=0 and B=1. It is not a GIF byte stream.

The output is 0, 1, 2, 4. The decoder emits A, B and AB while growing its dictionary. When it receives the final code 4 before that entry exists, it reconstructs ABA by appending the first symbol of the previous sequence, AB, to that sequence. This special case applies when the received code is the next code to be assigned.

Seven characters becoming four codes does not imply a file size of 4/7 of the original. Code widths, initialization and end codes, image headers and other overhead also matter. Short or poorly repetitive input can become larger.

CompuServe’s GIF87a specification is dated June 15, 1987. GIF applies LZW to a sequence of color-table indices rather than to the color values themselves. A color table has at most 256 entries. Although LZW is lossless, reducing a photograph to a limited palette can lose color information before compression begins.

Under GIF89a, a minimum code size of m gives an initial code width of m+1 bits, with a maximum of 12 bits. With m=8, codes start at nine bits, but that is not universal. Even a two-color image uses m=2. A Clear code resets the dictionary; an End of Information code ends the data. Reaching the dictionary limit does not require an immediate Clear code.

GIF87a already allowed multiple images in a data stream. GIF89a’s Graphic Control Extension supplies controls such as delays, transparency and disposal methods. Multiple-image storage itself was therefore not introduced for the first time in 89a.

US Patent 4,558,302 names Welch as inventor and Sperry as the original assignee. It was filed on June 20, 1983, and the granted patent was published on December 10, 1985. The paper appeared in 1984; that was not the patent’s filing year. Following the 1986 merger of Sperry and Burroughs, the rights passed to Unisys.

Older US patents can be affected by transitional term rules, so a blanket calculation using today’s “20 years from filing” explanation is insufficient. The expiry dates below come from dates expressly stated in a contemporary licensing document. Google Patents’ automated legal-status field should not be treated as an individual legal opinion.

PNG contributor Greg Roelofs identifies CompuServe’s announcement on December 28, 1994, as a turning point. Discussions with Unisys had begun earlier. The start of negotiations, the public announcement and the precise contract terms are different matters.

The central issue was patent licensing for software implementing the compression technology, not a tax on a filename extension. “GIF tax” was a nickname, not a tax regime. Licensing demands, including later demands involving websites, depended on the period, agreement and implementation used. They should not be reduced to a claim that every website displaying a GIF owed a uniform fee.

In early 1995, Thomas Boutell and other contributors began discussing a replacement for GIF. Avoiding the patent problem was one motivation; support for more colors and more flexible transparency also helped shape PNG.

• October 1, 1996: PNG 1.0 became a W3C Recommendation.
• March 1997: RFC 2083 was published. It did not appear on the same date as the 1996 Recommendation.
• March 2004: ISO/IEC 15948:2004 was published. Its designation is not a 2003 edition.

PNG adopted DEFLATE, choosing a different compression format rather than waiting for the LZW patent to expire. RFC 1951 describes DEFLATE as a combination of LZ77 and Huffman coding.

PNG 1.0 did not include animation, so its original role as a GIF replacement centered on still images. That is no longer an enduring limitation of the standard: the PNG Third Edition W3C Recommendation of June 24, 2025 includes APNG animation. PNG transparency is not universally limited to eight bits either; the rules depend on color type and bit depth.

The following dates are stated in the LZW notice within a 2005 License Agreement between Stellent and Guidance Software, filed with the SEC. This is a contemporary record about the specified Unisys patents, not a claim that we have independently re-examined every national patent register.

Source: Stellent Chicago Sales, Inc. / SEC: License Agreement (LZW notice).

The US expiry date is not a worldwide expiry date. Nor does this table establish that all rights held by other companies or covering improvements disappeared in 2004. The same notice mentions separate patents and applications concerning improvements.

Image selection need not be dictated by GIF’s history. Compare colors, transparency, still versus animated content, destination support, encoding time and file size. WebP or AVIF may produce smaller files, but not invariably one fifth or one tenth the size of GIF. Compare the same material, quality, resolution and frame count. See our WebP, AVIF and JPEG comparison for related considerations.

NanToo’s Japanese GIF animation maker uses gif.js, which is distributed under the MIT license. Patent expiry and the copyright license of an implementation are separate issues. Distribution of a library can still carry notice requirements, and the rights to the input images also matter.

LZW encodes recurring sequences as dictionary codes; GIF is an image format that incorporates it. The 1983 filing, 1984 paper, 1985 grant and late-1994 licensing announcement are distinct events. So are PNG’s subsequent development and its standardization milestones in 1996, 1997 and 2004.

The expiry of the relevant Unisys patents in 2003–2004 was an important milestone, but it did not erase software licenses or copyright in images. This article explains technology and patent history in general terms. For a legal assessment of a particular contract or product, identify the implementation and jurisdiction and consult an appropriate professional.