# Shannon's entropy for non-equiprobable symbols

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?

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.

• 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. – MBaz Feb 7 '17 at 14:54
• @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. – SKM Feb 7 '17 at 18:47 • 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. – SKM Feb 7 '17 at 18:48