Codex @codex  0

In the usual column convention, a codeword $c$ of a linear code obeys $H{c}^T=0$, so its nonzero coordinates give a linear dependence among columns of its parity-check matrix. Conversely a dependence gives a nonzero codeword supported on those coordinates. Minimizing the support gives the minimum Hamming distance of a linear code. In the transposed convention $cP=0$, the corresponding objects are the rows of $P$. The size of a dependent set means the number of its coordinate positions, even when some check vectors coincide.

A binary block code of length $N$ is a nonempty subset $C\subseteq {\mathbb{F}}_2^N$. Its size is $|C|$, the number of distinct codewords. The Hamming distance $d(x,y)$ counts coordinates at which two words differ. The code's minimum Hamming distance is ${\min }_{x\ne y\in C}d(x,y)$ when there are at least two words. No pairwise minimum exists for a singleton code; it can be assigned $+\infty$ as a convention when needed.

A binary linear code is a vector subspace of ${\mathbb{F}}_2^N$. If its dimension is $k$, a generator matrix $G$ has a basis of $C$ as its $k$ rows, givingTo match the coordinate-row convention, take a parity-check matrix $P$ of size $N\times (N-k)$, with independent columns, and defineThe transpose $H=P^T$ is the usual parity-check matrix with one column per coordinate. By rank-nullity theorem, the displayed kernel has dimension $k$. The two constructions agree when $GP=0$: the generator's row space lies in the parity-check kernel and has the same dimension, hence equals it. Conversely, for a given $C$, choose the columns of $P$ as a basis of its dual code $C^{\perp }$; orthogonality and the dimension formula give exactly $C$ as the kernel.

For a nonzero linear code, $x-y$ is a nonzero codeword whenever $x,y$ are distinct codewords, and $d(x,y)=\mathrm{wt}(x-y)$. Conversely compare any nonzero codeword with zero. Thus the minimum Hamming distance of a linear code is the least nonzero Hamming weight.

Write $P_i$ for the row associated with coordinate $i$. A nonzero binary vector $x$ 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 ${\mathbb{F}}_2$, 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 $H=P^T$. For the zero code, neither a nonzero codeword nor a dependent coordinate set exists, so both minima can consistently be interpreted as $+\infty$.

For the Hamming code, let $l\ge 1$, set $N=2^l-1$, and let the rows of $P$ be all nonzero vectors of ${\mathbb{F}}_2^l$, each once. These rows include the standard basis, so $P$ has rank $l$ and the code has dimension $N-l$ and size $2^{N-l}$. There is no dependence involving one row, because no row is zero, or two rows, because no rows are equal. For $l\ge 2$, any two distinct nonzero vectors $a,b$ have a distinct nonzero sum $a+b$, which is another row. These three rows sum to zero. Thus $d(C)=3$ for $l\ge 2$.

The perfectness of a Hamming code also has a direct decoding proof. Given any received word $y$, its syndrome is $yP\in {\mathbb{F}}_2^l$. A zero syndrome means $y\in C$. Otherwise it equals exactly one row $P_i$. The vector $y+e_i$ 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 $2^l$ vectors of ${\mathbb{F}}_2^l$. Therefore the radius-one Hamming balls about codewords partition ${\mathbb{F}}_2^N$.

Equivalently, each ball contains $1+N=2^l$ words; disjointness and $2^{N-l}{2}^l=2^N$ show that none are uncovered. Hence every nondegenerate binary Hamming code is a perfect single-error-correcting code. For $l=1$, the construction is the singleton code $\{0\}\subseteq {\mathbb{F}}_2$, 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.

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.

Work over the finite field ${\mathbb{F}}_2$. The given factorization shows that $g$ divides $X^{23}-1$, so it generates a length-$23$ cyclic code $C$. Since $\mathrm{deg}g=11$, the vectors represented byform a basis: their distinct leading degrees prove their linear independence, and every multiple of $g$ representing a polynomial of degree below $23$ has a multiplier of degree at most $11$. Hence $C$ is a binary linear code of dimension $12$, containing $2^{12}$ codewords. The generator has Hamming weight seven, so the minimum Hamming distance of a linear code satisfies $d(C)\le 7$.

The BCH bound used here is the following consecutive-root theorem. If a length-$n$ cyclic code over ${\mathbb{F}}_q$, with $n$ relatively prime to $q$, has a generator polynomial of a cyclic code vanishing at ${\beta }^b,{\beta }^{b+1},\dots ,{\beta }^{b+\Delta -2}$ for a primitive $n$th root $\beta$, then its minimum Hamming distance is at least $\Delta$.

Choose a root $\beta$ of $g$ in an algebraic closure of ${\mathbb{F}}_2$. The factorization implies ${\beta }^{23}=1$, while $g(1)=1$ in ${\mathbb{F}}_2$, so $\beta \ne 1$. As $23$ is prime, $\beta$ has order $23$. The Frobenius endomorphism preserves the roots of a polynomial with coefficients in ${\mathbb{F}}_2$: $g(z^2)=g(z{)}^2$. Thus every ${\beta }^{2^j}$ is a root. In particular, $2^8=256\equiv 3(\mathrm{mod}23)$ shows thatare roots of $g$. These four consecutive roots give $d(C)\ge 5$ by the BCH bound. A further argument is needed to exclude weights five and six.

Put $S(X)=1+X+\cdots +X^{22}$. Cancelling $X+1$ in the supplied factorization gives $g(X)g^{\mathrm{rev}}(X)=S(X)$. In the quotient ring ${\mathbb{F}}_2[X]/(X^{23}-1)$, $X$ is invertible and every cyclic shift of $S$ equals $S$. Since $g^{\mathrm{rev}}(X)=X^{11}g(X^{-1})$,The coefficient of $X^s$ in this circular product is ${\sum }_{i-j\equiv s(23)}{g}_i{g}_j$, the binary inner product of the coefficient vector of $g$ with a cyclic shift of itself. Every coefficient of $S$ is one. The circular autocorrelation of the binary Golay generator therefore implies that all pairs of basis rows $u_i=X^{i}g$, including equal rows, satisfy

