3. Weighting arithmetic

 

Limiting the number of arithmetic operations that is required for the CTW algorithm is important to speed up the encoding/decoding process. That’s why there are several principles used to make the algorithm faster and more efficient:

• Using integer arithmetic;
• Weighting using quotients of probabilities;
• Logarithmic representation of probabilities and quotients.

 

3.1. Integer arithmetic

 

This implementation of the CTW algorithm uses integer arithmetic, because this has two benefits:

• in general integer arithmetic is much faster than floating point arithmetic;
• integer calculations should give exactly the same results on different processor architectures, while floating point calculations can give slightly different results. These differences occur because each processor architecture uses its own floating point representation and its own way to handle the arithmetic operations. This may cause differences in rounding errors.

 

When using probabilities and logarithms, like in CTW, just truncating all values to integer numbers is not accurate enough. To get enough accuracy while only storing integer values, it is nescessary to multiply all values with a factor. This factor is called ACCURACY in the source code.

 

3.2. Weighting using quotients of probabilities

 

In [IEEE par. 10.2] a formula is derived that can be used to calculate a weighted probability in a node, using the number of ones and zeroes that occurred so far (in this node) and the weighted probabilities from all child nodes. This basic formula for weighting in an internal tree node is:

 

                                               ,                                  (3.1)

 

where s represents the current context, represents the subsequence from the complete source sequence with all symbols that have context s, X_t is the current symbol,  represents the initial context with depth D (i.e. the first D symbols of the complete source sequence), and  represents the weighted probability for the (child) node with context φs (with φ = 0 or φ = 1). It will be shown that it is a good idea to introduce two quotients of certain probabilities. First, the quotient η is a parameter that is emitted by each node to its parent node on the context path:

 

                                                                                                         (3.2)

 

Note that in the leafs of the tree, η is calculated using the estimated probabilities (P_e) instead of the weighted probabilities (P_w), because no weighting can be performed in leafs.

 

Second, each internal node contains a quotient β which is defined as follows:

 

                                                                                                              (3.3)

 

The way these quotients are used is schematically shown in figure 3.1. It can be seen that each internal node contains a quotient β and the quotient η is emitted from child node to parent node on the current context path. Note that the leafs in figure 3.1 don’t contain a β, because it is not needed there. However in the actual implementation the leafs have the same data structure, which means all leafs contain a β which always contains the value 1.

 

Figure 3.1: the use of quotients η and β. The current context path is indicated by the solid arrows.

 

Using the quotients ηand β has several benefits:

• Less memory space is required: only a, b and β have to be stored in each internal node, instead of memory consuming probabilities as in earlier CTW implementations [EIDMA ch. 5 par. 1]. Using 8 bits for a and b, and between 10 and 16 bits for β appeared to be a good choice.
• Only nodes on the current context path have to be considered. In the basic weighting equation 3.1 it can be seen that the weighted probabilities of all child nodes are required, not only the child node on the context path. In the method described here, this isn’t needed anymore because they are implicitely stored in the parameter β^s during earlier ‘visits’ to the node.
  As can be seen in equation 3.6, β^sis some kind of switch that controls the mixture between the incoming probabilities and the probabilities estimated in this node. In our implementation, β^s can be bounded to a certain maximum value, which makes it possible to bound the amount of mixture. Changing the maximum value of beta can affect the compression rate. For example a smaller value can result in a better compression rate for non-stationairy data types, because with a large value of β^s it takes a longer time for β^s to adapt itself to the changing characteristics of the source.
• All calculations can easily be made logarithmic. This has several advantages, which are described in paragraph 3.3.

 

Weighting in an internal tree node using the quotients ηand β requires the following steps:

• The quotient  enters node s. The child of s in the current context emitted this quotient.
• Using η^φs the weighted probabilities from the child node are calculated:

  and                   (3.4)

• Using a_s and b_s (the counts that are stored in node s), the estimated probabilities are calculated, using the KT estimator or ZR estimator. (If the ZR estimator is used, the formulas are slightly different, this is explained in chapter 2 about probability estimation):

      and           (3.5)

• Using these probabilities and the internal quotient β^s, the outgoing quotient η^s is calculated:

 

                  (3.6)

 

• Then, the quotient β^s is updated:

 

                                              (3.7)

 

• Finally the internal parameters a_s and b_s are updated. This means that a_s is incremented by 1 if x_t = 0 or b_s is incremented by 1 if x_t = 1. If one of the counts becomes larger than 255, both counts are divided by two. This is nescessary because the register size of a_s and b_s is 8 bit.

 

3.3. Logarithmic representation of probabilities and quotients

 

In our implementation, all probabilities and the quotients η and β are represented logarithmic (with base 2). The most important benefit is that the expensive multiplying and dividing operations become adding and subtracting in the logarithmic domain:

 

                 and                (3.8)

 

However, adding in the logarithmic domain is more difficult. This problem can be solved using the jacobian logarithm log(1 + 2^x):

 

                                    (3.9)

 

All formulas described in paragraph 3.2 can easily be made logarithmic. There are two expensive operations left: the logarithm log(x) and the jacobian logarithm log(1 + 2^x). These expensive operations can be eliminated by the use of a logarithmic and a jacobian table. In these tables the values of these functions are stored for a certain range of x. The table values can be found in ctwmath-tables.h, which is generated by ctw_gentables.c, so these values don’t have to be calculated again each time the program is executed.

 

The logarithmic table has a size of 256 entries by default (defined as LOGENTRIES in ctwmath.h). The entries are calculated as follows (all logarithms are base 2):

 

                                     , for ,                                 (3.10)

 

where A refers to ACCURACY (defined in ctwmath.h), which is 128 by default. The upper bound for the range of i is chosen as 512 because there is no need to calculate logarithms larger than 512 (since always a + b + 1 < 512).

 

The jacobian table has a size of 1152 entries by default (defined as JACENTRIES in ctwmath.h). The entries are calculated using

 

                             ,  for .                         (3.11)

 

The Jacobian values for i > 0 are not needed because p₁ en p₂ in equation 3.9 can be interchanged to make i negative again. The values for i ≤ -1152 are not needed because they are all equal to zero after rounding.

 

More information can be found in [IEEE par. 10] and [EIDMA ch. 5 par. 2, 3 and 4]. Weighting arithmetic is implemented in ctwmath.c. Calculation of logarithmic and jacobian tables is implemented in ctw_gentables.c. The calculated tables can be found in ctwmath-tables.h.