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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Commented Jul 11, 2011 at 16:21
  • $\begingroup$ @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. $\endgroup$ Commented Jul 11, 2011 at 17:38

1 Answer 1

5
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .