0
$\begingroup$

I am trying to understand the concept of Shannon's entropy and deciding the codelength. In first case, b is an array of 5 symbols. The symbol set is $\{1,2,...,8\}$. In general, there could be any integer value between 1 and 8 in b. For this data array, Shannon's entropy = NaN.

clear all
b = [1,3,2,6,1]; 
p_1 = sum(b==1)/length(b);
p_2 = sum(b==2)/length(b);
p_3 = sum(b==3)/length(b);
p_4 = sum(b==4)/length(b);
p_5 = sum(b==5)/length(b);
p_6 = sum(b==6)/length(b);
p_7 = sum(b==7)/length(b);
p_8 = sum(b==8)/length(b);

ShEntropy =  -p_1 * log2(p_1) - (p_2) * log2(p_2) - p_3 * log2(p_3) -p_4 * log2(p_4) -p_5 * log2(p_5) -p_6 * log2(p_6)...
    -p_7 * log2(p_7) -p_8 * log2(p_8)
%codelength
L = max(- log2(p_1), -log2(p_2), -log2(p_3), -log2(p_4), -log2(p_5), -log2(p_6), -log2(p_7), -log2(p_8))

For the otehr case, I am considering a binary arrays of symbols, d.

 d = [0,0,0];
    p1 = sum(d==1)/length(d);
    Shannonentropy_binary = -p1 * log2(p1) - (1 - p1) * log2(1 - p1)

I can see that when all the symbols are occuring then only there is a legal value for entropy, else it is infinite. But, in real life we cannot ensure that all the symbols would occur in a signal or some other data. So, my questions are

(1)for non-equiprobable sysbols, how can I calculate entropy without encoutering infinity value. Where am I going wrong?

(2) I need help in determining the L, the codeword length or the minimum number of bits required to encode a message. The optimal codeword length / block size should be $HN$ for $N$ number of messages. But, I need to know the value of $L$ which is the block size as I don't know how many number of messages, $N$ would be transmitted. Is there a way to find the exact value of $L$ without using the knowledge of $N$? I had remembered reading somewhere that the block size would be $\max\{-log2(p_i)\} $. What is the correct way?

$\endgroup$
1
$\begingroup$

You need to distinguish between the entropy of your underlying distribution and the "entropy" of the realization.

Consider a set $\mathcal{X}\subset \mathbb{N}$. This set defines, which symbols are allowed to be contained in a random sequence $X=(x_1, \dots, x_N)$. In this sequence, each element $x_i\in\mathcal{X}$ is drawn from the distribution over $\mathcal{X}$ (i.e. there is a function $p(x)$ which gives the probability of occurence for each symbol $x\in\mathcal{X}$). As a constraint, you have $\sum_{x\in\mathcal{X}}p(x)=1$ (i.e. it is certain that one symbol out of $\mathcal{X}$ is chosen for each $x_i$.

Now, the entropy of the random variable for each symbol is defined by $$H=\sum_{x\in\mathcal{X}} -p(x)\log(p(x)).$$ Here, we use the convention $(p(x)=0) \Rightarrow (p(x)\log(x)=0)$, i.e. if the probability for one symbol to occur is 0, it does not influence the overall entropy. This is inline with the limit

$$\lim_{p\rightarrow +0}p\log p=0.$$

So, now to encode a given sequence $b$ (which is drawn from the distribution above), you take each element $b_i$ from the sequence $b$ and associate a bit-word of a length which is (roughly) proportional to its "realization entropy" (sorry, I forgot the common term for this) $p(b_i)\log(p(b_i))$.

So, on average, the encoding for each symbol has $H$ bits. Hence, to encode $N$ symbols, you'd need (on average) $NH$ bits.

$\endgroup$
  • $\begingroup$ By "realization entropy of $b_i$" I think you mean "the information in the sequence $b_i$". With optimum coding, a message with $b$ bits of information requires $b$ binary symbols ("bits") to encode. $\endgroup$ – MBaz Feb 7 '17 at 14:54
  • $\begingroup$ @Maximillian Matthe: Thank you for explaining in a simpler way. My confusion about minimum code length, $L$ arises from a paper which applies entropy to find it. The Authors say that $L$ is chosen as the length for which entropy estimation is maximum. I have asked a question on this topic here (math.stackexchange.com/questions/2129579/…) So, I cannot figure out if the concept that you mention here which is $L = $NH$ bits is the same idea as the one in that paper. $\endgroup$ – SKM Feb 7 '17 at 18:47
  • $\begingroup$ Could you maybe please clarify if indeed $L = max{entropy}$? The Authors use entropy to decide what is the value of $N$ which is actually their $L$ denoted as the code length. $\endgroup$ – SKM Feb 7 '17 at 18:48

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.