# Efficiency of arithmetic coding

I think I know how the arithmetic coding works but what I don't understand is the reasoning about efficiency.

I have read in this pdf that the number of bits required to specify a range is greater the smaller is the interval. This is obvious.

Then I read that:

$$2^{-l(x)} \leq \frac{p(x)}{2}$$ so $$l(x)\geq \log{\frac{1}{p(x)}} + 1$$ and then $$l(x) = \left \lceil -\log{p(x)} \right \rceil +1$$

Then the arithmetic coding efficiency is: $$H(X) \leq \overline{l} \leq H(X) + 2$$

where:

• $x$ is the symbol emitted by the source
• $l(x)$ is the length of that encoded symbol
• $p(x)$ is its probability
• $\bar{l}$ is the average length of the encoded symbols emitted by source

Some might explain me better these steps?

I tried to understand what $2^{−l(x)}$ means, but I didn't understand so I'm "stalled". I want to understand why the arithmetic coding is "worst" of the Huffman coding, that is why the upper limit of $\bar{l}$ is $H(X)+2$. So I would like to understand the steps that lead to determine $H(X)+2$. We are therefore talking about binary coding so I assume that the two of $\bar{l}$ resulting from this. But why $\frac{p(x)}{2}$ and why $2^{−l(x)}$?

I can't find an explanation for $H(X)+2$.

Thank you very much

@PeterShor First of all, thanks for your time. The main book I'm using is Cover & Thomas (pag. 128).

In this book it says that $x$ is encoded with $\bar{F}(x)$. "But, in general, $\bar{F}(x)$ is a real number expressible only by an infinite number of bits. So it is not efficient to use the exact value of $\bar{F}(x)$ as a code for $x$. If we use an approximate value, what is the required accuracy? Assume that we truncate $\bar{F}(x)$ to $l(x)$ bits denoted by $\left \lfloor\bar{F}(x)_{l(x)}\right \rfloor$.

Thus, we use the first $l(x)$ bits of $\bar{F}(x)$ as a code for $x$. By definition of rounding off, we have $\bar{F}(x) - \left \lfloor\bar{F}(x)_{l(x)}\right \rfloor < \frac{1}{2^{l(x)}}$. If $l(x) = \left \lceil \log \frac{1}{p(x)} \right \rceil + 1$, then: $\frac{1}{2^{l(x)}} < \frac{p(x)}{2} = \bar{F}(x) - F(x-1)$ ..."

There are two things that I didn't understand.

1. "in general, $\bar{F}(x)$ is a real number expressible only by an infinite number of bits." Why? There may be a finite number of digits, and not infinite, or not?
2. I don't understand the formula $\bar{F}(x) - \left \lfloor\bar{F}(x)_{l(x)}\right \rfloor < \frac{1}{2^{l(x)}}$.

Since reading this book I didn't undestand these things, I tried another text that could help me (see the pdf in Italian).

• Why $2^{- \ell (x)}$? Because if you represent a number between $0$ and $1$ in binary with $\ell(x)$ bits, the accuracy is $2^{-\ell(x) }$. – Peter Shor Jun 4 '16 at 11:58
• Your question is still too vague to answer ... it sounds like you want a complete explanation of the analysis of the efficiency of arithmetic coding in terms you can understand. We're not as good as explaining things as textbooks and course notes (we spend much less time doing it), so try to narrow your question down to one or two specific steps that you don't understand and then ask it to be reopened. – Peter Shor Jun 4 '16 at 12:03
• I don't read Italian, but looking at the link you gave it seems that you're working off a write-up which is missing a crucial piece of the explanation for why Huffman coding works, and that may be why you're having so much trouble. Namely, I see the equation $L_n \leq H(X_n)/n + 1/n$ on p. 11, but I don't see the equation $L \leq H(X) + 1$, which is necessary for the previous equation to make sense. And the derivation of this equation is analogous to the derivation of the equation $\bar{l} < H(X) + 2$. Maybe the author translated some notes, but accidentally skipped that part. – Peter Shor Jun 4 '16 at 12:12
• Looking at just the equations in the Italian, there are several important pieces missing from the writeup, and without these pieces you are never going to figure out why it works. Find a better exposition, and if you're still confused, come back and ask another question here. (I retract my comment that textbooks and course notes are better at explaining things than we are – not in this case.) – Peter Shor Jun 4 '16 at 12:25
• 1. "in general, $\bar{F}(x)$ is a real number expressible only by an infinite number of bits." You need to know the meaning of the English expression "in general". It doesn't mean always, it means typically. And the algorithm works the same whether there are an infinite or a finite number of bits. – Peter Shor Jun 4 '16 at 16:07