A block code is a type of error-correcting code where data is encoded in fixed-length blocks, meaning each piece of data is individually converted into a codeword (also called a block) with a specific pattern of bits, allowing for detection and correction of errors during transmission or storage.
In block coding, a message is divided into blocks of \( k \) information digits. Each block is then encoded into a longer block of \( n \) digits, called a codeword. The set of all possible codewords forms the block code.
A linear block code is a type of error-correcting code where the codewords (the encoded data) are created by linearly combining the original data bits with additional parity check bits, meaning the process of generating codewords involves only simple addition operations (like XOR) and forms a vector subspace over a finite field, typically the binary field \( GF(2) \).
A block code with length $n$ and $2^k$ codewords is classified as a linear $C(n, k)$ code iff its $2^k$ codewords form a $k$-dimensional subspace of the $n$-dimensional vector space over $GF(2)$.
A generator matrix, denoted as $\mathbf{G}$, is a matrix that defines a linear code. It is used to generate the code by multiplying it with the vectors in the message space.
A linear \( C(n, k) \) code, as a \( k \)-dimensional subspace of the vector space \( V_n \), can be spanned by \( k \) linearly independent codewords \( \mathbf{g}_0, \mathbf{g}_1, \dots, \mathbf{g}_{k-1} \). Every codeword \( \mathbf{v} \) in the code is a linear combination of these vectors:
\[ \mathbf{v} = \sum_{i=0}^{k-1} a_i \mathbf{g}_i, \quad \text{where } a_i \in \text{GF}(2). \]
These \( k \) codewords form the rows of a \( k \times n \) generator matrix \( \mathbf{G} \):
\[ \mathbf{G} = \begin{bmatrix} \mathbf{g}_0 \\ \mathbf{g}_1 \\ \vdots \\ \mathbf{g}_{k-1} \end{bmatrix} = \begin{bmatrix} g_{0,0} & g_{0,1} & \cdots & g_{0,n-1} \\ g_{1,0} & g_{1,1} & \cdots & g_{1,n-1} \\ \vdots & \vdots & \ddots & \vdots \\ g_{k-1,0} & g_{k-1,1} & \cdots & g_{k-1,n-1} \end{bmatrix} \]
For an input message \( \mathbf{u} = (u_0, u_1, \dots, u_{k-1}) \), the codeword is:
\[ \mathbf{v} = \mathbf{u} \cdot \mathbf{G} = u_0 \mathbf{g}_0 + u_1 \mathbf{g}_1 + \dots + u_{k-1} \mathbf{g}_{k-1}. \]
The generator matrix \( \mathbf{G} \) allows the encoder to store only \( k \) rows and compute codewords efficiently via matrix multiplication.
Consider the generator matrix for a \( C(7, 4) \) linear code:
\[ \mathbf{G} = \begin{bmatrix} 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 \end{bmatrix} \]
For message \( \mathbf{u} = (0, 1, 0, 1) \), the codeword is (modulo-2 addition):
\[ \mathbf{v} = \mathbf{u} \cdot \mathbf{G} = 0 \cdot \mathbf{g}_0 + 1 \cdot \mathbf{g}_1 + 0 \cdot \mathbf{g}_2 + 1 \cdot \mathbf{g}_3 = \mathbf{g}_1 + \mathbf{g}_3 = (0, 1, 1, 1, 0, 0, 1). \]
A code is systematic if the message \( \mathbf{u} \) is directly embedded in the codeword \( \mathbf{v} \), either at the start or end:
For the systematic form \( \mathbf{v} = (u_0, u_1, \dots, u_{k-1}, v_k, \dots, v_{n-1}) \), the generator matrix is:
\[ \mathbf{G} = [\mathbf{I}_k | \mathbf{P}_{k \times (n-k)}], \]
where \( \mathbf{I}_k \) is the \( k \times k \) identity matrix, and \( \mathbf{P} \) contains parity coefficients. The parity bits are:
\[ v_i = \sum_{j=0}^{k-1} u_j p_{ji}, \quad \text{for } i = k, \dots, n-1. \]
Consider the \( C(4, 2) \) code:
| Message | Codeword |
|---|---|
| 0 0 | 0 0 0 0 |
| 0 1 | 0 1 0 1 |
| 1 0 | 1 0 1 1 |
| 1 1 | 1 1 1 0 |
Linear block codes can also be characterized using parity-check matrices, which provide an alternative description to the generator matrix approach.
For any \( k \times n \) matrix \( \mathbf{G} \) over \( \text{GF}(2) \) with \( k \) linearly independent rows, there exists an \( (n - k) \times n \) matrix \( \mathbf{H} \) over \( \text{GF}(2) \) with \( n - k \) linearly independent rows such that: $\mathbf{g}_i \cdot \mathbf{h}_j = 0$, for any row \( \mathbf{g}_i \) in \( \mathbf{G} \) and any row \( \mathbf{h}_j \) in \( \mathbf{H} \). This implies that the row space of \( \mathbf{G} \) is the null space of \( \mathbf{H} \), and vice versa. Mathematically, this relationship is expressed as:
\[ \mathbf{G} \cdot \mathbf{H}^T = \mathbf{0}_{k \times (n-k)}, \]
where \( \mathbf{0}_{k \times (n-k)} \) is the \( k \times (n - k) \) zero matrix. Any vector in the row space of \( \mathbf{G} \) is orthogonal to the rows of \( \mathbf{H} \), and any vector orthogonal to the rows of \( \mathbf{H} \) lies in the row space of \( \mathbf{G} \).
Consequently, a linear code \( C(n, k) \) generated by \( \mathbf{G} \) can be alternatively defined as the set of \( n \)-tuples \( \mathbf{v} \) satisfying:
\[ \mathbf{v} \cdot \mathbf{H}^T = \mathbf{0}, \]
where \( \mathbf{0} \) is the zero vector of length \( n - k \). This follows because \( \mathbf{v} = \mathbf{u} \cdot \mathbf{G} \) for some \( \mathbf{u} \), and thus:
\[ \mathbf{v} \cdot \mathbf{H}^T = (\mathbf{u} \cdot \mathbf{G}) \cdot \mathbf{H}^T = \mathbf{u} \cdot (\mathbf{G} \cdot \mathbf{H}^T) = \mathbf{u} \cdot \mathbf{0} = \mathbf{0}. \]
The code \( C \) is thus the null space of \( \mathbf{H} \), and \( \mathbf{H} \) is called the parity-check matrix of the code.
For systematic linear codes, the structure of \( \mathbf{G} \) determines the form of \( \mathbf{H} \). Consider the two systematic forms of the generator matrix:
1. If \( \mathbf{G} = [\mathbf{P}_{k \times (n-k)} | \mathbf{I}_k] \), then the corresponding parity-check matrix is:
\[ \mathbf{H}_{(n-k) \times n} = [\mathbf{I}_{n-k} | \mathbf{P}^T_{(n-k) \times k}], \]
2. If \( \mathbf{G} = [\mathbf{I}_k | \mathbf{P}_{k \times (n-k)}] \), then:
\[ \mathbf{H}_{(n-k) \times n} = [\mathbf{P}^T_{(n-k) \times k} | \mathbf{I}_{n-k}], \]
where \( \mathbf{I}_k \) and \( \mathbf{I}_{n-k} \) are identity matrices of sizes \( k \times k \) and \( (n - k) \times (n - k) \), respectively, and \( \mathbf{P}^T \) is the transpose of the parity submatrix \( \mathbf{P} \). For \( \text{GF}(q) \) with \( q \neq 2 \), \( \mathbf{P}^T \) is replaced by \( -\mathbf{P}^T \), but over \( \text{GF}(2) \), \( -\mathbf{P}^T = \mathbf{P}^T \) since \( -1 = 1 \) modulo 2.
The parity-check equations are directly derived from \( \mathbf{H} \). For a codeword \( \mathbf{v} \), \( \mathbf{v} \cdot \mathbf{H}^T = \mathbf{0} \) imposes \( n - k \) linear constraints, corresponding to the rows of \( \mathbf{H} \).
The \( 2^{n-k} \) linear combinations of the rows of \( \mathbf{H} \) form an \( (n, n - k) \) linear code \( C_d \), known as the dual code of \( C \). This code is the null space of the \( C(n, k) \) code generated by \( \mathbf{G} \), meaning:
\[ \forall \mathbf{v} \in C, \forall \mathbf{w} \in C_d, \quad \mathbf{v} \cdot \mathbf{w} = 0. \]
Thus, the parity-check matrix \( \mathbf{H} \) of \( C \) serves as the generator matrix of its dual code \( C_d \). This duality reflects the orthogonal relationship between the code and its dual in the vector space over \( \text{GF}(2) \).
The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. For binary strings, it's the number of bits that need to be flipped to change one string into the other. Essentially, it measures the number of differences between two sequences.
By designing codes with a sufficient minimum Hamming distance, we can detect and even correct errors that occur during data transmission or storage. For example, it helps determine how many errors a code can detect or correct.
The minimum distance of a linear block code \( C \) is equal to the minimum weight of its nonzero codewords. Formally:
\[ d_{\text{min}} = \min \{ d(\mathbf{v}, \mathbf{w}) : \forall \mathbf{v}, \mathbf{w} \in C, \mathbf{v} \neq \mathbf{w} \}, \]
where \( d(\mathbf{v}, \mathbf{w}) \) is the Hamming distance, the number of positions in which \( \mathbf{v} \) and \( \mathbf{w} \) differ. Since \( C \) is linear, the sum \( \mathbf{v} + \mathbf{w} \) (modulo-2) is also a codeword, and:
\[ d_{\text{min}} = \min \{ w_H(\mathbf{v} + \mathbf{w}) : \forall \mathbf{v}, \mathbf{w} \in C, \mathbf{v} \neq \mathbf{w} \}, \]
where \( w_H(\mathbf{x}) \) is the Hamming weight, the number of nonzero components in \( \mathbf{x} \). Because \( \mathbf{v} + \mathbf{w} = \mathbf{x} \) for some \( \mathbf{x} \in C \), and \( \mathbf{x} \neq \mathbf{0} \) when \( \mathbf{v} \neq \mathbf{w} \), this simplifies to:
\[ d_{\text{min}} = \min \{ w_H(\mathbf{x}) : \forall \mathbf{x} \in C, \mathbf{x} \neq \mathbf{0} \}. \]
Thus, the minimum distance \( d_{\text{min}} \) is the weight of the lightest nonzero codeword in \( C \).
For a linear block code \( C(n, k) \) with parity-check matrix \( \mathbf{H} \), the minimum distance is tied to the linear dependencies among the columns of \( \mathbf{H} \). Specifically, for each codeword \( \mathbf{v} \in C \) with Hamming weight \( w_H(\mathbf{v}) = \ell \), there exist \( \ell \) columns of \( \mathbf{H} \) whose vector sum is zero. We can prove this by writing \( \mathbf{H} = [\mathbf{h}_0, \mathbf{h}_1, \ldots, \mathbf{h}_{n-1}] \), where \( \mathbf{h}_i \) are the columns of \( \mathbf{H} \). For \( \mathbf{v} \in C \), we have:
\[ \mathbf{v} \cdot \mathbf{H}^T = \mathbf{0}, \]
which expands to:
\[ 0 = \sum_{i=0}^{n-1} v_i \mathbf{h}_i. \]
Suppose \( w_H(\mathbf{v}) = \ell \), with nonzero components at indices \( \{ i_1, i_2, \ldots, i_\ell \} \) (i.e., \( v_{i_j} = 1 \) and \( v_i = 0 \) elsewhere). Then:
\[ 0 = v_{i_1} \mathbf{h}_{i_1} + v_{i_2} \mathbf{h}_{i_2} + \cdots + v_{i_\ell} \mathbf{h}_{i_\ell} = \mathbf{h}_{i_1} + \mathbf{h}_{i_2} + \cdots + \mathbf{h}_{i_\ell}, \]
since \( v_{i_j} = 1 \) over \( \text{GF}(2) \). Thus, the sum of these \( \ell \) columns is zero, completing the proof.
Conversely, if there exist \( \ell \) columns of \( \mathbf{H} \) summing to zero, there exists a codeword \( \mathbf{v} \in C \) with \( w_H(\mathbf{v}) = \ell \). Define \( \mathbf{v} \) with \( v_i = 1 \) at those \( \ell \) column indices and 0 elsewhere; then \( \mathbf{v} \cdot \mathbf{H}^T = \mathbf{0} \), so \( \mathbf{v} \in C \).
Consider the \( C(4, 2) \) code from previous example:
| Message | Codeword |
|---|---|
| 0 0 | 0 0 0 0 |
| 0 1 | 0 1 0 1 |
| 1 0 | 1 0 1 1 |
| 1 1 | 1 1 1 0 |
The generator matrix is:
\[ \mathbf{G} = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \end{bmatrix}. \]
The parity-check matrix, using \( \mathbf{G} = [\mathbf{I}_2 | \mathbf{P}] \) where \( \mathbf{P} = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} \), is:
\[ \mathbf{H} = [\mathbf{P}^T | \mathbf{I}_2] = \begin{bmatrix} 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \end{bmatrix}. \]
To find \( d_{\text{min}} \), compute the weights of nonzero codewords:
Therefore, \( d_{\text{min}} = 2 \), the minimum weight among nonzero codewords.