Why do we need at least 2 Code Words of the max length in optimal Codes?

Any why do they just differ in their Prefix?

Could someone give me more insight into this?

Have to proof that for a given optimal Code C with max length L there are at least 2 Code Words of max length that just differ in their prefix.

I have nothing to start so some start would be good.

I have no given definition of optimal Code in my script and I don't know if it has to be a block code that I see in most definitions.


1 Answer 1


So first, some terminology.

A uniquely decodable code is a code where every string has at most one decoding.

A prefix code is a code where no code word is a prefix of any other. This is an interesting property because it means that the system is uniquely decodable without using lookahead.

A uniquely decodable code is optimal if it has minimal average code word length.

An optimal prefix code is, just as the name suggest, a prefix code that is also optimal.

The main result that you should know about uniquely decodable codes is the Kraft-McMillan inequality. It states that if you have an alphabet of size $r$ ($r=2$ if the codes are binary), and a uniquely decodable code with code word lengths $l_1, l_2, \ldots, l_n$, then:

$$\sum_i r^{-l_i} \le 1$$

And, conversely, for any code word lengths that satisfy the above inequality, there exists a prefix code with the same code word lengths.

Taken together, this means that for every uniquely decodable code, there is an equivalent prefix code.

I'm going to suggest looking at the link above, and work through the proofs. This should give you the head start that you need.

One of the questions that you asked, whether the two maximum-length code words differ only in the prefix, is true for optimal prefix codes, but doesn't have to be true for uniquely decodable codes in general. But as noted, for every uniquely decodable code, there is an equivalent prefix code.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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