ConceptDBISAI-written · not yet proofread

Entropy-Optimal Code

A code is entropy-optimal for a distribution p if its expected code length equals the entropy H(p), which holds exactly when every codeword length is L_i = log₂(1/p_i); by Shannon's source coding theorem a prefix-free code with expected length below H + 1 always exists.

Know these firstEntropy Prefix-Free Code

Formula#

H(X) \leq \bar L < H(X) + 1 \quad \text{for the best prefix-free code (Shannon's source coding theorem)}

The theorem’s code uses lengths $L_i = \lceil \log_2(1/p_i) \rceil$ , with expected length $\sum_i p_i \lceil \log_2 (1/p_i) \rceil$ .

Properties#

Lower bound. Among codes with $\sum_i 2^{-L_i} = 1$ (Kraft equality, see Prefix-Free Code), $\bar L \geq H(X)$ . Proof (DBIS Exam WS1920 (not published), Task 2.2): minimize $\sum_i p_i L_i$ subject to $\sum_i 2^{-L_i} = 1$ with the Lagrangian $\sum_i p_i L_i + \lambda(\sum_i 2^{-L_i} - 1)$ . Setting $\partial/\partial L_i = p_i - \lambda \ln 2 \cdot 2^{-L_i} = 0$ gives $p_i = \lambda \ln 2 \cdot 2^{-L_i}$ . Summing over $i$ gives $1 = \lambda \ln 2$ , so $p_i = 2^{-L_i}$ , i.e. $L_i = \log_2(1/p_i)$ , and then $\sum_i p_i L_i \geq \sum_i p_i \log_2(1/p_i) = H(X)$ (the exam allows assuming there are no saddle points).
Exactly $H(X)$ iff every $p_i$ is a negative power of 2 ( $\tfrac12, \tfrac14, \tfrac18, \dots$ ), because only then $\lceil \log_2(1/p_i) \rceil = \log_2(1/p_i)$ , i.e. no rounding (DBIS Exam WS1819 (not published), Task 2.2).
Standard proof technique that a given code is entropy-optimal for some distribution: set $p_i = 2^{-L_i}$ , check $\sum_i p_i = 1$ , and compute $\bar L = H(X)$ .
Uniform distribution over $n = 2^m$ symbols: the fixed-length $m$ -bit code is entropy-optimal.

Example#

Code $a = 000$ , $b = 001$ , $c = 01$ , $d = 10$ , $e = 11$ (DBIS Exam WS2122 (not published), Task 2.3): choose $p_i = 2^{-L_i}$ , i.e. $p_a = p_b = \tfrac18$ , $p_c = p_d = p_e = \tfrac14$ (sum $\tfrac28 + \tfrac34 = 1$ ). Then $\bar L = 2 \cdot \tfrac18 \cdot 3 + 3 \cdot \tfrac14 \cdot 2 = \tfrac94 = H(X)$ .

Sources#

DBIS Exam WS1314 (not published) Task 1.4, DBIS Exam WS1516 (not published) Task 2.4, DBIS Exam WS1718 (not published) Tasks 2.3–2.4, DBIS Exam WS1819 (not published) Tasks 2.1–2.2, DBIS Exam WS1920 (not published) Tasks 2.1–2.2, DBIS Exam WS2122 (not published) Task 2.3
Not lectured in WS 25/26.

Connections

Mentioned in inline links5

Entropy
Lower bound for compression: every prefix-free code for $X$ has expected code length $\sum_i p_i L_i \geq H(X)$ , and Shannon’s source coding theorem gives one with $< H(X) + 1$ (Entropy-Optimal Code). §
Gap Encoding
$1, 10, 11, 20, 21, 30, 31, 40$ becomes $1, 9, 1, 9, 1, 9, 1, 9$ (DBIS Exam WS1314, Task 1.1). For the entropy-optimal code of the gaps (two values with probability $\tfrac12$ each, lengths 1 bit) see Entropy-Optimal Code. §
Prefix-Free Code
Lengths constrain each other. Kraft’s inequality is the only restriction: short codewords “use up” $2^{-L_i}$ of the available budget $1$ . Codes with $\sum_i 2^{-L_i} = 1$ waste nothing; this is the constraint under which the past exams mi… §
Unary Code
Entropy-optimal for $\Pr(X = x) = 2^{-x}$ (geometric distribution with $p = \tfrac12$ ): $p_x = 2^{-L(x)}$ , and $\sum_{x \geq 1} 2^{-x} = 1$ (Entropy-Optimal Code). This is exactly the distribution of the random process “flip a fair coin un… §
Encodings and Compression
Entropy-Optimal Code — code whose expected length equals the entropy; exists iff all $p_i = 2^{-L_i}$ §
From prefix-freeness to optimality. A code is only usable without separators if it is prefix-free. Kraft’s inequality $\sum_i 2^{-L_i} \le 1$ characterises the code lengths a prefix-free code can have. Among these, the expected length… §

Search in these mentions →