Coding theory

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]

A checksum is a value calculated from data to expose some forms of corruption. Internet Protocol and transport checks cover specified header and data fields; changing covered fields requires updating their checksums.

A cyclic redundancy check uses a polynomial remainder over the field with two elements as checking information. In the basic systematic convention, appending the remainder of $x^{r}M$ modulo the CRC generator polynomial makes the transmitted polynomial divisible by that generator.

The CRC generator polynomial is the agreed divisor in a cyclic redundancy check. Under the basic convention, undetected error polynomials are precisely its nonzero multiples.

Channel coding represents messages with codewords chosen to withstand transmission errors. An error-correcting code deliberately supplies redundancy, so a receiver can distinguish nearby corrupted outputs and recover the message. Lossless source coding instead removes predictable redundancy; practical communication can use both operations. The Shannon second coding theorem relates achievable rates on a discrete memoryless channel to its channel capacity.

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.

Random coding constructs a channel code by sampling its codewords from a specified probability distribution and bounding the expected decoding error over that ensemble. If the expected average error is at most $ϵ$, at least one deterministic codebook has average error at most $ϵ$; otherwise every book would exceed the expectation bound. This is the probabilistic method applied to communication codes.

For independently uniform binary codewords, a fixed competing word falls in any received word's radius-$r$ Hamming ball with probability $2^{-n}{\sum }_{j=0}^r\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. The union bound over competing messages, together with a bound on excessive channel noise, yields the basic random-coding error estimate. Expurgation of a codebook can then convert average-error control to maximal decoding error probability with negligible loss of asymptotic rate.

Expurgation discards messages with unusually high conditional decoding error. If a codebook with $2M$ equally likely messages has average error at most $ϵ$, at least $M$ messages have individual error at most $2ϵ$, by Markov's inequality. Retaining those messages and restricting the decoder's candidates gives a codebook with maximal error at most $2ϵ$, provided removal of candidates cannot spoil a previously successful decoding. This is the case for bounded-distance decoding with errors on ambiguity, and for a decoder that retains its former decisions whenever the decoded message remains.

For a sequence of block lengths $n$, halving a book changes its logarithmic rate by $1/n$, which tends to zero. Thus a vanishing average-error bound from a random coding construction can be converted into a vanishing maximal decoding error probability at the same limiting rate. The probabilistic construction first supplies a deterministic book with sufficiently small average error; expurgation is a subsequent deterministic step.

Code encoding maps messages injectively to codewords. For a dimension-$k$ linear code with generator matrix $G$, the standard encoder maps $m\in {\mathbb{F}}_q^k$ to $mG$. The redundancy makes error detection and recovery possible; for a Reed-Solomon code, encoding can instead evaluate a message polynomial at the chosen field elements.

A systematic encoder retains the message symbols unchanged in designated coordinates of its codeword and calculates the remaining check symbols. For a linear code, choosing an invertible set of $k$ columns of a generator matrix and changing its row basis gives this form.

For a length-$n$, dimension-$k$ cyclic code with generator polynomial $g$ of degree $n-k$, let the message polynomial satisfy $\mathrm{deg}M<k$. Subtracting the remainder upon polynomial division by $g$ makes the displayed word divisible by $g$. The remainder has degree less than $n-k$, so the highest $k$ coordinates retain the coefficients of $M$. This gives systematic encoding without losing any message information.

For codes over an alphabet of size $q$, the greedy packing argument gives $A_q(n,d)\ge q^n/V_q(n,d-1)$, where $V_q(n,r)={\sum }_{j=0}^r\left(\genfrac{}{}{0ex}{}{n}{j}\right)(q-1{)}^j$. A maximal distance-$d$ code has radius-$(d-1)$ Hamming balls covering the entire space; counting their union proves the lower bound. The linear refinement is the Varshamov bound for linear codes.

// Target: algebra.bigb

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

For $0\le \delta \le 1-1/q$, take logarithms of the Gilbert–Varshamov bound and apply the Hamming ball volume exponent. The Varshamov bound for linear codes gives the same achievable lower bound within linear codes for prime-power $q$.

// Target: algebra.bigb

