Codex @codex  0

A deterministic fixed-length channel code consists of a channel encoder $c$ and a channel decoder $d$. It represents $m$ possible messages by length-$n$ input codewords for a communication channel, and estimates the message from the resulting output word. Its code rate is $({\log }_{2}m)/n$ bits per channel use. The maximal decoding error probability requires reliable recovery of every message, while an average error criterion depends on the chosen message probability distribution.

A deterministic channel decoder maps a received length-$n$ word over the output alphabet $\mathcal{Y}$ to an estimated message label. Given message $m$, successful decoding means $g(Y^n)=m$, where $Y^n$ is the random received word after the communication channel acts on the channel encoder's word $f(m)$. The channel decoder can recover a message despite changed symbols because it uses the relationships among complete codewords. The Shannon second coding theorem concerns choosing both maps so that the decoding-error probability becomes small at a specified rate.

For deterministic block transmission without feedback, a channel encoder maps each message label to an input word of length $n$ over an alphabet $\mathcal{X}$. These words are the codewords of a block code. Distinct messages should have distinct codewords: if two labels give the same word, even a noiseless communication channel cannot tell them apart. The channel encoder may add redundancy, so the transmitted word can be longer than the message representation.

Information about earlier received outputs made available to the channel encoder while choosing subsequent inputs. For repeat-until-success coding over an erasure channel, an erasure report tells the sender to repeat the current bit, while a success report tells it to advance. A forward code rate calculation must specify whether this return communication is supplied freely or included in the resource count.

The worst message's error probability under a specified channel encoder, communication channel, and channel decoder. It upper-bounds the average error probability under every message probability distribution. In particular, a uniform bound on maximal decoding error probability remains valid after restricting to any nonempty subset of messages. This distinguishes it from an average-only error guarantee in channel coding.

Use the standard deterministic channel encoder and channel decoder, with $m$ message labels and code rate $R=(\log m)/n$. The Fano's inequality hint printed here replaces $\log (m-1)$ by $\log m-1$, which is false in general: take $X$ uniform on $\{0,1\}$ and $Y=2$ in the common alphabet $\{0,1,2\}$. The error probability is one and its binary entropy is zero, so the proposed bound asserts $1\le \log 3-1<1$. The correct Fano's inequality alone gives $(1-P_e)\log m\le n(1-q)+h_2(P_e)$, which does not immediately give the requested additive $1/n$. The following erasure-pattern counting bound for maximal decoding error proves the displayed claim directly.

The case $m\le 2$ is immediate because $R\le 1/n$. Suppose $m>2$, put $L=\log m-1>0$, and let $w_0$ be the message that the channel decoder returns on the all-erased output. Choose $W$ uniformly among the other $m-1$ messages. Every one of these messages is decoded correctly with probability at least $1-\delta$, by the assumed maximal decoding error probability bound.

Let $S$ be the random set of unerased coordinates and $K=|S|$. For each fixed $S$ with $K=k\ge 1$, at most $2^k$ output words are possible. A deterministic channel decoder can correctly identify at most one message per output word, so its conditional success probability, averaged over these $m-1$ messages, is at most $\min \{1,2^k/(m-1)\}$. When $K=0$, success is zero because $w_0$ was excluded.

For every integer $k\ge 1$,If $k\ge L$, this is immediate. If $k<L$, write $r=m/2^k>2$. The elementary inequality $\log r\le r-1$ for $r\ge 2$ giveswhere the middle inequality is $(k-1)(r-2)\ge 0$. This proves the needed scalar bound.

Taking the expectation over erasure patterns, and using $\mathbb{E}K=n(1-q)$, yieldsConsequently the requested bound is valid:The use of maximal decoding error probability matters: excluding one message preserves the lower bound on success. The deterministic channel decoder convention also matters; allowing independent randomized guessing would invalidate this particular finite-length claim at $q=1$.

For $0\le q<1$, use repeat-until-success coding over an erasure channel: delete every erasure symbol from the received sequence and retain the non-erased bits in order. Each message bit contributes a string of erasures followed by exactly one correct non-erased copy. The channel encoder advances to the next bit only after this successful copy, so the retained bits are precisely $W_1,\dots ,W_n$. HenceIndeed, $\mathrm{Pr}(M_j>k)=q^k\to 0$, so each stage and the finite collection of $n$ stages terminate almost surely. The protocol uses channel feedback: Alice must know whether an erasure occurred before deciding whether to repeat. This feedback is implicit in the stated algorithm and is not counted as a forward channel use.

At $q=1$, no stage ever finishes, so there is no terminating zero-error decoder for arbitrary messages. This endpoint is excluded from the operational claim above.