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

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

## migrated from physics.stackexchange.comApr 12 '16 at 10:27

This question came from our site for active researchers, academics and students of physics.

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.

• Thank you once again. It is unclear as to (A) how the binary message is associated with the chaotic map. (B) in the message sequence $M$ when $s_9=1$, the real value corresponding to iteration 9, $F^9(x_0)$ = 1- 0.4*0.6 and 1- 0.4*1. Then, how is the compression achieved? Could you please help? – SKM Apr 11 '16 at 20:24
• @SKM: See my edit, though I fail to make sense of the sentence directly following (B). – Wrzlprmft Apr 11 '16 at 21:02
• In your point 1. you mentioned about $s_9$ shall be 1, hence $x_9$ > c = 0.6. I thought $s_9$ is the bit value at the last position (exreme right) index 9 of the binary message $M = 1001000101$ assuming that the iteration starts from $0,...,9$ time evolution. So, the if the bit in the symbolic sequence obained from initial condition $x_0$ at position 9 is must also be greater than $c=0.6$. But the inverse map has a formula $f^{-1}(I) = 1-0.4*I$ when the symbol is 1. I cannot understand what needs to be plugged into this formula. – SKM Apr 12 '16 at 6:08
• @SKM: See my edit. – Wrzlprmft Apr 12 '16 at 7:35