The direct codes-distributions correspondence says that every mass function $Q$ on a finite alphabet admits a binary <prefix code> with lengths $L(x)=\lceil-\log_2Q(x)\rceil$. Conversely, every binary prefix code has lengths satisfying the <Kraft inequality> $K=\sum_x2^{-L(x)}\leq1$, and hence defines the mass function $Q_C(x)=2^{-L(x)}/K$.

Solution

Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 224 / 4 / a / Solution

 Solution (source code)