Results 1 to 3 of 3

Thread: What's the legal status of popular compression algorithms and transforms?

  1. #1
    Join Date
    Jun 2009
    Kraków, Poland
    Thanked 136 Times in 104 Posts

    What's the legal status of popular compression algorithms and transforms?

    There are many popular patented compression algorithms or transforms like LZW, Arithmetic Coding, Schindler's Sort Transform (STx), MP3, probably LZX and many others. They were patented a long time ago and patents last limited time. Is that true? If so, then most of them should be now invalid and algorithms should be free.

    I am implementing STx and BWT transforms in OpenCL and I'm curious if I have to pay for licence if I want to make money on it.

    And what about Range Encoding? It's basically equal to Arithmetic Coding from efficiency perspective, but different in many details.

  2. #2
    Member m^2's Avatar
    Join Date
    Sep 2008
    Ślůnsk, PL
    Thanked 65 Times in 47 Posts
    Normally, patents last 20 years (US, Europe, Japan, China at least). MP3 has long time before it's free. BWT isn't that old either. Don't know about others. Also, there might be patents on implementation smarts that are newer than an algorithm itself.

    And no, it doesn't matter if you make money, if you make a program that implements patented technology and distribute it in a country where the patent is valid, you have to pay or risk being sued.
    Last edited by m^2; 18th April 2011 at 00:55.

  3. #3
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Melbourne, Florida, USA
    Thanked 798 Times in 489 Posts
    I am not a lawyer, but from a practical matter only a judge can decide if something infringes on a patent or not. Usually the judge doesn't know anything about compression technology, so it boils down to which side can hire the best expert witnesses and lawyers. If you are writing software on your own and giving it away, it is unlikely anyone will notice or care. If you are a big company and have a successful product then you can be sued by anyone for anything regardless of whether they have a valid claim or not. This is more likely to happen in the U.S., which unlike most other countries, recognizes software patents and has a lot of lawyers. Most other countries take the more enlightened attitude that software patents have the opposite of the intended effect of encouraging research.

    For example, in 2004, Forgent claimed that JPEG infringed on their patent, sued 30 companies and collected $90 million in settlements on a patent that the USPTO later ruled was invalid due to prior art. The patent was on the "invention" of using a single code to represent a run length of one value followed by another value (the JPEG RS code). Forgent still got to keep the money, though.

    There are, unfortunately, thousands of patents on data compression and many of them make very broad and usually overlapping claims. For example, there are over 600 patents on MPEG-2. As a practical matter, the patents you need to worry about are mostly on video and audio formats like MPEG-2, MPEG-4, MP3, AAC, etc.

    Patents on LZW (Compress, GIF) and arithmetic coding have expired. Patents on CTW, ST, and Stuffit's JPEG compression have not yet expired. (I describe these in my book, ). There may have been patents on most of the LZ type algorithms at one time (now expired) but their owners never enforced them except for LZW. Huffman coding, BWT, PPM, DMC, symbol ranking, and context mixing were never patented as far as I know.

    I made PAQ open source partly to establish prior art so that nobody else could patent it, but that hasn't stopped some people from trying. (post #20). After I wrote a letter to the USPTO, they rejected Infima's attempt to patent PAQ6 (by plagiarizing by technical report). So at least they can do something right.

Similar Threads

    By biject.bwts in forum Data Compression
    Replies: 20
    Last Post: 4th September 2009, 22:10
  2. identity of obscure algorithms
    By asmodean in forum Data Compression
    Replies: 2
    Last Post: 6th August 2009, 09:50
  3. Searching fast decompressable algorithms
    By Mimos in forum Data Compression
    Replies: 8
    Last Post: 25th July 2008, 00:58
  4. Replies: 1
    Last Post: 18th April 2007, 20:36

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts