For the direct half of the <code-distribution correspondence>, let $L$ be the length function of a binary prefix code and put
$$
K=\sum_x2^{-L(x)}\leq1,
\qquad
R(x)=\frac{2^{-L(x)}}K.
$$
Then $R$ is a <probability mass function> and
$$
-\log_2R(x)=L(x)+\log_2K\leq L(x).
$$
Thus every prefix code determines a distribution whose ideal description lengths do not exceed the codeword lengths.

Conversely, given a probability mass function $R$, set
$$
L(x)=\left\lceil-\log_2R(x)\right\rceil
$$
for $R(x)>0$. Then $2^{-L(x)}\leq R(x)$, so the <Kraft inequality> is satisfied. Its converse supplies a binary prefix code with these lengths, and
$$
-\log_2R(x)\leq L(x)<-\log_2R(x)+1.
$$
If real lengths are allowed, the ideal choice $L(x)=-\log_2R(x)$ satisfies Kraft with equality.

Solution

Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 224 / 3 / b / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/iii/paper-224/3/b/solution