Back to the on-screen lesson ·
Codes as subspaces of F_2^n; c = mG; systematic form [I | A].
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.
A binary linear $[n, k]$ code is a $k$-dimensional subspace of $\mathbb{F}_2^n$, the space of $n$-bit words with XOR as addition. Linearity means the sum of two codewords is a codeword, so the code is closed, contains the zero word, and has exactly $2^k$ codewords and rate $k/n$. It is described by a generator matrix $G$, $k \times n$, whose rows are a basis: the message $m \in \mathbb{F}_2^k$ is encoded as $c = mG$, the XOR of the rows selected by the $1$s of $m$. Row operations and a permutation of positions bring $G$ to systematic form $G = [I_k \mid A]$, where the codeword is the message followed by $n - k$ parity bits $mA$. Linearity also simplifies distance: since $d(c, c') = \text{wt}(c + c')$ and $c + c'$ is a codeword, the minimum distance equals the minimum weight of a nonzero codeword. The repetition code, the parity-bit code and the Hamming codes are all linear, and almost every code used in practice is.
Another way: example
The $[5, 2]$ code with $G = \begin{pmatrix} 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 \end{pmatrix}$: messages $00, 10, 01, 11$ give codewords $00000, 10110, 01011, 11101$. Nonzero weights $3, 3, 4$, so $d = 3$: a one-error-correcting code of rate $0.4$.
Another way: steps
A binary linear $[n, k]$ code is a $k$-dimensional subspace of $\mathbb{F}_2^n$, the $n$-bit words with XOR as addition. Being a subspace does three things at once: the sum of two codewords is a codeword, the zero word is one, and there are exactly $2^k$ of them. A generator matrix $G$ is $k \times n$ and its rows are a basis, so encoding is $$c = mG,$$ the XOR of the rows the message's $1$s select. Take the $[5, 2]$ code with $$G = \begin{pmatrix} 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 \end{pmatrix}:$$
| message $m$ | rows XORed | codeword $c = mG$ | weight |
|---|---|---|---|
| $00$ | none | $00000$ | $0$ |
| $10$ | row 1 | $10110$ | $3$ |
| $01$ | row 2 | $01011$ | $3$ |
| $11$ | both rows | $11101$ | $4$ |
This $G$ is in systematic form $G = [I_k \mid A]$: the first $k$ columns are the identity, so the codeword is the message followed by $n - k$ parity bits $mA$. Read the table again and you can see the message in the first two bits of every codeword. Any generator matrix can be brought to this form by row operations and a permutation of positions, and the resulting code is equivalent — same size, same distances.
Linearity also makes the minimum distance cheap to find. Since $d(c, c') = \text{wt}(c \oplus c')$ and $c \oplus c'$ is itself a codeword, the minimum distance equals the smallest weight of a nonzero codeword. Instead of comparing all $\binom{2^k}{2}$ pairs you weigh $2^k - 1$ words — for the table above, weights $3, 3, 4$, so $d = 3$ and the code corrects one error.
Common mistakes
Message $11$ with the $[5, 2]$ code above: XOR both rows, $10110 \oplus 01011 = 11101$.
$c = mG$.
Read it systematically: message $11$, then parity bits $m_1 = 1$, $m_1 \oplus m_2 = 0$, $m_2 = 1$.
For codewords $c, c'$: $d(c, c') = \text{wt}(c \oplus c')$, and $c \oplus c'$ is itself a codeword by linearity.
So the minimum over pairs equals the minimum weight of a nonzero codeword: $2^k - 1$ weights to check instead of $\binom{2^k}{2}$ pairs.
One message bit, three sent: $G = \begin{pmatrix} 1 & 1 & 1 \end{pmatrix}$, a $[3, 1]$ code.
Codewords: $0 \cdot G = 000$ and $1 \cdot G = 111$; there are $2^1 = 2$.
Minimum weight of a nonzero codeword: $\text{wt}(111) = 3$, so $d = 3$ — the same answer lesson 18 got by comparing the pair.
Message $11$ in the $[5, 2]$ code: XOR both rows, $10110 \oplus 01011$.
Position by position: $1{\oplus}0, 0{\oplus}1, 1{\oplus}0, 1{\oplus}1, 0{\oplus}1 = 11101$.
The first two bits are the message $11$; the parity bits are $m_1 = 1$, $m_1 \oplus m_2 = 0$, $m_2 = 1$.
Systematic form lets you read the message off without decoding.
$G = (1 \; 1 \; 1)$, a $[3, 1]$ code with codewords $000$ and $111$.
Minimum weight $3$, so $d = 3$; rate $\tfrac{1}{3}$.
A $[5, 2]$ code has generator matrix $G = \begin{pmatrix} 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 \end{pmatrix}$. Encode the message $10$.
c = c
A generator matrix has $8$ linearly independent rows of length $12$. How many codewords does the code have?
Computed value: answer
A systematic generator matrix $G = [I_k \mid A]$ for an $[\,14, 10\,]$ code: how many columns does $A$ have?
Computed value: answer
A $[5, 2]$ code has generator matrix $G = \begin{pmatrix} 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 \end{pmatrix}$. Encode the message $11$.
c = c
What does it mean for a generator matrix to be in systematic form $G = [I_k \mid A]$?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A generator matrix has $2$ linearly independent rows of length $5$. How many codewords does the code have?
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: the $3$-repetition code as a linear code, step 2