This is a continuation from Linear Block Codes II

Hamming Codes

Hamming codes are a family of linear error-correcting codes that can detect up to two-bit errors and correct single-bit errors.

For \( m \geq 3 \), a Hamming code has the following parameters:

• Code length \( n = 2^m - 1 \)
• Number of information bits \( k = 2^m - m - 1 \)
• Number of parity-check bits \( n - k = m \)
• Error-correcting capability \( t = 1 \) due to a minimum Hamming distance \( d_{\text{min}} = 3 \)

These codes are constructed using a parity-check matrix \( H \) whose columns are all non-zero \( m \)-tuples in the vector space \( V_m \) over \( \text{GF}(2) \) (the binary field).

Systematic Hamming Code C(7, 4, 3)

Consider the Hamming code \( C(7, 4, 3) \) with \( m = 3 \). Here, \( n = 2^3 - 1 = 7 \), \( k = 2^3 - 3 - 1 = 4 \), and \( n - k = 3 \).

In systematic form, the parity-check matrix \( H \) is arranged such that the left submatrix is the \( m \times m = 3 \times 3 \) identity matrix \( I_m = I_3 \), followed by a submatrix \( Q \). For \( C(7, 4, 3) \), the parity-check matrix is:

\[ H = [ I_m | Q ] = \begin{bmatrix} 1 & 0 & 0 &|& 1 & 0 & 1 & 1 \\ 0 & 1 & 0 &|& 1 & 1 & 1 & 0 \\ 0 & 0 & 1 &|& 0 & 1 & 1 & 1 \end{bmatrix} \]

The corresponding generator matrix \( G \) in systematic form is \( G = [Q^T | I_{2^m - m - 1}] \), where \( Q^T \) is the transpose of the right submatrix of \( H \), and \( I_4 \) is the 4×4 identity matrix for \( k = 4 \).

Why \( d_{\text{min}} = 3 \)?

The minimum Hamming distance \( d_{\text{min}} \) of a code determines its error-correcting capability. For Hamming codes like \( C(7, 4, 3) \), \( d_{\text{min}} = 3 \), and here’s why:

• No column is the zero vector: Each column of \( H \) is a non-zero \( m \)-tuple, ensuring that the weight of any codeword (a linear combination of columns of \( G \)) is at least 1. Thus, \( d_{\text{min}} > 1 \).
• No two columns are identical: Since all columns of \( H \) are distinct non-zero \( m \)-tuples, the sum of any two columns (corresponding to a codeword) has weight at least 2, implying \( d_{\text{min}} > 2 \).
• Sum of two columns is another column: Because \( H \) contains all \( 2^m - 1 \) non-zero \( m \)-tuples, the binary sum of any two distinct columns is another non-zero column of \( H \). The minimum weight of a codeword formed by three or more columns can be 3 (e.g., adding three columns like \( [1,0,0]^T \), \( [0,1,0]^T \), and \( [1,1,1]^T \) yields a weight-3 codeword). Thus, \( d_{\text{min}} = 3 \).

With \( d_{\text{min}} = 3 \), the error-correcting capability is: \[ t = \left\lfloor \frac{d_{\text{min}} - 1}{2} \right\rfloor = \left\lfloor \frac{3 - 1}{2} \right\rfloor = 1 \] This means the code can correct all single-bit errors.

Decoding with a Look-Up Table

Decoding a Hamming code like \( C(7, 4, 3) \) can be efficiently performed using a syndrome look-up table. The syndrome of a received vector \( r \) is computed as \( s = H r^T \). If \( s = 0 \), no error is detected. If \( s \) matches a column of \( H \), a single-bit error is assumed at the position corresponding to that column. For \( C(7, 4, 3) \), with \( H \) as given, the look-up table is constructed as follows:

