LZW: Don’t it feel good when a patent dies?

LZW stands for Lempel-Ziv Welch, and is the name of a very elegant compression algorithm suitable for a variety of applications, but it is best known for being the foundation of the GIF image format created by CompuServe.

GIF images were in very wide use in the early days of the web; it was a good way to compress images such as logos that need to have sharp edges. (This is as compared to photo-type pictures, which need a lot more colours, but still look good if you sacrifice some sharpness – that’s roughly how JPEG works.) However, for all their elegance, efficiency, and former widespread use, images with a .gif suffix are rather seldom seen today? Why?

Both GIF and LZW received a lot of bad press over the last decade after the emergence of some relevant software patents owned by Unisys and IBM. In the second half of the 90s, Unisys started threatening to prosecute websites and application vendors that used the GIF format, which resulted in a lot of bad publicity for them and the gradual transition of most of the world’s websites to the new, open, PNG format which has taken its place today. Purveyors of closed, proprietary standards beware!

A company called Forgent tried to pull the same trick in 2002, claiming a patent on JPEG images. The patent was declared invalid in 2006, but not before Forgent had collected $90M in licensing fees, according to Wikipedia. I wonder if they had to give any of that back? The sad thing is that such legal action can often be rather profitable, even if you lose in the end.

Three years ago I pointed out the rather distressing effect on SCO’s share price when it started claiming ownership of parts of Linux in early ’03. The claims have been rebutted one after another as SCO failed to produce any convincing evidence, and the share price has now fallen back to where it was when the whole thing started.

SCO share price

I enjoyed the latest developments in SCO’s attempt to sue IBM for $5bn, as reported by Dow Jones Newswire:

Wells ruled in June that SCO had “willfully failed to comply” with court orders to show IBM which of millions of lines of computer code in Linux were supposedly misappropriated.

SCO argued that was IBM’s job, a stance Wells likened to a security guard who accuses a shopper of stealing merchandise and demanding the shopper show proof of the theft.

The case remains scheduled for a February 2007 trial, but the ruling by Wells gutted SCO’s case.

So SCO managed to keep alive for a while on the back of this, but everybody now thinks of them primarily as a litigation company, not as a software company, and no techie worth his salt would ever want to work there now, which must spell doom in the long term.

But, anyway, back to LZW. The GIF format is nearly dead, and long live PNG, which has quite a few technical advantages in addition to giving its users freedom from litigation. Unisys’s actions not only damaged their brand, but spurred the rapid development of a superior replacement over which they had no control. And now, at long last, the patents have finally all expired – hurrah! – which means that, GIFs or no GIFs, the LZW algorithm can be restored to its rightful place as a rather useful implement in the Computer Science toolbox.

Thanks to E-Scribe news for the reminder.

Enjoyed this post? Why not sign up to receive Status-Q in your inbox?


For me, this is what the patent system is all about, giving technology to the world.

Actually, the normal argument that the patent system encourages innovation by granting inventors protection for their ideas is given an extra twist here. If those ideas are released into an unsuspecting but grateful public, the system can then be used to unexpectedly deny access to the ideas at a later date when the public has become dependent on them, spurring them to further innovation much faster than might otherwise be the case! 🙂

As I think David knows, I’m not against the patent system. I have my name on more patent applications than I can remember now – thirty or forty, I think – so I would be rather a hypocrite to condemn it too roundly! There are many parts of our modern economy that simply couldn’t work without a robust Intellectual Property framework – ask any pharmaceutical or chip-design company.

So while I sometimes write long rants against its misuse, unfortunate side-effects, or other failings (see The Patent Cold War, for example), I suspect we can’t do without it, any more than we can do without dentistry, however much we may dislike the process at times. I just hope that yelling when it hurts will help improve the experience over time!

And I have more good friends (David included) who are Intellectual Property professionals than I have who are dentists!

Got Something To Say:

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax


© Copyright Quentin Stafford-Fraser