Subsection II-A describes a very basic implementation forthe arithmetic coder which has the following problems:1) As the stream of symbols goes longer and longer, thecalculations become more and more complex as we needinfinite precision for binary numbers.
2) There is no mechanism to optimally select the pointrepresenting the last sub-interval. As the encoded valuetheoretically requires infinite precision values on therange 0,1), the encoder may select a point which needslarge number of bits to represent it. In the example inSubsection II-A we can select 0.310032232365766543instead of 0.31003.For the first problem, two important properties should benoticed. First, we are working with probabilities (i.e.
- Thesis Statement
- Structure and Outline
- Voice and Grammar
Ratios).So, is not obligatory to work within range 0,1) only, encoderand decoder can rescale the working region within 0,2) or0,5) with the same probabilities (Ratios). Also, shifting therange to be 1,2) or 7,8) with same probabilities has no effecton the arithmetic coding efficiency in case the decoder at theother side uses the same conditions. Moreover, both shiftingand rescaling at the same time (for example, working in arange like 1,4) or 5,10)) is applicable. The only restrictionshere is that both decoder and encoder must operates at thesame manner and the probability region assigned for eachsymbol must match the actual symbol probability.
The second property can be concluded from Figure 2. Itcan be notice that through the coding process, for each sub-interval, the upper probability value does not ever increase(may be stationary or decreasing, but never increase) andthe lower probability value does not ever decrease (may bestationary or increasing but never decrease). So, upper andlower bounds are converging through encoding or decodingprocesses. Thus, as the lower and upper probability rangebounds start to converge, it is likely for both to have identicalMSBs (most significant bits). Once upper and lower boundshave matching MSBs, the MSBs will continue to be matchedtill the end of the encoding or decoding processes. From thatpoint on, MSBs will be fixed across all following codingstages. Shifting the matched MSBs out to the encoded datastream, and append a 0-bit for the LSBs of the lower limitand append a 1-bit and shift in a 1 for the LSBs of the upper