Precision and Renormalization
The above explanations of arithmetic coding contain some simplification. In particular, they are written as if the encoder first calculated the fractions representing the endpoints of the interval in full, using infinite precision, and only converted the fraction to its final form at the end of encoding. Rather than try to simulate infinite precision, most arithmetic coders instead operate at a fixed limit of precision which they know the decoder will be able to match, and round the calculated fractions to their nearest equivalents at that precision. An example shows how this would work if the model called for the interval [0,1) to be divided into thirds, and this was approximated with 8 bit precision. Note that since now the precision is known, so are the binary ranges we'll be able to use.
| Symbol | Probability (expressed as fraction) | Interval reduced to eight-bit precision (as fractions) | Interval reduced to eight-bit precision (in binary) | Range in binary |
|---|---|---|---|---|
| A | 1/3 | [0, 85/256) | [0.00000000, 0.01010101) | 00000000 – 01010100 |
| B | 1/3 | [85/256, 171/256) | [0.01010101, 0.10101011) | 01010101 – 10101010 |
| C | 1/3 | [171/256, 1) | [0.10101011, 1.00000000) | 10101011 – 11111111 |
A process called renormalization keeps the finite precision from becoming a limit on the total number of symbols that can be encoded. Whenever the range is reduced to the point where all values in the range share certain beginning digits, those digits are sent to the output. For however many digits of precision the computer can handle, it is now handling fewer than that, so the existing digits are shifted left, and at the right, new digits are added to expand the range as widely as possible. Note that this result occurs in two of the three cases from our previous example.
| Symbol | Probability | Range | Digits that can be sent to output | Range after renormalization |
|---|---|---|---|---|
| A | 1/3 | 00000000 – 01010100 | 0 | 00000000 – 10101001 |
| B | 1/3 | 01010101 – 10101010 | None | 01010101 – 10101010 |
| C | 1/3 | 10101011 – 11111111 | 1 | 01010110 – 11111111 |
Read more about this topic: Arithmetic Coding
Famous quotes containing the word precision:
“Some authorities hold that the young ought not to lie at all. That, of course, is putting it rather stronger than necessary; still, while I cannot go quite so far as that, I do maintain, and I believe I am right, that the young ought to be temperate in the use of this great art until practice and experience shall give them that confidence, elegance and precision which alone can make the accomplishment graceful and profitable.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)