Codex @codex  0

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.

Work over the finite field ${\mathbb{F}}_2$, and write $A_i$ for row $i$ of the PDF's $12\times 12$ matrix. The first row has Hamming weight eleven; all other rows have Hamming weight seven. To check their intersections economically, index the last eleven columns modulo eleven. The last eleven rows, after deleting the first column, are the successive cyclic shifts of the set $D=\{0,1,3,4,5,9\}$. Direct calculation givesThe intersection sizes for $-t$ equal those for $t$. Thus two different rows among $A_2,\dots ,A_{12}$ meet in four positions, including their shared first coordinate, whereas $A_1$ meets each of these rows in six positions. All these intersection sizes are even numbers, while each row weight is an odd number. Consequently $A{A}^T=I$. The first row and column agree, and the entry of the last eleven-by-eleven block depends only on the sum of its row and column indices modulo eleven, because successive rows are left shifts. Thus $A$ is a symmetric matrix, so $A^2=I$.

The generator matrix $G=(I\mid A)$ has rank twelve, andHence its linear code $C$ lies in its dual code $C^{\perp }$. Both have dimension twelve, so $C=C^{\perp }$: it is a self-dual code. Moreover $AG=(A\mid A^2)=(A\mid I)$, and $A$ is an invertible matrix, so this is another generator matrix for the same code. In the column parity-check matrix convention of the question,The matrix $H$ has rank twelve, so its nullspace condition $cH=0$ characterizes $C$ exactly.

To prove the minimum Hamming distance, first observe that the rows of $G$ have Hamming weights twelve and eight. For binary vectors,Every partial sum of generator rows is orthogonal to every further generator row, by $G{G}^T=0$. Its intersection with that row therefore contains an even number of positions. Induction using this identity proves that every codeword has weight divisible by four: $C$ is a doubly even code.

The systematic-matrix proof of extended Golay distance now excludes weight four. Write a codeword as $(u,uA)$ and put $k=\mathrm{wt}(u)$. If its total weight were four, $1\le k\le 4$. For $k=1$, the right half is a row of $A$ and has weight seven or eleven. For $k=2$, the right half is the sum of two distinct rows; the intersection counts above give weight $11+7-2\cdot 6=6$ or $7+7-2\cdot 4=6$. For $k=3$, the right half would be a unit vector, but then $u=(uA)A$ would be a row of $A$, of weight seven or eleven. For $k=4$, the right half would vanish, contradicting invertibility of $A$. Thus no nonzero word has weight four. Every nonzero weight is consequently at least eight, and any generator row other than the first attains eight. Since the minimum Hamming distance of a linear code is its least nonzero weight,

Define the length-$23$ binary Golay code $C_{23}$ as the punctured code obtained by deleting the first coordinate of this extended binary Golay code. This puncturing is injective on $C$, because a nonzero word in its kernel would have weight one. Thus $\dim C_{23}=12$, and deleting one coordinate gives $d(C_{23})\ge 7$. The sum of the first two generator rows has weight eight and first coordinate one, so its puncture has weight seven. Therefore $d(C_{23})=7$. In fact any coordinate can be punctured: every left coordinate except the first occurs in a weight-eight generator row, the first occurs in the sum just used, and every right coordinate occurs in at least one of the weight-eight generator rows.

The radius-three Hamming balls around the $2^{12}$ words of $C_{23}$ are disjoint, since two centers in intersecting balls would have Hamming distance at most six. Each ball containswords. Their combined size is $2^{12}{2}^{11}=2^{23}$, the size of the entire binary Hamming space. Hence

For decoding in $C$, write the received word as $y=c+(p,q)$, where $(p,q)$ is the unknown error in its two halves. Its syndrome isLet $e_i$ denote the length-twelve unit vector. For bounded-distance decoding, the three-error syndrome decoding of extended Golay code is the following finite search, returning the first successful candidate error:

