Some Specific Linear Block Codes

We review some well-known linear block codes and their important parameters.

Repetition Codes

A binary repetition code is an \((n, 1)\) linear block code featuring exactly two codewords of length \(n\): the all-zero codeword (e.g., \((0, 0, \ldots, 0)\)) and the all-one codeword (e.g., \((1, 1, \ldots, 1)\)).

This simple structure encodes a single information bit, repeating it \(n\) times, yielding a code rate of \(R_c = \frac{1}{n}\), which decreases as \(n\) increases due to heightened redundancy.

The minimum distance \(d_{\min} = n\), as the two codewords differ in all \(n\) positions, enhancing error detection and correction capability.

The dual code, an \((n, n - 1)\) code, comprises all \(n\)-bit binary sequences with even parity (i.e., an even number of 1s), such as \((0, 0, \ldots, 0)\) or \((1, 1, 0, \ldots, 0)\).

Its minimum distance is \(d_{\min} = 2\), reflecting the smallest number of bit flips (two) needed to change parity, offering minimal but distinct separation.

Hamming Codes

Hamming codes, among the earliest constructs in coding theory, are linear block codes defined by parameters \(n = 2^m - 1\) and \(k = 2^m - m - 1\), where \(m \geq 3\) is an integer determining the code’s size (e.g., for \(m = 3\), \(n = 7\), \(k = 4\)).

These codes are efficiently characterized by their parity check matrix \(\mathbf{H}\), an \((n - k) \times n = m \times (2^m - 1)\) matrix.

The \(2^m - 1\) columns of \(\mathbf{H}\) encompass all possible nonzero binary vectors of length \(m\) (e.g., for \(m = 3\), columns are 001, 010, 011, 100, 101, 110, 111), excluding the all-zero vector.

This design ensures a systematic approach to error detection, leveraging the full range of nonzero patterns to define parity constraints.

Hamming Codes Properties

The code rate of a Hamming code is:

\[ R_c = \frac{2^m - m - 1}{2^m - 1} \]

For large \(m\), \(R_c\) approaches 1 (e.g., \(m = 5\): \(R_c = 26/31 \approx 0.84\)), indicating high efficiency with minimal redundancy.

The parity check matrix \(\mathbf{H}\)’s columns, being all nonzero \(m\)-bit vectors, imply that any two columns sum to a third (e.g., 001 + 010 = 011), making three columns linearly dependent.

Thus, the minimum distance is consistently \(d_{\min} = 3\) across all \(m\), as no fewer than three columns can be dependent, enabling correction of single-bit errors.

The weight distribution polynomial is:

\[ A(Z) = \frac{1}{n+1} \left[(1 + Z)^n + n(1 + Z)^{\frac{n-1}{2}}(1 - Z)^{\frac{n+1}{2}}\right] \]

This formula quantifies the number of codewords per weight, reflecting the code’s structured weight profile and error-correcting capacity.

EXAMPLE: (7, 4) Hamming Code Parity Check Matrix

For a \((7, 4)\) Hamming code with \(m = 3\), the parity check matrix \(\mathbf{H}\) is constructed using all \(2^3 - 1 = 7\) nonzero binary sequences of length 3 as columns.

Arranging these systematically, we obtain:

\[\begin{split} \mathbf{H} = \begin{bmatrix} 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 \end{bmatrix} \end{split}\]

This matches the parity check matrix from a prior example, confirming its systematic form where the last \(n - k = 3\) columns form an identity matrix.

Tools like MATLAB’s hammgen function can generate both \(\mathbf{H}\) and the corresponding generator matrix, validating this structure for a Hamming code with \(n = 7\) and \(k = 4\).

Maximum-Length Codes

Maximum-length codes, duals to Hamming codes, are \((2^m - 1, m)\) codes for \(m \geq 3\) (e.g., (7, 3) for \(m = 3\)).

Their generator matrix is the parity check matrix of a Hamming code, with \(2^m - 1\) columns comprising all nonzero \(m\)-bit sequences.

