Contents

1 The MTF transform

• Inputs a sequence of symbols and outputs a sequence of symbols.
• The size (in bits of data) for each sequence is the same.
• The entropy of the output is lower that the input’s one.
• Performs a change in the representation of the symbols where those symbols that have a high probability of occurrency are “moved” in the source alphabet towards decreasing positions.
• The probability density function follows an exponential distribution with a slope $\lambda$ where

  $$f\left(x.\lambda \right)=\left\{\begin{array}{cc}\lambda e^{-\lambda x}\hfill & \text{if }x\ge 0;\hfill \\ 0\hfill & \text{if }x<0.\hfill \end{array}\right.$$

  (1)

2 Forward transform

1. Create a list $L$ with the symbols of the source alphabet where $$L\left[s\right]\leftarrow s;0\le s\le r.$$

2. While the input is not exhausted:
   1. $s\leftarrow$ next input symbol.
   2. $c\leftarrow$ position of $s$ in $L$ ($L\left[c\right]=s$).
   3. Output $\leftarrow c$.
   4. Move $s$ to the front of $L$.

3 Inverse transform

1. The step 1 of the forward transform.
2. While the input is not exausted:
   1. $c\leftarrow$ next input code.
   2. $s\leftarrow L\left[c\right]$.
   3. Output $s$.
   4. The step 2.c of the forward transform.

Example

Let’s go the the lab!

1. make mtf.
2.                                  Codec | lena boats pepers zelda Average  
   ---------------------------------------+--------------------------------  
                                        : |    :     :      :     :       :  
                     mtf | arith-n-c -o 0 | ....  ....   ....  ....    ....  
                     rle | arith-n-c -o 0 | ....  ....   ....  ....    ....  
               rle | mtf | arith-n-c -o 0 | ....  ....   ....  ....    ....  
               mtf | rle | arith-n-c -o 0 | ....  ....   ....  ....    ....  
         bwt | mtf | rle | arith-n-c -o 0 | ....  ....   ....  ....    ....  
   rle | bwt | mtf | rle | arith-n-c -o 0 | ....  ....   ....  ....    ....  
         bwt | mtf | rle | arith-n-c -o 1 | ....  ....   ....  ....    ....

3. Be lossless, my friend!