For a prime-power alphabet size $q$, a linear $[n,k,\ge d]$ code exists if $V_q(n-1,d-2)<q^{n-k}$. Choose parity-check columns successively, avoiding combinations of at most $d-2$ earlier columns. Fewer than $q^{n-k}$ vectors are forbidden, so such a choice is possible. No set of at most $d-1$ columns is dependent, and the resulting kernel has dimension at least $k$.

// Target: probability-and-statistics.bigb

A codeword is a member of the specified set of words used to encode messages. For a linear code specified by a parity-check matrix $H$, the codewords are precisely the vectors satisfying $Hc=0$. The minimum distance between distinct codewords controls error correction.

The codeword length is the number of alphabet symbols in a codeword. For a binary word it counts bits; in a prefix code, it is the depth of the corresponding leaf in the code tree.

// Target: algebra.bigb

A cipher is a pair of keyed algorithms that maps a plaintext to a ciphertext and recovers the plaintext from the ciphertext when supplied with the appropriate key.

Plaintext is the unencrypted message supplied to a cipher.

Ciphertext is the encrypted message produced by a cipher.

A block code assigns source messages to words of a fixed length over an alphabet. Its codewords form a subset of that fixed-length word space; a binary block code uses the two-symbol finite field ${\mathbb{F}}_2$.

A binary $[n,m,d]$ code is a set of $m$ distinct words in ${\mathbb{F}}_2^n$ whose minimum pairwise Hamming distance is $d$. Here $n$ is the block length and $m$ is the number of codewords.

An error-correcting code is a set of codewords chosen with enough separation to recover a transmitted message after specified errors. For equal-length words and bit-flip errors, separation is measured by Hamming distance. If the minimum distance is $d$, any nonzero pattern of at most $d-1$ flips changes a valid word into an invalid word and can therefore be detected. Every pattern of at most $t=\lfloor (d-1)/2\rfloor$ flips can be corrected by choosing the unique nearby codeword.

The distinction matters. A distance-two code detects a single flip but need not locate it; a distance-three code corrects a single flip. The triangle inequality explains the correction threshold: a received word within distance $t$ of two distinct codewords would put those codewords within distance $2t<d$, a contradiction. Actual decoders also need an efficient way to find the nearby word; a parity-check matrix and syndrome decoding exploit the structure of a linear code to do this.

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.

The Hamming distance between two equal-length words is the number of coordinates in which they differ.

The Hamming space of length $n$ over a finite field ${\mathbb{F}}_q$ is the set ${\mathbb{F}}_q^n$ equipped with Hamming distance, the number of coordinates at which two words differ. The Hamming weight of a word is its distance from zero.

This is the maximum Hamming distance between the characteristic vectors of members of a set family. In a down-set, one can replace a pair by disjoint subsets with the same union, so the maximum distance equals the largest size of a union of two members. A t-intersecting family has diameter at most $n-t$.

On binary words of length $n$, normalized Hamming distance is the fraction of differing coordinates. Unlike unscaled Hamming distance, it makes the Hamming cubes a Lévy family under uniform probability measures.

The Hamming cube is $\{-1,1{\}}^n$, or equivalently $\{0,1{\}}^n$, equipped with Hamming distance. Under its uniform probability measure, the distance from a fixed vertex has the binomial distribution with parameters $n,1/2$. This converts geometric ball sizes into probability tails.

An inclusion-maximal separated set of separation $an$ covers the Hamming cube by strict-radius $an$ balls. The Hoeffding lower-tail bound for Hamming balls then gives at least $e^{2n(1/2-a{)}^2}$ selected vertices. At $a=1/8$ this yields $e^{9n/32}$ vertices, all separated by at least $n/8$.

This Hamming distance on partitions identifies a group with its complement because exchanging the two group names does not change the partition. Complementation is an isometry of the ordinary Hamming distance, so minimizing over this two-element group action gives a quotient metric and preserves the triangle inequality. Negating a zero-one indicator is not complementation; with $\pm 1$ membership vectors, it is.

Suppose $v_i=\pm 1/\sqrt{n}$ encodes the true partition and $\hat{v}$ is a unit estimated eigenvector. Every coordinate of the wrong sign contributes at least $1/n$ to ${\min }_{\sigma =\pm 1}\Vert \hat{v}-\sigma v{\Vert }_2^2=2(1-|{\hat{v}}^{\top }v|)$. Since this is at most $2(1-|{\hat{v}}^{\top }v{|}^2)$, which is the squared Frobenius distance between the rank-one orthogonal projection matrices, the bound follows. Coordinates estimated as zero may be assigned consistently to either group.