These codes are constant-weight, with all nonzero codewords having weight \(2^{m-1}\) (e.g., 4 for \(m = 3\)), and one codeword of weight 0.

The weight enumeration function is:

\[ A(Z) = 1 + (2^m - 1)Z^{m-1} \]

Applying the MacWilliams identity to this \(A(Z)\) derives the Hamming code’s weight distribution, linking the dual relationship and confirming the uniform weight property of maximum-length codes.

Reed-Muller Codes

Reed-Muller (RM) codes, developed by Reed and Muller in 1954, are linear block codes with block length \(n = 2^m\) and order \(r < m\).

Their parameters are:

\[ n = 2^m, \quad k = \sum_{i=0}^{r} \binom{m}{i}, \quad d_{\min} = 2^{m-r} \]

The generator matrix is:

\[\begin{split} \mathbf{G} = \begin{bmatrix} \vec{g}_0 \\ \vec{g}_1 \\ \vec{g}_2 \\ \vdots \\ \vec{g}_r \end{bmatrix} \end{split}\]

These codes are notable for simple decoding algorithms, with \(k\) reflecting the number of basis vectors up to degree \(r\), and \(d_{\min}\) decreasing as \(r\) increases, balancing complexity and error correction.

Reed-Muller Codes Generator Matrix

The generator matrix components are: \(\vec{g}_0\), a \(1 \times n\) row of all 1s:

\[ \vec{g}_0 = [1 \ 1 \ \dots \ 1] \]

\(\vec{g}_1\), an \(m \times n\) matrix with columns as all distinct \(m\)-bit sequences in binary order (e.g., for \(m = 3\), columns range from 000 to 111); and \(\vec{g}_i\) (for \(i = 2\) to \(r\)), a \(\binom{m}{i} \times n\) matrix with rows from bitwise multiplication of \(i\) rows of \(\vec{g}_1\).

This hierarchical structure generates codewords systematically, leveraging combinatorial patterns for flexibility.

EXAMPLE: Reed-Muller Codes with \(n = 8\)

A first-order RM code (\(m = 3, r = 1\)) is an (8, 4) code with:

\[\begin{split} \mathbf{G} = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{bmatrix} \end{split}\]

Derived from a (7, 3) maximum-length code with an added parity bit for even weight, it has \(d_{\min} = 4\).

A second-order RM code (\(r = 2\)) with the same \(n = 8\) has a larger \(\mathbf{G}\) (8 rows) and \(d_{\min} = 2\), showing how higher order reduces distance while increasing codeword count.

Hadamard Codes

Hadamard codes use rows of a Hadamard matrix \(\mathbf{M}_n\) (where \(n\) is even) as codewords.

An \(n \times n\) Hadamard matrix has entries of 0s and 1s, with each row differing from others in exactly \(n/2\) positions, one row being all zeros, and others having \(n/2\) ones.

For \(n = 2\):

\[\begin{split} \mathbf{M}_2 = \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix} \end{split}\]

Larger matrices are built recursively:

\[\begin{split} \mathbf{M}_{2n} = \begin{bmatrix} \mathbf{M}_n & \mathbf{M}_n \\ \mathbf{M}_n & \overline{\mathbf{M}}_n \end{bmatrix} \end{split}\]

where \(\overline{\mathbf{M}}_n\) is the complement of \(\mathbf{M}_n\), enabling systematic code expansion.

Hadamard Codes Construction

For \(n = 4\):

\[\begin{split} \mathbf{M}_4 = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \end{bmatrix}, \quad \overline{\mathbf{M}}_4 = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 \end{bmatrix} \end{split}\]

Rows of \(\mathbf{M}_4\) and \(\overline{\mathbf{M}}_4\) form an (4, 3) code with \(2n = 8\) codewords and \(d_{\min} = n/2 = 2\). Generally, for \(n = 2^m\), parameters are \(k = m + 1\), \(d_{\min} = 2^{m-1}\), though non-power-of-2 lengths yield nonlinear codes.