Past exam question: 2072 Chaitra, Q8
Open in the Padhaiko appWhat are block codes? The generator matrix for a (6,3) block code is shown below. Obtain all code words.
Solution
Definition of Linear Block Codes: A block code is an error-control coding scheme that divides an incoming message bitstream into distinct -bit blocks called datawords. Redundancy is added by appending parity bits to each block, producing an -bit codeword ().
In a linear block code denoted as an code:
- The modulo-2 sum (XOR) of any two valid codewords is also a valid codeword.
- The all-zero vector is always a valid codeword.
- Systematic form is represented as , where is the identity matrix and is the parity submatrix.
- Codewords are generated through matrix multiplication:
Matrix Setup and Parity Equations: For the given code, , , and :
Let dataword be and codeword be :
Generating All Codewords: Compute using modulo-2 arithmetic:
- For :
- For :
- For :
- For :
- For :
- For :
- For :
- For :
Summary Table of Generated Codewords:
| Dataword () | Parity Bits () | Codeword () | Weight |
|---|---|---|---|
0 0 0 | 0 0 0 | 0 0 0 0 0 0 | 0 |
0 0 1 | 1 0 1 | 0 0 1 1 0 1 | 3 |
0 1 0 | 1 1 0 | 0 1 0 1 1 0 | 3 |
0 1 1 | 0 1 1 | 0 1 1 0 1 1 | 4 |
1 0 0 | 1 1 1 | 1 0 0 1 1 1 | 4 |
1 0 1 | 0 1 0 | 1 0 1 0 1 0 | 3 |
1 1 0 | 0 0 1 | 1 1 0 0 0 1 | 3 |
1 1 1 | 1 0 0 | 1 1 1 1 0 0 | 4 |
The minimum non-zero weight is , hence the minimum Hamming distance of this code is .
A block code maps data bits into an -bit codeword by adding parity bits. For the given systematic generator matrix , the 8 codewords are: 000 000000, 001 001101, 010 010110, 011 011011, 100 100111, 101 101010, 110 110001, 111 111100 (with ).