Chapter 3 Linear Block Codes

3.1 Basic Definitions

$\mathcal{A}$ having $q$ symbols, where $\mathcal{A}$ forms a field. $(c_0, \cdots, c_{n-1}) \in \mathcal{A}^n$ with $n$ elements as an $n$-vector or an $n$-tuple.

Definition 3.1

An $(n,k)$ block code $\mathcal{C}$ over an alphabet of $q$ symbols is a set of $q^k$ $n$-vectors called codewords or code vectors. Associated with the code is an $encoder$ which maps a $message$, a $k$-tuple $m ∈ \mathcal{A}^k$, to its associated codeword.

Definition 3.2

A block code $\mathcal{C}$ over a field $\mathbb{F}_q$ of $q$ symbols of length $n$ and $q^k$ codewords is a $q$-ary linear $(n,k)$ code if and only if its $q^k$ codewords form a $k$-dimensional vector subspace of the vector space of all the $n$-tuples $\mathbb{F}_q^n$. The number $n$ is said to be the length of the code and the number $k$ is the dimension of the code. The rate of the code is $R = k∕n$.

Definition 3.3

The Hamming weight $wt(𝐜)$ of a codeword $𝐜$ is the number of nonzero components of the codeword. The minimum weight $𝑤_{\min}$ of a code $\mathcal{C}$ is the smallest Hamming weight of any nonzero codeword: $w_{\min} = \min_{𝐜 ∈ \mathcal{C},𝐜≠0}wt(𝐜)$.

Theorem 3.4

For a linear code $\mathcal{C}$, the minimum distance $d_{\min }$ satisfies $d_{\min} = 𝑤_{\min}$. That is, the minimum distance of a linear block code is equal to the minimum weight of its nonzero codewords.

Proof:

Since there are only finite codewords, we can find 2 codewords that satisfies the $d_{\min}$, say they are $c_0, c_1$.

So $d_{\min} = d(c_0, c_1) = wt(c_0 - c_1)$.

Let $c_2 = c_0 - c_1$. Since $\mathcal{C}$ is a linear code, $0, c_2 \in \mathcal{C}$.

$d(c_2, 0) = wt(c_2) = wt(c_0 - c_1) = d_{\min}$.

On the other hand, given any $c \in \mathcal{C}$,

$wt(c) = d(c,0) \geq d_{\min} = wt(c_2)$, so $c_2$ is a codeword with minimum weight.

We have found a codeword with minimum nonzero weight and its weight equals to the $d_{\min}$

$\square$

3.2 The Generator Matrix Description of Linear Block Codes

Since $\mathcal{C}$ is a $k$ dimensional subspace, we can find $g_0, \cdots, g_{k-1}$ such that for $c \in \mathcal{C}$.

$$\tag{3-1} c = m_0 g_0 + \cdots + m_{k-1} g_{k-1}$$

where $m_i \in \mathbb{F}_q$.

Think $g_i$ as row vectors and stack them together, we have

$$G = \begin{bmatrix} g_0 \\ g_1 \\ \vdots \\ g_{k-1} \end{bmatrix}$$

and let $m = [m_0, \cdots, m_{k-1}]$, we have $c = m G$.

Definition 3.6

Let $\mathcal{C}$ be an $(n,k)$ block code (not necessarily linear). An encoder is systematic if the message symbols $m_0,m_1, ...,m_{k−1}$ may be found explicitly and unchanged in the codeword. That is, there are coordinates $i_0,i_1, ...,i_{k−1}$ (which are most frequently sequential, $i_0,i_0 +1, ...,i_0 +k−1$) such that $c_{i_0} = m_0,c_{i_1} = m_1, ...,c_{i_{k−1}} = m_{k−1}$.

$\square$

Frequently, a systematic generator is written in the form

$$G = [P \quad I_k]$$

where $I_k$ is the $k ×k$ identity matrix and $P$ is a $k ×(n−k)$ matrix which generates parity symbols. The encoding operation is

$$c = [m_P \quad m]$$

