0
$\begingroup$

The entropy of a source $H(S)$ gives the average codeword length to encode a given source alphabet. i.e. it is the average number of bits per symbol required to encode the information in the source. Let, $S_1 = 101101...$ be a message of length $N$. The entropy of the system that produces the message depends on the number of unique symbols, $k$ and the formula is $H(S) = ln k$ where $k$ is the number of unique symbols. The entropy $H(S_1) = \log(2) = 0.69$ bits/symbol. For another different message, $S_2$ having $k=8$ unique symbols, $H(S_2) = \log(8) = 2.07$ bits/symbol. I have 2 questions

  1. Is there a way to determine $n$, the minimum word length for a message sequence of $N$? For example, $S_1 = (10)(11)(01)$ here $n$ = 2.
  2. It is desired that the entropy of the system be maximized, so $H(S_1) < H(S_2)$ so should I prefer $k=8$ symbols then? Which entropy do we prefer - message with higher entropy and hence is this the reason why we prefer higher modulation?
$\endgroup$
  • $\begingroup$ given two sets of messages, both sets have the same number of messages, the set with lower entropy will require fewer bits, on average, per message to send the messages. dunno if you consider that good or not. certainly, the message set with maximum entropy is the simplest to encode and send because all of the messages have equal likelihood and get the same number of bits allocated to each. $\endgroup$ – robert bristow-johnson Jan 30 '17 at 3:32
  • $\begingroup$ Thank you for your comment but few things are unclear. (A) From information theory perspective, we prefer higher entropy so I should prefer $k=8$ since the entropy is higher for a message with 8 unique symbols. Is my understanding correct? (B) how to determine the word /block size, $n$ in general? $\endgroup$ – SKM Jan 30 '17 at 3:51
  • $\begingroup$ may i treat all of your "symbols" as statistically independent of each other? so that each "symbol" can be treated as a message? $\endgroup$ – robert bristow-johnson Jan 30 '17 at 4:03
  • $\begingroup$ A collection of symbols is a message, denoted by variable $b$ of length $N$. The message can be composed of 2 unique symbols like 0 or 1 or $k>=2$ unique symbols. If $k = 2$, then probability of the message of length $N$ is $p_0 = sum(b==0)/length(b); p_1 = sum(b==1)/length(b)$ Similarly, for $k=8$, I can use the same probability calculation. I don't know if the symbols by this definition falls under statistically independent category which you mentioned in your comment. Shall appreciate your insights and please correct me if wrong. $\endgroup$ – SKM Jan 30 '17 at 8:58
  • $\begingroup$ I would apply the probability formula to calculate probability of each unique symbol for $k>2$ case. The entropy of the source is dependent on $k$ like I have written in the Question. $\endgroup$ – SKM Jan 30 '17 at 9:06
7
$\begingroup$

You seem to have a number of misunderstandings, which I'll try to clarify while also trying to help with your questions.

The entropy of a source $H(S)$ gives the average codeword length to encode a given source alphabet. i.e. it is the average number of bits per symbol required to encode the information in the source.

While this is true, I think it's not the more enlightening way to look at the entropy. Think of the entropy as an inherent property of a source. The entropy measures the average information of each message produced by the source.

As an analogy, think of the source as a black box with a button; every time you press the button, the source tells you something. A high-entropy source will consistently (not necessarily always) produce messages that leave you saying "Wow! That's amazing". A low-entropy source will be boring most of the time.

Now, Shannon proved that it's possible to find an enconding from source messages to bits, so that the average number of bits required per message is equal to the entropy. This is why your statement above is technically correct. Note that, typical of Shannon, he didn't actually tell us how to design such an encoder (but he provided a few hints).

Let $S_1=101101...$ be a message of length $N$ [...] The entropy $H(S_1)=\log(2)=0.69$ bits/symbol.

Now you can see this statement makes no sense. $S_1$ is a message, so it cannot have an entropy. What it does have is information. To find the entropy of the corresponding source, you need to look at its message set (alphabet) and its probability distribution. If the source has memory, you also have to take that into account.

Is there a way to determine $n$, the minimum word length for a message sequence of $N$? For example, $S_1=(10)(11)(01)$ here $n = 2$.

