From Nonzero Columns to a Binary Code
A parity-check matrix describes a code by specifying which binary vectors satisfy a system of linear equations. For the binary \([7,4,3]\) Hamming code, the central construction is to take a \(3\times 7\) matrix whose columns are exactly the nonzero vectors of \(\mathbb{F}_2^3\). The arrangement of those columns makes the code’s dimension and minimum distance visible: the equations leave four independent bits free, while the column relations rule out codewords of weight one or two and provide one of weight three.
Here \(\mathbb{F}_2=\{0,1\}\), with addition and multiplication performed modulo \(2\). In particular, \(1+1=0\), and subtraction is the same as addition. Vectors in \(\mathbb{F}_2^n\) are columns. The Hamming weight \(\operatorname{wt}(\mathbf{x})\) of a vector \(\mathbf{x}\) is the number of its nonzero coordinates. Its Hamming distance from \(\mathbf{y}\) is the number of coordinates in which \(\mathbf{x}\) and \(\mathbf{y}\) differ.
Use the following order for the seven nonzero columns: first the three standard basis vectors, followed by the other four nonzero vectors. Let \(\mathbf{h}_i\) denote column \(i\) of \(\mathbf{H}\).
Thus the columns, in order, are \((1,0,0)^{\top},(0,1,0)^{\top},(0,0,1)^{\top},(1,1,0)^{\top},(1,0,1)^{\top},(0,1,1)^{\top},(1,1,1)^{\top}\). Each is nonzero, and every nonzero vector in \(\mathbb{F}_2^3\) appears once.
Since \(\mathbf{H}\) has three rows, the equation \(\mathbf{H}\mathbf{x}=\mathbf{0}\) imposes three parity checks on seven coordinates. All calculations in these checks take place in \(\mathbb{F}_2\).
Solving the Parity Checks
Worked Example: Describe Every Codeword
Write \(\mathbf{x}=(x_1,x_2,x_3,x_4,x_5,x_6,x_7)^{\top}\). Multiplying by \(\mathbf{H}\) gives the three equations \[ x_1+x_4+x_5+x_7=0,\qquad x_2+x_4+x_6+x_7=0,\qquad x_3+x_5+x_6+x_7=0. \] The first three columns of \(\mathbf{H}\) form the identity matrix, so these equations solve directly for \(x_1,x_2,x_3\). Because each element of \(\mathbb{F}_2\) is its own additive inverse, the equations give \[ x_1=x_4+x_5+x_7,\quad x_2=x_4+x_6+x_7,\quad x_3=x_5+x_6+x_7. \]
Choose the four free coordinates \(x_4,x_5,x_6,x_7\) in turn to be \(1\), with the other three free coordinates set to \(0\). This produces the following four codewords as columns:
Each solution is the combination \(x_4\mathbf{g}_1+x_5\mathbf{g}_2+x_6\mathbf{g}_3+x_7\mathbf{g}_4\). For instance, setting \((x_4,x_5,x_6,x_7)=(1,0,1,1)\) yields \((x_1,x_2,x_3)=(0,1,0)\), so \[ \mathbf{x}=(0,1,0,1,0,1,1)^{\top}. \]
Check: the three entries of \(\mathbf{H}\mathbf{x}\) are, respectively, \(0+1+0+1=0\), \(1+1+1+1=0\), and \(0+0+1+1=0\) in \(\mathbb{F}_2\). Therefore \(\mathbf{H}\mathbf{x}=\mathbf{0}\), as required.
It is useful to collect these basis codewords as the columns of a \(7\times4\) matrix \(\mathbf{G}\). This convention makes encoding a column of four message bits a matrix-vector product:
The final four rows of \(\mathbf{G}\) form the \(4\times4\) identity matrix. They record the four freely chosen coordinates and will also make the independence of its columns straightforward to verify.
Why the Code Has Dimension Four
The dimension of a code is the number of vectors in any basis of that code. To establish the dimension here, it is enough to show that \(\mathbf{g}_1,\mathbf{g}_2,\mathbf{g}_3,\mathbf{g}_4\) span \(\mathcal{C}\) and are linearly independent. The equations above give both facts directly.
Proof. First, each \(\mathbf{g}_j\) satisfies the parity checks. This can be checked by adding the columns of \(\mathbf{H}\) in the support of that vector: \[ \mathbf{H}\mathbf{g}_1=\mathbf{h}_1+\mathbf{h}_2+\mathbf{h}_4=\mathbf{0},\quad \mathbf{H}\mathbf{g}_2=\mathbf{h}_1+\mathbf{h}_3+\mathbf{h}_5=\mathbf{0}, \] \[ \mathbf{H}\mathbf{g}_3=\mathbf{h}_2+\mathbf{h}_3+\mathbf{h}_6=\mathbf{0},\quad \mathbf{H}\mathbf{g}_4=\mathbf{h}_1+\mathbf{h}_2+\mathbf{h}_3+\mathbf{h}_7=\mathbf{0}. \] For example, the first sum is \((1,0,0)^{\top}+(0,1,0)^{\top}+(1,1,0)^{\top}=(0,0,0)^{\top}\) in \(\mathbb{F}_2^3\); the other three sums also equal zero coordinate by coordinate. Since matrix multiplication is linear, every combination of the \(\mathbf{g}_j\) belongs to \(\mathcal{C}\). Conversely, let \(\mathbf{x}\in\mathcal{C}\). Its parity equations show that its first three coordinates are determined by its last four. Substituting \(x_4,x_5,x_6,x_7\) into the formulas for \(x_1,x_2,x_3\) gives \[ \mathbf{x}=x_4\mathbf{g}_1+x_5\mathbf{g}_2+x_6\mathbf{g}_3+x_7\mathbf{g}_4. \] Thus the four columns span \(\mathcal{C}\). Finally, suppose \(a_1\mathbf{g}_1+a_2\mathbf{g}_2+a_3\mathbf{g}_3+a_4\mathbf{g}_4=\mathbf{0}\). Looking at coordinates \(4,5,6,7\) gives \(a_1=0,a_2=0,a_3=0,a_4=0\), respectively, because those coordinates of the four columns form the identity matrix. So the columns are linearly independent as well as spanning. They form a basis, and therefore \(\dim\mathcal{C}=4\). \(\square\)
Worked Example: Encode and Check a Message
Take the message column \(\mathbf{u}=(1,0,1,1)^{\top}\in\mathbb{F}_2^4\). Encoding with \(\mathbf{G}\) gives \[ \mathbf{G}\mathbf{u}=\mathbf{g}_1+\mathbf{g}_3+\mathbf{g}_4 =(0,1,0,1,0,1,1)^{\top}. \] The first coordinate is \(1+0+1=0\), the second is \(1+1+1=1\), and the third is \(0+1+1=0\), all in \(\mathbb{F}_2\); the last four coordinates are \(1,0,1,1\).
Check: multiplying the resulting vector by \(\mathbf{H}\) gives row sums \(0+1+0+1=0\), \(1+1+1+1=0\), and \(0+0+1+1=0\). Thus the encoded vector satisfies every parity check and is a codeword.
In general, a message \(\mathbf{u}=(u_1,u_2,u_3,u_4)^{\top}\) produces \(\mathbf{x}=\mathbf{G}\mathbf{u}\). Its last four coordinates are exactly \(u_1,u_2,u_3,u_4\), so distinct messages give distinct codewords. There are four freely chosen binary coordinates, hence \(2^4=16\) codewords. This count agrees with the four-dimensional basis just proved.
Why the Minimum Distance Is Three
For a linear code, the minimum distance between distinct codewords equals the smallest weight of a nonzero codeword. Indeed, if \(\mathbf{x},\mathbf{y}\in\mathcal{C}\), then \(\mathbf{x}-\mathbf{y}\in\mathcal{C}\), since \(\mathcal{C}\) is a subspace. The coordinates of \(\mathbf{x}-\mathbf{y}\) are nonzero exactly where \(\mathbf{x}\) and \(\mathbf{y}\) differ, so \(d(\mathbf{x},\mathbf{y})=\operatorname{wt}(\mathbf{x}-\mathbf{y})\). For distinct codewords, \(\mathbf{x}-\mathbf{y}\ne\mathbf{0}\). Conversely, every nonzero codeword \(\mathbf{z}\) is the difference of \(\mathbf{z}\) and \(\mathbf{0}\), both codewords. Thus it suffices to find the least weight of a nonzero vector in \(\mathcal{C}\).
Proof. Write \(\mathbf{x}=(x_1,\dots,x_7)^{\top}\). By matrix multiplication, \[ \mathbf{H}\mathbf{x}=\sum_{i=1}^{7}x_i\mathbf{h}_i. \] If \(\mathbf{x}\) has weight one, this sum is a single column \(\mathbf{h}_i\), which is nonzero by construction. Therefore no weight-one vector is a codeword. If \(\mathbf{x}\) has weight two, its parity-check sum is \(\mathbf{h}_i+\mathbf{h}_j\) for two distinct indices \(i,j\). If this sum were zero, then \(\mathbf{h}_i=-\mathbf{h}_j\). In \(\mathbb{F}_2^3\), \(-\mathbf{h}_j=\mathbf{h}_j\), so the two columns would be equal. But all seven columns are distinct. Hence no weight-two vector is a codeword either. There is a codeword of weight three: the first, second, and fourth columns satisfy \[ \mathbf{h}_1+\mathbf{h}_2+\mathbf{h}_4 =(1,0,0)^{\top}+(0,1,0)^{\top}+(1,1,0)^{\top} =\mathbf{0}. \] The vector \((1,1,0,1,0,0,0)^{\top}\) therefore lies in \(\mathcal{C}\) and has weight three. Since no nonzero codeword has weight one or two and one has weight three, the least nonzero weight is exactly three. The minimum distance is consequently \(3\). \(\square\)
Worked Example: Verify a Minimum-Weight Codeword
Let \(\mathbf{z}=(1,1,0,1,0,0,0)^{\top}\). Its nonzero coordinates are \(1,2,4\), so \(\operatorname{wt}(\mathbf{z})=3\). To check that it is a codeword, add the corresponding parity-check columns: \[ \mathbf{H}\mathbf{z}=\mathbf{h}_1+\mathbf{h}_2+\mathbf{h}_4 =(1+0+1,\;0+1+1,\;0+0+0)^{\top} =(0,0,0)^{\top}. \]
Check: the three sums in the middle expression are all calculated modulo \(2\), so \(\mathbf{H}\mathbf{z}=\mathbf{0}\). The vector is a codeword of weight three, matching the upper bound in the minimum-distance proof.
The theorem proves both sides needed to identify the distance: the distinct nonzero columns prevent any codeword of weight one or two, and a relation among three columns gives a codeword of weight three. The construction therefore has length \(7\), dimension \(4\), and minimum distance \(3\), which is precisely the \([7,4,3]\) code.
Common Pitfall: Use Arithmetic in the Correct Field
A frequent error is to treat the entries of \(\mathbf{H}\) as ordinary integers while checking a parity equation. For example, an integer calculation gives \[ (1,0,0)^{\top}+(0,1,0)^{\top}+(1,1,0)^{\top}=(2,2,0)^{\top}. \] It would be wrong to conclude from this that the sum is nonzero in the code construction. The calculation must be performed in \(\mathbb{F}_2\): \(2=0\) in that field, so the sum is \((0,0,0)^{\top}\). The correction is to reduce each coordinate modulo \(2\), which verifies the parity check and the weight-three codeword.
Another useful check is to keep the roles of the two matrices distinct. The \(3\times7\) matrix \(\mathbf{H}\) tests whether a length-seven vector is in the code through \(\mathbf{H}\mathbf{x}=\mathbf{0}\). The \(7\times4\) matrix \(\mathbf{G}\) builds codewords from four message bits through \(\mathbf{G}\mathbf{u}\). In this construction, direct verification gives \(\mathbf{H}\mathbf{g}_j=\mathbf{0}\) for each column of \(\mathbf{G}\), so every encoded vector passes the parity checks.
Check Your Understanding
Use arithmetic in \(\mathbb{F}_2\) throughout. Verify calculations by substituting vectors into the parity checks.
- What are the three parity equations obtained from \(\mathbf{H}\mathbf{x}=\mathbf{0}\)?
- Find the codeword whose free coordinates are \((x_4,x_5,x_6,x_7)=(0,1,1,0)\), and check it using \(\mathbf{H}\).
- Why does the identity matrix in rows \(4\) through \(7\) of \(\mathbf{G}\) prove that its columns are linearly independent?
- Explain why two distinct columns of \(\mathbf{H}\) cannot sum to zero over \(\mathbb{F}_2\).
- Give a weight-three codeword by choosing three columns of \(\mathbf{H}\) that sum to zero.
