Summary of "Lec-29: Single Bit Parity along With Hamming Distance Concept | Error Control"

Main Ideas / Concepts

1) Single Parity Bit (least expensive error detection)

• Purpose: Detect transmission errors by adding only 1 redundant bit to the message.
• Terminology:
  • Message bits = m
  • Codeword bits = m + 1 (because exactly one parity bit is added)
• Why it’s “least expensive”:
  • Compared to methods like double parity / CRC / checksum, it adds fewer redundant bits, so more useful data can be sent for the same overhead.

Parity types

• Even parity (mainly used): the total number of 1s in the codeword must be even.
• Odd parity: the total number of 1s in the codeword must be odd.

---

2) How the Even Parity bit is computed

Assume a dataword example.

• Given dataword: 1010

  • Number of 1s = 2 (already even)
  • Even parity bit added = 0
  • Result: total 1s in the full codeword remain even.

• Given dataword: 1110

  • Number of 1s = 3 (odd)
  • Even parity bit added = 1
  • Result: total 1s becomes 4 (even).

---

3) What Single Parity Bit can detect (and what it can’t)

(a) Detects all single-bit errors

• If an error flips one bit, the parity of the number of 1s changes.
• Example:
  • If the sent (data + parity) has even parity, but one bit flips:
    • The receiver’s recomputed parity no longer matches the parity bit → error detected
• Limitation: It detects that an error occurred, but cannot identify/correct the position of the wrong bit.

(b) It fails to detect some double-bit errors

• If two bits flip, the total number of 1s parity may remain unchanged.
• Example:
  • If the receiver’s recalculated parity still matches the received parity bit → error not detected.

(c) General rule

• The method detects errors where the number of flipped bits is odd:
  • 1-bit error → detected
  • 3-bit error → detected
  • 5-bit error → detected
  • etc.
• If an even number of bits flip, parity can stay consistent → not reliably detected.

---

4) Hamming Distance connection (used to answer typical exam questions)

The video introduces Hamming Distance because students often struggle with questions like:

• “Given codewords, compute minimum Hamming distance”
• “From that, determine how many bit errors can be detected”

Definition: Hamming Distance

• Hamming distance between two codewords is computed by:
  1. Take the EXOR of the two codewords
  2. Hamming distance = number of 1s in the EXOR result
• Interpretation of EXOR:
  • 0 where bits are the same
  • 1 where bits differ

Example computations described

• Between 0000 and 1111:
  • EXOR = all 1s → Hamming distance = 4
• Between 0101 and 1000:
  • EXOR = 1101
  • Count 1s = 3 → Hamming distance = 3

Using minimum Hamming distance (core exam rule)

• Consider a set of valid, parity-attached codewords.
• Compute the minimum Hamming distance = d across all pairs.
• Rule stated:
  • If minimum Hamming distance is d, the scheme can detect up to (d − 1) bit errors.
• Example logic in subtitles:
  • If d = 2, then it detects d − 1 = 1 bit error.
  • It cannot guarantee detection of 2-bit errors, because flipping 2 bits can turn one valid codeword into another valid one, making it indistinguishable.

---

Step-by-step Methodology (as presented)

A) Single Even Parity Bit Method

1. Input: m-bit message/dataword
2. Compute parity bit (even parity):
   • Count the number of 1s in the m bits
   • If count is even, parity bit = 0
   • If count is odd, parity bit = 1
3. Form the codeword: append the parity bit → total length m + 1
4. At receiver:
   • Recount 1s in the received codeword (including parity bit)
   • If total number of 1s is not even (for even parity), declare error
   • Note: this only detects errors, not their location or correction.

B) Hamming Distance and Error Detection Rule

• Given two codewords:
  • Perform EXOR
  • Count the number of 1s in the EXOR result → that is the Hamming distance
• Across a set of codewords:
  • Compute distances between all pairs
  • Take the minimum value → call it d
• Detection capability:
  • The scheme can detect (d − 1) bit errors

---

Speakers / Sources Featured

• Gate Smashers (channel/creator; the speaker addressing viewers is implied but not explicitly named)

Category

Educational

---

Share this summary

Share on X/Twitter Share on Facebook Share on LinkedIn Share on Reddit Share on WhatsApp Share on Telegram

---

Is the summary off?

If you think the summary is inaccurate, you can reprocess it with the latest model.

Reprocess summary

Video