A one-line software patent – and a fix

I have been waiting for this day for 17 years! Today, United States Patent 5,404,140 titled “Coding system” owned by Mitsubishi expires, 22 years after it was filed in Japan.

Why the excitement? Well, 17 years ago, I wrote JBIG-KIT, a free and open-source implementation of JBIG1, the image compression algorithm used in all modern fax machines. My software is about 4000 lines of code long (in C), and only one single “if” statement in it is covered by the above patent:

      if (s->a < lsz) { s->c += s->a; s->a = lsz; }

And sadly, there was no way to implement a JBIG1 encoder or decoder without using this patented line of code (in some form) while remaining compatible with all other JBIG1 implementations out there.

For the technically interested: JBIG1 uses an arithmetic coder that estimates the probability that the next pixel to be encoded is either black or white (taking into account 10 previously transmitted neighbour pixels). Arguably in the interest of saving a bit of RAM in hardware implementations, the standard does not use the simple arithmetic expression that estimates these pixel probabilities based on counts of how often a pixel has been black or white before in that context: p(next pixel is white) = (#white pixel so far + 1) / (#pixels so far + 1). Instead, it defines a finite-state machine that comes up with a cruder estimate, using just 7 bits to define 113 states, rather than actually counting pixels with 32-bit registers. IBM had a patent on that finite-state machine, which is really hardly more than an obfuscated counter. Then a Mitsubishi employee noticed that the crude IBM approximation sometimes ended up assigning to the “less probable pixel colour” a probability larger than 0.5, making it actually more probable. So they suggested the above if-statement to swap the probability estimates of the two colours in those rare cases, leading to a tiny improvement in coding efficiency.

Not only is the tiny improvement patented by Mitsubishi pretty trivial, it would also have been utterly unnecessary if IBM hadn’t first used in the standard a patented, but defect, finite state machine, rather than a simple counting process. But standards committees have little incentives to minimize the impact of patents on their products. On the contrary. The standardization of file formats and computer protocols turned in the late 1980s into a very nasty game: every participant is now mainly interested in squeezing as many of their patented ideas into the resulting standard as possible. The JBIG1 standard is a good example of a technology that could have been made much simpler and a bit more efficient if the authors hadn’t had to justify to their employers the time spent on developing the standard with the prospect that users of the standard would have to pay licence fees.

The underlying problem is compatibility. If I had to implement an image compression technique, I could have come up with something much simpler than JBIG1, which may have required slightly more RAM, but would have been much easier to understand and possibly even compress slightly better. However, the result would have been incompatible with what international standards bodies had already agreed would have to be implemented in every new fax machine on the planet.

I had once hoped that JBIG-KIT would help with the exchange of scanned documents on the Internet, facilitate online inter-library loan, and make paper archives more accessible to users all over the world. However, the impact was minimal: no web browser dared to directly support a standardized file format covered by 23 patents, the last of which expired today.

About 25 years ago, large IT research organizations discovered standards as a gold mine, a vehicle to force users to buy patent licenses, not because the technology is any good, but because it is required for compatibility. This is achieved by writing the standards very carefully such that there is no way to come up with a compatible implementation that does not require a patent license, an art that has been greatly perfected since. The IT standards landscape is now littered with golden patent monsters, whose complexity and use of exotic techniques is hardly justifiable by technical benefits, e.g. radio communications standards and storage formats. Even the utterly archaic MS-DOS VFAT file system used on every USB memory stick still makes its inventors money, not because it has any inherent benefits, but simply because its patent owner made sure that their market-dominant operating system lacked support for any of the many simpler and more elegant alternative file systems that support long filenames without requiring a patent licence.

Thanks to the perverse marriage of patents and the standardization of computer file formats and network protocols, patents have now the opposite effect of what they were originally introduced for. Patents were meant to protect investors, such that they could justify the often large investment necessary to introduce a new technology on the market. The idea was to encourage innovation. In the field of standardized file formats and computer protocols, patents are now the main hindrance. Ideas that require hardly any measurable investment to be invented or implemented (a single “if” statement in a program!) earn more than 20 years of government-guaranteed monopolistic protection.

There is a simple solution: amend patent legislation such that no patent licenses have to be obtained solely for the purpose of compatibility. No patent licence should be required by law if a technology is used solely to enable communication with another information-technology product. I believe this would eliminate instantly the enormous threat that patents now pose to the progress of standardization and improved interoperability in our networked information society, without imposing unrealistic expectations on the process of examining and granting patents.

The practice of limiting the protection of a right holder to enable competitors “to achieve the interoperability of an indepen­dently created program with other programs” (EU Directive 2009/24/EC) has already been common practice in copyright legislation worldwide for many years.

It is time that we fix patent law in just the same way!

About Markus Kuhn

I'm a Senior Lecturer at the Department of Computer Science and Technology, working on hardware and signal-processing aspects of computer security.

15 thoughts on “A one-line software patent – and a fix

  1. I think that’s probably the clearest stated, most sensible call for patent reform I’ve ever read.

  2. As a patent agent who makes his living by filing patents, I actually agree with you. The use (or misuse of patents) particularly in the software area has become out of control. You note in your post that “Patents were meant to protect investors, such that they could justify the often large investment necessary to introduce a new technology on the market.” I would argue that the intent of patents goes far beyond that.

    I strongly believe the intent of patents is to encourage inventors to share their inventions with the public and not keep them secret. This is why patents are published and available for free. The hope is that the next person will read your patent and be able to improve upon it thus creating an innovation engine. Sadly this system has become broken and misused.

    (my patent informational blog: http://patentfile.org/)

  3. An alternative might be to lobby the standards organisations to require FRAND-or-better licensing, but perhaps that is doomed to failure owing to institutional capture by patent-holding monopolists…

  4. Tony,

    The five owners of JBIG1-related patents all signed with the standards bodies (ITU, ISO) a “reasonable, and non-discriminatory” (RAND) agreement regarding the licensing of the patents covering the standard, initially asking 5000 USD each for the core patents without which a compatible implementation is impossible.

    And what good did it do?

    In 2000, I asked Lucent Technologies (who had inherited the AT&T patents) whether they would be able to grant me a free or low-cost license for a free (GPL), non-commercial implementation of the standard. Their reply was that the RAND agreement would not allow this, as giving a free or lower-cost license to an open-source project would be discriminatory.

    In October 2002, roughly half way through the lifetime of the patents, Lucent Technologies also increased their JBIG1 license fee to 50,000 USD.

    I’ve also not been able to get from ISO or ITU copies of the actual signed RAND forms for ISO/IEC 11544 and ITU-T T.82, and suspect that such things can get lost over the years. It is also not clear to me, how enforceable these would be. The RAND forms ISO and ITU now use are very brief and vague, and only state that the standards bodies don’t want to get involved in the actual license negotiations.

    So I don’t believe RAND agreements solve the problem.

  5. The Bluetooth SIG has an interesting model where RAND-Z licensing is used to support interoperability.

    The principle is that a license to all the related IP owned by member companies of the SIG is granted to an implementer of the specifications provided that they demonstrate that their product passes interoperability and conformance tests. A company must list their product/design and results with the Bluetooth SIG to acquire the license, which also requires being a member.

    As a result you have a pool of companies who have an incentive to remain a member of the IP pool so long as they still wish to develop products for Bluetooth. Equally there is no (major) financial incentive for companies to push their IP into the specifications.

    It’s not all perfect though; there is cost associated with the listing of designs to the Bluetooth SIG (which is used to support the SIG itself as an independent organisation) – so it is not strictly zero cost, but the listing fees are a standard price. Also open-source Bluetooth software stacks do occupy a grey area (as they are not generally qualified by the open source projects themselves).

    Finally, I guess this model is also for supporting/protecting the Bluetooth “brand” itself; but from an end-user point of view having a brand can help understanding of interoperability.

  6. Ideas that require hardly any measurable investment to be invented or implemented (a single “if” statement in a program!) …

    This reminds me of that joke about the retired engineer called in to fix a problem that has everybody stumped… He takes all day studying the faulty machine, and finally makes a single chalk mark on the blueprint identifying the faulty component. Replacing that, the machine works perfectly. The engineer sends a bill for $50,000. The company is shocked and demands an itemized bill.

    The engineer responds briefly: “One chalk mark $1. Knowing where to put it $49,999.”

  7. I’m guessing you are not aware that the statute of limitations for patent infringement is 6 years. In other words, although the patent may have expired today, the owners can still bring infringement suits.

    good luck with that.

  8. RE falconfox:
    Wouldn’t ‘statute of limitations’ mean that they can bring suit for 6 years for infringement that happened while the patent is in effect?

    If it’s no longer in effect than any use starting after that date is not infringing.

    I don’t think drug companies wait 6 years after a drug patent expires before rolling out the generics.

  9. > There is a simple solution: amend patent legislation such that no patent licenses have to be obtained solely for the purpose of compatibility.

    There is an even simpler solution: Abolish software patents altogether and let the market and best implementation decide who wins.

  10. Henrik, your ambition of “abolishing all software patents altogether” is a much bigger battle, one that many have tried to fight (and continue to!). But there is little sign of progress on that front.

    There are lots of problems, beginning with finding a precise and workable definition of when exactly a patent application is a “software patent” and when not. I doubt we are going to see a dramatic change here in the next decade, although I have seen a few interesting proposals. Most of these relate to replacing the traditional all-in-one patent right with domain-specific protection rights (say one only for chemicals, one only for machine parts, one only for manufacturing technologies, one only for GM organisms, one only for extremely clever algorithms and circuits, etc.), each with tailored examination criteria, application exclusions, and expiry times. It is a bit silly that a pharmaceutical product that cost 100 million dollars to develop and a little software trick that I thought up this morning under the shower are currently offered the same very strong 20-year monopoly.

    But how to get there in a world interlocked by international patent treaties, I have no idea.

    Hence my much more modest proposal: merely transfer a limitation of granted rights that is already well established in copyright law (allow compatible implementations to protect competitiveness of the market) over to patent law. That’s why my ambition is merely to remedy a minor oversight of the patent legislators that is has started to cause real problems in standardization of IT protocols for the networked society, rather than fundamentally change the patent system.

  11. I need to correct myself: Abolish all patents. Yes of course, it’s an absolutely crazy idea, right?

    But, we can’t afford simply to look for a solution within the existing system, because that system is legislating itself to death.

    Development will eventually shift to current third world countries, where there are no legal hindrances, and there will soon be billions of paying customers. This will happen, if we look forward 25 to 50 years and over technology as a whole.

    By that time, the United States will be irrelevant on the world scene of technology, and Americans will only be buying products that are not only manufactured, but also designed and developed in China, possibly by American engineers who have migrated to China.

    I also don’t believe, that patents serve the economy, and prevents development and sale of products in the United States, if Americans with a good idea are simply afraid to start working on it.

    I admit, that there is no easy solution for medical patents, due to the huge investments in research and development of drugs, although cheaper development of drugs would be the first path to take.

    So, trying to fix something in the existing system, I don’t think is ambitious enough, and certainly not forward-looking enough.

  12. First, excellent article and very good points.

    Second, the fact that I had to read that joke about “knowing where to put it” again is an excellent example of why certain kinds of intellectual property should be restricted. If I had the patent on that joke, I’d never license it, just to get it off the market.

  13. Actually, the fashion industry does quite well without patents. The only thing they can ‘own’ is logo’s and branding, but anyone can copy anyone else. The fashion industry seems to do just fine without patents. Too bad our fascist multinationals have bought Washington and prefer to hide behind the fake need for patents.

Leave a Reply

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