The codeword is divided into two parts: the part $𝐦$ consists of the message symbols, and the part $𝐦P$ consists of the parity check symbols.

Definition 3.7

Two linear codes which are the same except for a permutation of the components of the code are said to be equivalent codes.

$\square$

3.3 The Parity Check Matrix and Dual Codes

Definition 3.9

The dual space to an $(n,k)$ code $\mathcal{C}$ of dimension $k$ is the $(n,n−k)$ dual code of $\mathcal{C}$, denoted by $\mathcal{C}^{\perp}$. A code $\mathcal{C}$ such that $\mathcal{C} = \mathcal{C}^{\perp}$ is called a self-dual code.

Theorem 3.10

Let $\mathcal{C}$ be an $(n,k)$ linear code over $\mathbb{F}_q$ and let $H$ be a parity check matrix for $\mathcal{C}$. A vector $𝐯 ∈ \mathbb{F}_q^n$ is a codeword if and only if

$$v H^T = 0$$

That is, the codewords in $\mathcal{C}$ lie in the (left) nullspace of $H$.

Proof:

This problem is in fact same as the "Linear Algebra Done Right 4th Ed." exercise 3F.20, which states:

Suppose $𝑉$ is finite-dimensional and $𝑈$ is a subspace of $𝑉$. Show that

$$𝑈 = \{𝑣 ∈ 𝑉 ∶ \varphi(𝑣) = 0 \text{ for every } \varphi ∈ 𝑈^0\}.$$

$\square$

Theorem 3.13

Let a linear block code $\mathcal{C}$ have a parity check matrix $H$. The minimum distance $d_{\min}$ of $\mathcal{C}$ is equal to the smallest positive number of columns of $H$ which are linearly dependent. That is, all combinations of $d_{\min}-1$ or fewer columns are linearly independent, so there is some set of $d_{\min}$ columns which are linearly dependent.

Proof:

$H$ is an $n-k$ by $n$ matrix, and let $h_i$ be the ith column of $H$, so

$$H = \begin{bmatrix} h_1 & h_2 & \cdots & h_n \end{bmatrix}$$

If $c = [c_1, c_2, \cdots, c_n]$ is a codeword with $c H^T = 0$, note that

$$c H^T = c_1 h_1 + \cdots + c_{n} h_{n}$$

$\square$

3.3.1 Some Simple Bounds on Block Codes

Theorem 3.15

The Singleton bound. The minimum distance for an $(n,k)$ linear code is bounded by

$$\tag{3.8} d_{\min} \leq n-k+1$$

Proof:

The row rank of $H$ is $n-k$, so is the column rank. Which means any $n-k+1$ columns of $H$ must linear dependent. Then from theorem 3.13, we have $d_{\min} \leq n-k+1$.

$\square$

Hammsphere

The vectors at Hamming distances $≤ t$ away from a codeword form a “sphere” called the Hamming sphere of radius $t$. The number of vectors in a Hamming sphere up to radius $t$ for a code of length $n$ over an alphabet of $q$ symbols is denoted $V_q(n,t)$, where

$$V_q(n,t) = \sum_{j = 0}^{t} \binom{n}{j} (q-1)^{j}$$

redundancy

The redundancy of a code is essentially the number of parity symbols in a codeword. More precisely we have

$$r = n - \log_{p} M$$

where $M$ is the number of codewords. For a linear code we have $M = q^k$, so $r = n−k$.

Theorem 3.17 (The Hamming Bound)

A $t$-random error correcting $q$-ary code $\mathcal{C}$ must have redundancy $r$ satisfying

$$r \ge \log_{q} V_q(n, t).$$

Proof:

Each of $M$ spheres in $\mathcal{C}$ has radius $t$. The spheres do not overlap, or else it would not be possible to decode $t$ errors. The total number of points enclosed by the spheres must be $≤ q^n$. We must have

$$M V_q(n, t) ≤ q^n$$

from which the result follows by taking $\log_{q}$ of both sides.

$\square$

perfect code

A code satisfying the Hamming bound with equality is said to be a perfect code.