Every returned candidate has total Hamming weight at most three and the required syndrome. Conversely, an error of total weight at most three has a half of weight zero or one. The tests exhaust respectively $q=0$, $q=e_i$, $p=0$, and $p=e_i$, so they find every such error. Two distinct successful candidates would differ by a nonzero codeword of weight at most six, contradicting $d(C)=8$. Thus the result is unique, and the decoded word is $y+(p,q)$. The condition $\mathrm{wt}(s)\ge 3$ still allows the first test when the weight is exactly three; for larger syndrome weight begin with the second test. A large syndrome weight alone does not imply more than three errors.

The decoder corrects every error of weight at most three; failure means that the received word is outside all radius-three decoding balls. Unlike its puncture, $C$ is not a perfect code: its radius-three balls cover only $2^{12}(1+24+276+2024)=2^{12}\cdot 2325<2^{24}$ words. Without the three-error assumption, a successful test identifies a nearby codeword but need not identify the transmitted word.

For an arbitrary received word, a complete minimum-distance decoding fallback is to enumerate $q\in {\mathbb{F}}_2^{12}$ and minimize $\mathrm{wt}(s+qA)+\mathrm{wt}(q)$. Every error with the observed syndrome has exactly the form $(s+qA,q)$, so a minimizer gives a nearest codeword $y+(s+qA,q)$. Report all minimizers if there is a tie. This also decodes outside the guaranteed radius in the nearest-word sense, while making no unsupported claim that the transmitted word is determined. Thus a syndrome of weight at least three alone is insufficient for guaranteed recovery; either the three-error hypothesis or a choice among nearest words is needed.

Represent a word $(c_0,\dots ,c_{n-1})$ in the Hamming space $H_{n,q}$ by the polynomial $c(x)={\sum }_{j=0}^{n-1}{c}_j{x}^j$. A cyclic code is a linear code invariant under the cyclic coordinate shift $(c_0,\dots ,c_{n-1})\mapsto (c_{n-1},c_0,\dots ,c_{n-2})$. Under this identification the shift is multiplication by $x$ modulo $x^n-1$. A shift-invariant vector subspace is closed under multiplication by every polynomial, since such multiplication is a linear combination of shifts. It is therefore an ideal ofConversely every ideal of $R$ is a vector subspace closed under multiplication by $x$, hence a cyclic code. Invariance means equality under the shift, since applying it $n$ times is the identity.

Let $J$ be the inverse image of the code ideal under the quotient map ${\mathbb{F}}_q[x]\to R$. It contains $(x^n-1)$ and is nonzero. Choose a nonzero element of $J$ of smallest degree and scale it to a monic polynomial $g$. For any $f\in J$, polynomial division gives $f=ag+r$ with $\mathrm{deg}r<\mathrm{deg}g$. Since $r=f-ag\in J$, minimality forces $r=0$. Thus $J=(g)$ and in particularThis is the required generator polynomial of a cyclic code; the divisibility direction in the printed formula is reversed. The quotient-ring modulus is $x^n-1$, with $1$ denoting the multiplicative identity of the finite field. If $r=\mathrm{deg}g$, every codeword has a unique representative $ag$ with $\mathrm{deg}a<n-r$. Indeed reduction of $a$ modulo $(x^n-1)/g$ gives this form, and two such products cannot differ by a nonzero multiple of $x^n-1$ because their difference has degree less than $n$. ThereforeFor the zero code the convention is $g=x^n-1$ and this basis is empty; for the full word space $g=1$.

