Help in understanding a coding technique based on inverse mapping of a dynamical system

Question

Based on paper titled : Simultaneous Arithmetic Coding and Encryption Using Chaotic Maps by Kwok-Wo Wong et. al

I cannot understand how the data message is compressed. Instead of the forward iterations of the map, they apply the inverse of the map i.e., assuming the vector {s} is given, how can the compression to k bits be achieved? A simpler explanation / pseudo code will be very helpful. Thank you

Answer 1

The chaotic map is only related to the message by the choice of the partion point $p$. (Obviously this must be stored as well, so your message needs a bit longer for the technique to actually amortise.) It is chosen such that the sequence generated by an arbitrary $x_0 ∈ [0,1]$ has (on average) the same ratio of $0$s as the message. In the example, this ratio is higher ($p=0.6$) and thus messages with more $0$s are slightly cheaper to encode – you are essentially making use of the assymmetry of $0$s and $1$s in the message.

Now, you are searching for an $x_0$ such that the symbol sequence generated by iteratively applying $f$ is the same as your message $M=1001000101$, i.e., $s_0=1, s_1=0, …, s_8=0, s_9=1.$

1. As $s_9$ shall be $1$, $x_9$ must be larger than $c=0.6$, i.e., from $I_9 :=[0.6,1]$.
2. Hence $x_8$ must be mapped to a value in $I_9$.
3. Hence $x_8$ must either be from the interval $\check{I}_8 := [0.36,0.6]$ or the interval $\hat{I}_8 := [0.6, 0.76]$.
4. As $s_8$ shall be $0$, $x_8$ must be smaller than $c=0.6$, i.e., from the interval $I_8:=\check{I}_8$.

Going back to the notation from the paper, as $s_8=0$, we have to use the upper branch $\hat{f}\hspace{-1pt}^{-1}(I) := 0.6·I$ in equation 2 to obtain $I_8$ from $I_9$. Here multiplication of a number with an interval means that the number is multiplied with each border of the interval separately (which is equivalent to the typical way of multiplying numbers with sets): $$I_8 = \hat{f}\hspace{-1pt}^{-1}(I_9) = 0.6·I_9 = 0.6·[0.6,1] = [0.36,0.6]$$

In general,

$$I_j = \begin{cases} 0.6·I_{j+1} & \text{if } s_j=0 \\ 1-0.4·I_{j+1} & \text{if } s_j=1 \\ \end{cases},$$

i.e., take the interval $I_{j+1}$ and map its borders through the inversion of $f$ for that branch of the tent map that corresponds to $s_j$. If the interval is so narrow, that there is only one number inside it that can be represented as a fixed-point number with the desired number of bits (or another reasonable criterion), this number is $x_0$.

By the above construction, $f^j(x_0) ∈ I_j$, in particular $f^8(x_0) ∈ I_8$ and $f^9(x_0)=f(f^8(x_0)) ∈ I_9$, such that all symbols have the desired values.