2
$\begingroup$

While trying to understand Shannon's information theory, I never quite managed to get an intuitive feeling for the "optimal input ensemble probability distribution" $p^*_x$, which is the distribution that maximizes the mutual information of a channel and gives its capacity

$C = max_{p_x} I(X;Y)$.

Specifically, I'm not sure if $p^*_x$ provides any insight as to how to construct a code which allows us to communicate efficiently through a channel.

Take for example the "noisy typewriter", through which you are able to send all 26 English letters, but for each letter you send, the channel may output either that letter, or the next one, so A can become either A or B, M can become M or N etc. If you calculate the capacity of such a channel using standard methods, you get $C=log_2 13$ bits and $p^*_x$ a uniform distribution over the input alphabet. However, for this channel it's easy to devise an optimal coding strategy - just use every other letter, A, C, E..., because they produce outputs fully distinguishable from each other. Since there are now 13 letters you can send with perfect decodability, you can transmit $log_2 13$ bits per channel use so this strategy achieves the previously calculated capacity. It turns out, that a uniform distribution over every other letter in the alphabet, call it $p^{*'}_x$, ($p_A = 1/13$, $p_B = 0$, $p_C = 1/13$...) also maximizes the capacity. So now we're left with a conundrum - both $p^*_x$ and $p^{*'}_x$ achieve capacity, but the latter gives an understanding of how the channel can be effectively used, and the former doesn't really say much at all (certainly interpreting it as "use all letters equally often" doesn't lead to a efficient coding strategy).

If so, how do you interpret any other capacity achieving distributions for different channels? Or, why this methodology of assigning probabilities to input symbols and calculating the most optimal ones gives us any clue as to how we should go about sending any message of our own through a noisy channel?

$\endgroup$
6
  • 1
    $\begingroup$ The codebook should have those symbols appearing with those fractions of occurrence. If we have binary symbols and the optimal input distribution has p(1)=3/4, then codewords should roughly have 1s appearing 75% of the time. $\endgroup$
    – Michael
    Mar 3 '20 at 1:23
  • 2
    $\begingroup$ If multiple input distributions maximize, it is possible to construct codewords according to each different distribution, so there are multiple optimal codes. It is easy to do: use the first code (using only a,c,e,...) for even letters and the second (b,d,f...) for odd (this uniformly uses all letters). $\endgroup$
    – Michael
    Mar 3 '20 at 1:27
  • $\begingroup$ Thank you, this does provide intuition. Could you point to some theoretical argument in which it is either derived that "the codebook should have those symbols appearing with those fractions of occurrence" or stated from the beginning, that the input alphabet probabilities correspond to frequencies of symbols in the codebook? I guess part of my confusion stems from the "every-day" understanding of sending messages as in "I want to send a single telegram", while Shannon's theory is in some way asymptotic and thus not directly applicable to single messages, or am I incorrect in saying that? $\endgroup$
    – neverneve
    Mar 3 '20 at 1:47
  • $\begingroup$ Suppose p(0) = p(1) = 0.5. An "every-day" question one could ask is: ok, so what if the probabilities of 0 and 1 should be equal. I want to send the message 111010 and none other, and I need to send it in this particular order and length". I suppose the answer would be: "the distribution p(0)=p(1)=0.5 only tells us that 0s and 1s should be used equally frequently when you average over all possible messages, it doesn't tell us anything about how to transmit this specific 111010 message". $\endgroup$
    – neverneve
    Mar 3 '20 at 1:52
  • $\begingroup$ Shannon tells us that we can form a codebook randomly by generating codewords according to iid symbols with distribution close to the optimal input distribution. $\endgroup$
    – Michael
    Mar 3 '20 at 2:05
1
$\begingroup$

If you calculate the capacity of such a channel using standard methods, you get $C=log_2 13$ bits and $p_x$ a uniform distribution over the input alphabet

Not quite. What you get is $I(X;Y)=H(Y)-H(Y|X)=H(Y)-1$ bits, which is bounded by an uniform output distribution $p_y$, with $H(Y)=\log 26 $ bits. Then comes the realization that a uniform $p_y=1/26$ can be obtained by a uniform input $p_x=1/26$ - but this not the only solution, you could alternate the probabilities $P_x(A)=1/13$ $P_x(B)=0$ $P_x(C)=1/13$ etc.

Hence the noisy typewriter has several input distributions that attain the capacity (not a very frequent case). All of them are optimal (in the Shannon sense), but it happens that one of those alternatives leads to a simple (almost trivial) optimal encoding (again, a rather rare occurence).

$\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.