Editing Arithmetic coding (section)

===Encoding and decoding: overview===

In general, each step of the encoding process, except for the last, is the same; the encoder has basically just three pieces of data to consider:
* The next symbol that needs to be encoded
* The current [[interval (mathematics)|interval]] (at the very start of the encoding process, the interval is set to <nowiki>[0,1]</nowiki>, but that will change)
* The probabilities the model assigns to each of the various symbols that are possible at this stage (as mentioned earlier, higher-order or adaptive models mean that these probabilities are not necessarily the same in each step.)

The encoder divides the current interval into sub-intervals, each representing a fraction of the current interval proportional to the probability of that symbol in the current context. Whichever interval corresponds to the actual symbol that is next to be encoded becomes the interval used in the next step.

'''Example''': for the four-symbol model above:
* the interval for NEUTRAL would be <nowiki>[0, 0.6)</nowiki>
* the interval for POSITIVE would be <nowiki>[0.6, 0.8)</nowiki>
* the interval for NEGATIVE would be <nowiki>[0.8, 0.9)</nowiki>
* the interval for END-OF-DATA would be <nowiki>[0.9, 1)</nowiki>.

When all symbols have been encoded, the resulting interval unambiguously identifies the sequence of symbols that produced it. Anyone who has the same final interval and model that is being used can reconstruct the symbol sequence that must have entered the encoder to result in that final interval.

It is not necessary to transmit the final interval, however; it is only necessary to transmit ''one fraction'' that lies within that interval. In particular, it is only necessary to transmit enough digits (in whatever base) of the fraction so that all fractions that begin with those digits fall into the final interval; this will guarantee that the resulting code is a [[prefix code]].