0
$\begingroup$

It has been proved on the Cover-Thomas book that for a set of uniquely decodable codes with lengths $\{l_i\}$ (finite or infinite) that satisfies the Kraft-McMillan inequality, $\sum_i 2^{-l_i}\le 1$, we can construct an instantaneous code with the same code-word lengths, which can be expressed as nodes on a tree graph.

I'm a bit confused about a (counter)example: fixed-length code (for example, all binary codes with length 10, not more/less, of which there are $2^{10}=1024$ of them; they should be uniquely decodable but not prefix-free). It obviously satisfies the Kraft-McMillan inequality: the sum $\sum 2^{-10}=2^{10}\cdot2^{-10}=1$. Henceforth, we should be able to construct an instantaneous code with the same code-word length. However, the lengths are uniformly l=10; while for instantaneous codes, there is at most 1 code per length (which, on the tree graph, means that no code-word is an ancestor of any other code words). We cannot assign codes with the same length to nodes of different depths. There seems to be a contradiction.

I'm pretty sure that I misunderstood something. I would really appreciate it if you could let me know where I am wrong.

$\endgroup$
1
  • 2
    $\begingroup$ Prefix-free means that no codeword is a prefix of another codeword. This is clearly true of the code you describe. The code is instantaneous. Every $10$ bits you have a codeword and decode it. I don't know why you say that in an instantaneous code, all codewords are or different lengths. Huffman codes are instantaneous, but you can have multiple codewords of a given length. $0,10,11$ is an instantaneous code with two codewords of length $2$. $\endgroup$
    – saulspatz
    Commented Mar 6, 2021 at 18:34

1 Answer 1

1
$\begingroup$

fixed-length codes ... should be uniquely decodable but not prefix-free

This is false. A (non singular) fixed-length code is trivially prefix-free, because a codeword cannot be a prefix of another codeword.

while for instantaneous codes, there is at most 1 code per length

Again, false.

An instantaneous codes correspond to a rooted tree where the codewords correspond to leaves (i.e., non internal nodes). Both codes (source) here are instantaneous

enter image description here

$\endgroup$

You must log in to answer this question.

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