The Patent on LZW Compression

[David Cressey]

One software patent that sticks in my mind,  thanks to GB,  is the LZW patent.  This became important when the GIF format used LZW,  and that prevented the owners of GIF from being able to release it into the public domain.  In retrospect, they might have done better to create a second format, and used an unlicensed compression method.

There is an article on LZW compression in Wikipedia.

Note two things:  the patent has expired.  LZW is now public property.  And it was the algorithm,  not any particular source code,  that was protected.

I've got a few  questions for us:

Should the LZW patent have been issued?  Why or why not?

Did the LZW compression algorithm fall below the tirviality threshold?

Should IBM and Unisys have been more liberal in granting licenses to use LZW?

Did IBM and/or Unisys earn the right to have the patents assigned to them,  or should the originators have (in  a fair world)  had the right to keep the license?

[The Gorn]

I was thinking of LZW when I posted that stuff recently about software patent law. I think (qualitative statement now) that LZW is probably non trivial enough to count as a patentable invention and not merely a "concept".

However....

I have read that programmers regularly came up with something very much like LZW on their own, independently, without any study of compression techniques. In other words, LZW can be stumbled upon without a great concerted effort, just by individuals working on their own.

And THAT was the big risk of the LZW patent and in like manner, some other SW patents: it penalizes people for doing their job by placing arbitrary limits on their own inventiveness where there is absolutely no intend to clone, steal or take credit for someone else's invention.

So, is LZW non trivial enough to merit a patent? Possibly. Is it "unique" and non duplicable enough to merit being restricted? I say no, but that's my personal self interest as the kind of freelance inventor known as a programmer.

Now, the same argument could be made about the paper clip or the pneumatic inner tube or the pop top can. And there are counter arguments you can make in favor of the patentability on both sides.

IE: you can argue that LZW could be developed from first principles by one lone SW developer. Whereas duplicating any of the three physical inventions I listed would require an investment in machine tools, etc. so duplicating, say, paper clips on a significant scale is beyond the reach of "just anyone", so they should know better if they do.

However, that lone software developer is exercising non-trivial talents and abilities and may just "reinvent" a patented algorithm on his own, so he should be careful, because, since he's so smart, he should "know better".

Unfortunately, the precedent of rather simple physical things being patentable argues in favor of allowing software patents for darned near anything.

So if there is a challenge to the whole notion of software patents, then it must come from elsewhere, other than from the "triviality" argument.

I developed an if() statement for tax calculations! My patent, please!

[David Cressey]

I was thinking of LZW when I posted that stuff recently about software patent law. I think (qualitative statement now) that LZW is probably non trivial   enough to count as a patentable invention and not merely a "concept".  
 
  However....  
 
  I have read that programmers regularly came up with something very much like LZW on their own, independently, without any study of compression techniques. In   other words, LZW can be stumbled upon without a great concerted effort, just by individuals working on their own.  
 
  And THAT was the big risk of the LZW patent and in like manner, some other SW patents: it penalizes people for doing their job by placing arbitrary limits on   their own inventiveness where there is absolutely no intend to clone, steal or take credit for someone else's invention.  
 
  So, is LZW non trivial enough to merit a patent? Possibly. Is it "unique" and non duplicable enough to merit being restricted? I say no, but   that's my personal self interest as the kind of freelance inventor known as a programmer.  
 
  Now, the same argument could be made about the paper clip or the pneumatic inner tube or the pop top can. And there are counter arguments you can make in   favor of the patentability on both sides.  
 
  IE: you can argue that LZW could be developed from first principles by one lone SW developer. Whereas duplicating any of the three physical inventions I   listed would require an investment in machine tools, etc. so duplicating, say, paper clips on a significant scale is beyond the reach of "just   anyone", so they should know better if they do.  
 
  However, that lone software developer is exercising non-trivial talents and abilities and may just "reinvent" a patented algorithm on his own, so   he should be careful, because, since he's so smart, he should "know better".  
 
  Unfortunately, the precedent of rather simple physical things being patentable argues in favor of allowing software patents for darned near anything.  
 
  So if there is a challenge to the whole notion of software patents, then it must come from elsewhere, other than from the "triviality" argument.  
 
  I developed an if() statement for tax calculations! My patent, please!

 

