30

Is there any evidence to support the claim that software patents stifle creativity and put many people at risk of legal action?

If necessary refer to some background reading:

Seriously think about it. Every time you write code -- even a brand new algorithm in a clean room environment-- you could be infringing a patent, somehow, somewhere.

It's probably not fair to say that software patents are 100% evil. But from what I've read, I'd say they're 99 and 44/100ths percent evil. I'm not sure what any of us can do about this, but it's clear that the current situation is untenable

Something has to be done, or else we truly are staring down a coming software patent apocalypse.

  • 4
    I doubt patents stifle creativity but they could stifle the commercialisation of the results of that creativity. – Craig Jun 3 '11 at 1:17
  • 1
    Does anybody else wonder why software patents don't include source code? Isn't the source code be necessary for others to use the ideas in your patent, once the patent expires. Otherwise, they would have to reinvent your patent just to reuse an expired patent. – Kibbee Jun 3 '11 at 1:20
  • 2
    @xiaohouzi79, What would consider to be acceptable evidence in either direction? I can give anecdotal evidence where software patents have been used to encourage innovation. No doubt others could give counter-anecdotes. But what would evidence look like? – Oddthinking Jun 3 '11 at 2:19
  • And what would be acceptable evidence against? I can give anecdotal evidence of (1) patent hoarding for defensive purposes, (2) a lot of legal activity required Someone could dig up the $/p.a. spent on patent lawyers per annum. But none of that addresses the question: Does it stifle creativity, encourage it, or a bit of both? (NB: I have my name on many software patents & have stated many times that I will vote for the 1st politician to abolish them.) – Oddthinking Jun 3 '11 at 2:39
  • 4
    Wouldnt a better question be, "Do frivolous software patents stifle creativity?" since most software patents are frivolous, caused by lack of understanding in the Patent Office (sorry, no citation for this now)? Or does that make the question too obvious... So maybe the question should be tilted the other way, to exclude the frivolousnesses, and focus only on the principle? – AviD Jun 19 '11 at 8:55
26

Yes

