Back to the on-screen lesson ·
H with Hc^T = 0; H = [A^T | I]; minimum distance from dependent columns.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to define a linear code as a subspace of $\mathbb{F}_2^n$, encode messages by multiplying by a generator matrix, put a generator matrix into systematic form and read off the message and parity positions, and explain why the minimum distance of a linear code is its minimum nonzero weight. You will construct the parity-check matrix from a systematic generator, prove that it annihilates exactly the codewords, determine the minimum distance from the smallest set of linearly dependent columns, and see that the syndrome of a received word depends only on the error pattern.
The parity-check matrix $H$ of an $[n, k]$ code is an $(n - k) \times n$ matrix whose null space is the code: $c$ is a codeword if and only if $Hc^T = 0$. From a systematic $G = [I_k \mid A]$ one reads off $H = [A^T \mid I_{n-k}]$, since $G H^T = A + A = 0$ over $\mathbb{F}_2$ and the ranks match. Each row of $H$ is one parity check, an equation the codeword bits must satisfy. $H$ makes the minimum distance visible: $Hc^T$ is the sum of the columns of $H$ at the positions where $c$ has a $1$, so a codeword of weight $w$ exists exactly when some $w$ columns sum to zero, and $d$ is the smallest number of linearly dependent columns. A zero column means $d = 1$; two equal columns mean $d = 2$; distinct nonzero columns give $d \ge 3$. For a received word $r = c + e$ the syndrome $s = Hr^T = He^T$ depends only on the error, which is the basis of syndrome decoding in the next lesson.
Another way: example
For the $[5, 2]$ code, $H = \begin{pmatrix} 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 \end{pmatrix}$. Its columns are $(1,1,0), (0,1,1), (1,0,0), (0,1,0), (0,0,1)$: no zero column, no repeat, but columns $1, 3, 4$ sum to zero, so $d = 3$, matching the minimum weight $3$.
Another way: steps
The parity-check matrix $H$ of an $[n, k]$ code is $(n - k) \times n$ and its null space is the code: $$c \text{ is a codeword} \iff Hc^T = 0.$$ Each row is one parity check — an equation the codeword's bits must satisfy — and there are $n - k$ of them, one per redundant bit. From a systematic $G = [I_k \mid A]$ you read $H$ off directly: $$H = [A^T \mid I_{n-k}],$$ because $GH^T = [I \mid A]\begin{pmatrix} A \\ I \end{pmatrix} = A + A = 0$ over $\mathbb{F}_2$, and $H$ has rank $n - k$ thanks to its identity block, so its null space has exactly dimension $k$.
The deeper use of $H$ is that it makes the minimum distance visible. $Hc^T$ is the sum of the columns of $H$ at the positions where $c$ has a $1$, so a codeword of weight $w$ exists exactly when some $w$ columns sum to zero. Hence $$d = \text{the smallest number of linearly dependent columns of } H.$$
| columns of $H$ | smallest dependent set | $d$ | capability |
|---|---|---|---|
| a zero column | that column alone | $1$ | nothing |
| two equal columns | that pair | $2$ | detects $1$ |
| all distinct and nonzero | three that sum to zero | $3$ | corrects $1$ |
| no three sum to zero | four that sum to zero | $4$ | corrects $1$, detects $2$ |
That table is the whole practice item: look for a zero column first, then for two equal columns, then for three that sum to zero, and stop at the first one you find. It is also the design rule behind the Hamming codes of the next lesson — take all distinct nonzero columns and you get $d = 3$ with as many positions as possible.
Common mistakes
$H = \begin{pmatrix} 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \end{pmatrix}$: columns $(1,1), (1,0), (0,1), (1,0), (0,1)$.
List the columns.
Columns $2$ and $4$ are equal, so $d = 2$: the code detects one error but corrects none.
Two equal columns give a weight-$2$ codeword.
$G H^T = [I \mid A] \begin{pmatrix} A \\ I \end{pmatrix} = A + A = 0$ over $\mathbb{F}_2$: every row of $G$, hence every codeword, is annihilated by $H$.
$H$ has rank $n - k$ because of its identity block, so its null space has dimension $k$: exactly the code.
The code is all words of even weight, so the one check is $c_1 \oplus c_2 \oplus c_3 \oplus c_4 = 0$.
$H = \begin{pmatrix} 1 & 1 & 1 & 1 \end{pmatrix}$: one row, because $n - k = 1$.
Its columns are all $(1)$, so two of them are equal: $d = 2$, detection only, as expected of a parity bit.
$H$ has columns $(1,1), (1,0), (0,1), (1,1)$.
No column is zero, so $d > 1$; but columns $1$ and $4$ are equal, so they sum to zero.
Two equal columns mean a weight-$2$ codeword, here $1001$.
$d = 2$: the code detects one error and corrects none.
$G = [I_3 \mid \mathbf{1}]$, so $A$ is a column of ones and $H = [A^T \mid I_1] = (1 \; 1 \; 1 \; 1)$.
All columns equal, so $d = 2$; the one check says the total parity is even.
The columns of a parity-check matrix $H$ are $(0, 0), (1, 0), (0, 1)$. What is the minimum distance of the code?
Computed value: answer
An $[\,8, 7\,]$ linear code: how many rows does its parity-check matrix $H$ have, and how many syndromes $Hr^T$ are possible? Enter the number of rows.
Computed value: answer
For $G = \begin{pmatrix} 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 \end{pmatrix} = [I_2 \mid A]$, which construction gives a parity-check matrix?
The columns of a parity-check matrix $H$ are $(0, 0), (1, 0), (0, 1)$. What is the minimum distance of the code?
Computed value: answer
What does the parity-check matrix $H$ of a linear code do?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
An $[\,6, 5\,]$ linear code: how many rows does its parity-check matrix $H$ have, and how many syndromes $Hr^T$ are possible? Enter the number of rows.
Computed value: answer
You can encode with $G$, check with $H$ and read the distance from $H$'s columns. Next: using the syndrome to locate errors, and the Hamming codes that do it perfectly.
9. Your turn: $H$ for the single-parity $[4, 3]$ code, step 2