secblogs

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!