I'm not sure what you're asking here, but I'll make a guess. One of the hints Shannon gave us about source encoding is that efficient encoding requires us to gather many source messages and encode them together. This is equivalent to defining a new source with a different alphabet (whose elements are concatenations of the original symbols) and a different probability distribution.

You seem to be asking about moving in the other direction: breaking up the source alphabet into simpler symbols. In the case of a source whose messages are strings of 0s and 1s, you can always define it as a source with alphabet $\lbrace 0,1 \rbrace$, but you have to be careful when doing so, as you may need to introduce memory to the source.

For example, say you have a source with alphabet $\lbrace 00, 01, 11 \rbrace$. To redefine it a source with alphabet $\lbrace 0,1 \rbrace$, you'll need to introduce a mechanism to avoid messages such as $0,0,1,0$, which the original source cannot produce.

It is desired that the entropy of the system be maximized, so $H(S1)<H(S2)$, so should I prefer $k=8$ symbols then? Which entropy do we prefer - message with higher entropy and hence is this the reason why we prefer higher modulation?

This question does not make much sense to me, since a given source has a given entropy (remember that entropy is an inherent property of a source). So, what is there to maximize?

Now, if you're given a choice between two sources, one of which has higher entropy, what you should do is not clear either. What do you want to achieve?

From the point of view of a source coder (compressor), which is trying to compress the messages as much as possible, having a low-entropy source is preferable. For example, a PNG compressor which is fed single-color images will be able to compress them a lot.

From the point of view of the communications engineer, what you want to do is to match the information content of the source to the capacity of the channel.

Maybe what you mean is this: remember that Shannon says that we need to group source messages together to achieve larger encoding efficiency. This process will also result in a source of larger entropy -- but this means more bits per message, so how can this be better?!

To clarify this point, consider a binary source with alphabet $\lbrace 0,1 \rbrace$ and probability distribution $\lbrace 0.9,0.1 \rbrace$. Even though this source is low-entropy (most of its messages are boring), it's very hard to compress: you still need one bit per message!

Let's say that you redefine this source to have 1024 messages of 10 bits each, and calculate the new probability distribution. You'll find that a few of the new 10-bit messages are much more likely than the others. You can then use (for instance) the Huffman algorithm to find an encoding that approaches the entropy.

So, from this perspective, redefining your source to have larger entropy is better, because you'll be able to find better encoders.

About higher-order modulation -- that doesn't play a role in this problem at all.

$\endgroup$
  • $\begingroup$ This answer was awesome to read, great job. I have one doubt, however. You state that "Shannon says that we need to group source messages together to achieve larger encoding efficiency. This process will also increase the entropy of each message", but above you said that "$S_1$ is a message, so it cannot have an entropy". Is it me or is there a contradiction there? I didn't understand the first sentence, where you refer to the entropy of each message. $\endgroup$ – Tendero Jan 30 '17 at 15:28
  • 1
    $\begingroup$ @Tendero You're right: it is the entropy of the source that increases. Thanks for catching that -- fixed! $\endgroup$ – MBaz Jan 30 '17 at 15:46
  • $\begingroup$ @MBaz: Thank you for your reply. I would like to reframe two points as it may not be clear earlier. (A) Considering two sources source 1 and source 2. The entropy of source 1 is higher than source 2. Which one do we prefer to use as the source to generate messages? Based on your answer, I should select source 2 since that would give better encoders. Is my understanding correct? $\endgroup$ – SKM Jan 30 '17 at 18:36
  • $\begingroup$ (B) If entropy of either source is $H$, I want to know if there is a way to determine what should be $n$ so that I can transmit few bits $n < N$ or block of bits from a sequence of message of length $N$ based on knowledge of $H$ (something like varaible length encoding)? Could you please clarify these points? $\endgroup$ – SKM Jan 30 '17 at 18:37
  • 1
    $\begingroup$ @SKM (A) You need to specify a criterion for selection. If you want to an efficient encoder, in general you need to jointly encode many messages. (B) If I'm understanding correctly, for variable length encoding, you need Kraft's inequality (en.wikipedia.org/wiki/Kraft_inequality). In any case, I suggest studying the Shannon-Fano algorithm, and then Huffman's. I think you'll find them very useful to understand these concepts. $\endgroup$ – MBaz Jan 30 '17 at 19:21

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.