6
$\begingroup$

There is this interpretation of the entropy $-\sum_i p_i \log_2 p_i$ as the average length (in bits) per character when using an optimal encoding of a message.

Now, if we use the simple 3-letter case of A (80%), B (10%) and C(10%), the entropy is smaller than 1 bit, which seems strange (from a naive standpoint). How can this be reconciled with the interpretation above (if it can at all)?

$\endgroup$
  • $\begingroup$ Arithmetic coding can use less than one bit per symbol (of course you still have to round up to the nearest bit for the whole message) $\endgroup$ – user253751 May 31 '16 at 23:10
11
$\begingroup$

Code:

AAA as 0
AAB,AAC,ABA,ACA,BAA,CAA as 1000...1101
12 triplets with 1 letter "A" as 1110000...1111011
8 triplets without "A" as 11111000...11111111

Each triplet takes on average 0.512*1+0.384*4+0.096*7+0.008*8=2.784 bits, or 0.928 bits per character. With coding 4-character, 5-character etc. groups, you can further decrease the number of bits per character. With long groups of characters and optimal coding, you can make the number of bits per character as close to the entropy as you want, but not less than the entropy.

$\endgroup$

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.