[Commons-Law] Sad day... GIF patent dead at 20

[Sunil Abraham]

Sad day... GIF patent dead at 20 (Internet)
http://www.kuro5hin.org/story/2003/6/19/35919/4079

By it certainly is
Thu Jun 19th, 2003 at 11:20:58 AM EST

I just heard some sad news on talk radio - GIF patent US4,558,302 was
found expired in its patent office filing
cabinet this morning. There weren't any more details. I'm sure everyone
in the internet community will miss it - even if you didn't enjoy the
litigation, there's no denying its contribution to bandwidth
conservation. Truly a compression icon. 

On Friday, 20th June 2003, the death knell sounds for US patent number
4,558,302. Having benefitted its owner, the Unisys Corporation for 20
years, the contents of the patent are entered into the Public Domain and
may be used absolutely freely by anyone. 

Officially titled "High speed data compression and decompression
apparatus and method", it is more commonly known as the LZW patent or
Unisys's GIF tax. 

History:

A timeline of the GIF/LZW patent saga runs like so: 

May 1977: [LZ77] published. Most popular compression techniques build on
this technique and most archivers (e.g. ZIP, ZOO, ARC, gzip, LhA, CAB,
Arj, RAR, StuffIt) include it in their compression methods. I only
mention this to tell you it's unrelated to LZ78 or LZW. 
September 1978: [LZ78] published. Virtually nobody uses the technique
given directly (or the implementation given in [US4,464,650]), but the
LZW derivative is widely used. 
20th June 1983: LZW patent filed. Terry Welch has been working for the
Sperry Research Center and invents a derivative of LZ78 with much
simplified, faster dictionary handling. He calls it LZW, after the names
of the inventors, Lempel-Ziv-Welch. 
June 1984: Terry Welch's article A Technique for High-Performance Data
Compression appears in IEEE Computer magazine. If you're reading these
links, you'll note that the article is very well written, much more
readily understandable than the math-laden monstrosities that are [LZ77]
and [LZ78]. The article includes a justification for data compression,
an overview of common methods, and a detailed explanation and runthrough
of the LZW algorithm. At no point does it mention the pending patent
application! 
5th July 1984: UNIX compress version 1.2 is released by Spencer Thomas,
after the LZW article was published but before LZW was patented. Like
many IEEE Computer readers, Spencer decided to implement the LZW
algorithm he read in the magazine, completely unaware that there was a
patent pending on the technique. compress later replaced pack as the
de-facto UNIX compression tool, at least until gzip took the throne. 
10th December 1985: LZW patent is granted. 
September 1986: The Sperry Corporation (owners of the Sperry Research
Center) and the Burroughs Corporation merge to form Unisys. 
15th June 1987: Bob Berry and the team at Compuserve release a new
graphics file format called GIF (Graphics Interchange Format). It can
handle anything from 2 to 256 colours -- wow! -- and the graphics data
is compressed with LZW. Just like Spencer, they had read the LZW
algorithm in a magazine and had wrongly assumed that it wasn't patented.
Unisys does nothing. 
1988: Unisys does nothing. The GIF format becomes even more popular. 
1989: Unisys does nothing, although Raymond Gardner tries to bring up
the issue in public. Unisys have been ensuring hardware manufacturers
(e.g. V.42bis modem manufacturers and Postscript printer manufacturers)
are licensed. The GIF format becomes even more popular. 
1990: Unisys says nothing. The GIF format becomes even more popular. 
1991: Unisys says nothing. The GIF format becomes even more popular. 
1992: Unisys says nothing. The GIF format becomes even more popular. 
1993: Unisys says nothing. The GIF format becomes even more popular. 
1994: Unisys says ... no, wait, on 24th December 1994, Unisys and
Compuserve jointly announce that any developers writing software that
creates or reads the GIF file format will have to license the LZW patent
from Unisys! It's a GIF tax! Burn all GIFs! Merry Christmas! 

That's enough history. I didn't even mention IBM's duplicate LZW patent.
You can get a similar chronology from lzw.info or burnallgifs.org. 

One down, seven to go:

So the US patent has expired. What does this leave? 

The European patent EP0,129,439 covers Germany, France, Britain and
Italy and expires on the 18th June 2004. 
The Canadian patent CA1,223,965 expires on the 6th June 2004. 
The Japanese patents 2,123,602 and 2,610,084 expire on the 20th June
2004. 

This creates an interesting legal situation where LZW-based sofware is
legal to distribute in the United States, but risks patent infringement
claims in or when exported to Europe, Canada and Japan. 

Oh no! The world's going to end! What can be done?

Calm down. Firstly, the persistent threat of expensive litigation just
for having GIF images on your website hasn't diminished GIF's popularity
in the slightest. Webmasters are completely and utterly unwilling to
move to the replacement PNG format. What happened to the "BURN ALL GIFS"
rallying cry? It has been forgotten. There are all sorts of excuses;
"It's too much hassle to convert all my graphics and their links",
"Internet Explorer doesn't support PNG properly", "PNGs can't do
animation and nobody supports MNGs". The best one of all: "Unisys will
never sue me!". 

I wish Unisys a happy year squeezing the very last drops out of their
monopoly. 

Further information: 

PNG home page
Burn All GIFs
Slashdot relaying Unisys's position on GIF-using webmasters
Unisys's published position on GIF and LZW
The Free Software Foundation's position on GIF files
The League for Programming Freedom's position on GIF files
The GIF Controversy: A Software Developer's Perspective
Dr Ross Williams's list of compression patents or "Why He Stopped
Writing Compression Software". 
Jean-Loup Gailly's opinion on compression patents given in interview

References: 

[LZ77] Abraham Lempel, Jacob Ziv; A Universal Algorithm for Sequential
Data Compression, IEEE Transactions on Information Theory May 1977. 
[LZ78] Abraham Lempel, Jacob Ziv; Compression of Individual Sequences
Via Variable-Rate Coding, IEEE Transactions on Information Theory
September 1978. 
[US4,464,650] Willard Eastman, Abraham Lempel, Jacob Ziv, Martin Cohn;
Apparatus and Method for Compressing Data Signals and Restoring the
Compressed Data Signals, US patent 4,464,650 filed August 10, 1981 


-- 
Sunil Abraham, sunil at mahiti.org http://www.mahiti.org
MAHITI Infotech Pvt. Ltd.'Reducing the cost and complexity of ICTs'
314/1, 7th Cross, Domlur Bangalore - 560 071 Karnataka, INDIA
Ph/Fax: +91 80 4150580. Mobile: 98455 12611
"If you have an apple and I have an apple and we exchange apples 
then you and I will still each have one apple. 
But if you have an idea and I have one idea and we exchange these ideas,
then each of us will have two ideas" George B. Shaw
Shaw