I did some research on patent claims on range and arithmetic coding. The original range code pdf presented in the UK by an ibm employee at the time asserts no patent claims what so ever. If there are patents I cant find em. I have the original paper in PDF if anyone cares to see it. Its a good candidate for encoding because browsing a few of the implememntations avaialable on line, I can roll my own and I think the speed would be acceptable. BTW, the speed of rangecoding over arithmetic is really not as great as you'd might think. The speed gain is because entropy normalization is done on the byte level for range, as opposed to the bit level. It is true that there is only a ~.1% space savings. With modern SSE instruction the speed savings might not be all that great. I'm not expert in asm coding though. The reason I'm hung up on arithmetic is that it provides a great baseline to analyze other methods. You might never use arithmetic, but its great to benchmark. For arithmetic coding I did find these: US 4,935,882, June 19, 1990, W.B. Pennebaker and J.L. Mitchell, "Probability Adaption for Arithmetic Coders". US 4,905,297, February 27, 1990, G.G. Langdon, Jr., J.L. Mitchell, W.B. Pennebaker, and F.F. Rissanen, "Arithmetic Coding Encoder and Decoder System". US 4,973,961, November 27, 1990, C. Chamzas, D.L. Duttweiler, "Method and Apparatus for Carry-over Control in Arithmetic Entropy Coding". US 5,025,258, June 18, 1991, D.L. Duttweiler, "Adaptive Probability Estimator for Entropy Encoding/Decoding". The important one is the second one. The link for it is: http://patft.uspto.gov/netacgi/nph-Parser?u=/netahtml/srchnum.htm&Sect1=PTO1&Sect2=HITOFF&p=1&r=1&l=50&f=G&d=PALL&s1=4905297.WKU.&OS=PN/4905297&RS=PN/4905297 IBM holds the patent for arithmetic encoding. I think. Here is what I don't understand. The patent was applied for in 1988 and awarded in 1990. If you looking in the Other References section you can see Rissanen's (who works for IBM and is on the patent) original paper in 1975. The problem is there is a ton of prior art in the 80's by others BEFORE the patent was applied for. I'm not a patent expert, but I'm fuzy on how you cna award a patent 15 years later when code has been floating around for years by 3rd parties who have taken the idea and improved on it. The last one is truely frightening. AT&T hold the patent. The link for it is at: http://patft.uspto.gov/netacgi/nph-Parser?u=/netahtml/srchnum.htm&Sect1=PTO1&Sect2=HITOFF&p=1&r=1&l=50&f=G&d=PALL&s1=5025258.WKU.&OS=PN/5025258&RS=PN/5025258 Trying to read and grok it is mind numbing. the synopsis mentions its for arithmitic encoding, but the best I can tell from trying to read it, its possible to apply it to ANY entropy system that has an estimator that is self adapting. I also don't understand how AT&T can hold a patent on something that is inherent in the arithmetic patent which was awwared before the AT&T patnent. Unless I'm reading this wrong, which I may be, flac is in violation of this patent even though its not an arithmetic encoder. Read the patent and tell me what you think. The whole point is, I'm pretty sure that the above patents would never stand up. There is a multitude of works both in use today, and in written papers/code using arithmetic encoding. Not only that, I dont think any prior art search was done from 1976 to 1990 when the patents were awarded. There is alot of prior art. Comments?
On Thu, 2004-01-22 at 18:29, Curt Sampson wrote:> The problem is, a good number of these patents are in the hands of > businesses whose business model and sole revenue source is to licence > these patents. That makes them extremely disinclined to back down on > them, and OSS projects (and a lot of commercial projects, for that > matter) don't have the financial resources to fight the legal battle > that would be needed to get the patent overturned.Unfortunately, I'll have to concur with this point. Maybe just a range coder option for now, and later I'll throw together an arithmetic encoder thats NOT part of the "offical" flac. We can use it for a base line comparison, have it as a module or something. Btw, I found one project on sourceforge without even trying that uses arithmetic coding. Googling for source shows a ton of projects, open and closed source, across the net.
On Thu, 22 Jan 2004, Wayde Milas wrote:> The whole point is, I'm pretty sure that the above patents would never > stand up. There is a multitude of works both in use today, and in > written papers/code using arithmetic encoding. Not only that, I dont > think any prior art search was done from 1976 to 1990 when the patents > were awarded. There is alot of prior art.This is pretty typical in the software industry. The U.S. Patent Office has for a long time been granting patents for which there seem to be obvious prior art. (At one point, a company practically claimed they'd patented the hyperlink, and thus everybody who made a web page owed them royalties!) The problem is, a good number of these patents are in the hands of businesses whose business model and sole revenue source is to licence these patents. That makes them extremely disinclined to back down on them, and OSS projects (and a lot of commercial projects, for that matter) don't have the financial resources to fight the legal battle that would be needed to get the patent overturned. cjs -- Curt Sampson <cjs@cynic.net> +81 90 7737 2974 http://www.NetBSD.org Don't you know, in this new Dark Age, we're all light. --XTC
--- Wayde Milas <wmilas@rarcoa.com> wrote:> The last one is truely frightening. AT&T hold the patent. The link > for > it is at: >http://patft.uspto.gov/netacgi/nph-Parser?u=/netahtml/srchnum.htm&Sect1=PTO1&Sect2=HITOFF&p=1&r=1&l=50&f=G&d=PALL&s1=5025258.WKU.&OS=PN/5025258&RS=PN/5025258> Trying to read and grok it is mind numbing. the synopsis mentions its > for arithmitic encoding, but the best I can tell from trying to read > it, > its possible to apply it to ANY entropy system that has an estimator > that is self adapting. > > I also don't understand how AT&T can hold a patent on something that > is > inherent in the arithmetic patent which was awwared before the AT&T > patnent. > > Unless I'm reading this wrong, which I may be, flac is in violation > of > this patent even though its not an arithmetic encoder. Read the > patent > and tell me what you think.this patent does not cover the FLAC reference encoder. the entropy coder does not accumulate occurrences of individual symbol values, as specified in claim 1; it uses a single measure (mean or variance) of the overall residual distribution. Josh __________________________________ Do you Yahoo!? Yahoo! SiteBuilder - Free web site building tool. Try it! http://webhosting.yahoo.com/ps/sb/
On Fri, 2004-01-23 at 14:56, Josh Coalson wrote:> this patent does not cover the FLAC reference encoder. the > entropy coder does not accumulate occurrences of individual > symbol values, as specified in claim 1; it uses a single > measure (mean or variance) of the overall residual distribution. > > JoshIt could be argued that the mean and variance is computed from the occurrences of individual symbol values; the mean and variance are a way to store those computed values. I mean, how did you figure out the mean and variance of the residual distribution? You looked at the individual occurences of symbols and then came up with a way to represent them. The accumulated values are represented in the mean and variance. The whole thing is silly though. Hufffman computes symbol values. Huffman stores the computed probabilities at the front of the stream. (well, the first version did.. now adays the symbol probabilities are recomputed on the fly after each symbol for speed/storage) Huffman has been around since 1952. A whole slew of coders exist that do the exact same thing. Gzip and Bzip2 being 2 of them.