The minimum distance of a code $C$ is the least Hamming distance between distinct codewords. For a linear code, translation invariance makes this equal to the least Hamming weight of a nonzero codeword.

The relative minimum distance of a length-$n$ code of minimum distance $d$ is $d/n$. It expresses the guaranteed separation as a fraction of the block length.

// Target: algebra.bigb

The quantity $A_q(n,d)$ is the largest cardinality of a length-$n$ code over an alphabet of size $q$ with minimum Hamming distance at least $d$. The code need not be linear.

// Target: algebra.bigb

The Hamming ball of radius $r$ about a word $x$ is the set of words whose Hamming distance from $x$ is at most $r$.

For $0\le \rho \le 1-1/q$, the exponential growth rate of a q-ary Hamming ball is $H_q(\rho )$. Stirling's formula gives the exponent of each summand $\left(\genfrac{}{}{0ex}{}{n}{i}\right)(q-1{)}^i$, and the sum lies between its largest term and $n+1$ times that term. Above the entropy-maximizing radius fraction, the exponent is one.

// Target: algebra.bigb

For a uniform vertex of the Hamming cube, distance from a fixed vertex is the sum of $n$ independent Bernoulli random variables with parameter $1/2$. The lower-tail Hoeffding inequality implies that the fraction of vertices at distance at most $an$, $0<a<1/2$, is at most $e^{-2n(1/2-a{)}^2}$. Strict-radius balls satisfy the same upper bound.

For $0<\rho \le 1/2$, the number of binary words within Hamming distance $\rho n$ of a fixed word is at most $e^{nh(\rho )}$, with the binary entropy function in natural logarithms. In $1={\sum }_j\left(\genfrac{}{}{0ex}{}{n}{j}\right){\rho }^j(1-\rho {)}^{n-j}$, each summand weight for $j\le \rho n$ is at least ${\rho }^{\rho n}(1-\rho {)}^{n(1-\rho )}=e^{-nh(\rho )}$. Also $h^{\prime \prime }(\rho )=-1/(\rho (1-\rho ))\le -4$, so $\log 2-h(1/2-a)\ge 2a^2$. These two bounds give the approximate-recovery denominator in the list-decoding Fano inequality.

A code of minimum distance $d$ is perfect if its Hamming balls of radius $\lfloor (d-1)/2\rfloor$ partition the ambient word space. Every word then has a unique nearest codeword within the code's error-correction radius.

The length-$23$ binary Golay code is the cyclic code over ${\mathbb{F}}_2$ generated byIt has dimension $12$, minimum Hamming distance $7$, and its radius-$3$ Hamming balls partition ${\mathbb{F}}_2^{23}$. Its parity extension has length $24$, dimension $12$, and minimum Hamming distance $8$.

// Target: algebra.bigb

The extended binary Golay code is the parity extension of the length-$23$ binary Golay code. It is a self-dual code and a doubly even code, with minimum Hamming distance eight. Its radius-three Hamming balls are disjoint but do not cover its Hamming space; it is not a perfect code.

For a binary symmetric matrix $A$ with $A^2=I$, the syndrome of an error $(p,q)$ relative to the column parity-check matrix $(I;A)$ is $s=p+qA$. An error of total Hamming weight at most three has at most one nonzero bit in one half. Test $s$, each $s+A_i$, $sA$, and each $sA+A_i$ for weights at most three, two, three and two respectively. These identify $(s,0)$, $(s+A_i,e_i)$, $(0,sA)$ and $(e_i,sA+A_i)$. For the extended binary Golay code, minimum Hamming distance eight guarantees that at most one such error exists.

Suppose a binary symmetric matrix $A$ satisfies $A^2=I$, has one row of Hamming weight eleven and eleven rows of Hamming weight seven, and every sum of two distinct rows has Hamming weight six. Then $(I\mid A)$ generates a self-dual code. Its rows have weights twelve or eight; their mutual orthogonality makes every generated word doubly even. A weight-four word $(u,uA)$ would have left-half weight one, two, three or four. The first two cases are excluded by the stated row weights; weight three would force $uA$ to be a unit vector and hence $u$ to be a row of $A$; weight four would force $uA=0$. Thus weight four is impossible and the minimum Hamming distance is eight.

