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.com Apr 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.

  • $\begingroup$ 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? $\endgroup$ – SKM Apr 11 '16 at 20:24
  • $\begingroup$ @SKM: See my edit, though I fail to make sense of the sentence directly following (B). $\endgroup$ – Wrzlprmft Apr 11 '16 at 21:02
  • $\begingroup$ 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. $\endgroup$ – SKM Apr 12 '16 at 6:08
  • 1
    $\begingroup$ @SKM: See my edit. $\endgroup$ – Wrzlprmft Apr 12 '16 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.