<p>Another answer is to consider how you apply concatenation process. </p>

<p>When you concatenate two messages (apply the concatenation operator) you choose <em>a priori</em> an order for the two messages, before concatenation takes place. This order is extra information <em>besides</em> the message bits. Concatenation essentially <em>preserves</em> the order you have presented the messages to the concatenation operator, it does not add any.</p>

<p>If you use a commutative operator, such as "building a multiset", then there is no extra ordering information in the input and thus no extra information in the output. </p>

CC BY-SA 3.0
2012-08-16T04:19:08.743Z
2012-08-16T04:19:08.743Z
kena
<p>Recently a friend of mine asked a question I couldn't give immediate answer to.</p>

<p>Say we have $ n $ messages of length $ m $ bits each. Now we can pack them in a single message of length $ n * m $ bits. So far so good, information quantity is additive. </p>

<p>But, from another side of view, besides coding the meaning of $n$ messages we also gave an order to them, this gives us additional $ \log _2( n!) $ bits. How is that?</p>

<p>I told that unordered messages are meaningless, but he replied, "Take something like photos or novels for example, clearly the order doesn't matter and we can use it to pass additional information".</p>

<p>Can you please explain this apparent paradox?</p>

<it.information-theory><coding-theory>
Gift bits when encoding a sequence of messages, how is that?
Dmitry Vyal
# Gift bits when encoding a sequence of messages, how is that?

(Asked by: username_0 on 2012-08-14)

Recently a friend of mine asked a question I couldn't give immediate answer to.

Say we have $ n $ messages of length $ m $ bits each. Now we can pack them in a single message of length $ n \* m $ bits. So far so good, information quantity is additive.

But, from another side of view, besides coding the meaning of $n$ messages we also gave an order to them, this gives us additional $ \log \_2( n!) $ bits. How is that?

I told that unordered messages are meaningless, but he replied, "Take something like photos or novels for example, clearly the order doesn't matter and we can use it to pass additional information".

Can you please explain this apparent paradox?

**Tags:** it.information-theory, coding-theory


---

## 1 answers

### Answer by username_1 on 2012-08-16. Score: 2

Another answer is to consider how you apply concatenation process.

When you concatenate two messages (apply the concatenation operator) you choose *a priori* an order for the two messages, before concatenation takes place. This order is extra information *besides* the message bits. Concatenation essentially *preserves* the order you have presented the messages to the concatenation operator, it does not add any.

If you use a commutative operator, such as "building a multiset", then there is no extra ordering information in the input and thus no extra information in the output.


---

