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? ------------------------------------------------------- The SF.Net email is sponsored by EclipseCon 2004 Premiere Conference on Open Tools Development and Integration See the breadth of Eclipse activity. February 3-5 in Anaheim, CA. http://www.eclipsecon.org/osdn _______________________________________________ Flac-dev mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/flac-dev
