GIF Tax/LZW Patent

[David Farber <farber () central cis upenn edu>]

As a side issue, while at Bell Labs I implemented one of
the first (maybe the first) run length compression schemes
that I called Crunch. That was in 1959-60. I suspect it may
be relevent to this also   Dave


Date: Tue, 3 Jan 95 14:00:05 -0500
From: shap () viper cis upenn edu (Jonathan Shapiro)


I'm not expert on patent law OR compression, but I've had occasion to
read up on the LZW patents at a very high level.


The LZW patent family is contested by a number of parties who claim to
have independently invented the basic technologies involved.


If any of you are interested enough to want to read a synopsis, check
out the FAQ in comp.compression.  Among other things, it will point
you to a collection of implementations of the various algorithms in
the LZW family.  Among the files you will find a readme that lists all
of the patents that were known to the collector, along with a
human-readable description of what they cover.  There are many
conflicts among these patents.


An interesting issue is who has liability.  Compuserve offered a
royalty free license for this technology for many years.  Implicit in
the concept of a license is that the licensor owns the subject matter
of the license.  If I implemented and used the technology under that
license, and the license was invalid, then Compuserve has exposed me
to liability, and may be responsible for that exposure.


In order to apply, the relevant patent must predate 1987 (the initial
release of the GIF standard), so a case could be made that Compuserve
misrepresented their ownership of the technology in the first place.
If you are a provider of a GIF implementation, and Unisys has come
after you for infringement of the LZW patent, you may be able to sue
Compuserve for the damages.


Many of the LZW patents are written in such a way as to cover
ENcoding, but not DEcoding.  Depending on which patents Unisys has
obtained, your product may not infringe unless it *generates* GIF
files.


Another possibility to consider is that Unisys has not managed to tie
down all of the LZW patents.  It might be possible to form a temporary
alliance around one of the earlier patents in order to countersue
Unisys and possibly get their patent thrown out.


It seems a safe prediction that Compuserve will ultimately release
some new standard, say GIF95, based on the compression algorithm used
in GNU ZIP, which is not currently encumbered by patent.  It would
certainly be simple enough to convert the existing images.




Some food for thought:


Though the media have covered primarily compression and encryption
patents, this sort of problem is occuring in more and more parts of
the software industry.  Perhaps software patents are not such a great
idea?  One wonders if something like a class action suit could be
brought against the patent agency on the grounds that by refusing to
use software professionals to assess new patent applications, they
knowingly and willfully conspired to restrain trade, and that many of
the patents they granted fell outside of what was patentable under the
law.  If this could be done, perhaps the older patents could be
eliminated.


The most obvious thing to do about the GIF standard is to start using
JFIF (JPEG), which is a better technology in any case.  Unfortunately,
the JFIF standard specifies an encoding that appears to be patent
encumbered...




Jonathan