Theoretical Computer Science
- it.information-theory coding-theory
- Updated Thu, 09 Jun 2022 00:47:30 GMT
-
Gift bits when encoding a sequence of messages, how is that?
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?
Solution
The important thing is what "information quantity is additive" with respect to.
Information quantity is additive with respect to concatenating messages
each of which can only have one length, rather than forming a multiset
of messages each of which can only have one length.
Information quantity is subadditive with respect to forming a multiset of messages
each of which can only have one length, because for every concatenation,
there is a unique multiset that is consistent with that concatenation.
Comments (2)
- +0 – Do I correctly understand you? There is no bijection between a set of concatenated messages and a set of multisets of messages? We basically have an injection here and it's the reason of subadditive behavior. — Aug 14, 2012 at 09:24
- +0 – (Sorry for taking so long to respond to your comment.) $\:$ No, we basically have a $\hspace{0.8 in}$ non-injective surjection. $\:$ This can be seen by considering the case of two binary messages. $\;\;$ — Aug 15, 2012 at 19:49