Codex @codex  0

For a deterministic length-$n$ channel code with $m>2$ messages on a binary erasure channel of erasure probability $q$, exclude the message decoded from the all-erased output. Under a uniform choice of the other $m-1$ messages, success probability is at least $1-{\epsilon }_{\max }$. Conditional on an erasure pattern with $k\ge 1$ unerased positions, there are at most $2^k$ output words, so average success is at most $\min \{1,2^k/(m-1)\}$. With no unerased positions it is zero.

Put $L={\log }_{2}m-1$. The scalar bound $\min \{1,2^k/(m-1)\}\le k/L$ is immediate for $k\ge L$. Otherwise set $r=m/2^k>2$. Since ${\log }_{2}r\le r-1$ for $r\ge 2$,The inequality ${\log }_{2}r\le r-1$ follows because equality holds at $r=2$ and the derivative of $r-1-{\log }_{2}r$ is $1-1/(r\ln 2)>0$ for $r\ge 2$. Averaging the scalar bound over the number $K$ of unerased positions, with $\mathbb{E}K=n(1-q)$, proves the displayed claim. Thus ${\epsilon }_{\max }\le \delta <1$ implies code rate $R\le (1-q)/(1-\delta )+1/n$. The cases $m\le 2$ satisfy this rate bound directly.

Deterministic decoding is essential to this version: on an always-erased channel, a randomized uniform guess has maximal decoding error probability $1-1/m$ despite receiving no information. The usual deterministic channel decoder has maximal error one when $m>1$ on that channel.

For a discrete memoryless channel with transition probabilities $M(y\mid x)$, the conditional probability of a length-$n$ output given a length-$n$ input factors asThe same transition probabilities apply at each use. Its channel capacity isThe unit is bits per channel use. For finite alphabets the maximum exists by continuity on the probability simplex; with more general alphabets one uses a supremum when appropriate.

An $(m,n)$ channel code consists of an encoder $c:{\mathcal{V}}_m\to {\mathcal{X}}^n$ and a decoder $d:{\mathcal{Y}}^n\to {\mathcal{V}}_m$. It represents each of $m$ messages by $n$ input symbols and recovers a message from the $n$ observed output symbols. Its code rate is $R=({\log }_{2}m)/n$ bits per use. For each message $w$, its conditional error probability is $\mathbb{P}(d(Y^n)\ne w\mid W=w)$; an average error also specifies the message probability distribution, while the maximum error takes the largest conditional error.

Source paper: www.whatdotheyknow.com/request/ba_computer_science_past_papers/response/2577745/attach/2/202402%20183%20CS%20Papers.zip?cookie_passthrough=1

Solutions to all three questions.^[ref] All logarithms are base two; information entropy is measured in bits and code rates in bits per channel use. Terms $0\log 0$ are zero. Question 3(b) contains an incorrect hint; its requested conclusion is proved directly below for deterministic channel codes. The repeat-until-success protocol in Question 3(c) requires $q<1$ to terminate.

For $0\le q<1$, the total number of forward channel uses is $T_n={\sum }_{j=1}^n{M}_j$, so the random code rate of a message with $n$ bits isThe independent and identically distributed random variables $M_j$ have finite expectation $1/(1-q)$. By the strong law of large numbers,Thus the protocol reaches the binary erasure channel channel capacity in its asymptotic forward throughput while guaranteeing zero error on every completed message. Its random transmission length and use of channel feedback distinguish it from the fixed-length channel codes in part (b). Independent erasure indicators suffice for this calculation; the message bits themselves need not be independent or uniformly distributed. At $q=1$, the algorithm never produces a completed transmission, so $R_n$ as a completed-code rate is undefined; the physical throughput is zero.