0
$\begingroup$

I am currently working on data compression and thought it would be a good time to read up on the basics of information theory to better understand data compression and its algorithms.

As I understand, given a set of data, we can compute the minimum no. of bits on average required to encode the data my multiplying the rounded-up entropy value with length of the set. Following is the formula to compute the entropy of a set:

$$H ( X ) = −\sum i = 1 N p ( x_i ) \text{log}_2 ⁡ ( p ( x_i ) )$$

So, for a set $G = \{A,B,B,C,C,C,D,D,...D\}$ of length 1000, the probability set would be $\{0.001, 0.002, 0.003, 0.994\}$ and the Entropy would be 0.06. Rounding this up would give 1. This means 1 * 1000 = 1000 bits would be required to encode this set.

This would entail I use only 1 bit per symbol to encode this whole set. I am unable to understand how can I use just 1 bit per symbol when there are 4 unique symbols in the set. Won't I require 2 bits per symbol at least? $G = \{00, 01, 01, 10, 10, 10, 11, 11, ..., 11\}$.

But this would lead to a usage of 2000 bits in total betraying the value computed using entropy. What am I missing here?

$\endgroup$
1

1 Answer 1

1
$\begingroup$

Using a fixed-length code, you indeed need two bits and the average length is 2.

With a variable-length code, you will reserve a single bit (say 0) for the most frequent symbol, and two or three bit numbers (say 10, 110 and 111) for the remaining cases. The average length will remain close to 1.

More precisely 1.009.

$\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.