# Relation between Kraft's inequality and optimal entropy encoding codes

Given a binary code that verifies Kraft's inequality can I state that this code is optimal?

I know that optimal codes verify this inequality, like so $\sum\limits_{i=1}^{M} 2^{-\ell_i} \leq 1$ where $\ell_i$ is the length of a given word. The otherwise is also true?

The condition for an optimal code is it has to be uniquely decodable and instant (doesn't have words as prefixes of another word), right?

For example this binary code $\{0,01,110,111\}$ satisfies this condition but isn't instant. Is it optimal still?

-
Is that code really uniquely decodable? Can't you for example parse the string 01110 as (0)(111)(0) as well as (01)(110)? IIRC unique decodability doesn't allow something like this. – Jyrki Lahtonen Jul 11 '11 at 16:21
@Jyrki: The code was probably supposed to be $C = \{0,01,011,111\}$, which is uniquely decodeable: it’s the reverse of the prefix code $C' = \{0,10,110,111\}$, so you just reverse the code string, decode via $C'$, and reverse the result. – Brian M. Scott Jul 11 '11 at 17:38

No. Whether a code is optimal depends on the probability distribution of the source symbols. Take the code $\{a \mapsto 0,b \mapsto 01,c \mapsto 011,d \mapsto 111\}$. It's optimal if $Pr(a) = 1/2,Pr(b)=1/4,Pr(c)=1/8$, and $Pr(d)=1/8$; it’s far from optimal if $Pr(a) = 1/8,Pr(b)=1/8,Pr(c)=1/4$, and $Pr(d)=1/2$. In the first case the cost is $(1/2)\cdot 1 + (1/4)\cdot 2 + (1/4)\cdot 3 = 1.75$; in the second it’s $(1/8)\cdot 1 + (1/8)\cdot 2 + (1/4)\cdot 3 + (1/2)\cdot 3 = 2.625$.

-