Linear Block Codes

Linear block codes form the mathematical foundation of virtually all practical error control coding systems. A linear block code is a set of codewords that forms a linear subspace, meaning the XOR of any two codewords is also a codeword. This algebraic structure enables systematic encoding using matrix multiplication and efficient decoding using syndrome decoding. GATE problems on this topic regularly test the generator matrix, parity check matrix, and syndrome computation.

Core Concept Explanation

A linear (n, k) block code maps every k-bit message vector m to an n-bit codeword c using the relation c = m G, where G is the generator matrix of size k x n. The linearity property ensures that the XOR of any two valid codewords is also a valid codeword. The set of all 2^k codewords forms a k-dimensional linear subspace of the n-dimensional binary vector space.

In systematic form, the generator matrix is written as G = [I_k | P], where I_k is the k x k identity matrix and P is the k x r parity sub-matrix. The resulting codeword is c = [m | mP], placing the original message bits in the first k positions and the computed parity bits in the last r positions. Systematic codes are preferred in practice because the message can be read directly from the received word without full decoding.

The parity check matrix H of size r x n is defined such that c H^T = 0 for every valid codeword c (all arithmetic in GF(2), i.e. modulo 2). In systematic form, H = [P^T | I_r]. The relationship G H^T = 0 holds by construction, confirming that every row of G (and thus every codeword) satisfies all parity check equations.

Mathematical Expression

When a codeword c is transmitted and received as r = c + e (where e is the error pattern), the receiver computes the syndrome s:

s = r H^T = (c + e) H^T = c H^T + e H^T = 0 + e H^T = e H^T

The syndrome depends only on the error pattern e, not on the transmitted codeword c. If s = 0, either no error occurred or an undetectable error pattern was received. If s is non-zero, s identifies which column of H was affected, pointing to the error location. This is the basis of syndrome decoding, which requires a pre-built syndrome lookup table (also called the standard array).

The minimum Hamming distance d_min of a linear block code equals the minimum weight (number of 1s) among all non-zero codewords. This is a unique property of linear codes that makes d_min easy to compute: just find the lightest codeword. For a Hamming(7,4) code, d_min = 3, allowing single error correction.

Practical Understanding

The (7,4) Hamming code is the canonical example of a linear block code. It has n=7, k=4, r=3, rate R=4/7, and d_min=3. It can correct any single-bit error in a 7-bit received word. The syndrome is a 3-bit binary number that directly gives the column index of H corresponding to the error, making hardware implementation very simple.

For a (7,4) code, the syndrome points to the position of the erroneous bit (1 through 7). Syndrome 000 means no error. Syndrome 001 through 111 correspond to bit positions 1 through 7 in the H matrix column ordering. The receiver simply flips the bit at the indicated position.

The standard array is a 2^r x 2^k table that lists all coset representatives (error patterns) and their syndromes. For a large (n,k) code this table becomes impractical, motivating more structured codes like BCH, Reed-Solomon, and LDPC codes that use algebraic or iterative decoding instead of table lookup.

Given:
(7,4) Hamming code, systematic form
Received word r = 1 0 1 1 0 1 0 (bits 1 through 7)

Parity Check Matrix H (3x7):
H = [ 1 1 0 1 1 0 0 ]
    [ 0 1 1 1 0 1 0 ]
    [ 1 1 1 0 0 0 1 ]

Why this formula applies:
Syndrome s = r H^T reveals error position.
If s = 0, no single-bit error. If s != 0, s is the column index of H.

Formula:
s = r H^T  (mod 2 arithmetic)

Substitution:
r = [1 0 1 1 0 1 0]
s1 = 1*1+0*1+1*0+1*1+0*1+1*0+0*0 = 1+0+0+1+0+0+0 = 0 (mod 2)
s2 = 1*0+0*1+1*1+1*1+0*0+1*1+0*0 = 0+0+1+1+0+1+0 = 1 (mod 2)
s3 = 1*1+0*1+1*1+1*0+0*0+1*0+0*1 = 1+0+1+0+0+0+0 = 0 (mod 2)

Calculation:
Syndrome s = [0 1 0] = column 2 of H (column index in binary)
Error is in bit position 2.

Final Answer:
Flip bit 2 of received word.
Corrected word = 1 1 1 1 0 1 0
Message bits (first 4) = 1 1 1 1

Exam Tip: For GATE, the syndrome of a single-bit error in position i equals the i-th column of H. If H columns are arranged in binary counting order, the syndrome directly gives the binary position of the error bit.

Key Properties of Linear Block Codes

• Encoding: c = m G, where G is the k x n generator matrix.
• In systematic form G = [I_k | P] and H = [P^T | I_r], giving c = [m | mP].
• Valid codewords satisfy c H^T = 0; syndrome s = r H^T = e H^T depends only on error pattern.
• d_min of a linear code equals the minimum Hamming weight (fewest 1s) of any non-zero codeword.
• Syndrome lookup table maps each correctable error pattern to its error position.
• (7,4) Hamming: n=7, k=4, r=3, R=4/7, d_min=3, corrects 1 error per codeword.

Quick Revision

• Linear (n,k) code: 2^k codewords forming a linear subspace; XOR of two codewords is a codeword.
• Encoding: c = m G (k-bit message times k x n generator matrix gives n-bit codeword).
• Systematic G = [I_k | P]: message bits preserved, parity appended.
• Parity check: c H^T = 0 for all valid c, where H = [P^T | I_r].
• Syndrome s = r H^T = e H^T; non-zero syndrome reveals error location.
• d_min = minimum weight non-zero codeword; determines correction and detection capability.
• GATE trap: syndrome gives the column of H matching the error, not directly the bit number unless H columns are in standard binary order.