[Flac-dev] Blocking and compression.

[Wayde Milas]

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?