Something "very much like" LZW might very well not have been covered under the span of the patent.  I'll give you two examples of compression techniques that are in the public domain:  Huffman encoding and Run Length Encoding.  They may suffer from defects, when compared with LZW,  but I'll bet that anybodty who used Huffman or RLE could mount a successful defense in an infringement lawsuit,  and present "prior art" as part of the defense.  BTW,  courts can,  and have,  struck down a patent or ruled for the defendant based on "prior art" discovered by the defense but undiscovered by the patent attorney at the time of the patent aspplication.  I think that all you would need to mount a "prior art" defense in this case would be a copy of Knuth.

I am NOT suggesting that programmers should have to worry about patents while dreaming up ways to code.  But I am suggesting that the hazard to the programmer (or his employer) is far less than you assert.  Incidentally,  the same agreement to assign IP rights that JavaMouse complained about would also be sufficient to get an employee off the hook and transfer the problem to the employer if somebody raised a lawsuit.  IANAL.  (I know you know this, GB.  This is just for the benefit of later lurkers).

I don't think that absence of intent to steal is enough, in and of itself, to absolve a person of responsibility in patent matters.  It's a point in the case, but not convincing in and of itself.  If I were on the jury, for example,  absence of intent,  and absence of gross negligence would be enough to get me to vote for $0 in punitive damages.  Compensatory damages might be another story.

The argument you make for yourself as a free lance inventer turns on its head when you stumble across something real valuable and want to take out a patent for yourself.  If we are going to say that algorithms and data structures are so easily stumbled upon that they should be devoid of patent protection,  then we are going to say that programmers should be denied protection for what they stumble upon.  They might still have a little protection under copyright,  but "independently arrived at"  is even more risky to the property owner under copyright than under patent.

In fact,  there have been several cases where the development team is prevented from seeing the competitor's source code precisely in order to avoid being liable for the "reverse engineering"  lawsuit later on.

I believe that Chinese copyright law,  and its sloppy enforcement, is going to pose a greater threat to your viability as a professional  than any hazard you face from unwitting violation of patents.  And,  given good modular methodologies,  its easy enough for a software vendor to cross check for "obivous" patent infractions in parallel with beta testing,  and swap out any offending modules in favor of innocent replacements.

I don't quite think we should discard the triviality argyument completely.  I'm just arguing for a lower threshold than you seem to want.

In the specific case of an if statement for tax calculations,  there are two points;  first the "if statement"  itself is an expression of the algorithm and not the algorithm itself.  Expressions can't be patented.  "Expression"  means something slightly different here than it does in programming linguistics.  And second,  it's almost certainly derived from the tax code or tax reegulations,  which are in the public domain.  Therefore it would be proper for the patent office to deny the patent.

[The Gorn]

Clear definitions of terms like "patent worthy" are just about impossible. I agree with that. Few laws can stand whose practice hinges on intentions. And most of my arguments against patenting "trivial" inventions are in terms of intent.

I also agree with your statement about China and much of the Pacific Rim's threat to the livelihood of IP producers. A strong and consistently enforced legal environment is necessary for the sustenance of our industry.

Without the right to shut down unauthorized duplication, you have nothing to sell.

[David Cressey]

Good points.

(warning:  this comment is long, and winding).
 
I think that most patents, historically,  were proven "patent worthy"  on a case by case basis.  And I think that most of the big bucks that patent attorneys make is precisely in putting together a good case for the patent application at hand.  Patent attorneys with high professional ethics spend a considerable amount of their time trying to dissuade would be patent seekers from pursuing a patent for some particular innovation.  And that's a terribly ego deflating response.  The people you've dealt with who thought their SW business was going to turn the world upside down were probably relying on trade secrets rather than patent protection,  but the ego involvement is the same.

