Design a C(8,4) linear block code

A linear block code is a block code in which the modulo-2 sum of any two codewords is also a codeword. A C(n, k) code encodes k message bits into n bits by c = m·G, where G is a k × n generator matrix. It has 2ᵏ codewords, and d_min equals the minimum non-zero codeword weight.

Design of C(8,4)

Here n = 8, k = 4, so 4 parity bits are added (rate 1/2). Use the systematic form G = [I₄ | P]:

      | 1 0 0 0 : 0 1 1 1 |
 G =  | 0 1 0 0 : 1 0 1 1 |
      | 0 0 1 0 : 1 1 0 1 |
      | 0 0 0 1 : 1 1 1 0 |

Parity equations for c = [m1 m2 m3 m4 | p1 p2 p3 p4]:

• p1 = m2 ⊕ m3 ⊕ m4
• p2 = m1 ⊕ m3 ⊕ m4
• p3 = m1 ⊕ m2 ⊕ m4
• p4 = m1 ⊕ m2 ⊕ m3

Example codeword

Message 1011: c = row 1 ⊕ row 3 ⊕ row 4 = 10000111 ⊕ 00101101 ⊕ 00011110 = 10110100.

All 16 codewords

Minimum weight of non-zero codewords = 4, so d_min = 4: the code detects 3 errors and corrects 1 (single-error correcting, double-error detecting). Parity-check matrix H = [Pᵀ | I₄].