Past exam of the communication Theory course of the University of Oxford / 2009 / 2 / a

In the terminology used here, a block code assigns a distinct word of the same length to every source symbol. For a binary code with $m$ symbols this common length must satisfy $2^{\ell }\ge m$. The equal-length property is what matters in this question; elsewhere the term can also refer more generally to coding blocks of source symbols.

A prefix code has no codeword that is a proper prefix of another. Its code tree therefore places source symbols at leaves. It is instantaneous because the decoder knows that a source symbol has ended as soon as its leaf is reached, without needing to inspect later transmitted symbols.

A compact code or optimal prefix code minimizes the expected codeword length ${\sum }_x{p}_x{\ell }_x$ for the given source probabilities and coding alphabet. The relevant comparison here is among binary prefix codes. The minimum is also the minimum among uniquely decodable codes, since the Kraft-McMillan inequality permits every uniquely decodable length list to be realized by a prefix code with the same lengths.