As far as the Patent office lowering its standards due to bad faith as you suggest,  or due to sheer future shock as I tend to believe,  that's a separate subthread,  and I'm going to start another discussion dealing with that aspect.  I expect a lot of political flak on that subthread.  And here in the political forum,  reason tends be used like rhetoric,  as if it were a mere tool at the service of attitude.  Still, it's an important part of the discussion.

Meanwhile, back to LZW.

I've been thinking over my mention of other compression algorithms,  and I came up with the following:  compression of photographs (as in GIF) is probably a lot more subtle than compression of text,  which RLE and Huffman are pretty good for.  The folks who chose LZW for use in GIF were probably seeking superior compression ratios,  and/or speed at compression and decompression,  big time.  And they were probably aware of the proprietary nature of LZW when they made their choice.  So it really isn't like the free lancer case stumbling over an algortithm that somebody else patented.

And, IIRC,  the owners of LZW didn't sue the owners of GIF (Compuserve?) for infringement.  Compuserve must have been licensed to use LZW.  Where the legal issue came up was when they tried to make GIF an open format,  and couldn't because of LZW.

In routine information system creation,  including database design,  one relies heavily on tried and true methodologies that are all in the public domain,  coupled with tools that are distinctly propietary in nature,  and that the client will have to get a license for.  The legal  issues are pretty cut and dried.   Where a truly professional practitioner differentiates himself is this:  most newbies at database design make the same old mistakes over and over again,  and they are profoundly disruptive for misson critical databases:  they prevent data from being effectively shared and exploited.  I suspect that something analogous is true for forms design and SPARC layered architecture,  although I can't say for sure.  That's anotrher discussion.

Anyways,  anybody inventing his own algorithms on the fly for the purpose of freelance work is 99% likely to redevelop an algorithm that's already in the public domain.  And even if he infringes on a patent,  he's likely to escape unpunished,  until such time as he goes to apply for a patent of his own.  My sympathies are very limited.  however, this attitude of mine is subject to revision if I find out that there's been a growing body of cases in which free lancers have actually been sued or threatened with lawsuit because of infringements that a reasonable man might have committed unawares.



When I studied Rdb internals,  I learned about an enhancement that DEC engineers had made to the standard B-tree data structure.  DEC had a patent on that enhancement.  To tell the truth, if I had had to implement B-trees for some client,  I would have been strongly tempted to bend the rules,  and see if DEC actually came after my client.  Sorta like cruising at 5 MPH over the speed limit.  Everybody does it.  I never had occasion to do such a thing,  so it's a moot point.


Enough rambling already.

[David Randolph]

The argument about allowing patents at all for any reason start with the benefits to the public: the public benefits when an inventor is compensated for his invention. Thus, when Eli Whitney did not get compensated by people who used his invention to gin cotton, he left that area of the country and decided to build something totally different up North. The economy of the US during the 1800's is dominated by Eli Whitney's work. In the South, the cotton gin allowed huge profits from growing cotton. The North built an economy off of his manufacturing ideas. The South badly lost out because of not compensating him for his ideas.

So, take a look at the results of software patents. Has there been an increase in products offered to the public because software is patented? Has there been more value to the public because inventors are better compensated? Can we make the argument that providing legal protection to corporate control over software provides a better marketplace? When there is a movement to destroy software patents through "Open Source", is the marketplace showing that patents have value by buying more of the stuff with patents?

When we look at what has been patented in the software field, who has held those patents, who has actually benefited, and how those patents have been used to get payment from other companies, my opinion is that software patents have provided almost no value to the public, have resulted in less invention, and have served mainly to extort payments out of competitors when the company that holds the patent is unable to compete either technically or in the market.

[The Gorn]