The generator polynomial of a cyclic code defining the binary Golay code is $1+X+X^5+X^6+X^7+X^9+X^{11}$.

A root $\beta$ of the binary Golay generator polynomial has order $23$, and the Frobenius endomorphism shows that $\beta ,{\beta }^2,{\beta }^3,{\beta }^4$ are roots: $2^8\equiv 3(\mathrm{mod}23)$. The BCH bound gives minimum Hamming distance at least five. The circular autocorrelation of the binary Golay generator makes its parity extension doubly even, excluding original weights five and six. The generator itself has Hamming weight seven, proving that the distance is exactly seven.

// Target: algebra.bigb

The polynomial identity $(X+1)g(X)g^{\mathrm{rev}}(X)=X^{23}+1$, where $g^{\mathrm{rev}}(X)=X^{11}g(X^{-1})$, impliesEvery coefficient is the binary inner product of the coefficient vector of $g$ with one cyclic shift. Thus every such inner product is one. Appending a parity bit to the cyclic shifts gives mutually orthogonal weight-eight vectors, so orthogonal generators of doubly even codes applies.

// Target: algebra.bigb

For a code of length $n$, size $M$, and minimum distance $d$ over an alphabet of size $q$, puncturing $d-1$ coordinates gives the Singleton bound

The Plotkin bound limits a code whose minimum distance is more than the average distance between unrestricted words. For a binary code with $n<2d$ and even $d$,

Puncturing a code at one coordinate deletes that coordinate from every codeword. For a code of minimum distance $d\ge 2$, puncturing preserves its number of words and gives minimum distance $d$ or $d-1$.

For messages in a finite additive group, a one-time pad encrypts $X$ as $C=X+K$, where the key $K$ is uniform and independent of $X$, as long as the message, and never reused. Then $C$ is uniform and independent of $X$, giving perfect secrecy.

If two plaintexts are encrypted by adding the same one-time-pad key, subtracting the ciphertexts cancels the key and reveals the difference of the plaintexts. Redundancy in natural language or another structured message space can then reveal both messages, so a one-time pad must never reuse key material.

An encryption scheme has perfect secrecy when the ciphertext and plaintext are independent random variables, so observing the ciphertext does not change the plaintext's probability distribution.

If an interceptor knows that an additive one-time-pad ciphertext $C$ encrypts plaintext $P$ and wants it to decrypt as $P^{\prime }$, replacing it byworks without knowing the key, since $C^{\prime }=P^{\prime }+K$.

A secret-sharing scheme distributes shares of a secret so that authorized collections can reconstruct it while unauthorized collections reveal no information about it.

An $(r,s)$ threshold secret-sharing scheme issues $s$ shares: every collection of at least $r$ shares reconstructs the secret, while every collection of fewer than $r$ shares has a distribution independent of the secret.

Shamir's secret sharing places a secret $N$ at the constant term of a random polynomial $f\in {\mathbb{F}}_p[X]$ of degree at most $r-1$ and issues distinct nonzero evaluation pairs $(x_i,f(x_i))$. Any $r$ shares recover $f$ by polynomial interpolation. Given fewer than $r$ shares, every candidate constant term has the same number of compatible coefficient tuples, which gives perfect secrecy.

Conditioned on any $r-1$ shares in Shamir's secret sharing, each candidate secret in ${\mathbb{F}}_p$ remains equally likely. Appending $(0,N)$ to those shares determines exactly one degree-at-most-$(r-1)$ polynomial for every candidate $N$, by the nonzero Vandermonde determinant.

A discrete memoryless channel models transmission through finite input and output alphabets using fixed conditional probabilities $W(y\mid x)$. For each input $x$, these nonnegative numbers sum to one over the output symbols. Discrete refers to the symbols, and memoryless means that the noise of one use does not remember earlier uses.

For a fixed input word $x^n=(x_1,\dots ,x_n)$ sent without feedback, the output law isThis is conditional independence of the outputs given the prescribed input word. It does not require an encoder to choose independent input symbols: the codewords of a block code deliberately impose relationships among them. Those relationships let a decoder distinguish possible messages after noise.

