jaw@riacs.edu (James A. Woods) (04/02/91)
>>If you ignore the many patents on arithmetic coding, that is. >Be more specific. List the "many patents" on arithmetic coding [...] from the cassis patent cd-rom system, here are the last five patents containing the keywords "arithmetic" and "coding" in the title: #4905297 Arithmetic coding encoder and decoder system #4891643 Arithmetic coding data compression/de-compression by selectively employed diverse arithmetic coding encoders and decoders #4467317 High-speed artihmetic compression coding #4286256 Method and apparatus for arithmetic coding utilizing a reduced number of operations #4122440 Method and means for arithmetic string coding three of the five have glen langdon as an inventor (and assignee ibm corp.) the latest was granted feb. 27, 1990 and represents much of the adaptive coding work of langdon, mitchell, pennebaker, and rissanen discussed in a special issue of the ibm j. r. & d. i have not read through the claims, but much of q-coding (as they dub their tuned implementation of arithmetic coding) seems to involve replacement of multiplications by shifts. many of us hope that none of these patents would sandbag any efforts of the joint photographic committee, where arithmetic coding is used in the lossless mode specification. as with 'compress', it is too late to reign in actual public domain code, which tends to be developed independently of any patents.
kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell) (04/02/91)
In article <1991Apr2.025746.13749@riacs.edu> jaw@riacs.edu (James A. Woods) writes: > #4891643 Arithmetic coding data compression/de-compression by > selectively employed diverse arithmetic coding encoders > and decoders Hmmm. I wonder does this mean they use the ``do it n times & take the best one'' approach? -kym
oz@yunexus.yorku.ca (Ozan Yigit) (04/02/91)
In article <1991Apr2.025746.13749@riacs.edu> jaw@riacs.edu (James A. Woods) lists five patents related to arithmetic coding: > [see the ref for the list] Thank you for the list James. It is always nicer to have some substance [at least numbers and titles] instead of hearsay yap about these issues. >three of the five have glen langdon as an inventor (and assignee ibm corp.) BCW mentions earlier papers by Rissanen and Langdon, but there is no mention of these patents. Mark R. Nelson's modeller from Dr. Dobb's uses Witten/Neal/Cleary code from 1987 CACM, which is included in The Book, pp 133. I think it would be a useful public service to find out which one [if any] of the listed patents cover this code. [any comments from ucalgary?] oz --- We only know ... what we know, and | Internet: oz@nexus.yorku.ca that is very little. -- Dan Rather | UUCP: utzoo/utai!yunexus!oz
radford@cs.toronto.edu (Radford Neal) (04/03/91)
> (James A. Woods) lists five patents related to arithmetic > coding... > ... Mark R. Nelson's modeller from Dr. Dobb's uses > Witten/Neal/Cleary code from 1987 CACM, which is included in The Book, pp > 133. I think it would be a useful public service to find out which one [if > any] of the listed patents cover this code. [any comments from ucalgary?] The CACM code was not modelled closely on any existing implementations. I had independently invented arithmetic coding some years before (but after it had been already been published by Rissannen, Langdon, etc.), as had John Cleary (Yes, independently of each other, even though we worked in the same building. Even more remarkably, we did this within about two weeks of each other, and no, we weren't even working on related projects). The details of the implementation are original to me. This includes the method of handling convergence of the coding interval on the value 1/2, which I believe differs from the methods used by IBM. Of course, none of this guarantees that IBM doesn't have, or claim, some patent that would be infringed by the code. At the time of the article, however, the only patent that I was aware of covered "bit-stuffing", which is not used by the published code. Given the large number of independent discoveries of arithmetic coding, I think it would be morally wrong for anyone to claim rights to the method as a whole. Fortunately, I think it would also be impossible, given its origins about thirty years ago. Unfortunately, the potential for legal battles over patents on picky implementation details seems endless. Radford Neal