• Syndrome computation: For a received vector \( r = [r_1, r_2, r_3, r_4, r_5, r_6, r_7] \), compute \( s = H r^T \) (modulo 2).
• Coset leaders: There are \( 2^{n-k} = 2^3 = 8 \) coset leaders, corresponding to the all-zero vector (no error) and the 7 single-bit error patterns.
• Table:
  • Syndrome \( [0, 0, 0]^T \): No error, error pattern \( [0, 0, 0, 0, 0, 0, 0] \).
  • Syndrome \( [1, 0, 0]^T \): Error in position 1, error pattern \( [1, 0, 0, 0, 0, 0, 0] \).
  • Syndrome \( [0, 1, 0]^T \): Error in position 2, error pattern \( [0, 1, 0, 0, 0, 0, 0] \).
  • Syndrome \( [0, 0, 1]^T \): Error in position 3, error pattern \( [0, 0, 1, 0, 0, 0, 0] \).
  • Syndrome \( [1, 1, 0]^T \): Error in position 4, error pattern \( [0, 0, 0, 1, 0, 0, 0] \).
  • Syndrome \( [0, 1, 1]^T \): Error in position 5, error pattern \( [0, 0, 0, 0, 1, 0, 0] \).
  • Syndrome \( [1, 1, 1]^T \): Error in position 6, error pattern \( [0, 0, 0, 0, 0, 1, 0] \).
  • Syndrome \( [1, 0, 1]^T \): Error in position 7, error pattern \( [0, 0, 0, 0, 0, 0, 1] \).

To decode, compute the syndrome of the received vector, look up the corresponding error pattern in the table, and subtract it (modulo 2) from the received vector to recover the transmitted codeword.

Perfect Codes

Hamming codes are perfect codes, meaning they achieve the Hamming bound exactly. For a code with minimum distance \( d_{\text{min}} \) and error-correcting capability \( t = \lfloor (d_{\text{min}} - 1)/2 \rfloor \), the number of correctable error patterns is: \[ \sum_{\ell=0}^{t} \binom{n}{\ell} = 2^{n-k} \] For \( C(7, 4, 3) \), \( t = 1 \), and: \[ \binom{7}{0} + \binom{7}{1} = 1 + 7 = 8 = 2^{7-4} = 2^3 \] This confirms \( C(7, 4, 3) \) is perfect, as all error patterns of weight \( t = 1 \) or less are coset leaders.

Note that perfect codes are rare. And Besides the Hamming codes, the only other nontrivial binary perfect codes is \( C(23, 12, 7) \), Golay code, with \( d_{\text{min}} = 7 \).

Shortened Hamming Codes

