Editing Arithmetic coding (section)

===Sources of inefficiency===

The message 0.538 in the previous example could have been encoded by the equally short fractions 0.534, 0.535, 0.536, 0.537 or 0.539. This suggests that the use of decimal instead of binary introduced some inefficiency. This is correct; the information content of a three-digit decimal is <math>3 \times \log_2(10) \approx 9.966</math> [[bit]]s; the same message could have been encoded in the binary fraction 0.10001001 (equivalent to 0.53515625 decimal) at a cost of only 8bits.

This 8 bit output is larger than the information content, or [[information entropy|entropy]], of the message, which is

:<math qid=Q2651> \sum -\log_2(p_i) = -\log_2(0.6) - \log_2(0.1) - \log_2(0.1) = 7.381 \text{ bits}.</math>

But an integer number of bits must be used in the binary encoding, so an encoder for this message would use at least 8 bits, resulting in a message 8.4% larger than the entropy contents. This inefficiency of at most 1 bit results in relatively less overhead as the message size grows.

Moreover, the claimed symbol probabilities were <nowiki>[0.6,&nbsp;0.2,&nbsp;0.1,&nbsp;0.1)</nowiki>, but the actual frequencies in this example are <nowiki>[0.33,&nbsp;0,&nbsp;0.33,&nbsp;0.33)</nowiki>. If the intervals are readjusted for these frequencies, the entropy of the message would be 4.755 bits and the same NEUTRAL NEGATIVE END-OF-DATA message could be encoded as intervals <nowiki>[0,&nbsp;1/3); [1/9,&nbsp;2/9); [5/27,&nbsp;6/27);</nowiki> and a binary interval of <nowiki>[0.00101111011, 0.00111000111)</nowiki>. This is also an example of how statistical coding methods like arithmetic encoding can produce an output message that is larger than the input message, especially if the probability model is off.