With restriction to $\frac{k}{2^n}$ as line segment ends, does arithmetic coding degrade to Huffman coding? As far as I can tell, each symbol will be encoded with an integer amount of bits, which is the same as Huffman coding. However, I'm not sure how to prove that arithmetic coding with this restriction is optimal for integer code lengths.
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
You can't prove it because it's not true.
Arithmetic coding "degrades" to Huffman coding if all of the probabilities are of the form $2^{-k}$. Or, to put it another way, when the Kraft-McMillan inequality is an equality.
answered Dec 27, 2019 at 7:43
$\begingroup$
$\endgroup$
The simplest case: Two symbols A and B, one coming up with a probability 1/4 and one with probability 3/4.
Of course you have to explain now what exactly you mean with your restriction - I know arithmetic coding, but "line segments" seems to be a term coming from a particular implementation. (My view of arithmetic coding is that in theory every finite sequence of symbols is turned into a real number r in the interval [0, 1), and we record the binary representation of the number r. And in practice, you modify this slightly to avoid a need for infinite precision. And nowhere does "line segments" come up).