By deleting \(\ell\) columns from the parity check matrix \(H\), a new parity check matrix \(H'\) of size \(m \times (2^m - m - \ell - 1)\) is obtained, with the following properties:

• Code length: \( n = 2^m - \ell - 1 \)
• Number of information bits: \( k = 2^m - m - \ell - 1 \)
• Number of parity check bits: \( n - k = m \)
• Error correcting capability: \( d_{\text{min}} \geq 3 \)

By deleting specific columns of \(H\), a shortened Hamming code with \( d_{\text{min}} = 4 \) can be obtained.

For a systematic Hamming code \( C(2^m - 1, 2^m - m - 1, 3) \), the parity check matrix is: \[ H_{m \times (2^m - 1)} = \begin{bmatrix} I_m | Q_{m \times (2^m - m - 1)} \end{bmatrix} \]

If all columns of even weight from submatrix \(Q\) are deleted, the resulting matrix \(H'\) is: \[ H'_{m \times (2^m - 1)} = \begin{bmatrix} I_m | Q'_{m \times (2^{m - 1} - m)} \end{bmatrix} \] where \(Q'\) contains \( 2^{m-1} - m \) columns of odd weight.

Observe that:

• All columns of \(H'\) have odd weights.
• No three columns in \(H'\) add to zero (ensuring \( d_{\text{min}} \geq 3 \)).
• Four columns in \(H'\) can be found that add to zero, implying \( d_{\text{min}} = 4 \).

Error Correction and Detection Capabilities

The distance-4 shortened Hamming code can:

1. Correct all error patterns of weight 1 (single errors).
2. Detect all error patterns of weight 2 (double errors).

The decoding process is as follows:

1. Compute the syndrome vector \( \mathbf{s} = \mathbf{r} \cdot H'^T \).
2. If \( \mathbf{s} = 0 \):
   • No error is assumed.
3. If \( \mathbf{s} \neq 0 \):
   • If \( \mathbf{s} \) contains an odd number of 1's:
     • A weight-1 error is assumed, and the corresponding error pattern is added to \( \mathbf{r} \) to correct it.
   • If \( \mathbf{s} \) contains an even number of 1's:
     • A weight-2 error is detected (uncorrectable).

Extended Hamming Codes

Extended Hamming Codes can be constructed by adding an additional overall even parity check coordinate to every codeword, producing:

• Code length: \( n = 2^m \)
• Number of information bits: \( k = 2^m - m - 1 \)
• Number of parity check bits: \( n - k = m + 1 \)
• Error correcting capability: \( d_{\text{min}} = 4 \)

To do so, a parity check bit is added to every codeword. That is, if \( \mathbf{v} = (v_0, v_1, \ldots, v_{2^m-2}) \) is a codeword of the Hamming code, the corresponding codeword \( \mathbf{v}' \) in the extended Hamming code is: \[ \mathbf{v}' = (v_0, v_1, \ldots, v_{2^m-2}, v_{2^m-1}) \] where \[ v_{2^m-1} = v_0 + v_1 + \cdots + v_{2^m-2}. \]

Example

The parity check matrix for the \( C(7, 4, 3) \) Hamming code is given as: \[ H = \begin{bmatrix} 1 & 0 & 0 &|& 1 & 0 & 1 & 1 \\ 0 & 1 & 0 &|& 1 & 1 & 1 & 0 \\ 0 & 0 & 1 &|& 0 & 1 & 1 & 1 \end{bmatrix} \]

The corresponding generator matrix \( G \) is: \[ G = \begin{bmatrix} 1 & 1 & 0 &|& 1 & 0 & 0 & 0 \\ 0 & 1 & 1 &|& 0 & 1 & 0 & 0 \\ 1 & 1 & 1 &|& 0 & 0 & 1 & 0 \\ 1 & 0 & 1 &|& 0 & 0 & 0 & 1 \end{bmatrix} \]

To construct the generator matrix \( G' \) of the extended Hamming code \( C(8, 4, 4) \), we add an even parity-check bit at the end of each row: \[ G' = \begin{bmatrix} 1 & 1 & 0 &|& 1 & 0 & 0 & 0 &|& 1 \\ 0 & 1 & 1 &|& 0 & 1 & 0 & 0 &|& 1 \\ 1 & 1 & 1 &|& 0 & 0 & 1 & 0 &|& 0 \\ 1 & 0 & 1 &|& 0 & 0 & 0 & 1 &|& 1 \end{bmatrix} \]

The corresponding parity check matrix \( H' \) for the extended Hamming code \( C(8, 4, 4) \) is: \[ H' = \begin{bmatrix} 1 & 0 & 0 &|& 1 & 0 & 1 & 1 &|& 0 \\ 0 & 1 & 0 &|& 1 & 1 & 1 & 0 &|& 0 \\ 0 & 0 & 1 &|& 0 & 1 & 1 & 1 &|& 0 \\ - & - & - & - & - & - & - & - & - & -\\ 1 & 1 & 1 &|& 1 & 1 & 1 & 1 &|& 1 \end{bmatrix} \]

Every codeword of the extended Hamming code has even weight.

Syndrome Decoding

Compute the syndrome vector: \[ \mathbf{s} = (s_0, s_1, \ldots, s_{m-1}, s_m) = \mathbf{r} \cdot H'^T \]

1. If \( \mathbf{s} = 0 \):
   • The decoder assumes that no error occurred.
2. If \( \mathbf{s} \neq 0 \) and \( s_m = 1 \):
   • The error pattern has odd weight, and the decoder assumes that an error pattern of weight 1 has occurred. It will correct the error.
3. If \( \mathbf{s} \neq 0 \) and \( s_m = 0 \):
   • The error pattern has even weight, and the decoder can detect it (but not correct it).

Code Operations

In summary, the following operations can be performed on a code \( C(n, k) \):

• Shortening: \( C(n, k) \rightarrow C(n - \ell, k - \ell) \)
• Extending: \( C(n, k) \rightarrow C(n + \ell, k) \)
• Puncturing: \( C(n, k) \rightarrow C(n - \ell, k) \)
• Lengthening: \( C(n, k) \rightarrow C(n + \ell, k + \ell) \)
• Expurgating: Deleting some codewords
• Augmenting: Adding new codewords

Hamming Code Properties

The Hamming code is a \( C(2^m - 1, m) \) linear block code. Its weight distribution in polynomial form is: \[ B(z) = 1 + (2^m - 1) z^{2^{m-1}} \quad \]

The probability that the decoder fails to detect the presence of errors in the Hamming code \( C(2^m - 1, 2^m - m - 1, 3) \) is given by: \[ P_U(E) = 2^{n-k} B(1 - 2p) - (1 - p)^n \quad \] Substituting the weight distribution polynomial \( B(z) \) from (3) into (4), we get: \[ P_U(E) = 2^{-m} \left[ 1 + (2^m - 1)(1 - 2p)^{2^{m-1}} \right] - (1 - p)^{2^m - 1} \quad \]