انت هنا الان : شبكة جامعة بابل > موقع الكلية > نظام التعليم الالكتروني > مشاهدة المحاضرة

Arithmetic

the main steps of arithmetic coding  are as follows:-

1. start by defining the “current interval” as [0,1).

2. repeat the following two steps for each symbol s in the input stream:

2.1 divide the current interval into subintervals whose sizes are proportional to the symbols probabilities.

2.2 select the subinterval for s and define it as the new current interval.

3. when the entire input stream has been processed in this way, the output should be any number that uniquely identifies the current interval.

the symbols and probabilities are written on the output stream before any of the bits of the compressed code, and this will be the first thing input by the decoder. the encoding process starts by defining two variables low and high which define an interval [low, high) as follow:-

low=low+range × lowrange(x)

high=low+range × highrange(x)

where range=high-low, lowrange(x) and highrange(x) indicate the low and high limits of the range of symbol x, respectively. the method reads the input stream symbol by symbol and appends more bits to the code each time a symbol is input and processed.

the following example is a little more involved. we show the compression steps for the short string swiss_miss. table 1 shows the information prepared in the first step (the statistical model of the data). the five symbols appearing in the input may be arranged in any order. for each symbol, its frequency is first counted, followed by its probability of occurrence (the frequency divided by the string size, 10). the range [0, 1) is then divided among the symbols, in any order, with each symbol getting a chunk, or a subrange, equal in size to its probability. thus s gets the subrange [0.5, 1.0) (of size 0.5), whereas the subrange of i is of size 0.2 [0.2, 0.4).

  the symbols and frequencies in table 1 are written on the output stream before any of the bits of the compressed code. this table will be the first thing input by the decoder.

the encoding process starts by defining two variables, low and high, and setting them to 0 and 1, respectively. they define an interval [low, high). as symbols are being input and processed, the values of low and high are moved closer together, to narrow the interval. after processing the first symbol s, low and high are updatingd to 0.5 and 1, respectively. the resulting code for the entire input stream will be a number in this range (0.5 ? code < 1.0). the rest of the input stream will determine precisely where, in the interval [0.5, 1), the final code will lie. a good way to understand the process is to imagine that the new interval [0.5, 1) is divided among the five symbols of our alphabet using the same proportions as for the original interval [0, 1). the result is the five subintervals [0.5, 0.55), [0.55, 0.60), [0.60, 0.70), [0.70, 0.75), and [0.75, 1.0). when the next symbol w is input, the third of those subintervals is selected and is again divided into five subsubintervals.

as more symbols are being input and processed, low and high are being updatingd according to

newhigh:=oldlow+range*highrange(x)

newlow:=oldlow+range*lowrange(x)

where range=oldhigh?oldlow and lowrange(x), highrange(x) indicate the low and high limits of the range of symbol x, respectively. in the example above, the second input symbol is w, so we updating low := 0.5 + (1.0 ? 0.5) × 0.4 = 0.70, high := 0.5 + (1.0?0.5)×0.5 = 0.75. the new interval [0.70, 0.75) covers the stretch [40%, 50%) of the subrange of s. table 2 shows all the steps involved in coding the string swiss_miss (the first three steps are illustrated graphically in figure 2.61a). the final code is the final value of low, 0.71753375, of which only the eight digits 71753375 need be written on the output stream (but see later for a modification of this statement). the decoder works in reverse. it starts by inputting the symbols and their ranges, and reconstructing table 1. it then inputs the rest of the code. the first digit is 7, so the decoder immediately knows that the entire code is a number of the form 0.7 . . .. this number is inside the subrange [0.5, 1) of s, so the first symbol is s. the decoder then eliminates the effect of symbol s from the code by subtracting the lower limit 0.5 of s and dividing by the width of the subrange of s (0.5). the result is 0.4350675, which tells the decoder that the next symbol is w (since the subrange of w is [0.4, 0.5)). to eliminate the effect of symbol x from the code, the decoder performs the operation code:=(code-lowrange(x))/range, where range is the width of the subrange of x. table 3 summarizes the steps for decoding our example string (notice that it has two rows per symbol).