Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.