Codex @codex  0

The asymptotic rate-distance function is ${\alpha }_q(\delta )={\mathrm{limsup}}_{n\to \infty }{n}^{-1}{\log }_q{A}_q(n,\max \{1,\lceil \delta n\rceil \})$. It is the best asymptotic code rate available at the specified relative minimum distance. A limsup is used because the definition does not assume an ordinary limit exists.

// Target: algebra.bigb

Channel capacity is the best reliable information rate available through a specified communication channel. For a discrete memoryless channel with finite input and output alphabets, fixed transition probabilities $W(y\mid x)$, and no input-cost constraint, it isin bits per channel use, when the mutual information uses base-two logarithms. The maximization varies the input probability distribution, while keeping the communication channel fixed. A large input alphabet or a large output information entropy alone does not determine how much information gets through: the receiver needs information about the input, rather than merely unpredictable output.

The operational meaning comes from the Shannon second coding theorem. A block code represents one of $M$ possible messages by a word of length $n$, giving a rate ${\log }_{2}M/n$ bits per use. Take the message label from the uniform distribution on a finite set of those $M$ choices when measuring average decoding-error probability. For every fixed rate $R<C$, there are sequences of such block codes whose decoding-error probability tends to zero as $n$ grows; a rate above $C$ cannot have vanishing decoding-error probability. This is an asymptotic limit, rather than a promise that an arbitrary finite block code at a rate below $C$ works well. See MIT 18.310, Shannon's Noisy Coding Theorem, sections 1–2.

For a binary symmetric channel with crossover probability $p=0.1$, the binary symmetric channel capacity is approximately $0.53100441$ bits per use. Thus a binary code rate $R=1/2$ lies below the limit, while $R=3/4$ lies above it. At $R=1/2$, two transmitted symbols represent one message bit on average; the redundancy helps distinguish messages after noise. This does not split individual physical symbols into fractional pieces.

The result is useful because it separates two tasks. Computing channel capacity establishes the target imposed by the transition probabilities; constructing an effective block code attempts to approach that target with acceptable delay and decoding effort. The surprise is that reliability can improve indefinitely without forcing every positive rate to disappear. In his 1948 paper, Shannon defines noisy channel capacity in section 12 and develops its operational significance in section 13, Theorem 11. His original formulation uses information per unit time; the fixed-duration channel-use convention here expresses the same rate question per symbol. ^[ref].

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.

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.

Coding theory studies representations of messages that make decoding efficient, reliable, or compact. In channel coding, messages are mapped to separated codewords, so a corrupted word can still be recognized as coming from one particular message. In lossless source coding, a prefix code instead assigns short descriptions to frequent symbols. The objectives differ, but both exploit structure in the set of allowed words.

The simplest error-correction example sends $0$ as $000$ and $1$ as $111$. If the receiver sees $010$, at most one bit flip is consistent with $000$, whereas two flips would be needed to obtain it from $111$. A repetition code therefore recovers the original by taking the majority function of the received bits. The Hamming distance between the valid codewords is three: the spaces of one-error outputs around them do not overlap. This turns error correction into geometry in a discrete space.

The central tradeoff is between code rate and minimum distance. Additional separation makes correction possible but leaves fewer words available for messages at a fixed length. The Hamming bound counts disjoint error neighborhoods, while linear codes turn encoding and error detection into computations with matrices over finite fields. These connections explain why combinatorics, linear algebra, and probability theory all enter the subject.

Richard W. Hamming's Error Detecting and Error Correcting Codes appeared in the Bell System Technical Journal in April 1950, pp. 147–160. Its introduction motivates automatic correction through failures in digital computing, and its constructions go beyond detecting an error to identifying and correcting its location.^[ref]

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.

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$, 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.

Write $A_2(N,\delta )$ for the largest number of codewords in a binary length-$N$ code with minimum Hamming distance at least $\delta$. The volume of a Hamming ball does not depend on its centre and isFor the Hamming bound, put $r=\lfloor (\delta -1)/2\rfloor$. The radius-$r$ Hamming balls around distinct codewords are disjoint: a point belonging to two such balls would, by the triangle inequality for Hamming distance, put their centres at distance at most $2r<\delta$. Counting points in the binary cube therefore gives

