Linear Codes & Generator Matrix

Generator matrix G, encoding uG, and the [n, k, d] parameters.

The idea

A linear code over $\mathbb{F}_2$ is a code in which the sum of two codewords is again a codeword, arithmetic taken modulo $2$ so that $1 + 1 = 0$. Without this structure a code is a bare list of allowed strings, and encoding means looking a message up in the list; linearity replaces the list with a matrix.

A linear code is a subspace of $\mathbb{F}_2^{n}$, so it has a basis. Write the basis vectors as the rows of a $k \times n$ matrix $G$, the generator matrix. Every codeword is a combination of the rows, and the message specifies which combination: the message $u \in \mathbb{F}_2^{k}$ is encoded as $c = uG.$ Encoding is a single matrix multiplication, and the $2^{k}$ messages give $2^{k}$ distinct codewords.

Three numbers, written $[n, k, d]$, summarize a linear code. The length $n$ is the number of symbols in a codeword, so it is the number of columns of $G$. The dimension $k$ is the number of symbols in a message, so it is the number of rows. The minimum distance $d$ is the smallest number of positions in which two distinct codewords differ.

Linearity simplifies finding $d$. The difference of two codewords is itself a codeword, so every distance between a pair equals the weight — the number of nonzero entries — of some nonzero codeword. Instead of comparing every pair, find the lightest nonzero codeword; its weight is $d$.

Ways to work on it

• Walkthrough. A code as a subspace, encoding with a generator matrix, and reading off the code's parameters.
• Practice. Read length, dimension, or codeword count from a generator matrix.
• Hardest. Encode a message and find the code's minimum distance.

Not sure where to start? Take the ten-question placement test.