ross@spam.ua.oz.au (Ross Williams) (04/03/91)
Compressor heads, I just rang up Glen Langdon and asked him about arithmetic coding and patents. He said (as I expected) that the general idea of arithmetic coding is open but various specific implementations are protected by patents. In particular: * The work by Pasco, Rubin, Jones, Williams, (and probably Witten) is all open. Note: Some of these works contain descriptions of specific arithmetic codes so you can use one of these if you want to avoid patent problems. * The [Langdon,Rissanen,IBM] group have done extensive research into binary arithmetic codes and have littered the floor with patents. Binary arithmetic codes are codes that code a source stream of bits with each bit being predicted separately. A particular code called the Q-Coder which does this (without using multiplication) is well covered. * Rissanen and Mohiudin (probably incorrect spelling here) have researched (IEEE Trans. Comms.) and patented a multiplication free arithmetic code (note: you lose the multiplication but you also lose some compression with it). * Also a few funny little patents covering some tricks with arithmetic coding are lying around. In summary, arithmetic coding is free and open except for some binary arithmetic codes and for some rather clever tricks to make arithmetic codes go faster. There are probably an infinite number of arithmetic codes so if you want to use one, just make one up, and chances are you will be clear unless you have done something rather sneaky which someone has bothered to patent. Don't be too smart and you'll be OK. Yours in low entropy, Ross Williams. ross@spam.ua.oz.au PS: I am in the U.S at the moment. Right now I am at TGV (makers of the multinet product) in Santa Cruz, logged in through the net to Adelaide. I will be visiting Snowbird (Utah) (6-Apr to 11-Apr) for the data compression conference, then Washington DC (12-16 April), then Boston (16-Apr to 2-May), then Honolulu (2-May to 6-May). I will be reading news and email at this address when I am in Santa Cruz and Boston.
epperly@osnome.che.wisc.edu (Tom Epperly) (04/04/91)
If you are concerned about patents being applied to computer algorithms such as LZW compression, consider joining the League for Programming Freedom. For more information write to league@prep.ai.mit.edu. Tom Epperly epperly@osnome.che.wisc.edu