# Prefix-Free vs Uniquely Decodable Codes

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.

• 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$. Commented Mar 6, 2021 at 18:34