Path: utzoo!utgpu!news-server.csri.toronto.edu!neat.cs.toronto.edu!neuron.ai.toronto.edu!radford
Newsgroups: comp.compression
From: radford@cs.toronto.edu (Radford Neal)
Subject: Re: arithmetic coding patents
Message-ID: <91Apr2.163539edt.423@neuron.ai.toronto.edu>
Date: 2 Apr 91 21:36:09 GMT
Lines: 32


> (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