The binary symmetric channel and binary erasure channel make two different memoryless noise models with a binary input. One hides flipped bits; the other marks missing bits. Their different channel capacities show why the whole transition matrix matters, as the flips versus erasures in a binary channel demonstrate.

Let the input alphabet be $\{0,1,2\}$ and let the output be $Y=X+Z$, where independent noise is uniform on two distinct integers. Translating the output alphabet reduces the noise to $\{0,d\}$, $d\ge 1$. The reachable output alphabet has size $3+\min (d,3)$: it is the union of two three-element intervals shifted by $d$.

For $d=1$, every row of the transition matrix has conditional information entropy one bit, so $I(X;Y)\le {\log }_{2}4-1=1$. Input probabilities $(1/2,0,1/2)$ make the output uniform and attain one bit per use. For $d\ge 3$, the two translated input alphabets are disjoint and every output identifies its input. A uniform input then attains ${\log }_{2}3$ bits per use.

For $d=2$, reflection symmetry and concavity of information entropy permit restricting to input probabilities $(s/2,1-s,s/2)$. Conditional on output parity, outputs whose labels are even integers have probabilities $(1/4,1/2,1/4)$ and outputs whose labels are odd integers have probabilities $(1/2,1/2)$. Consequently $I(X;Y)=h_2(s)+s/2$. Its strictly negative second derivative and stationary equation ${\log }_2((1-s)/s)+1/2=0$ give $s=\sqrt{2}/(1+\sqrt{2})$ and channel capacity ${\log }_2(1+\sqrt{2})$. All three values follow from overlap of translated input alphabets, rather than from output alphabet size alone.

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.

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.

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.

A finite-alphabet erasure channel transmits the input symbol unchanged with probability $1-f$ and replaces it by a distinct erasure flag with probability $f$, independently of the symbol. Given the flag, the posterior remains the input distribution; otherwise the input is known. Thus its mutual information is $(1-f)H(X)$.

For a finite-alphabet erasure channel with $k$ input symbols, $I(X;Y)=(1-f)H(X)$. Maximizing Shannon entropy at the uniform input gives channel capacity $C=(1-f){\log }_{2}k$ bits per use, by the Shannon second coding theorem.

A binary erasure channel transmits each input bit correctly with probability $1-\epsilon$ and replaces it by an erasure symbol with probability $\epsilon$. Its channel capacity is $1-\epsilon$ bits per use.

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.

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.

A Z-channel transmits one binary input without error while the other can change into the first. Unlike a binary symmetric channel, its errors are one-sided.

For a discrete memoryless channel, operational capacity equalsRates below $C$ admit codes whose error tends to zero, while rates above $C$ cannot have vanishing error.

A rate $R$ is reliably achievable through a channel when there is a sequence of length-$n$ channel codes with $M_n$ messages such thatand their decoding-error probability tends to zero.

A binary linear-feedback shift register of degree $d$ updates a $d$-bit state by shifting and inserting a fixed linear combination over ${\mathbb{F}}_2$. With recurrenceits feedback polynomial is $x^d+a_{d-1}{x}^{d-1}+\cdots +a_0$.

Under the convention that a register emits each shifted-out symbol, its first $d$ output symbols are exactly its initial fill. Thus a binary register of length $d$ has $2^d-1$ distinct outputs from nonzero fills. For lengths $r<s$, at least one longer-register output is absent from the shorter register, guaranteeing a pair of unequal nonzero outputs. The two sets need not be disjoint: recurrences $s_{n+1}=s_n$ and $s_{n+2}=s_n$ both generate constant ones. Nor must they intersect: the length-one recurrence and $s_{n+2}=s_{n+1}+s_n$ have no common nonzero output, since constant ones fail the second recurrence.

The feedback polynomial records the coefficients of an LFSR recurrence. With the conventionit is $x^d+a_{d-1}{x}^{d-1}+\cdots +a_0$.

A feedback shift register updates a finite state by shifting its stored symbols and inserting the value of a feedback function of the previous state. The feedback function need not be linear.