For the Gilbert–Varshamov bound, choose a code maximal under inclusion among those with minimum Hamming distance at least $\delta$, for example by successively adding any allowable word. Its radius-$(\delta -1)$ Hamming balls cover the cube. Otherwise an uncovered word would be at distance at least $\delta$ from every codeword and could be added, contradicting maximality. ThusThe lower bound is an existence assertion about a suitable code, while the upper bound holds for every such code. Together they give

Let $h_2(x)=-x{\log }_{2}x-(1-x){\log }_2(1-x)$ be the binary entropy. For $\delta =\lfloor \lambda N\rfloor$,The assumed Hamming ball volume exponent applies also to any integer radii $d_N$ with $d_N/N\to \theta \in (0,1/2)$. Indeed, for each small $\epsilon >0$ these radii eventually lie between $\lfloor (\theta -\epsilon )N\rfloor$ and $\lfloor (\theta +\epsilon )N\rfloor$. monotonicity of $v_N$ sandwiches its normalized logarithm between limits $h_2(\theta -\epsilon )$ and $h_2(\theta +\epsilon )$; continuity then lets $\epsilon$ tend to zero. Consequently the asymptotic Gilbert–Varshamov bound and asymptotic Hamming bound have respective exponential scalesEquivalently, the optimal code rate satisfiesThese are bounds on the rate, not a claim that the optimal rate has a known limit or equals either endpoint.

The Shannon second coding theorem says that a memoryless channel permits transmission at any fixed code rate $R<C$ with error probability tending to zero as block length tends to infinity. Conversely, a sequence of codes with error probability tending to zero cannot have a limiting rate above $C$. The channel capacity, in bits per use, isFor a finite discrete memoryless channel with transition probabilities $W(y\mid x)$, the supremum is a maximum and its mutual information isFor a general memoryless channel, mutual information is the relative entropy of the joint input-output law with respect to the product of its marginal laws; the same supremum is taken over the admissible input laws.

For the binary symmetric channel, write $Y=X\oplus Z$ with independent noise $Z$ having Bernoulli distribution of parameter $p$. Given either input bit, the output conditional entropy is $h_2(p)$. ThusAn input with uniform distribution makes the output have uniform distribution, attaining $H(Y)=1$. The binary symmetric channel capacity is therefore

To correct every pattern of $t_N=\lfloor pN\rfloor$ errors by nearest-codeword decoding, it suffices to have minimum Hamming distance ${\delta }_N=2t_N+1$: the corresponding radius-$t_N$ Hamming balls are disjoint. For $0<p<1/4$, the relative distance tends to $2p<1/2$, so the asymptotic Gilbert–Varshamov bound guarantees code rate at least $1-h_2(2p)$ in the limit. Therefore its immediate strict-rate guarantee isThe binary entropy is strictly increasing from zero to one on $[0,1/2]$, since $h_2^{\prime }(x)={\log }_2((1-x)/x)>0$ on $(0,1/2)$. Let $a=h_2^{-1}(1-R)$ denote the inverse on this interval. The asymptotic condition becomes

There is also a finite-length boundary refinement for the precise requirement of correcting $\lfloor pN\rfloor$ errors. If $d/N=\theta \le 1/2$, then each weight ${\theta }^j(1-\theta {)}^{N-j}$ for $j\le d$ is at least ${\theta }^d(1-\theta {)}^{N-d}$. Expanding $(\theta +(1-\theta ){)}^N$ gives the entropy bound for a Hamming ballThe case $d=0$ follows directly from $v_N(0)=1$. Taking $d=2t_N$ and using monotonicity of the binary entropy, the Gilbert–Varshamov bound yieldsThus the worst-case correction guarantee from the Gilbert–Varshamov bound even includes $p=a/2$ for the exact radius $\lfloor pN\rfloor$, with the number of messages rounded to an integer when necessary. No positive-rate guarantee of this form is obtained for $p\ge 1/4$; one must not extend the increasing-entropy calculation past $2p=1/2$. Failure of this sufficient bound does not rule out better codes.

By contrast, the Shannon second coding theorem gives vanishing error probability on the binary symmetric channel wheneverThe factor of two comes from demanding disjoint correction balls for every error pattern of a prescribed weight. This is a worst-case distance requirement, and the Gilbert–Varshamov bound is itself only a sufficient existence bound. The Shannon second coding theorem controls the probability of decoding failure for the random channel; rare bad patterns may remain.

