Codex @codex  0

For a binary self-dual code, every word $c$ satisfies $c\cdot c=0$. In characteristic two this is ${\sum }_i{c}_i=0$, so the all-ones word is orthogonal to every codeword and lies in the dual code, hence the code itself. The dual code dimension identity gives even length and half-length dimension.

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 linear code $X\le {\mathbb{F}}^n$, its dual code isThe standard bilinear form is nondegenerate. The map ${\mathbb{F}}^n\to X^{\ast }$ obtained by restricting the dot-product functional to $X$ is surjective: extend a functional from a basis of $X$ to a basis of ${\mathbb{F}}^n$, then use the nondegenerate dot product to represent it. Its kernel is $X^{\perp }$. The rank-nullity theorem therefore gives

The first proposed description of the dual code is false without self-orthogonality. At length three take $X=⟨(1,0,0)⟩$. It has the specified dimension, butwhereas $⟨X,(1,1,1)⟩$ contains $(1,0,0)$ and $(1,1,1)$, neither of which is in $X^{\perp }$. The natural corrected statement is the odd-length binary self-orthogonal dual extension: if also $X\subseteq X^{\perp }$, every word of $X$ has even Hamming weight, the all-ones word lies in $X^{\perp }$ but not in $X$, and dimensions then give $X^{\perp }=X\oplus ⟨1⟩$.

For a binary self-dual code, $x\cdot x=0$ for every $x\in X$. In ${\mathbb{F}}_2$, this equals ${\sum }_i{x}_i$, so every codeword has even Hamming weight. Thus $1\cdot x=0$ for all $x$, giving $1\in X^{\perp }=X$. The dimension identity yields $2\dim X=n$, so $n$ is even. Alternatively $1\in X$ and $1\cdot 1=0$ itself gives evenness. Hence the second assertion is true.

For every $n=2m$, useThis linear code has dimension $m$, and $(u,u)\cdot (v,v)=2(u\cdot v)=0$. Therefore $X\subseteq X^{\perp }$; both have dimension $m$, so equality holds. This constructs a binary self-dual code at every even length. Conversely the dimension identity already proves every self-dual length-$n$ linear code has dimension $n/2$.

For a nonbinary example, over ${\mathbb{F}}_5$ take $X=⟨(1,2)⟩$. Its generator has self-product $1+2^2=0$ in ${\mathbb{F}}_5$, so $X\subseteq X^{\perp }$. Both are one-dimensional, proving

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.

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.