Coding theory Created 2026-09-24 Updated 2026-10-18
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 as and as . If the receiver sees , at most one bit flip is consistent with , whereas two flips would be needed to obtain it from . 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]
https://zoo.cs.yale.edu/classes/cs323/doc/Hamming.pdf. Hamming, Error Detecting and Error Correcting Codes, 1950
Dual code Created 2026-09-24 Updated 2026-11-05
For a linear code , the dual code is the orthogonal complementunder the standard bilinear bilinear form. If has dimension , the dual code has dimension and , because this bilinear form is nondegenerate.
The independent rows of a parity-check matrix for form a basis of , so that matrix is a generator matrix for the dual code. If a check matrix has redundant rows, its rows still span the dual code but are not themselves a basis. For example, the dual code of the length- binary even-weight binary code is the repetition code spanned by the all-one word.
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 31 4 Solution Created 2026-10-03 Updated 2026-10-14
Use binary codes, so the polynomial modulus is in . A cyclic code is a linear subspace of invariant under the cyclic shift . Identify a word with . Addition is coefficientwise, and multiplication is polynomial multiplication reduced modulo . In the quotient ringmultiplication by is exactly that cyclic shift. Closure under this map and linear combinations gives closure under multiplication by every polynomial, so a cyclic code is an ideal of . Conversely, an ideal is a linear subspace closed under multiplication by , proving the correspondence.
Take the inverse image of in . This is an ideal containing . The polynomial division algorithm shows directly that it has a unique monic generator : choose a nonzero polynomial of least polynomial degree and divide any other member by it; the remainder is in the ideal and has smaller polynomial degree, so must vanish. If two monic generators existed, mutual divisibility would make them equal. Because belongs to the ideal, . Conversely every monic divisor of defines an ideal of . Thus the generator polynomial of a cyclic code satisfiesFor a nonzero code, is its nonzero polynomial representative of least polynomial degree. For the zero code, use , whose residue in is zero; this standard convention covers that endpoint despite its having no nonzero codeword.
Let and , and put . Every codeword has a unique representation with : dividing an arbitrary multiplier by does not change its product with modulo . The words have distinct leading degrees below and are independent. ConsequentlyThe statement remains valid for the zero code, with an empty basis, and the full code, with .
For length 16, characteristic two gives . Its only monic divisors are for . Hence all binary cyclic codes of length a power of two in this case areThere are exactly 17 codes, forming the chain . This is a repeated-root cyclic code situation, so it would be incorrect to count just square-free factors. Their canonical check polynomials of a cyclic code are . An explicit expansion of each generator is .
The canonical check polynomial of a cyclic code isIndeed means . Since , cancellation in the polynomial ring gives , exactly code membership. No coprimality of and is needed, including for length 16.
There is a normalization qualification in the printed definition. The kernel condition alone does not force the supplied polynomial to equal this canonical . If , write and with . Then holds exactly when , so its kernel is the ideal generated by . ThereforeEquivalently with . Requiring the monic divisor of selects the canonical check polynomial of a cyclic code. For example gives the same kernel as , since is a unit modulo , but is generally a different polynomial. Given any permitted , taking recovers the canonical .
To construct a parity-check matrix, write the canonical and its reciprocal polynomial . Take coefficient vectors, padded to length , ofas the rows of . Here because , so these rows have successive leading degrees and are independent. For a word , row has dot product , the coefficient of in the ordinary product . If , then with . This product has no terms in degrees , so . The kernel of has dimension , the same as , proving . This proves the reciprocal-polynomial parity-check matrix construction and identifies its rows as a basis for the dual of a cyclic code.
Alternatively, a supplied check polynomial of a cyclic code reduced modulo , , gives the polynomial multiplication parity-check matrixThis circulant matrix represents multiplication by modulo , so its kernel is and its matrix rank is . Selecting independent rows yields a rank- parity-check matrix even without initially normalizing the supplied polynomial.
The syndrome labels the coset . Indeed if and only if , equivalently . There are cosets, each with words, and the syndrome classification of code cosets gives a bijection between them and . If is a transmitted codeword plus an error, then : the syndrome determines the error coset. Choosing a minimum-weight coset leader and subtracting it performs minimum-distance decoding. The error itself need not be uniquely identified, but it is unique when its weight is at most , since the corresponding error-correction balls are disjoint.
For the repetition code, the nonzero codeword is the all-ones word, soTheir product is , and the generator polynomial degree gives dimension one. For the single parity-check code, membership is , equivalent to divisibility by . ThusIts dimension is ; it is the even-weight code.
Finally, factor the binary length-seven modulus:A standard cyclic realization of the Hamming code of length seven usesIts dimension is four. The reciprocal-check construction givesIts columns are exactly the seven distinct nonzero vectors of , so no word of weight one or two is in its kernel. The generator itself has weight three, so the minimum Hamming distance is exactly three; this is the Hamming code. Reversing the cyclic coordinate order gives the equally valid reciprocal choiceThe polynomial answer therefore depends on the cyclic coordinate convention, while the resulting codes are equivalent.
Past exam of the mathematics course of the University of Cambridge 2011 ii Paper 3 4G Solution Created 2026-09-24 Updated 2026-10-14
For a binary linear code , its rank is its dimension of a vector space . Use the weight enumerator conventionwhere is the Hamming weight. This convention is essential here: counts words of weight , rather than zero words. There are codewords, so .
There is only one binary word of weight , namely . Thus precisely when . If this holds, the linear map is a bijection of and replaces weight by ; hence . Conversely this symmetry gives , because the zero word is the unique word of weight zero.
The repetition code consists of , givingThe single parity-check code consists of all words of even weight. Exactly words have weight , so the binomial theorem gives
Past exam of the mathematics course of the University of Cambridge 2015 ii Paper 4 3G Solution Created 2026-09-24 Updated 2026-10-06
Work over the finite field . Reduce polynomials modulo , so their monomials are square-free. The binary Reed-Muller code consists of the evaluation vectors of polynomials of degree at most at all points of , in a fixed order. This is a linear code of length and dimension , for . Square-free monomials give independent evaluation functions, as follows inductively by splitting according to the last variable.
The minimum Hamming distance of a linear code equals its least nonzero Hamming weight. The result isHere is the repetition code, while is the full binary vector space and has distance one. For the induction step, write , where and . Its evaluation vector is , the Reed-Muller bar-product recursion. If , its nonzero Hamming weight is at least , with the full-space endpoint treated as above. If , every position where contributes exactly one to the sum of the two weights; hence the weight is at least . The monomial is one exactly on points, attaining the bound. Degrees greater than give the same full code; the zero code at negative degree has no nonzero word whose weight could define a finite minimum.
Past exam of the mathematics course of the University of Cambridge 2018 ii Paper 2 3H Solution Created 2026-09-24 Updated 2026-10-03
The binary symmetric channel with crossover probability has channel matrixMaximum-likelihood decoding chooses a codeword maximizing , while minimum-distance decoding chooses one minimizing the Hamming distance . For a block of length sent through a binary symmetric channel,When , the final factor decreases strictly with the distance. Thus maximum-likelihood and minimum-distance decoding agree.
For the length-three repetition code , majority decoding is wrong exactly when at least two bits flip. Therefore
Reed-Muller code Created 2026-09-24 Updated 2026-11-05
For integers and , the binary Reed-Muller code evaluates polynomials of total polynomial degree at most on all points of . Evaluation allows every polynomial to be replaced by a square-free one, using on the field with two elements. Its parameters areThe dimension counts the independent square-free monomials of polynomial degree at most . The minimum Hamming distance follows inductively from the decomposition , with and . A product of coordinate variables attains weight .
For boundary conventions, put when , and when . The displayed parameter formula is asserted for ; in particular is a repetition code.
Unique decoding 2026-11-05
Unique decoding recovers a single codeword from a corrupted received word, with a guarantee that the transmitted codeword is the only candidate within the allowed error radius. If a block code has minimum distance , then every pattern of at mostsymbol errors can be corrected in principle. Indeed, if two codewords were both within Hamming distance of , the triangle inequality would put them at distance at most , a contradiction.[ref]
Bridging Shannon and Hamming: List Error-Correction with Optimal Rate by Venkatesan Guruswami. section 1, minimum-distance barrier
The repetition code has , so one error is correctable: identifies . Two errors can produce , which lies closer to ; no decoder can guarantee success for all two-error patterns. The distance bound proves uniqueness, but does not itself give a fast decoding algorithm.