LZW compression: conjugations patented
The LZW data reduction method is moderately ingenuous and moderately efficient. It was patented as US 4558302 and, against the letter and spirit of the written law, as EP 129439. Better solutions are meanwhile available, some non-patented. But due to the inertia of de-facto standards such as GIF, ZIP, PDF etc, the LZW patent it is still causing a lot of grief. It is as if the conjugations of the English language had been patented.
- (Unisys Web Site LZW license)
- The license conditions of the patentee
- (LPF on the GIF case)
- Detailed Documentation
- (Free Software developper forced to remove GIF support)
- GIF support may not be included in free libraries. A developper reports about his difficulties with Unisys.
- EPO patent descriptions cannot be viewed, printed or manipulated under free Unix systems, because they contain LZW compression. The Acrobat Reader provides only a very incomplete and non-free replacement. It is tedious to view EPO patent descriptions with Acrobat, because they are organised as one PDF document per page. Concatenating pages can normally be done using imagemagick, but this program too can not handle the LZW compression because of patent problems.
- Xpdf: LZW patent problems with many PDF files
- The authors of a popular PDF viewer explain how the Unisys LZW patents are causing them trouble
- Unisys study warns EU against Swpat
- a report written by Unisys for the European Commission's General Directorate Enterprise on pooling Open Source Software for administration. This report warns and explains in detail that software patents as a serious threat for open source software and the IT sector at large.
What about patents?
gzip was developed as a replacement for compress because of the UNISYS and IBM patents covering the LZW algorithm used by compress.
I have probably spent more time studying data compression patents than actually implementing data compression algorithms. I maintain a list of several hundred patents on lossless data compression algorithms, and I made sure that gzip isn't covered by any of them. In particular, the --fast option of gzip is not as fast it could, precisely to avoid a patented technique.
The first version of the compression algorithm used by gzip appeared in zip 0.9, publicly released on July 11th 1991. So any patent granted after July 11th 1992 cannot threaten gzip because of the prior art, and I have checked all patents granted before this date.
During my search, I found two interesting patents on a process which is mathematically impossible: compression of random data. This is somewhat equivalent to patents on perpetual motion machines. Check here for a short analysis of these two patents.
- Unisys responds to Questions
In April 1999, I asked the following two questions to Unisys: when does your patent on the LZW compression algorithm expire? do you agree that an algorithm is equivalent to a theorem, in the sense that for example, the Pythagorean theorem can be considered as an algorithm to find the length of the hypotenuse of a right triangle?
They answered this to the first question: The basic U.S. patent expires in June, 2003. Variants on the basic LZW patent run for about 20 years and further U.S. applications are pending. However, their answer to the second question was less precise: We do not agree or disagree with your statement regarding the relationship between an algorithm and a theorem.
I hope that everyone here is going to celebrate on June 20, 2003. That's when US patent 4,558,302 expires. That is the patent that unisys has on the lzw compression algorithm that is used in GIFs.
- US Patent 4558302
- Informatiker an Uni Tübingen über LZW
- Aufürhliche Informationen über das LZW-Patent, seine Verwertung durch UniSys sowie das IBM-Patent 4814746 auf das gleiche Verfahren.
- Explanation of the LZW Algorithm
- Patents on Compression Algorithms
- Unisys License Info
- Unisys Licensees
- Burn All Gifs
- RMS on GIF
- Lecture in German on the GIF format
- GIF FAQ
One company CEO wrote to us about his troubles with the Unisys patent licensing conditions:
I make a product called X which is a Y web server extension for dynamic image manipulation. I'd like to include GIF support in the product but its difficult to know how to do this effectively. The Unisys licensing restrictions are so severe that I wouldn't be able to offer a free trial version. Also I don't even see that I'm really responsible since I'm just providing a tool to enable others to put a solution together. It's a standard story.
An software entrepreneur working mainly in the field of individual solutions remarkes:
Due to the LZW patent, the development of user interfaces that run within a web browser has come to a halt. When you want to run complex ASP solutions in a browser, you can in many fields of application not avoid dynamic generation of graphics. The problem of picture formats currently creates a situation where no more software is developped in this area although many beautiful solutions would be conceivable.
This trouble is hitting us as well. We are stuck with the fruits of a development which we can no longer exploit without legal dangers.
A CEO of an SME in the embedded software field writes:
Die Anbieter der von dem LZW-Patent und ähnlichen Patenten bedrohten Software müssen stark reagieren, denn ihre Kunden fühlen die eingesetzte Software bedroht. Überall wo sich solche Unsicherheit breit macht, ziehen die Kunden es vor, Systeme einzusetzen, von denen sie vermuten, daß Sicherheit hinsichtlich der Lizenzen besteht. Mit der Zeit wird sich zeigen, daß bei keiner Software Sicherheit bezüglich der Lizenzen besteht (siehe die aktuelle JPEG-Diskussion). Deshalb werden sich die Kunden zu Anbietern hin orientieren, die von der Größe des Patentportfolios den Eindruck einer gewissen Sicherheit (Abschreckungs-Potential) bieten.
Daraus erklären sich allerlei bekannte Reaktionsmuster in der Branche, die einzeln oder in Kombination auftreten können:
- Wer kein entsprechendes Patentportfolio hat
- kämpft gegen den Unsinn der Software-Patente
- übt Kritik nicht laut, um keine schlafenden Hunde zu wecken
- sucht die Nähe (Geschäftsbeziehungen) zu Inhabern eines Patent-Portfolios, weil er sich damit deren Schutz erhofft (in der deutschen Automatisierungstechnik dürfte Siemens der Wunschpartner sein)
- glaubt daß er schon irgendwie zu einem Patent-Portfolio kommen wird (Glaube versetzt Berge)
- baut ein Patent-Portfolio auf
- Wer ein entsprechendes Patentportfolio hat
- versucht das friedlich zu begründen ("beweist Innovationskraft")
- versucht das als Abschreckungswaffe zu begründen
- droht schon mal ganz allgemein, um Kritiker ruhigzustellen und/oder neue Geschäftspartner zu finden
- kämpft für den Unsinn der Software-Patente
english version 2004/08/16 by Hartmut PILCH