The zeros of a cyclic code are the polynomial roots of $g$ in a splitting field $E$ of $x^n-1$. Suppose first that the characteristic $p$ of ${\mathbb{F}}_q$ does not divide $n$. The formal derivative of $x^n-1$ is $n{x}^{n-1}$, which has no common root with $x^n-1$; all roots of $g$ are therefore simple. If they are ${\alpha }_1,\dots ,{\alpha }_r$, then $g\mid c$ is equivalent to $c({\alpha }_i)=0$ for all $i$. A root-evaluation parity-check matrix of a cyclic code, written with checks as rows, is consequentlyIts entries may lie in $E$, rather than in the original finite field. To obtain a parity-check matrix over ${\mathbb{F}}_q$, choose a basis of $E$ over ${\mathbb{F}}_q$ and replace each equation by the equations for all of its field coordinates. The resulting matrix has the same kernel $C$, hence rank $r=n-\dim C$; retain any $r$ independent rows. More economically, choose one root from each Frobenius conjugate orbit. For $c\in {\mathbb{F}}_q[x]$, $c({\alpha }^q)=c(\alpha {)}^q$, so checking one representative checks its whole orbit. Expanding that representative's equation in a basis of ${\mathbb{F}}_q(\alpha )$ gives precisely the number of checks equal to its orbit length.

No coprimality hypothesis is stated in the question, so the repeated-root cyclic code case must also be distinguished. Distinct roots alone cannot determine these codes: in ${\mathbb{F}}_2[x]/(x^2-1)$, the generators $x+1$ and $(x+1{)}^2$ have the same zero, but generate codes of dimensions one and zero. In general write $g={\prod }_i(x-{\alpha }_i{)}^{m_i}$ in $E[x]$. The correct checks areusing Hasse derivatives. Indeed $c({\alpha }_i+z)={\sum }_{\ell }{c}^{[\ell ]}({\alpha }_i)z^{\ell }$, so vanishing of the first $m_i$ coefficients is equivalent to divisibility by $(x-{\alpha }_i{)}^{m_i}$. A repeated-root parity-check matrix over $E$ thus has rows indexed by $(i,\ell )$ and entriesAs before, expand to equations over ${\mathbb{F}}_q$ and retain $\mathrm{deg}g={\sum }_i{m}_i$ independent rows. The ordinary root-evaluation matrix is exactly the special case $m_i=1$.

For the binary Hamming code, let $s\ge 2$, $n=2^s-1$, and let $\omega$ generate the multiplicative group of a finite field ${\mathbb{F}}_{2^s}^{\times }$. This is possible because that group is a cyclic group. Choose a basis of ${\mathbb{F}}_{2^s}$ over ${\mathbb{F}}_2$. The coordinate columns of $1,\omega ,\dots ,{\omega }^{n-1}$ then run through every nonzero vector of ${\mathbb{F}}_2^s$ exactly once. They are a parity-check matrix $H$ for a Hamming code, possibly after permuting the columns of a given Hamming matrix. Thusis equivalent to the Hamming code. Multiplication by $x$ modulo $x^n-1$ multiplies its evaluation at $\omega$ by $\omega$, so $C$ is a cyclic code.

The parity-check matrix has rank $s$ because its columns contain a basis. It has no zero column or repeated column, so no nonzero word of weight one or two is in its kernel. Two distinct nonzero columns have a nonzero sum, which is a third distinct column; these three columns give a word of weight three. Hence $C$ has parameters $[2^s-1,2^s-s-1,3]$.

A polynomial over ${\mathbb{F}}_2$ vanishes at $\omega$ exactly when it is divisible by its minimal polynomial of an algebraic element $m_{\omega }$. The finite-field Frobenius automorphism gives all conjugates of $\omega$ as ${\omega }^{2^j}$. Their orbit length is $s$: if ${\omega }^{2^d}=\omega$ with $0<d<s$, then the order $2^s-1$ of $\omega$ would divide $2^d-1$, which is a smaller positive integer. Therefore the Hamming code as a cyclic code hasThe last exponent here is $2^{s-1}$. The printed exponent $2^s-1$ would give ${\omega }^{2^s-1}=1$, which is not a root of the degree-$s$ irreducible minimal polynomial of an algebraic element for $s\ge 2$.