1
$\begingroup$

I want to encode the messages to a sequence of 1s and 0s (subsequently called "bits"). This is called "source coding". Shannon's source coding theory states that the entropy of a source that emits a sequence of N symbols that are independent and identically distributed (iid) is N·H bits (per message of N symbols) where H is the source entropy.

Question 1: Does $N$ mean the length of the message or number of distinct symbols? For examp,e if message $m = 1001$, then $N = 4$ or $N = 2$?

Question 2: I want to apply the source coding similar to Arithmetic Coding using nonlinear dynamical system (chaos map). I had asked Help in understanding a coding technique based on inverse mapping of a dynamical system

for a detailed explanation on how this coding works. Using the inverse iterations of Skew Tent Map and the symbol representation of the message, we can get the initial condition from backward iterations of the map. In this way we can embed the message into the symbolic dynamics of the Skew Tent Map.

Now, my problem is that I have a database consisting of a collection of $N$ different messages of same length $D$. For each $N$, I apply the coding technique. Thus, I am using $N$ number of Skew Tent Maps each initialized with different initial condition. I then iterate the Skew Tent Map $d < D$ times and perform symbolization (or binarization) using the mean of the real valued time series as the cut-off (threshold) point. Please correct me if this way of applying $N$ maps is wrong. I now wonder how I can apply Shannon's source coding here - I want to transmit $N$ messages but what will be the length $d$ in bits? The entropy of the Tent Map = H = 1 bits/symbol.

$\endgroup$
  • $\begingroup$ N would be length of message in number of symbols, if it is the symbols probability distribution we have calculated the entropy for. $\endgroup$ – mathreadler Jun 1 '16 at 18:49
  • $\begingroup$ Thank you. So, if the message is made of 2 symbols, 0's and 1's and for example, the message is m=1001, then N=4 ? $\endgroup$ – SKM Jun 1 '16 at 18:52
  • $\begingroup$ Yes. That sounds right. Maybe you should learn the basics before jumping into a sophisticated coding technique. $\endgroup$ – mathreadler Jun 1 '16 at 18:53
1
$\begingroup$

For the first question:

Entropy can be viewed as the expected value of the random variable that is the logarithm of the probabilities (alphabet size $M$):

$$H_b = -\sum_{i=0}^{M}\log_b(p_i)p_i = -E[\log_b(p_i)]$$

For logarithm with base 2, this is the average number of bits required per symbol $(H_2)$. For some other number system, change the base of logarithm accordingly.

So observing $N$ independent events is what receiving $N$ symbols from the source would mean conceptually. The entropies, (which are expected or mean values, remember) add up: $$\underset{N \text{ times}}{\underbrace{H+H+ \cdots H}} = NH$$

The entropy of symbol nr $a$ would be it's corresponding term in the sum : $$H_b(a) = -p_a\log_b(p_a)$$

When having observed a message the information required to store that message is a weighted sum of occurrance and these $H_b(a)$s.

So information content for the specific message $1101$ after we have estimated the probabilities $$\cases{p_0 =0.25\\ p_1 = 0.75}$$ $$-3\log_2(0.75) - 1 \log_2(0.25) = 3.2451 [bits]$$

So we should need $3.245...$ bits to store it. You can experiment to see how the performance would change if guessing the $p$s wrong by changing 3 and 1 above.

For example if you instead observe $0010$ while having the same probability estimate as before that would give

$$-1\log_2(0.75) - 3\log_2(0.25) = 6.415 [bits]$$

So using bad estimations will punish us more than a naive 50/50 code.

$\endgroup$

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.