# How to make the encoding of symbols needs only 1.58496 bits/symbol as carried out in theory?

I'm reading the tutorial of Information Gain, and I see the following page:

I know in the example above, I can encode this way:

A 0
B 10
C 11


and then this will need $1/3*1+1/3*2+1/3*2=1.6667$ bits per symbol. But how can I code to achieve the 1.58 goal in theory? Is that possible in practice?

-
Arithmetic coding can achieve this order of compression efficiency. –  achille hui Mar 28 '14 at 13:13

You can't do that by using binary codewords for single symbols A, B and C.

As mentioned in the comments, for example, arithmetic coding can be used to get near the limit when the input sequence is long.

Another simple example: You can consider "super-symbols" that consist of 100 As, Bs and Cs and encode one super-symbol at a time, so that each of the $3^{100}$ possible super-symbols corresponds to a $159$-bit binary codeword ($3^{100}\leq 2^{159}$), giving you effectively $1.59$ bits per original symbol. Or sequences of $10000$ symbols, so that each sequence corresponds to a $15850$ bit codeword ($3^{10000}\leq 2^{15850}$), giving effectively $1.585$ bits per symbol.

-
wow! love you ;) –  zhangxaochen Mar 28 '14 at 13:28
Or more simply: put $A=0,B=1,C=2$ and store it in ternary, and that will have $log_2(3)\approx1.5849625...$ bits per symbol in the long run. –  chubakueno Mar 28 '14 at 16:57
What do you mean by "storing it in ternary" when the question was how to encode ternary symbols in binary? –  JiK Mar 28 '14 at 18:56
You can pretend you just see a ternary number written as a string, and convert it to binary. –  chubakueno Mar 28 '14 at 19:09
Oh, now I see. That seems to be the first example in the Wikipedia article on arithmetic coding. –  JiK Mar 28 '14 at 19:15

The optimal length is given by the Huffman code. In this case, that corresponds to your proposed coding, with average code length 1.6667. So, this is optimal... if you restrict to a single symbol=>single codeword coding. But you can do better if, instead of coding each symbol alone, you code the pairs, or triplets, or... That is, if you encode the "extended source".

For example, taking the extension of order $2$, you'd have $3\times 3=9$ symbols, each with probability $1/9$, and you could code them thus:

 AA 000
AB 001
AC 010
BA 011
BB 100
BC 101
CA 110
CB 1110
CC 1111


This gives an average length of $(3 \times 7/9 + 4 \times 2/9)/2=1.6111\cdots$. This is better, but still does not reach the Shannon limit.

For extension three, we'd have 27 symbols and the Huffman code would be

         n   L
00**    (4)  4
0100    (1)  4
0101*   (2)  5
011**   (4)  5
1****  (16)  5


with average length $[ 4 \times (4+1)/27 + 5 \times (2+4+16)/27]/3=1.605...$

You can do still better -and approximate asymptotically the theoretical value- by taking higher and higher order extensions. Or you can use arithmetic coding, which, essentially, does precisely that.

A simple coding -suboptimal but simple, and that achieves the goal in the original exercise - would be the extension of order 5, which gives $3^5=243$ symbols. This can be trivially coded by 8 bits each ($2^8=256 < 243$), what gives $8$ bits/$5$ symbols = 1.6 bits per symbol.

-