Patents stifle, not creativity, but innovation (which I'm sure you meant).

We argue that when innovation is “sequential” (so that each successive invention builds in an essential way on its predecessors) and “complementary” (so that each potential innovator takes a different research line), patent protection is not as useful for encouraging innovation as in a static setting. Indeed, society and even inventors themselves may be better off without such protection. Furthermore, an inventor's prospective profit may actually be enhanced by competition and imitation.

http://onlinelibrary.wiley.com/doi/10.1111/j.1756-2171.2009.00081.x/full

And not only in software.

However, the recent proliferation of intellectual property rights in biomedical research suggests a different tragedy, an “anticommons” in which people underuse scarce resources because too many owners can block each other. Privatization of biomedical research must be more carefully deployed to sustain both upstream research and downstream product development. Otherwise, more intellectual property rights may lead paradoxically to fewer useful products for improving human health.

http://www.sciencemag.org/content/280/5364/698.short

And finally, Bill Gates:

If people had understood how patents would be granted when most of today’s ideas were invented and had taken out patents, the industry would be at a complete stand-still today. The solution . . . is patent exchanges . . . and patenting as much as we can. . . . A future start-up with no patents of its own will be forced to pay whatever price the giants choose to impose. That price might be high: Established companies have an interest in excluding future competitors.

Fred Warshofsky, The Patent Wars 170-71 (NY: Wiley 1994).

  • 2
    Nice quote there from Bill G. – user2466 Jun 3 '11 at 7:40
  • 1
    -1 The middle quote is about biomedical patents not software: so it's argument by analogy. The first and third quotes seem to be just arguments or opinion, not evidence. – ChrisW Jun 3 '11 at 12:32
  • 4
    @ChrisW: The first is an economic paper. It is not argument or opinion, but as close as evidence as you can get in social sciences. The second paper is there to show that it's not just in software, it's about all patents, so it is in no way "by analogy". Bill Gates quote is indeed just opinion. – Lennart Regebro Jun 3 '11 at 12:41
  • 2
    HERE and HERE are additional discussions that might be of interest -- they center around a 2008 paper by Bessen & Meurer on this topic (well, patents in general) found HERE. – Hendy Jun 3 '11 at 16:10
  • 1
    Relevant paper: papers.ssrn.com/sol3/papers.cfm?abstract_id=1868979 – Brian M. Hunt Jun 23 '11 at 19:43
6

The accepted answer is a good one. Here I'd like to illustrate it by giving concrete examples from the field of data compression.

LZW, the "GIF Patents"

In the late 1970s, two fundamental dictionary-compression algorithms were published by Lempel and Ziv, known as LZ77 and LZ78 for short. Many modern data-compression algorithms can be described as being of the LZ77 or LZ78 family, though they invariably include significant enhancements over the originals, particularly in the use of an entropy coder.

One LZ78-family algorithm that became very popular in the 1980s was LZW, named after it's progenitor algorithm and its author, hence Lempel-Ziv-Welch. LZW was a very straightforward development of LZ78 which applied it to an 8-bit byte stream and a 4096-entry dictionary that could conveniently fit in the typical 64KB address space of the time. Most LZW implementations store the dictionary codes using a variable bit width, increasing as the dictionary fills up.

The two most famous uses of LZW are in the UNIX compress utility, and in the GIF image format which remains popular today. Early versions of the PKZIP utility also used it (known internally as "implosion"). By modern standards it isn't a very good compression algorithm, due mainly to its small dictionary and lack of further entropy coding. LZ78-based algorithms are now thought to converge on their optimal compression rate more slowly than equivalent LZ77 implementations.

Both LZ78 and LZW are quite simple in principle. Nevertheless, LZW was covered by no fewer than three US patents, plus corresponding patents filed internationally. Two of the US patents were assigned to Unisys, and the third to IBM.

The LZW algorithm was widely published outside the patent ecosystem, which led to its initial popularity. Software engineers usually don't read patents, and typically have trouble understanding the patent language sufficiently well to implement the algorithms they describe accurately on a practical computer. It's normally easier to understand an academic paper, or even a source-code listing, and those were the usual means of disseminating algorithms at the time. (To some extent, they still are.)

In the 1990s, Unisys expressed its intention to enforce the LZW patents it held. This would have required implementors of the algorithm to pay licence fees - even if they had never read or even heard of the patent, but now had millions upon millions of copies of LZW code on computers around the world which they were now responsible for.

It was soon realised that the patents essentially covered the encoding algorithm, not the decoder, so people who never compressed data using LZW, but only uncompressed existing data, were relatively safe. A workaround was discovered whereby an LZW-compatible file could be created without infringing the patent, but this produced equivalent compression to a simple RLE scheme - it was therefore only useful for making (big, inefficient) GIFs without infringing the patent.

Concern over the legality of using LZW led to a search for patent-free alternatives, and more-or-less directly to the development of the "deflate" algorithm, which is a straightforward combination of the LZ77 dictionary compressor (allowing dictionary windows up to 32KB) with the 1950s Huffmann entropy coder.

PKZIP version 2 dropped LZW support in favour of the measurably superior Deflate. Several other compression utilities, such as StuffIt on the Mac, followed suit. The GNU project introduced gzip as a direct replacement for UNIX compress, and zlib as an easy way to use Deflate in other applications and formats.

The PNG image format then aimed to replace GIF with the twin advantages of better compression (via zlib) and support for more than 256 colours - though it lost animation support, which proved to be a significant oversight.

Practically the only use for the GIF format today is its animation feature - and now that the LZW patents have expired, its popularity has resurged substantially. It must be noted however that GIF animation has nothing whatsoever to do with the LZW algorithm.

In this case, the patent-free alternative was found relatively easily and proved to be objectively superior, making migration away from the patented algorithm a relatively easy choice. Not every case is so fortuitous.

Arithmetic Coding

The earliest entropy coder to be proved "optimal" was the Huffmann coder of 1951, which itself was an improvement over the very similar Shannon-Fano coder. It essentially builds a balanced binary tree of the symbol dictionary, and stores one bit for each branch decision on the tree. Practical computing was still very much in its infancy at the time; if any patents were ever filed on the original Huffmann algorithm (which I doubt), they have long since expired, making it legally safe to use.

However, it is rare for the branches of a Huffmann tree to be perfectly balanced; this requires that the symbol frequencies are all powers of two. So in general, it is possible to obtain further compression by arithmetic coding rather than being constrained by bit boundaries. Essentially, a number with arbitrary precision is constructed, in a number space that is repeatedly subdivided in arbitrarily lopsided ratios according to relative symbol frequencies. Very frequent symbols are assigned large parts of the number space, and thereby can consume less than a bit per symbol in extreme cases. This is inherently superior to Huffmann coding, which must use at least one bit per symbol.

However, since arithmetic coding was developed in the 1970s, it was patented multiple times over a period of about 15 years. Most of the patents cover methods of implementing the algorithm efficiently for a particular type of data and on a particular class of computing hardware, but most of the reasonable options were in fact patented (though these patents, like LZW, have now expired). It was widely believed that a closely-related algorithm called range coding was patent-free, though this was mathematically equivalent to arithmetic coding.

The arithmetic-coding patents had direct, detrimental effects on at least two compression formats: bzip/bzip2 and JPEG.

The bzip compression utility was an attempt to improve on gzip's compression ratio by using more modern techniques; specifically the Burrows-Wheeler Transform (BWT) and arithmetic coding. Although the experiment was successful, the author realised that his software could not legally be published as Free Software in the US due to the patents, so he wrote bzip2 with the arithmetic coding replaced by Huffmann coding. This was still measurably better than gzip, so bzip2 became popular in the Free Software community for a while (until even more advanced utilities became available). The original bzip software was never widely published, but a decompress-only utility is available in case any files compressed by it come to light.

The JPEG standard of 1990 is extremely widely used; practically every digital camera, image editor and Web browser supports it today. However, almost without exception, the patent-free variant of the format using Huffmann coding is used. The standard also defines a variant using arithmetic coding, but due to the patents, it is rarely used and isn't even supported by most software. Several of the later arithmetic-coding patents are, in fact, specifically for JPEG-compliant arithmetic coders, sharply increasing the probability that an independent implementation of the JPEG standard might accidentally infringe.

A few archive compression utilities, including some versions of StuffIt, are capable of recognising JPEG files and handling them specially, essentially converting them to the arithmetic-coded variant in a losslessly reversible manner. This typically saves about 25% space, much better than applying a general-purpose compression algorithm to the original file. Without the arithmetic-coding patents stifling the more general use of the more efficient variant, JPEG files would mostly be this much smaller from the outset.

Now that the arithmetic-coding patents have mostly expired, use of this entropy-coding method is starting to increase. Several recent video compression standards rely on it heavily; notably both H.264 and H.265 use an arithmetic-coding algorithm called CABAC. H.264 also supports the less-advanced CAVLC, which does not use arithmetic coding, for the Baseline profile.

This case illustrates an example where the patented algorithm was significantly superior to the available patent-free alternatives, resulting in an observable and verifiable decrease in software capabilities available to end users over a multi-decade period of time.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .