1
$\begingroup$

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?

Thanks in advance.

  • 0
    @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.2011-07-11

1 Answers 1

5

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