Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 2 / 3I (Coding and Cryptography)

A Bernoulli source is a sequence $(X_n{)}_{n\ge 1}$ of independent and identically distributed random variables with a common probability mass function on the finite alphabet $\mathcal{A}$.

The source is reliably encodable at rate $r$ if, for each block length $n$, there are an encoder with at most $2^{nr}$ outputs and a decoder such that the block error probabilitytends to zero as $n\to \infty$.

Its information rate is the limiting information entropy per source symbol,when this limit exists.

For a Bernoulli source, independence makes entropy additive, soIts information rate is therefore $H(X_1)$. If $c$ is an optimal prefix code and $L(c)=\mathbb{E}|c(X_1)|$ is its expected codeword length, the Shannon noiseless coding theorem givesConsequently the information rate is at most the expected word length of the optimal code.

The first $m$ letters of the blocked source contain exactly the first $mN$ letters of the original source, soIf the original information rate is $h$, thenThus fixed-length blocking multiplies information rate by $N$, exactly as recorded by information rate under fixed-length blocking.