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