8
$\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)?

Improve this question
$\endgroup$
1
  • $\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$
    – user20574
    Commented May 31, 2016 at 23:10

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.