Past exam question: 2071 Chaitra, Q13(a)
Open in the Padhaiko appDiscuss the concept of redundancy in error detection and correction. Define Hamming distance?
Solution
Concept of Redundancy: Redundancy refers to the addition of extra check bits () to a message dataword that convey no new information on their own, but establish a mathematical constraint between all transmitted bits.
- If channel noise alters any transmitted bits during transit, the received bit combination violates this mathematical relationship.
- The receiver detects the inconsistency (error detection) or calculates the error position via syndrome evaluation to invert the erroneous bit back to its true value (error correction).
Definition of Hamming Distance: The Hamming distance between two binary words and of equal length is the number of bit positions in which the corresponding bits differ.
- Mathematically:
where is the bitwise XOR operator and is the Hamming weight (number of 1s).
- The minimum Hamming distance of a codebook determines its detection and correction bounds:
Redundancy adds extra check bits to datawords so only a sparse subset of -bit patterns are valid codewords, letting receivers detect or correct corruptions. Hamming distance is the number of bit positions where two equal-length words differ; bounds detection () and correction ().