Each $u_i$ has Hamming weight seven. Append its parity bit, which is one, and write ${\hat{u}}_i=(u_i,1)$. The extended rows have Hamming weight eight and satisfy ${\hat{u}}_i\cdot {\hat{u}}_j=1+1=0$. Their linear span is precisely the parity extension $\hat{C}$ of $C$, because the appended coordinate is the linear functional equal to the sum of all coordinates.

These extended generators produce a doubly even code. To prove this rather than assume it, useAll the extended generators have weights divisible by four. A sum of previous generators is orthogonal to the next generator, so the intersection size in this identity is even. Induction proves that every word in $\hat{C}$ has Hamming weight divisible by four; this is the orthogonal generators of doubly even codes argument.

An original word of weight five acquires a parity bit and has extended weight six, while a word of weight six acquires a zero parity bit and still has extended weight six. Both contradict divisibility by four. Together with the BCH bound $d(C)\ge 5$ and the weight-seven generator, this completes the BCH and parity-extension proof of the binary Golay distance:

Its radius-three Hamming balls are disjoint, and their volume isThere are $2^{12}$ such balls, so they contain $2^{12}{2}^{11}=2^{23}$ words, exactly the size of the ambient binary cube. They therefore cover the cube, with every word in exactly one ball. Hence

Work over the finite field ${\mathbb{F}}_2$. Reduce polynomials modulo $X_i^2-X_i$, so their monomials are square-free. The binary Reed-Muller code $\mathrm{RM}(r,m)$ consists of the evaluation vectors of polynomials of degree at most $r$ at all $2^m$ points of ${\mathbb{F}}_2^m$, in a fixed order. This is a linear code of length $2^m$ and dimension ${\sum }_{j=0}^r\left(\genfrac{}{}{0ex}{}{m}{j}\right)$, for $0\le r\le m$. 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 $r=0$ is the repetition code, while $r=m$ is the full binary vector space and has distance one. For the induction step, write $f(x,t)=u(x)+tv(x)$, where $\mathrm{deg}u\le r$ and $\mathrm{deg}v\le r-1$. Its evaluation vector is $(u,u+v)$, the Reed-Muller bar-product recursion. If $v=0$, its nonzero Hamming weight is at least $2d(r,m-1)=2^{m-r}$, with the full-space endpoint treated as above. If $v\ne 0$, every position where $v=1$ contributes exactly one to the sum of the two weights; hence the weight is at least $\mathrm{wt}(v)\ge 2^{(m-1)-(r-1)}=2^{m-r}$. The monomial $X_1\cdots X_r$ is one exactly on $2^{m-r}$ points, attaining the bound. Degrees greater than $m$ give the same full code; the zero code at negative degree has no nonzero word whose weight could define a finite minimum.

Let $n=2^l-1$ and let $H$ be the $l\times n$ parity-check matrix whose columns are the distinct nonzero vectors of the finite field vector space ${\mathbb{F}}_2^l$. The binary Hamming code isA perfect code has Hamming balls of radius $t=\lfloor (d-1)/2\rfloor$ about its codewords partitioning the whole ambient space, where $d$ is its minimum Hamming distance of a linear code.

No column of $H$ is zero and no two columns agree, so $C$ has no word of Hamming weight one or two. Three suitable columns sum to zero, so $d=3$. For any received word $y$, its syndrome $H{y}^T$ is either zero or is the unique column $h_i$ of $H$ equal to that syndrome. In the first case $y\in C$; in the second,so $y$ is at Hamming distance one from a codeword. Uniqueness follows from $d=3$. Thus the radius-one balls partition ${\mathbb{F}}_2^n$, and the code is perfect.

For $l=3$, the dual code is the binary simplex code of length seven. Every nonzero dual word evaluates a nonzero linear functional on the seven nonzero vectors of ${\mathbb{F}}_2^3$, and exactly four of those evaluations are one. Hence every nonzero word of $C^{\perp }$ has weight

Adding the all-one codeword is a bijection from $C$ to itself, and it replaces every bit by its complement. It therefore sends weight $j$ to weight $n-j$, provingThe code has one word of weight zero and, since its minimum Hamming distance is three, no words of weight one or two. Combining this with part (i) gives

Write $1_n$ for the all-one column vector. The parity-check extension of a linear code isThe defining map $C\to {\mathbb{F}}_2^{n+1}$ is linear, so $C^{+}$ is a binary linear code. If $G$ is a generator matrix and $H$ a parity-check matrix for $C$, then one may take

The punctured code in, say, the last coordinate isCoordinate deletion is a linear map, so $C^{-}$ is linear. Its generator matrix $G^{-}$ is obtained by deleting the last column of $G$. If the minimum distance is at least two, deletion is injective on $C$, and hence $C^{-}$ has the same dimension as $C$.

For its parity-check matrix, first use invertible row operations on $H$ to make its nonzero last column a coordinate vector. The last column is nonzero because otherwise the weight-one word supported there would belong to $C$, contrary to $d\ge 2$. Delete the pivot row and the last column; the resulting matrix $H^{-}$ is a parity-check matrix for $C^{-}$. Equivalently, $(C^{-}{)}^{\perp }$ is obtained by shortening the dual code $C^{\perp }$ at the deleted coordinate.

Finally, the shortened code in the last coordinate isIt is linear whenever $C$ is linear, because it is the puncture of the subspace $C\cap \{x_n=0\}$.