Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 1 / 3K (Coding and Cryptography)

For a $q$-ary code with codeword lengths $l_1,\dots ,l_m$, Kraft inequality isChoose an infinite random $q$-ary string with independent uniform symbols. The event that it begins with codeword $i$ has probability $q^{-l_i}$. For a prefix-free code, these events are disjoint, so their probabilities sum to at most one. This proves necessity.

If one comma codeword were a prefix of another, its terminal comma would occur inside the longer codeword, contrary to the definition. Thus every comma code is prefix-free. Directly, the disjoint cylinder sets of infinite strings beginning with the respective comma-terminated words have measures $q^{-l_i}$, so their total measure gives Kraft's inequality.

Kraft's inequality does not imply unique decipherability. Over the binary alphabet,has Kraft sum $1/2+1/4+1/4=1$, butThus it is not uniquely decipherable.