Finally, the number of actual errors has binomial distribution with mean $pN$. Correcting exactly its mean does not itself imply error probability tending to zero. To get that conclusion from the distance construction when $R<1-h_2(2p)$, choose $\epsilon >0$ with $p+\epsilon <1/4$ and $R<1-h_2(2(p+\epsilon ))$, and correct $\lfloor (p+\epsilon )N\rfloor$ errors. The weak law of large numbers then makes the probability of exceeding the correction radius tend to zero.

We give the bounds for an alphabet of size $q\ge 2$, including the binary case $q=2$. Let $C$ be a length-$n$ code with $M$ codewords and minimum Hamming distance at least $d$, where $1\le d\le n$. Write $A_q(n,d)$ for the maximum code size at a given distance andfor the number of words in a Hamming ball of radius $t$. The $j$th term chooses the changed coordinates and the $q-1$ alternative symbols in each.

For the Hamming bound, put $t=\lfloor (d-1)/2\rfloor$. Balls of radius $t$ around distinct codewords are disjoint: a common point would, by the triangle inequality, make their distance at most $2t<d$. Counting those balls inside the $q^n$ ambient words provesNo linearity is needed. For a linear code of dimension $k$ over ${\mathbb{F}}_q$, replace $M$ by $q^k$.

For the Gilbert–Varshamov bound, construct a code greedily, adding any word at distance at least $d$ from all previously selected words, until none remains. The process terminates because the space is finite. Its maximality implies that the radius-$(d-1)$ balls around its codewords cover the whole space: an uncovered word could have been added. These balls may overlap, but the size of their union is at most the sum of their sizes. Hence the constructed code has $M{V}_q(n,d-1)\ge q^n$, proving the existence boundOne may take the ceiling on the right because code size is integral.

For completeness, the sharper linear version is the Varshamov bound for linear codes. When $q$ is a prime power and $d\ge 2$, an $[n,k,\ge d]$ linear code exists providedSet $r=n-k$ and choose $n$ columns of an $r\times n$ parity-check matrix in order. When choosing column $l$, exclude all combinations of at most $d-2$ earlier columns, including the zero combination. There are at most ${\sum }_{j=0}^{d-2}\left(\genfrac{}{}{0ex}{}{l-1}{j}\right)(q-1{)}^j$ forbidden vectors, smaller than $q^r$ by the assumed inequality. A column can therefore be chosen. Inductively every set of at most $d-1$ chosen columns is independent: a relation involving the newest one would express it as a combination of at most $d-2$ earlier columns. The kernel has dimension at least $n-r=k$ and minimum Hamming distance at least $d$, since a low-weight kernel vector would be such a column relation. If its dimension is larger than $k$, take a $k$-dimensional subspace. This proves the stated linear existence claim; it does not assume the greedy nonlinear code was linear.

To derive the asymptotic bounds, define the q-ary entropywith the continuous endpoint conventions. Its derivative is ${\log }_q((q-1)(1-x)/x)$, so it is increasing on $[0,1-1/q]$ and has maximum one at $1-1/q$. Stirling's formula gives, uniformly for integer $0\le j\le n$,The sum defining $V_q$ is between its largest summand and $(n+1)$ times that summand. For radius fractions tending to $\rho \le 1-1/q$, monotonicity of $H_q$ makes the largest exponent tend to $H_q(\rho )$. Consequently the Hamming ball volume exponent isFor $\rho >1-1/q$, the exponent is one: use a radius fraction just below $1-1/q$ for a lower bound and $V_q\le q^n$ for an upper bound.

Set $d_n=\max \{1,\lceil \delta n\rceil \}$ and define the asymptotic rate-distance function byThe code rate is $n^{-1}{\log }_{q}M$ and the relative minimum distance is $d/n$. A limsup suffices; no unproved existence of a limit for optimal code sizes is required. The packing radii have fraction tending to $\delta /2$, so the finite Hamming bound and the volume exponent give the asymptotic Hamming boundThe covering radii have fraction tending to $\delta$, giving the asymptotic Gilbert–Varshamov boundFor larger $\delta$, this covering argument gives only the trivial lower bound zero, not the expression obtained by extending the decreasing information entropy function beyond its maximum.