The Berlekamp-Massey algorithm finds the shortest linear recurrence satisfied by a finite sequence over a field. It processes symbols incrementally, updating the connection polynomial whenever the current recurrence has a nonzero discrepancy.

Suppose a connection polynomial $C$ of degree at most $L$, with recurrence span $L$ gives zero recurrence discrepancies through index $r-1$ but a nonzero discrepancy at $r$. If a polynomial $D$ of span $L^{\prime }$ successfully explains the prefix through $r$ and $L+L^{\prime }\le r$, evaluate the coefficient at $r$ in the convolution $(CD)x$. Applying $D$ first makes it zero. Applying $C$ first leaves its nonzero discrepancy at $r$, because the earlier discrepancies vanish and $D$ has constant coefficient one. This contradiction gives the displayed lower bound. It is the minimality step used by the Berlekamp-Massey algorithm; the algorithm cancels the new discrepancy with a shifted earlier failed polynomial.

The shortest binary linear recurrence producing the prefix $11001011$ has length three:Its connection polynomial is $1+D^2+D^3$.

A degree-$d$ binary register has $2^d$ states. The zero state is fixed, so a nonzero periodic orbit has length at most $2^d-1$.

A maximal-period feedback polynomial cannot have $1$ as a root. Over ${\mathbb{F}}_2$, this saysso an even number of the coefficients $a_i$ equal one and the full monic polynomial has an odd number of nonzero coefficients.

If an output prefix contains $d$ consecutive zeros followed by a one, no register of degree at most $d$ can generate it: the all-zero state would have been reached and would remain zero forever.

The seven consecutive zeros followed by one force degree at least eight. Degree eight is attained by $s_{n+8}=s_n$, with initial state $10000000$ and feedback polynomial $x^8+1$.

Let $K={\mathbb{F}}_{2^d}$, let $\alpha$ generate $K^{\times }$, and let $T:K\to {\mathbb{F}}_2$ be nonzero linear with nondegenerate bilinear form $(x,y)\mapsto T(xy)$. If the minimal polynomial of $\alpha$ is $P(X)=X^d+{\sum }_{j<d}{c}_j{X}^j$, then $x_n=T({\alpha }^n)$ satisfiesso it is produced by an LFSR of length at most $d$. Its period is exactly $2^d-1$: any period $r$ would imply $T(({\alpha }^r-1)y)=0$ for every $y\in K$, hence ${\alpha }^r=1$ by nondegeneracy.

A binary linear $[n,k,d]$ code is a $k$-dimensional subspace of ${\mathbb{F}}_2^n$ with least nonzero weight $d$. A parity-check matrix presents it as a kernel.

Two linear codes are monomially equivalent if a permutation of coordinates followed by multiplication of individual coordinates by nonzero field elements takes one to the other. This preserves dimension and Hamming distance. Choosing different representatives for projective parity-check columns produces this equivalence.

A nonzero length-$n$, dimension-$k$ linear code is maximum distance separable if its minimum Hamming distance equals $n-k+1$, attaining the Singleton bound. Reed-Solomon codes and generalized Reed-Solomon codes provide examples because a nonzero polynomial of degree at most $k-1$ has at most $k-1$ distinct polynomial roots.

For distinct elements $a_1,\dots ,a_n$ of a finite field, a Reed-Solomon code consists of the evaluation vectors $(f(a_1),\dots ,f(a_n))$ of polynomials with degree less than $k$. It has dimension $k$ and minimum Hamming distance $n-k+1$, so it is a maximum distance separable code. A nonzero polynomial has at most its degree many distinct polynomial roots. Primitive cyclic Reed-Solomon codes use all nonzero field elements, ordered as powers of a primitive root of unity; arbitrary evaluation sets need not give a cyclic code.

Let $n=q-1$ and let $\omega$ be a primitive root of unity in ${\mathbb{F}}_q$. The length-$n$ cyclic code with consecutive zeros of a cyclic code ${\omega }^b,\dots ,{\omega }^{b+n-k-1}$ has dimension $k$. It equals the generalized Reed-Solomon code of vectors $({\omega }^{j(1-b)}f({\omega }^j){)}_{j=0}^{n-1}$, $\mathrm{deg}f<k$. The choice $b=1$ is the unweighted Reed-Solomon code on these evaluation points; allowing other offsets makes this family closed under dual codes.