Binary inner product Created 2026-09-28 Updated 2026-11-05
For vectors , the binary inner product is the bilinear formIts value is the parity of the coordinates at which both vectors are one. For example, , whereas because in the finite field .
The terminology does not impose the positive definiteness axiom of a real or complex inner product. A nonzero vector can have zero self-pairing, as the second example shows. The form is nevertheless a nondegenerate bilinear form: a nonzero coordinate of is detected by pairing with the corresponding standard basis vector. This pairing defines orthogonality and dual codes in coding theory.
CSS code Created 2026-10-14 Updated 2026-11-05
For binary linear codes , the CSS code has basis for . Its X stabilizers come from and its Z stabilizers from the dual code ; their commutation follows from orthogonality. For positive logical dimension, and , with quantum code distance . Thus arbitrary errors on at most qubits are correctable. Stabilizer errors are harmless even if their weight is small; the distances exclude them.
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.
For and , the two evaluation forms are and , with and . Their dot product is , since every appearing exponent is between one and and the sums of those powers of vanish. Comparing dimensions proves equality with the dual code. In particular, the dual of the unweighted evaluation code has multipliers ; it need not be an unweighted evaluation code on the same ordered points.
Dual of a Reed-Muller code Created 2026-09-24 Updated 2026-11-05
For , the standard binary bilinear form givesIndeed, the product of representing polynomials has polynomial degree at most . Each square-free monomial in that product omits at least one of the variables and therefore takes the value an even number of times on . Summing the product over all evaluation points gives zero in the field with two elements, proving orthogonality. The dimensions of the two Reed-Muller codes add to , by the symmetry , so containment is equality.
At , the Reed-Muller code is the full vector space and its dual code is zero. The same displayed identity holds if denotes the zero code, as in the boundary convention for Reed-Muller codes.
Generalized Reed-Solomon code Created 2026-10-14 Updated 2026-11-05
For , choose distinct evaluation points in a finite field and nonzero coordinate multipliers . The generalized Reed-Solomon code isMultiplying coordinates by nonzero field elements preserves Hamming weight, so this is a linear code with parameters , just as for a Reed-Solomon code. In particular it is a maximum distance separable code.
Its dual code is , where one may takeA common nonzero multiplier on all gives the same dual code. For the dual code is the zero code, interpreted as having no nonzero evaluation polynomials.
Hamming code weight enumerator 2026-10-14
Here , and the weight enumerator convention is . The dual code is the binary simplex code, with enumerator . The MacWilliams identity gives the formula. For , the ordinary enumerator is ; for , the degenerate one-word code has enumerator .
MacWilliams identity 2026-10-05
For a binary linear code of dimension and its dual code, the weight enumerator convention givesTo prove it, insert into the enumerator sum. Summing independently over each coordinate of yields a factor if and if .
Nested-code CSS syndrome recovery 2026-10-14
For binary linear codes , the coset superpositions of the CSS code have checks labelled by and checks by . A bit-error pattern gives the classical syndrome for , and a phase-error pattern gives the syndrome for the dual code . Errors with and are jointly correctable. Every pairwise Pauli-error product either anticommutes with a check, giving zero code compression, or its low-weight components belong to the stabilizer and give scalar compression. Thus the Knill--Laflamme condition covers coherent superpositions and quantum channels as well as definite bit and phase errors.
Write the Steane code basis as uniform quantum superpositions over a binary linear code and a disjoint coset , where is the even-weight part of the length-seven Hamming code. For , diagonal Pauli Z gates cannot connect the two cosets. Within coset , the overlap isIf , translation by a word with negates this sum, so it vanishes. Since the dual code is the length-seven Hamming code of minimum Hamming distance three, every nonzero of Hamming weight one or two has vanishing overlap. Taking from proves the displayed identity. The eight two-dimensional error images are orthogonal, so their projective measurement determines the error syndrome without revealing the logical state; applying the identified phase flip again recovers every code state. This proves nondegenerate quantum error-correcting code behaviour for the identity and all single-site phase flips, including their coherent linear span.
If a self-orthogonal binary subspace has odd length and dimension , its dual code is obtained by adjoining the all-ones word. Self-orthogonality makes every codeword even-weight, so but . Comparing dimensions proves the formula. The dimension hypothesis alone is insufficient: at length three is a counterexample.
Parity-check matrix Created 2026-09-24 Updated 2026-11-05
Past exam of the mathematics course of the University of Cambridge 2001 iii Paper 25 1 Solution Created 2026-10-03 Updated 2026-10-14
Use binary linear codes , with dimensions . For each coset in , defineRepresentatives of one coset give the same vector, and distinct cosets have disjoint computational supports, so these vectors are orthonormal. Their span is the CSS code , encoding .
For , write and . The code is stabilized by for , because it permutes the sum, and by for , because . These Pauli operators commute: . There are independent stabilizer generators, so their common positive eigenspace has dimension ; it is exactly the span above.
The commuting check measurements separate the two types of error. A bit error changes the signs of the checks by , giving the ordinary syndrome of for . A phase error changes the checks by , giving the syndrome of for the dual code . If corrects bit errors and corrects bit errors, these checks identify the respective patterns, and inverse Pauli operations recover the state without revealing the logical coset. This is the nested-code CSS syndrome recovery procedure.
The sharper distances account for harmless stabilizer errors. A Pauli commutes with every check precisely when and . Among these, it acts as a stabilizer, up to a phase, precisely when and . To justify the latter assertion, with permutes distinct logical cosets, while with has unequal signs on two such cosets. Neither can act as a scalar, and a combined operator has the same nontrivial permutation or phase distinction. For positive logical dimension setThe quantum code distance is : a nontrivial logical Pauli has at least one nonstabilizer component of weight at least the corresponding distance, while a pure or pure logical operator attains the minimum. The weight of counts the union of its supports, so this argument also includes errors.
Here is the correction proof for coherent errors, not only a classical decoding argument. Let be the code projector and let have bit-component weights at most and phase-component weights at most . If and , the corresponding components of have weights below . If this product anticommutes with a stabilizer , then , using . If it commutes with all stabilizers, the weight bounds force its two components into and , so its code compression is a scalar multiple of . Thus the Knill--Laflamme condition holds for the entire error family.
To see directly why this gives a common recovery, diagonalize its positive Gram matrix and form the corresponding error combinations . Their restrictions obey . For , is an isometry onto a syndrome subspace, and the different images are orthogonal. Measure these subspaces and apply the inverse isometry; zero- combinations annihilate the code. This recovers every quantum channel whose Kraus operators lie in the error span. Arbitrary operators supported on at most qubits expand in Pauli operators with the same support. Consequently the CSS code corrects all errors on up to qubits, and more generally the asymmetric family just described. The sufficient classical bound is obtained by replacing by the minimum distances of and , respectively; degeneracy can improve it.
Past exam of the mathematics course of the University of Cambridge 2002 iii Paper 30 1 Solution Created 2026-10-03 Updated 2026-10-14
Let be distinct elements of a finite field , with . The Reed-Solomon code consists of the evaluation vectorsEvaluation is an injective linear map: a nonzero polynomial of degree at most cannot vanish at all distinct points. Thus the dimension is . The same bound on polynomial roots shows that every nonzero codeword has Hamming weight at least . Conversely, choosing any evaluation points and taking their product of linear factors gives a polynomial whose evaluation vanishes at exactly those points. Its Hamming weight is . HenceFor completeness, deleting coordinates from a linear code of minimum Hamming distance is injective on codewords, since two words with the same retained coordinates would differ in fewer than positions. Therefore , giving the Singleton bound . The Reed-Solomon code attains this bound and is a maximum distance separable code. Multiplying individual coordinates by nonzero field elements changes neither the dimension nor the Hamming weight, so the same proof applies to a generalized Reed-Solomon code.
To specify the generator polynomials of a cyclic code unambiguously, use the primitive cyclic Reed-Solomon code convention. Put , choose a primitive element of a finite field , and setExponents are taken modulo . This generator polynomial is a monic polynomial of degree dividing , so the dimension is . It agrees with the evaluation formIndeed, at a defining exponent , a monomial contributes the finite geometric series . Its exponent lies between and , so the sum vanishes: but its th power is one. Every displayed evaluation vector therefore lies in the cyclic code, and both spaces have dimension , proving equality. The narrow-sense choice is the ordinary unweighted evaluation linear code on all nonzero field elements.
The duality of primitive cyclic Reed-Solomon codes now follows directly. A vector in has coordinates , while a vector in has coordinates , with . Their dot product is . Every appearing exponent is between and , so every such finite geometric series is zero. The two spaces are orthogonal and their dimensions sum to , givingThus the full cyclic family is closed under dual codes. The offset matters: the dual code of the narrow-sense linear code generally has offset zero, rather than one.
For arbitrary evaluation points, the precise statement is closure of generalized Reed-Solomon codes under duality. If , put and . Lagrange interpolation shows whenever : this sum is the coefficient of in the interpolation formula for . Taking with and proves orthogonality of and . Comparing dimensions gives equality with . An unweighted evaluation linear code at arbitrary points need not have an unweighted evaluation dual at the same points; the multiplier form and the cyclic offset formula resolve that convention issue.
For the length-, dimension- linear code, choose and as in the field table. Then andThe field characteristic is two, and the table gives . In the basis , the four roots are represented by . Their elementary symmetric functions areThe repeated terms in cancel because the field characteristic is two. There are no alternating minus signs in this characteristic, soFor example, the coefficient vectors in ascending order are , giving the required single powers of .
For the length-, dimension- linear code over , take the table's primitive element of a finite field and again . The four roots are . Expanding in givesThusThe coefficients are reduced modulo , including the constant term .
A suitable two-error-correcting Reed-Solomon code over is precisely the first linear code:Two distinct codewords cannot both be within Hamming distance two of a received word, because the triangle inequality would put them at distance at most four. Thus this linear code corrects any two symbol errors. Its generator polynomial has four consecutive defining zeros of a cyclic code, and its dimension and exact minimum Hamming distance have already been proved.
Past exam of the mathematics course of the University of Cambridge 2002 iii Paper 30 2 Solution Created 2026-10-03 Updated 2026-10-14
For a binary linear code , define the linear functional . This is the parity of the Hamming weight, so the even-weight subcode of a binary linear code isIf , then . Otherwise its image is all of , and rank-nullity theorem gives . The kernel of a linear map is a linear subspace, proving the required dichotomy including closure under addition.
Let be a full-rank generator matrix. Messages correspond bijectively to codewords . If the th column is nonzero, the coordinate is a nonzero linear functional. Choose with . Translation pairs the messages with coordinate zero and those with coordinate one, so exactly codewords contribute one at position . Summing over the columns proves the total weight of a full-support binary linear code formulaA zero column would contribute zero instead, explaining the hypothesis.
For the Hamming code, use a parity-check matrix whose columns are all nonzero vectors of , once each. Then and . The sum of all columns is zero: each coordinate occurs as one exactly times, which is even for . ConsequentlyUnder this column labelling, the support of a vector of a codeword is identified with a set of distinct nonzero columns whose sum is zero. No one-column or two-column support of a vector has this property, confirming .
We can count the low-weight coefficients of a binary Hamming code directly. For weight three, choose ordered distinct nonzero columns in ways. The third must be , which is nonzero and different from both. Every unordered support of a vector has orderings, so .
For weight four, the first two columns are again distinct and nonzero. The third must avoid , giving possibilities. The fourth is ; it is nonzero because , and cannot equal any of the first three because those are distinct. Conversely every ordered zero-sum four-tuple arises in this way. Dividing by gives .
For weight five, the first three columns must be linearly independent. If , the sum condition would force the fourth and fifth to coincide. Thus there are choices for the first three. Put . The fourth column must avoid all seven nonzero vectors of their linear span: would repeat a column; would force the fifth column to be zero; and would force the fifth column to be , respectively. Conversely, if avoids these seven vectors, is nonzero and distinct from . This gives choices for and determines . Dividing by yieldsAt , the last count is zero, as the argument also shows.
The dual code is the row space of , so its codewords are for . For nonzero , the linear functional takes value one on exactly half the vectors of , by the same translation-pairing argument used above. Removing the zero vector removes only a zero value, so the Hamming weight is still . Since has matrix rank , distinct give distinct codewords. This proves the constant weight of a binary simplex code and its full distribution:In particular, the ordinary weight enumerator of the binary simplex code is .
Apply the MacWilliams identity to this dual code, whose size is . For , the result isThe coefficient of in the second product is a value of the binary Kravchuk polynomialsThese bounds merely enforce and . Since , they agree with the bounds in the PDF. Therefore the requested formula isFor a further check on the low-weight counts, givesThus , , and . Substituting these into the boxed formula and using reproduces the three direct combinatorial counts above.
Finally, at the only possible term in the defining sum has , so , because is even. ConsequentlyThe unique length- binary word of weight is the all-ones word, exactly as proved by the parity-check matrix calculation.
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 36 1 Solution Created 2026-10-03 Updated 2026-10-14
For a linear code , its dual code isThe standard bilinear form is nondegenerate. The map obtained by restricting the dot-product functional to is surjective: extend a functional from a basis of to a basis of , then use the nondegenerate dot product to represent it. Its kernel is . The rank-nullity theorem therefore gives
The first proposed description of the dual code is false without self-orthogonality. At length three take . It has the specified dimension, butwhereas contains and , neither of which is in . The natural corrected statement is the odd-length binary self-orthogonal dual extension: if also , every word of has even Hamming weight, the all-ones word lies in but not in , and dimensions then give .
For a binary self-dual code, for every . In , this equals , so every codeword has even Hamming weight. Thus for all , giving . The dimension identity yields , so is even. Alternatively and itself gives evenness. Hence the second assertion is true.
For every , useThis linear code has dimension , and . Therefore ; both have dimension , so equality holds. This constructs a binary self-dual code at every even length. Conversely the dimension identity already proves every self-dual length- linear code has dimension .
Past exam of the mathematics course of the University of Cambridge 2004 iii Paper 32 1 Solution Created 2026-10-03 Updated 2026-10-14
Over a finite field , a linear code of length and dimension is a -dimensional subspace . A full-row-rank generator matrix gives , using row-vector messages. A full-row-rank parity-check matrix gives . The dual code is , of dimension . Thus the rows of span , andConversely the rank conditions and imply that the row space of equals the kernel of , by inclusion and equality of dimensions.
For a CSS code, specialize to binary linear codes , of dimensions . Define orthonormal encoded statesDifferent cosets have disjoint computational-basis support. Their span has dimension , so it encodes logical qubits. For binary vectors write and . The stabilizer generators are for a basis of , and for a basis of . They fix each encoded state: the former permute its coset terms and the latter contribute phases . Their commutation relation is , so the classical dual inclusion makes them commute. There are independent checks, giving precisely this encoded space.
For a Pauli error , the Z checks give bit-error syndrome , where checks , and the X checks give phase-error syndrome , where generates and hence checks . Classical decoders therefore correct up to bit flips and phase flips if and . A Y error has both components; it is not omitted from this correction scheme.
For the precise quantum code distance, harmless stabilizer errors must be excluded. A pure-X error preserves the code exactly when , and is a stabilizer when ; a pure-Z error preserves it when , and is a stabilizer when . Consequently, for ,A mixed Pauli error has weight equal to the size of the union of its X and Z supports. If it is a nontrivial logical operator, at least one component is nontrivial, so its weight is at least ; pure-X or pure-Z operators attain that minimum. Thus arbitrary-qubit errors are correctable: products of two such Pauli errors have weight below and act scalarly on the code, or take it to an orthogonal syndrome sector. This is the Knill--Laflamme condition. Expanding arbitrary errors in the Pauli basis extends correction to their coherent linear span.
An explicit example is the Steane code. Take to be the binary Hamming code withThe distinct nonzero columns show that has no weight-one or weight-two word, while three dependent columns give a weight-three word. Hence its classical distance is three. Direct multiplication gives , proving . Every nonzero word of has weight four, so the logical X and Z distances are both three. Its six stabilizer checks are the X and Z strings given by the three rows of . A logical basis is the uniform superposition over and over , since . The resulting CSS code corrects every single-qubit error.
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 33 3 Solution Created 2026-10-03 Updated 2026-10-14
A binary block code of length is a nonempty subset . Its size is , the number of distinct codewords. The Hamming distance counts coordinates at which two words differ. The code's minimum Hamming distance is when there are at least two words. No pairwise minimum exists for a singleton code; it can be assigned as a convention when needed.
A binary linear code is a vector subspace of . If its dimension is , a generator matrix has a basis of as its rows, givingTo match the coordinate-row convention, take a parity-check matrix of size , with independent columns, and defineThe transpose is the usual parity-check matrix with one column per coordinate. By rank-nullity theorem, the displayed kernel has dimension . The two constructions agree when : the generator's row space lies in the parity-check kernel and has the same dimension, hence equals it. Conversely, for a given , choose the columns of as a basis of its dual code ; orthogonality and the dimension formula give exactly as the kernel.
For a nonzero linear code, is a nonzero codeword whenever are distinct codewords, and . Conversely compare any nonzero codeword with zero. Thus the minimum Hamming distance of a linear code is the least nonzero Hamming weight.
Write for the row associated with coordinate . A nonzero binary vector is a codeword exactly whenIts nonzero coordinate positions therefore index a linearly dependent set of rows. Conversely, a dependence among a set of rows has coefficients in , not all zero; putting these coefficients in the corresponding coordinates gives a nonzero codeword of weight no greater than the number of rows in that set. Taking minima in both directions proves the parity-check dependencies determine minimum distance criterion:Rows here are indexed by positions: equal row vectors at different positions are two distinct members of the indexed family. In the usual matrix convention, the same result refers to columns of . For the zero code, neither a nonzero codeword nor a dependent coordinate set exists, so both minima can consistently be interpreted as .
For the Hamming code, let , set , and let the rows of be all nonzero vectors of , each once. These rows include the standard basis, so has rank and the code has dimension and size . There is no dependence involving one row, because no row is zero, or two rows, because no rows are equal. For , any two distinct nonzero vectors have a distinct nonzero sum , which is another row. These three rows sum to zero. Thus for .
The perfectness of a Hamming code also has a direct decoding proof. Given any received word , its syndrome is . A zero syndrome means . Otherwise it equals exactly one row . The vector then has syndrome zero and is the unique codeword obtainable by changing one coordinate. There is no other codeword at distance at most one: its necessary correction would have to have the same syndrome, and among zero and all single-coordinate errors the syndromes are precisely the distinct vectors of . Therefore the radius-one Hamming balls about codewords partition .
Equivalently, each ball contains words; disjointness and show that none are uncovered. Hence every nondegenerate binary Hamming code is a perfect single-error-correcting code. For , the construction is the singleton code , whose one radius-one ball is also the whole ambient space. This deals with the degenerate boundary without falsely claiming its minimum distance is three.
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 33 4 b Solution Created 2026-10-03 Updated 2026-10-14
Use the homogeneous weight enumerator conventionThus records ones, records zeros, and the ordinary weight enumerator is . For a binary linear code of dimension and its dual code , the MacWilliams identity isor, equivalently, . The second form applies the first to the dual and uses .
One can verify the variable order directly from the character identity . If is not orthogonal to , translation by a codeword having odd inner product pairs positive and negative terms, giving zero; otherwise all terms are one. After multiplying by and summing over , coordinate contributes when , and when . Their product is exactly the stated substitution.
For a Hamming code with , its dual is the binary simplex code, generated by the rows of the usual parity-check matrix . There are dual words. A nonzero message produces the evaluations as runs over all nonzero vectors of . Exactly of them are one: the nonzero linear functional takes each value equally often on the whole vector space, and removing zero removes a zero value only. This proves the constant weight of a binary simplex code.
Put , so . The dual enumerator is therefore . Applying the MacWilliams identity gives the Hamming code weight enumeratorIn one variable this isFor example, gives ; gives . For , the expression is , agreeing with the singleton code. Setting in the homogeneous formula gives , the correct number of codewords.