Regarding the whole triviality/patent worthiness issue - An important aspect of triviality in software occurred to me. In my opinion, it's impossible to prove that there isn't prior art for most software algorithms, and I'm thinking that determining that proof of no prior art should govern software patents. In other words, it should have to be proven that nobody has ever invented the algorithm, not that there IS prior art that disqualifies the patent.

For example, while LZW is non-trivial, it is something that many developers inadvertently re-invent. Unisys just decided to file a patent on the occurrence of LZW that they happened to manage at the time. But that fact that developers can re-invent it may argue that the patent should never have been granted in the first place.

And while LZW is non-trivial, it's also not terribly abstract or difficult to understand, either. I just looked at it; it is a particular way of searching for repeating string patterns in data, and creating (12 bit) codes that correspond to the patterns that repeat and using those codes to represent the strings.

Just some mental masturbation there...

As far as the role of LZW in GIF, I always had the impression that techies started to use it without the realization that it infringed a patent. And Unisys tolerated the infringement as benign until they saw the sheer volume of useage, and then decided to put a stop to it.

[David Cressey]

I agree with your general principle regarding the public good.  But I question your conclusions regarding software patents in general.

You say that some patent holder is unable to compete technically or in the market.  I thought that the whole idea of patents was to give an innovator a competitive edge,  that might make that enterprise viable in the marketplace,  even if it would not be viable without patent protection.

I wonder how you judge "an increase"?  compared to what?  Compared to the status quo ante before software could be patented at all?  The rate of innovation is thousands of times as large as it was then, although much of that increase can be attributed to factors other than patent protection.
Why are software patents different from patents in, say, electrical engineering or biotech?

I think I understand your assertion.  But I remain unconvinced.

[David Randolph]

The idea of a patent was to give the inventor a window in which they could profit from their invention.

Software is different from electrical engineering in that for many years, patents were not available to software designers. Thus, much of the industry was built without patent protection and other ways of compensating inventors were devised. Most inventions in software were made and marketed prior to patent protection. Patent protection of software started in 1981. That means that everything invented prior to that was unprotected from patents and now could be granted not to the inventor but to those who first filed under the new rules. When patent protection was offered, it was only the companies that saw how they could use patents to distort the market that went and aggresively sought out patents. Prior art and nonobviousness and the rule on "offered for sale" were ignored. Thus, IBM holds most of the software patents that have been granted in this country. So, in many cases, the actual inventor did not get the patent.

What has IBM done with those patents? Have they been able to use the patents to advance the state of the art? In most cases, they have trailed other companies. So, what value has IBM gotten from them? IBM uses the patents to force other companies to pay them royalties - in many cases, after the fact. Check out this Forbes article: http://www.forbes.com/asap/2002/0624/044.html

I saw a similar case in the prepaid phone card market a few years ago. A company went and got a patent for how they did part of that business using the ubiquitous credit card terminals. They made a lot of noise about how they now had the patent and everyone else was going to have to change their (prior art) software to match these people's patent and pay them royalties. The company with the patent announced that they would be suing those who did not pay the royalties. This was a field that had been wide open with a lot of people inventing ways of doing business. Since that time, the business has dried up. I know of at least one law suit that was going to use the fact of prior art to challenge the patent.

The current patent system is broken. The way it is conducted, there are two ways to run a inventive business in this country. This is in recognition that there is no way to write an up to date computer program without violating somebody's patents. The first way is to stay small and keep on building new products all the time. By being small, you won't run into the patent problems. The other way is to use the patent system and aggresively file for as many patents as possible. Then, when the bigger players walk in demanding "royalties", you can turn right around and demand equal royalties from them. By cross licensing, you won't have to pay the extortion. Note that this poses a strong problem for mid sized companies - they are neither small nor are they big enough to have the patent library (at $20,000 per patent). This system gives an economic advantage not to the inventor, but to large companies.

Much like the Republican party argued absolutely opposite points before different courts, the same company may have one attitude about software patents in this country and another in another country depending on the number of patents they control in each.