Lossless Compression and definition of Entropy

Question

I am taking an intro class to Information Theory and I have a question. Suppose we have three symbols a, b, and c with probabilities of them coming out of a chanell with 0.7, 0.15 and 0.15 respectively.

If we take 2 bits for each character we can encode them like below.

a - 0 b - 11 c - 10

With this encoding we get expected number of bits per source symbol is 1.3.

However, if we try to encode two symbols at a time in an attempt to find a better average bit per symbol we can do this:

aa - 00 ab - 100 ac - 111 ba - 101 ca - 1100 bb - 110100 bc - 110101 cb - 110110 cc - 110111

With this encoding scheme the expected number of bits per source is: 1.1975.

My question is, if we use the above encoding then how do we represent a, b and c considering it is a two-symbol encoding?

Thanks.

Answer 1

The question seems to be: when encoding the $2-$extension of a source, how do we encode a message consisting of just one (original, not extended) symbol? (Or, for that matter, an odd number of symbols?)

This is an implementation detail, which has no single/elegant/interesting answer. It's not very interesting because the theory of compression (in particular, Shannon first theorem, which implies that by coding the $m-$extension of a stationary memoryless source we approach the entropy for large $m$) is only valid/relevant asympotically, for large $n$ (total length of the message).

But how can we do it? Well, for example, by prepending to the coded sequence a (suitable coded) integer that signals the total number of (original, not extended) symbols included. In that way, we could encode the single (or last) symbol (say, a) using the code for (say) ab. The decoder will know that the last b is mere stuffing, and will discard it.

Sure, this will degrade the compression, but asymptotically, it does not matter.

There are other methods: add to the list of extended symbols an extra dummy symbol "EOF" (end of file, end of message), and assign to it a low probability. Again, the paragraph above applies.

(In a sense, the question is similar to this one: we know how to store and retrieve one byte, (or two, or three...) in the computer disk, by creating a file. Now, can we store 12 bits (one byte and a half)? Answer: we surely can, but the reader must know (either implicitly, or by reading some extra data, perhaps as a file preface) the total number of bits.)