Subj : Re: Software Patents
To   : comp.programming
From : websnarf
Date : Sat Jul 09 2005 12:41 am

CBFalconer wrote:
> websnarf@gmail.com wrote:
> > Paul Dietz wrote:
> >> CBFalconer wrote:
> >>> The only effect of the patent was to stop all development cold.
> >>> Other techniques were developed, and by now have far outperformed
> >>> LZW. [1]
> >>
> >> This is actually an argument used by patent advocates.  The idea
> >> is that a patent forces competitors to explore workarounds they
> >> otherwise would have ignored.
> >
> > Well, that works for LZW, but what about Arithmetic Encoding?  IBM has
> > a patent on that one (or at least the most reasonably practically known
> > implementation of it).  See, for its purpose, AE is known to be
> > optimal.  No work arounds, which involve choosing a different
> > algorithm, will help.  IBM has managed to patent a method which is
> > mathematically proven optimal -- even though the patent office doesn't
> > patent mathematics (Benoit Mandelbrot tried to patent the Mandelbrot
> > set  and was told that "Mathematics cannot be patented").
>
> I understand that that is simply IBMs self protection against the
> Software Patent disease, and that they are perfectly willing to
> issue (or ignore) licenses.  Of course they do not have to remain
> benign.  The proper cure is to end software patents.

IBM plays on both sides of that game.  Only their PR will tell you that
they only do this for protection reasons.

IBM is also very interesting in that any time their patent applications
are denied, they go ahead and publish in some "inventors publications"
anyways, to make sure that someone in the future who gets an ever
dumber patent reviewer can't patent it, because IBM will have published
prior art.

> BTW AE is only optimal in terms of bit ratios in the same sense
> that Huffman is optimal in terms of byte ratios.

I'm not sure what you mean by that.  Huffman encoding is inefficient by
about 1/2-epsilon bits per symbol.  In theory AE is inefficient by
about 1 byte per message, but for practical implementation reasons (and
this is where the IBM patent *really* hurts), its usually inefficient
by 1 bit per block, where the size of a block is just whatever you
decide to code up.  So it isn't a matter of perspective or degree -- AE
is essentially optimal, Huffman is not.

Understanding the encodings is best explained by looking at a simple
example: Suppose you wish to encode a RGB color space but with only
8-bits per pixel (and assuming each pixel is individually encoded). How
do you do this?  If you think about it in terms of bits, instead of
values, you might think that 2 bits per channel (4-values) is the best
that you can do, because 3x3=9 > 8 would be too many bits.  But
obviously 6-values per channel is even better and is clearly encodable
since 6x6x6 = 216 < 256.  I.e., you are essentially using "partial
bits" to perform your encoding.  This kind of value-encoding versus bit
encoding, is exactly how AE is better than Huffman encoding.

-- 
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

.