gen-define-error-correcting-codes-and-give-one-short-worked-exam-d92b

Define error-correcting codes and give one short worked example.

# Error-Correcting Codes **Definition:** Error-correcting codes are methods of encoding data by adding redundant information so that errors introduced during transmission or storage can be detected and corrected without retransmission. The key idea is to map messages to codewords in such a way that valid codewords are sufficiently "far apart" (in terms of differing bits/symbols), allowing corrupted data to be recovered. ## Worked Example: (7,4) Hamming Code **Setup:** Encode 4 data bits into 7 bits by adding 3 parity bits. This code can correct any single-bit error. **Encoding:** Let's encode the message **1011** The 7 bits are positioned as: p₁ p₂ d₁ p₃ d₂ d₃ d₄ - Data bits: d₁=1, d₂=0, d₃=1, d₄=1 - Parity bits calculated as: - p₁ checks positions 1,3,5,7: p₁ ⊕ 1 ⊕ 0 ⊕ 1 = 0, so **p₁=0** - p₂ checks positions 2,3,6,7: p₂ ⊕ 1 ⊕ 1 ⊕ 1 = 0, so **p₂=1** - p₃ checks positions 4,5,6,7: p₃ ⊕ 0 ⊕ 1 ⊕ 1 = 0, so **p₃=0** **Codeword:** 0110011 **Error correction:** Suppose we receive **0**1**1**0011 (error in position 5) - Check p₁: positions 1,3,5,7 → 0⊕1⊕1⊕1 = 1 ✗ - Check p₂: positions 2,3,6,7 → 1⊕1⊕1⊕1 = 0 ✓ - Check p₃: positions 4,5,6,7 → 0⊕1⊕1⊕1 = 1 ✗ Error position = 1 + 4 = **5** → flip bit 5 to recover correct codeword!