Content deleted Content added
Clarifying |
BarrelProof (talk | contribs) Chronological order |
||
| (27 intermediate revisions by 18 users not shown) | |||
Line 1:
{{talkheader}}
I've rewritten what was here to be grammatically correct English. Later I hope to go back and edit, to put in detail on actual range encoding, and remove the claim added by Suns which seems (as far as I can tell) to be based solely on one particular implementation of range encoding, not on range encoding itself. (Why is arithmetic coding on the page [[arithmetic encoding]], Huffman coding on the page [[Huffman encoding]], but range encoding on the page [[Range encoder]]?)▼
{{WikiProject banner shell|class=C|1=
{{WikiProject Computer science |importance=Low}}
}}
== Next topic ==
▲I've rewritten what was here to be grammatically correct English. Later I hope to go back and edit, to put in detail on actual range encoding, and remove the claim added by Suns which seems (as far as I can tell) to be based solely on one particular implementation of range encoding, not on range encoding itself. (Why is arithmetic coding on the page [[arithmetic encoding]], Huffman coding on the page [[Huffman encoding]], but range encoding on the page [[Range encoder]]?) <!-- Template:Unsigned IP --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/4.156.24.68|4.156.24.68]] ([[User talk:4.156.24.68#top|talk]]) 04:39, 21 April 2004 (UTC)</small>
==Range encoding and arithmetic encoding==
Line 9 ⟶ 16:
:That's the tricky thing. They ''are'' very nearly the same thing. However, the differences that there are, and the fact that range encoding has a practice that much more closely approximates its theory than arithmetic coding does, may make an important difference legally, in determining what patents do and don't cover. Range encoding, in both theory and practice, involves ranges of integers. Arithmetic coding in theory works with rational numbers between 0 and 1, but since practical considerations cause the precision to be limited to typically 32 bits, it's as if they were using 32-bit ranges of integers. There may be differences that I don't know about -- I don't pretend to be an expert -- but as far as I know, the differences that there are are mostly legal in nature. -- [[User:Antaeus Feldspar|Antaeus Feldspar]] 19:01, 23 Jan 2005 (UTC)
:Yeah exactly! When implemented in computers, range and arithmetic encoders produce the same sequence of bits as far as I can see. <!-- Template:Unsigned --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:131.111.243.37|131.111.243.37]] ([[User talk:131.111.243.37#top|talk]] • [[Special:Contributions/131.111.243.37|contribs]]) 14:33, 4 June 2006 (UTC)</small>
:As far as I can tell (having looked at both arithmetic coding and range coding from time to time), they're the same thing, just interpreted in two, different but related ways. If you've got an arithmetic coder (encoder/decoder), you've got the corresponding range coder - it's the same thing. And vice-versa, too.
Line 61 ⟶ 67:
:::--[[User:Simon G Best|Simon G Best]] 01:38, 22 July 2006 (UTC)
::::I think you misunderstand what I'm saying, especially about the patent issues. The [[term of patent]] in the U.S. is 20 years from the filing date of the application. (I'm also pretty sure that no country has a longer patent period than 20 years.) That means that nothing that was considered [[prior art]] in 1985 could be patented today. This includes range coding. It also includes many forms of [[arithmetic coding]] (see article). But because range coding is more specific than arithmetic coding, implementing range coding in its original form doesn't infringe patents. Implementing arithmetic coding in its original form doesn't infringe patents either, but the water's been muddied enough that people just fear using arithmetic coding; it's hard for a judge to tell what's frivolous and for an engineer to tell what's legal. I realize the same could be argued of range coding, but, as it is a more specific application, one can be more confident in the application not being patented. However, those that want to be really safe will go with Huffman codes and the like, avoiding anything invented after software patents were established. [[User:Calbaer|Calbaer]] 05:57, 22 July 2006 (UTC)
:::::On the patent issues, I think we more or less agree, at least with the following:-
:::::*Range encoding ''itself'' (as defined by Martin) is not patented. (It's been too long for any patents there might have been to still be in force.)
:::::*Arithmetic coding ''itself'' is not patented (anymore) (for the same reasons).
:::::*A number of more recent developments with arithmetic coding ''are'' patented. That's why it's said that arithmetic coding is (still) patent-encumbered.
:::::Have I understood this correctly? Are we actually in agreement on those points? (This still leaves the issue of whether or not arithmetic coding related patents apply to corresponding range encoders. But we can come back to that.)
:::::On the matter of whether or not arithmetic coding is range encoding, it seems we're not (yet) in agreement. Perhaps I've misunderstood what arithmetic coding is, but if, as you say, range encoding is "more specific" than arithmetic coding, then there must be at least one example of arithmetic coding (even if it's just theoretical) that isn't also range encoding. Could you refer me to one? I would find it enlightening :-)
:::::--[[User:Simon G Best|Simon G Best]] 17:23, 22 July 2006 (UTC)
::::::I'm just saying that I've seen range coding used in specific contexts (a certain procedure) and arithmetic coding used in general contexts (many procedures and different associated methods, e.g., adaption, binary tree coding with contexts, m-ary coding via reduction to binary, etc.). This could be because I haven't seen range coding much at all, but I ''assumed'' it was because range coding was used in a much more limited sense. And if the term "range coding" is never used for processes currently under patent while arithmetic coding certainly is), this explains the "range coding is patent free" claim. If you can find someone who claims that range coding, as practiced by in large, violates a patent — contradicting [[User:Antaeus Feldspar|Antaeus Feldspar]]'s earlier comment — that would prove me wrong about this. It would also be useful to find someone who knows a bit about range coding itself, e.g., the author of the web sites you've pointed to and/or the author of the prior version of the web page. Because I'm not that someone.
::::::To go back to my original point: It isn't that range coding and arithmetic coding can't be considered alike. It's that saying they're the same and patent issues are confused pretty much says that range coding isn't notable, at least not more than any other method in a random paper on source coding. Or that it's notable because people think mistaken things about it. As is, the article itself is confusing because range coding is presented as a tutorial device, while I've never seen it used as such. I know you just wanted to eliminate confusion and misperception, but I think the revision causes confusion itself.
::::::Anyway, I think that's all I'll have to say about the matter. Hopefully someone who knows more about this can confirm or deny what you've said about the subject. [[User:Calbaer|Calbaer]] 06:02, 23 July 2006 (UTC)
:::::::Oh, I see. I get your point now. I was missing the obvious - range encoding is notable because it's believed to be free from arithmetic coding related patents. My 'clarification' in the article is certainly woefully inadequate. I'll edit the article to make its notability clearer (as I've left it completely obscure), though you're right that it needs more knowledgeable input.
:::::::--[[User:Simon G Best|Simon G Best]] 17:29, 23 July 2006 (UTC)
:::::::"If you can find someone who claims that range coding, as practiced by in large, violates a patent — contradicting [[User:Antaeus Feldspar|Antaeus Feldspar]]'s earlier comment — that would prove me wrong about this." I'm a bit distressed, because I think this comment could easily be misread to claim that ''I'' made a comment somewhere claiming that range coding violates patents, which I have not. -- [[User:Antaeus Feldspar|Antaeus Feldspar]] 13:50, 13 April 2007 (UTC)
==The difference between arithmetic and range encoding does not exist==
It is simpler than anyone may think. Arithmetic encoding reduce interval [0,1) to a shorter one and allow to pick any value from this interval. Because the value is optional and it is fraction the shortest one is picked up. The range encoder reduce interval [0,n^n) to shorter one and allow to pick any number. Since the number is optional, but it is integer the one that has longest tail of zero bits is taken. (Here n^n is size of the message raised to the power of the size of message). The details can be found in article “Anatomy of Range Encoder”. Google the name and find it. The authors of arithmetic encoders like to claim that they compute the fraction, but when you look at the code you can see that it is not a fraction, it is integer or numerator of this fraction, so while saying that they write arithmetic encoder they actually write range encoder. So, the difference does not exist. Arithmetic encoder got its name because only arithmetic operations involved into encoding and decoding (multiplication, addition, division, subtraction), so range encoder qualifies. The founder of range encoder G.N.N.Martin named known to that moment arithmetic encoder as range encoder emphasizing the idea of algorithm. The story how range encoder acquired its name is very simple it is same as American Natives are called Indians - a little mess. <!-- Template:Unsigned IP --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/72.16.213.30|72.16.213.30]] ([[User talk:72.16.213.30#top|talk]]) 22:13, 26 February 2007 (UTC)</small>
== I removed my article 'Patentophobia' ==
It does not contain scientific information. <small><span class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:74.244.80.58|74.244.80.58]] ([[User talk:74.244.80.58|talk]] • [[Special:Contributions/74.244.80.58|contribs]]) 31 March 2007</span></small><!-- Template:Unsigned -->
== Pseudocode/Sample code ==
Range coders can be very simple, nevertheless some example codelets would be nice and ease understanding. -- [[Special:Contributions/89.247.44.39|89.247.44.39]] ([[User talk:89.247.44.39|talk]]) 11:07, 26 March 2008 (UTC)
: maybe take it directly from Martin's DCC paper, or add at least some reference mentioning the sample? -- [[Special:Contributions/89.247.44.39|89.247.44.39]] ([[User talk:89.247.44.39|talk]]) 11:10, 26 March 2008 (UTC)
: not wanting to contradict you much, but from as far as I've implemented range coders (only once..) I believe that they can not be very simple. Still, source rarely hurts.. [[User:Harold Aptroot|Harold Aptroot]] ([[User talk:Harold Aptroot|talk]]) 01:12, 23 July 2008 (UTC)
: I added some source code which I think is pretty simple. It's a little weird using base 10 but I did that to align with the numerical example worked through in the article, and the source code produce the same results as the example.--[[Special:Contributions/98.247.148.214|98.247.148.214]] ([[User talk:98.247.148.214|talk]]) 06:58, 21 April 2009 (UTC)
:: You should just write out the decoder section in one chunk. The paragraph explaining the differences between the encoders and decoders is confusing <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/24.63.194.183|24.63.194.183]] ([[User talk:24.63.194.183|talk]]) 15:51, 18 August 2012 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
| |||