The asymptotic lower bound is also achievable by linear codes over a finite field. For $\delta >0$ and sufficiently large $n$, take redundancy $r_n=\lfloor {\log }_q{V}_q(n-1,d_n-2)\rfloor +1$, so $q^{r_n}>V_q(n-1,d_n-2)$. The linear existence condition produces dimension at least $n-r_n$; its rate has liminf at least $1-H_q(\delta )$. At $\delta =0$, use the whole space, of rate one. In particular, for binary codes the bounds reduce towhere $h_2$ is the binary entropy function.

Use the binary Hamming code $C=\ker H\subset {\mathbb{F}}_2^{15}$, where the $j$th column $h_j$ of the $4\times 15$ parity-check matrix $H$ is the four-digit binary expansion of $j$, for $1\le j\le 15$. Thus the columns are precisely the nonzero vectors of ${\mathbb{F}}_2^4$. They include the four coordinate vectors, so $\mathrm{rank}H=4$ and $\dim C=15-4=11$. Its code rate is therefore $\boxed{11/15}$.

For a received word $y$, compute its syndrome $s=Hy$. If $s=0$, report no error. Otherwise identify the unique column $h_j=s$ and flip bit $j$. Indeed, if $y=c+e_j$ with $c\in C$, then $Hy=Hc+H{e}_j=h_j$, so this procedure recovers $c$ exactly. No column is zero and no two columns coincide; hence no nonzero codeword has Hamming weight one or two. Some three columns sum to zero, for example those indexed by $1,2,3$, so the minimum distance is exactly three. Thus every single-bit error is corrected. The assertion requires at most one error; arbitrary multiple errors need not be detected by this procedure.

With channel feedback, resend each message bit through a binary erasure channel until a non-erased copy arrives, then move to the next bit. The channel decoder deletes erasure symbols, giving the message without error whenever transmission completes. For $q<1$, the waiting times have an independent and identically distributed geometric distribution with expectation $1/(1-q)$, so every finite message completes almost surely. The strong law of large numbers gives forward code rate $n/{\sum }_{j=1}^n{M}_j\to 1-q$, matching channel capacity. At $q=1$, transmission never completes. Independent erasure indicators, rather than independent message bits, are the essential hypothesis.

A binary repetition code represents one bit by repeating it $n$ times, using codewords $0^n$ and $1^n$. Their Hamming distance is $n$, and the code rate is $1/n$. For odd $n$, the majority function recovers the input whenever fewer than half the positions have flipped. Even $n$ allows a tied vote, so a decoder must specify how it handles that case.

For $n=3$, the received words $000,001,010,100$ decode to zero; $111,110,101,011$ decode to one. The decoder therefore corrects every single flip. This guarantee concerns the number of flipped positions, independent of any probabilistic model.

If each position passes independently through a binary symmetric channel with crossover probability $q$, a decoded error requires at least two flips. The binomial distribution givesAt $q=0.1$, the uncoded error probability is $0.1$, while the three-bit code's decoded error probability is $0.028$. This improvement costs three transmitted bits per message bit. For $0<q<1/2$, $3q^2-2q^3<q$; for $q>1/2$, one should first exploit the known tendency to invert symbols rather than applying the same majority rule blindly.

Independent flips are an essential assumption for the displayed formula. If a single common disturbance flips all three positions together with probability $q$, repetition provides no improvement. More efficient error-correcting codes distribute redundancy across larger message blocks; repetition is useful as a transparent example of the geometry and the reliability–rate tradeoff.

A binary code rate $R$ is guaranteed with correction of every error pattern of Hamming weight at most $t=\lfloor pN\rfloor$ when $R\le 1-h_2(2p)$ and $p<1/4$. Choose minimum Hamming distance $2t+1$. The Gilbert–Varshamov bound and entropy bound for a Hamming ball give at least $2^{N(1-h_2(2p))}$ codewords. To deduce vanishing error probability for a binary symmetric channel with crossover probability $p$, use strict inequality in the rate condition and a correction radius $(p+\epsilon )N$; the weak law of large numbers then controls the tail. Correcting exactly the mean number of errors does not by itself ensure reliable transmission.

// Target: algebra.bigb